Little Jay

Condition Synchronization 지금까지의 Mutex는 임계영역에 들어갈 때 하나의 Thread 혹은 하나의 Process만 사용할 수 있도록 보장해준다고 배웠다. Mutex를 Guarantee하지 않으면 결국 Non-Deterministic한 동작으로 인해 잘못된 결과가 초래될 수 있다. 그렇다고 해서 Mutex가 동기화를 보장해주는 유일한 방법은 아니다. 조건 동기화(Conditional Synchronization)은 특정 조건(condition, or state)이 만족할 때까지 대기하게 해서 다수의 쓰레드의 흐름을 Re-Ordering하는 것이다. 다시 말해서 조건에 따라 실행 흐름을 대기시키고 재개시킬 수 있다는 것이다. 우리는 앞에서 Mutex는 P와 V Operation이 서..

Spin Lock 우리는 Busy Waiting하는 것을 Spin Lock이라고 한다. 이는 당연하게 Mutual Exclusion을 제공해준다. 그러나 Busy Waiting을 할때는 CPU의 낭비는 필연적이게 된다. 그러나 CPU 자원을 소모한다고 해서 Spin Lock 자체가 비효울적이라고는 할 수 없다. 이 시점에서 우리는 Context Switch의 비용과 Busy Waiting의 비용을 비교해야한다. 계속 Context Switching을 한다면 계속 Thread/Process를 바꾸는 비용이 기하급수적으로 증가할 수도 있다. 그러나 Spin Lock 자체는 fair한 것은 아니다. 결국 대기하면서 Thread/Process가 계속해서 Progress를 하지 못해 Starvation이 발생할 ..

Critical Section Problem 임계 영역에 대해서는 아래의 세 가지의 조건을 만족시켜야한다. Mutual Exclusion(상호 배제) : Critical Section에는 반드시 하나의 Thread/Process만 있어야 한다. Progress(진행): 만약 Critical Section을 사용하는 Thread/Process가 없고, 현재 임계영역의 자원을 사용하려고 누군가 기다려야한다면 적절한 Algorithm을 통해서 해당 Thread/Process를 진행시켜야 한다. Bounded Waiting(한정 대기): Process/Thread가 임계 영역을 위해 무한정 기다려서는 안된다. Naive Approach (Wrong Case) 위 그림을 보자. 이는 우리가 가장 간단하게 생각해볼..

위 코드를 우분투 환경에서 돌려보자. 그러면 처음 실행한 환경에서는 아래와 같이 동작한다. 코드를 천천히 뜯어보면 알겠지만 우리가 저 코드에서 목표하는 바는 마지막에 Counter를 0으로 만든느 것이 목표이다. 그러나 코드의 결과는 우리가 예측했던 값과는 동떨어진 값이 나왔다. 우선 x++ 하는 것 부터 살펴보자. 사실 시스템 프로그래밍파트에서 정리를 했지만 변수에 1만 감소시켜주는 Assembly가 존재한다. 그러나 정확한 설명을 위해서 x++을 해주는 것은 먼저 메모리에서 x를 레지스터에 불러오고, 1을 더한 후 다시 메모리에 저장해주는 3가지 lw, add, sw 이렇게 세 가지 명령어가 필요하다고 해보자. 그렇다면 이 명령어 하나하나는 Scheduling의 대상이 되는 하나의 Thread이다. ..

Type of Parallelism on Multicore 멀티 코어에서 병렬성은 두 가지의 종류로 나뉘게 된다. 하나는 Data Parallelism이다. 이는 task들 사이에서 Data의 Subset을 병렬화 하는 것이다. 쉽게 예를 들자면 arr[100]이 있을 때 4core라고 한다면 25씩 Data를 나누면 쉽게 병렬처리를 할 수 있다. 다음으로는 Task Parallelism이다. 오히려 이 부분이 조금 더 직관적으로 이해하기가 쉽다. 이는 data를 분산해서 처리하는 것이 아니라 task를 여러 Processor에 할당하여 처리하는 것이다. Multi-Threaded Process Model Thread도 결국 하나의 작업공간이기 때문에 Thread 당 1개의 Stack이 필요하다. 따라서..

Thread 우리는 지금까지 Process를 실행중인 Program. Program의 Execution Sequence이면서 System Resource를 다루는 단위라고 언급을했다. Process에는 두 가지의 특성이 있었는데, 하나는 자원 소유권의 단위로서 memory, heap, global vars, I/O등을 담당하였고, 실행단위의 특성으로서는 Process를 Scheduling의 단위로서 바라보아 Execution State와 Priority를 가지고 있었다. 그러나 이제는 Execution Sequence를 담당하는 주체를 Process가 아닌, Thread로 바라볼 것이다. 간단하게 정리해보자면 Execution Environment, 즉 환경을 Process가, 그 환경 안에서 Execu..

Multiprocessor Scheduling 우리는 지금까지 단일 처리기, 즉 Uniprocessor 에서의 Scheduling에 대해 다루었다. 단일 처리기에서는 단순히 Ready, Block, Running State를 결정하는 문제를 살펴보았다. 반면에 다중 처리기에서는 고려햐애 할 것들이 너무 많다. 우리가 일반적으로 사용했던 Ready Queue는 전역변수 형태로 선언이 되어있다. 따라서 다중 처리기가 하나의 Queue에 접근하려고 하면 동시에 메모리에 접근하게 되는 Race Condition이 생길 수도 있다. 또한 Cache 친화력 문제, 어떻게 다중 처리기에 Process를 할당할 것이며, Process의 Heterogeneity를 어떻게 다룰 것이며, Process를 어떻게 Balanc..

Scheudling Incorporating I/O 예를 들어 두 개의 Process가 있다고 가정하자. 하나의 Process는 5ms의 Service Time을 가지고 있고, I/O를 위해 25ms를 대기하고 있다. 반대로 다른 Process는 CPU-Intensive하여 Waiting이 발생하지 않는 CPU Burst적인 Operation을 한다고 하자. 아래의 그림은 각각 Time Slice가 50ms, 5ms일때의 상황이다. 두 상황에서 CPU Utilization은 모두 100%이다. A가 I/O를 하고 있더라고 B Process가 Running되기에 Utilization 측면에서는 그 활용도가 100%가 된다. 그러나 주목해야할 점은 I/O Utilization이다. 첫 번째의 50ms의 Ca..

Round Robin Round Robin은 스케줄링 알고리즘에서 가장 중요하다고 해도 과언이 아닌 알고리즘이다. Round Robin은 기본적으로 FIFO와 동일하다. FIFO가 하나의 Process를 전부 끝내고 나서 다음 Process로 넘어가는 것과 달리 Round Robin은 일정한 시간 간격을 두어 Process를 Time-Out 시켜버린다. 일정한 시간 간격을 Quantum이라고 한다. Process가 Quantum을 다 사용하면 해당 Process는 Time-Out되어 다시 Ready Queue로 보내버린다. 따라서 FIFO에서는 Long한 Process들이 우선적으로 선택되는 Convoy Effect가 자주 발견이 되었는데 이 Side Effect를 방지할 수 있는 것이 Round Rob..

Types of Process Scheduling Process를 스케줄링하는 것은 크게 세 가지로 분류된다. 먼저 Long-Term Scheduling이 있다. 이를 Job Scheduler라고도 하는데 이는 단순하게 시스템에 Program을 올릴지 말지를 결정하는 Scheduling이다. 다음으로는 Medium-Term Scheduling이 있다. 이를 Swapper라고도 부르는데 우리는 이전에 우리가 배운 Swapping 기법을 수행하는 Scheduler이다. 또한 Short-Term Scheduling이 있다. 이것이 우리가 초점을 두고 있는 CPU Scheduler이다. Processor가 어떤 Process를 수행할지 결정하는 Scheduling이다. 마지막으로 I/O Scheduling이 있..