건빵의 블로그

출처 : http://protospv.tistory.com/29 Knuth-Morris-Pratt 알고리즘, 곧 KMP 알고리즘입니다. 지금까지 알려진 중 가장 최저의 시간복잡도가 필요한, 즉 가장 최신의 알고리즘입니다. 일단, 짚고 넘어가자면 KMP 알고리즘의 평균 수행 속도는 O(N + K)(N과 K는 비교할 문자열의 길이)입니다. 매칭을 하려면 최소한 원문 문자열과 검색 문자열을 한번씩은 읽어봐야 할 테니, 가장 최적의 복잡도인 것입니다(사실 소스로 구현하기에 따라 약간씩 커질수도 있습니다). 이름에서 알 수 있듯이 Knuth, Morris, Pratt 세 사람이 완성한 알고리즘입니다. 기존의 문차열 매칭 방식인 '오토마타' 의 문제점을 극복하기 위해 만들어졌고, 그 결과 뛰어난 시/공간 복잡도를 ..

출처 : http://kldp.org/node/46637 본래 의미로 캐리지 리턴은 해당 라인에서 커서를 맨 앞으로 보내는 것이고 라인 피드는 다음 라인으로 이동하는 것입니다. 두 동작을 합치면 뉴라인 동작을 하게 되는데 이것은 과거의 느린 프린터에서 물리적인 속도차이를 커버하기 위해 만들어졌지만 현재에는 의미가 없습니다. 유닉스 계열 시스템에서는 LF로 뉴라인을 표시하고 윈도우즈에서는 CR+LF로 표현합니다. 그리고 정규식에서는 LF하나로 표현합니다.

동기화에서의 전통적 문제. (1) Bounded Buffer Problem (2) Readers and Writers Problem (3) Dining Philosophers Problem (1) Bounded Buffer Problem Producer-Consumer Process로 Producer는 버퍼에 데이터를 넣고 Consumer는 읽어온다. 동기화를 사용하지 않을 경우 한번씩 실행되는 것을 보장할 수 없으므로 버퍼가 넘칠 수 있다. 동기화 메커니즘을 이용해 해결 가능하다. semaphore mutex : 값 1 semaphore full : 값 0 semaphore empty : 값 N -Producer Process do{ // produce wait(empty); wait(mutex); /..

Race Condition : 여러 프로세스가 같은 데이터에 동시에 접근하며 조작하고 프로세스의 실행의 결과가 프로세스 실행 순서에 의존하는 상황 Critical Section : 공유 자원에 여러 프로세스가 접근하여 race condition을 야기할 수 있는 공유 데이터를 접근하는 코드의 일부분 Process Synchronization : 레이스 컨디션의 발생을 막기 위한 방법 Synchronization의 Desired Solution(완벽한 동기화를 위한 세 가지 조건) -Mutual Exclusion : 오직 프로세스 1개만 CS에 접근 가능하다. -Progress : CS에 있는 프로세스가 없고 한 프로세스만 CS에 진입하려 한다면 바로 진입 -Bounded Waiting : 유한시간 대기 ..

출처 : internet512.chonbuk.ac.kr/.../AVL/avl.html 높이 균형 트리(Hieght-Balanced Tree)라고도 부르며, 탐색 시간을 줄이기 위해서 좌,우측 부 트리의 높이가 1 이상 차이가 나지 않도록 균형을 유지해 주는 이진 트리로 동적 탐색 트리(Dynamic Search Tree)이다. 탐색시 비교 횟수가 작고, 노드 삽입시 트리의 균형이 크게 변하지 않는 성질을 만족하는 트리이다. T가 좌측과 우측 부트리인 TL과 TR을 가진 이진 트리라 할 때 아래의 조건을 만족하면 T는 높이가 균형을 이룬다. TL과 TR의 높이가 균형을 이루며 |HL-HR| ≤ 1 (HL, HR은 TL과 TR의 높이) AVL 트리 AVL 트리가 아닌 경우 높이 균형 트리를 구성하는데 있어서..

10.2 Access Methods 파일 정보 접근 방법 10.2.1 Sequential Access 순서대로 읽는다. 10.2.2 Direct Access 파일은 logical records로 이루어져 있고 번호를 이용해 프로그램을 빠르게 읽고 쓸수 있도록 한다. 순서에 제한이 없다. 이 방법은 많은 양의 즉각적인 접근에 유용하다.(예> db) 이 방법에서는 파일 오퍼레이션에 block number가 파라미터로 들어가야 한다. 일반적으로 os에서 사용자에게 제공되는 block number는 relative block number이다. 파일의 시작에서부터 상대적 위치이다. 모든 시스템이 sequential과 direct access를 허용하는 것은 아니다. 10.2.3 Other Access Method..

9.7.1 Basic Mechanism 파일 메모리 맵핑은 디스크 블락을 메모리의 페이지에 매핑시킨다. 파일에 대한 read write는 일반적인 메모리 접근과 같이 다뤄지기 때문에 파일 접근과 사용을 간략화시킬 수 있다. 파일 업데이트는 modify되었는지 체크하여 os가 주기적으로 점검할 수 있다. 여러 프로세스에서 같은 파일을 접근한다면 data sharing이 가능하며 각 페이지가 frame에 연결 될 수 있다. 만약 수정이 일어나면 cow 메커니즘이 적용되어서 새로운 프레임을 할당받는다. Memory mapping file을 공유하는 것은 공유 메모리와 비슷하지만 다른 시스템콜과 같은것을 사용한다. 하지만 어떤 os에서는 shared memory가 memory mapping file로 구현된다...

Chapter 9. Virtual Memory Managment Virtual Memory는 실행중인 프로세스가 전부 메모리에 없어도 되게 해주는 테크닉이다. 가장 큰 장점은 프로그램이 Physical Memory보다 커질 수 있다는 것이다. 9.1 Background 실행되게 위해서는 인스트럭션들이 피지컬 메모리에 반드시 있어야 한다는 것은 당연해보이지만 이것은 프로그램의 사이즈가 물리 메모리의 크기에 제한되게 한다. 많은 경우에 모든 인스트럭션이 사용되지는 않는다.(ex>에러처리, 배열, 특정 옵션) 프로그램이 부분적으로 메모리에 있게 하는 것은 많은 장점이 있다. -물리 메모리의 크기에 제한받지 않는다. -많은 프로그램이 동시에 실행될 수 있어서 응답시간의 증가 없이 CPU 이용률과 스루풋을 높인다..

Chapter 8 Memory Management Strategies 8.1 Background 실행중인 프로그램에 의해 만들어지는 메모리 주소의 sequence만 관심있다. 어떻게 프로그램이 메모리 어드레스를 generate 하는지에 대해서는 관심없음. 8.1.1 Basic Hardware 메모리와 CPU의 레지스터만 CPU가 바로 접근할 수 있다. 그러므로 동작을 위해서는 둘 중의 하나에 위치하여야 한다. 레지스터는 CPU안에 있으므로 접근이 매우 빠르지만, 메모리는 메모리 버스를 통하므로 메모리로부터의 데이터를 기다리는 stall라는 것이 생기고 이것은 자원낭비이므로 속도 차를 고려하여 cache라는 메모리 buffer를 둔다. user프로세스가 OS의 메모리 영역이나 다른 user의 메모리를 접근..

3장 Process concept 시스템은 프로세스의 콜렉션으로 이루어 진다. 3.1 Process concept 3.1.1 The process 프로세스는 다음에 실행될 위치를 명시한 프로그램 카운터와 연관된 리소스의 집합을 가지는 active entity이다. 프로그램은 디스크에 저장된 파일 형태의 passive entity이다. 3.1.2 Process state -New -Running : Instruction이 실행 중인 상태-> 한 순간에 하나의 프로세스만 실행 가능하다. -Wating : event를 기다리는 프로세스 -Ready : 프로세서 할당을 기다리는 프로세스 -Terminated : 종료 3.1.3 Process Control Block 각각의 프로세스는 OS에서 PCB로 표현되어짐..