동기화 문제 Bouded Buffer Problem (= Producer Consumer Problem) 버퍼가 비어있을 때 소비자가 기다려야하고, 버퍼가 가득 찼을 때 생산자가 기다려야한다. 이러한 문제를 해결하기 위해 Semaphore full, empty를 사용하여 비어있지 않은 버퍼의 개수와 비어있는 버퍼의 개수를 파악하고 각 상황에 맞게 생산자와 소비자가 접근할 수 있다. 이때 추가적으로 Critical Section에 대한 권한을 주기 위해 Mutex를 사용한다. 아래 예시를 보면 생성자는 empty가 1이상 있을 때 wait에서 빠져나와 Mutex를 통해 진입하여 작업을 실행한다. 반대로 소비자는 버퍼에 1개 이상 값이 들어있을 때 접근할 수 있다. Readers Writers Problem..

프로세스 동기화 여러 개의 프로세스가 데이터를 공유할 때 무결성을 유지해야한다. 예를 들어 P1과 P2가 공유 데이터를 사용할 때 아래와 같은 명령을 번씩 실행한다면, +1 -1이기 때문에 count의 값은 변화가 없어야한다. 하지만 count의 초기값이 0이라고 가정했을 때, P1과 P2가 count가 0일 때 동시에 접근한다면? 3번 라인이 실행될 때 count는 1이 됐다가 P2에 의해 -1이 될 수 있다. 1번씩 실행됐음에도 실행 결과가 바뀌었다. 동기화란 멀티 프로세싱에서 이와 같은 문제를 해결하기 위해 동시에 여러 프로세스가 접근해야하는 공유 데이터를 동시가 아닌 순차적으로 접근하도록 만드는 방법이다. Race Condition 여러 개의 프로세스에서 동시에 같은 데이터에 접근하려고 하는 상황..

버블 정렬 배열의 값을 다음 인덱의 값과 하나씩 비교하며 배열 끝까지 순회한다. 이 과정을 모든 인덱스에 대해 진행하므로 n*n 즉, 시간 복잡도가 O(n^2)으로 최악의 정렬 알고리즘이다. 선택 정렬 배열의 가장 작은 요소부터 찾아서 앞에서부터 순서대로 정렬한다. O(n^2) 삽입 정렬 배열을 순차적으로 돌면서 현재 인덱스를 앞에 위치하는 인덱스들 중에서 비교하여 현재 인덱스가 들어가야할 위치에 삽입힌다. O(n^2) 버블 정렬 보다 빠르며, 배열의 크기가 작을 경우에는 효율적이다. 셸 정렬 길이가 n인 배열이 있을 때 간격을 n/2로 주어 i번 인덱스부터 n-1번 인덱스까지 간격에 해당하는 인덱스들 중에서 값을 비교해서 더 작은 값이 앞으로 이동한다. 이후 간격을 n/4로 더 좁혀 더 넓은 범위에 대..

Scheduling Ready 상태에 있는 프로세스들 중 언제, 어떤 프로세스에게 CPU를 할당시킬 것인지 정하는 것 Scheduling을 통해 여러 프로세스를 왔다갔다하며 CPU를 최대로 활용할 수 있다. scheduling은 Kernel Thread에서 실행된다. Preemptive vs Non-Preemptive (선점형, 비 선점형 ) Preemptive: 스케줄러에 의해 실행 중인 프로세스의 CPU 할당을 헤제할 수 있다. Non Preemptive: 프로세스가 작업을 마치고 릴리스될 때까지 CPU 할당을 유지한다. CPU 스케줄링 결정 Running -> waiting (I/O 발생) runnging -> ready (다른 프로세스 할당) waiting -> ready (I/O가 끝남) ter..