Little Jay

Virtual Memory 간단하게 정의를 해보자면, 각 Process에게 전용의 큰 메모리를 제공하는 기법이다. 실제로는 없는 메모리를 있게 보이게 하는 기법이라고 생각하면 편하다. 이전의 Paging과 Segmentation은 다음과 같은 특성을 지니고 있었다. 먼저 Process들을 조각내는 것이다. 조각냄으로서 메모리에 연속적으로 할당될 필요가 없이 단순하게 분산적재를 하기만 하면 된다. 이어지는 얘기로는 분산적재를 한 Process의 조각이 Memory공간 어디에 위치하고 있는지 알 수 있는 Mapping Table이 필요하다. 조각에 대한 정보가 있어야 어디에서 정확한 Memory의 주소를 알 수 있기 때문이다. Mapping Table의 특징은 Relocatable할 수 있어야 한다는 것이다..

Memory Allocation 메모리를 할당하는 방법론에는 크게 두 가지가 있다. 하나는 Contigous Allocation(연속할당)이며, 다른 하나는 Non-Contigous Allocation(불연속할당)이다. 먼저 연속할당에는 어떤 방법론들이 있는지 살펴보자. 불연속 할당에 포함되는 Paging과 Segmentation은 다음 포스팅에서 다뤄볼 것이다. Fixed Partitioning - 고정분할 방식 이름만 보면 알 수 있듯이 메모리를 분할하는 방식이다. 초기에는 같은 Size의 Partitioning으로 나뉘었다. 어떻게 보면 가장 간단하게 생각할 수 있는 방식이다. 분할된 메모리의 Size가 모두 같기 때문에 빈 Slot이 있다면 거기에다가 그냥 할당을 해버리면 된다. 이 방법을 균등 ..

식사하는 철학자 문제 유명한 컴퓨터 공학자인 Dijikstra 께서 고안한 문제이다. 5명의 철학자가 있고, 5개의 포크가 테이블에 있다. 이때 철학자가 식사하기 위해서는 2개의 포크가 필요하다. 어떤 철학자라도 하나의 포크를 동시에 사용할 수 없다. 즉 포크는 Critical Resource로 Mutual Exclusion을 보장해줘야하는 존재이다. 식사하는 철학자의 문제는 Deadlock을 막기 위함이다. 식사하는 철학자 문제를 컴퓨터 공학적 관점에서 바라본다면, 철학자는 Process, 포크를 Resource로 바라보면 되겠다. 철학자는 단순히 다음과 같은 동작을 수행한다. 생각하고 -> 포크를 잡고 -> 먹고 -> 포크를 내려놓고. 즉 코드로 이를 정리해보자면 아래와 같을 것이다. 역시 뇌를 사용..

Deadlock Deadlock을 직역하면 교착상태라는 의미이다. 정확히 이게 어떤 뜻일까. OS에서의 Deadlock이란 Process들의 set이 System Resource 혹은 IPC를 위해 Competing 하다가 시스템이 영구적으로 Blocking되는 상태가 되는 것을 의미한다. 예를 들자면 어떤 Process의 set이 blocked되어 있는데 해당 Process set을 깨워줄 수 있는 Process의 set 역시 block 상태에 있다면 어떠한 Process도 진행할 수 없을 것이다. 이러한 상황을 우리는 Deadlock, 즉 교착상태라고 정의한다. 어떤 Process들도 Trigger될 수 없다면 어떤 Process도 진행할 수 없게 된다. Deadlock은 Programmer Leve..

Producer and Consumer Problem 계속해서 생산자 소비자 문제를 다루고 있다. 생산자 소비자 문제 중 생산자가 무한히 자원을 생산할 수 있다고 가정하자. 그렇기 때문에 우리가 집중해야 할 것은 소비자 파트이다. 상한은 고려할 필요가 없고 하한을 고려한다. 소비자는 단순히 empty 상태이면 wait을 하면 된다. 이 wait은 결국 어떤 data가 채워지기를 기다리는 상태이다. 앞에서 언급한 V operation과 같은 기능이다. 다시 정리를 하자면 생산자는 P, 소비자는 V Operation이다. Broken Scenario 이와 같은 생산자와 소비자고 있다고 해보자. 얼핏 보면 이렇게 생산자 소비자 문제를 구현 하는 것이 맞아 보인다. 그러나 이 코드에는 명백한 문제점이 있다. p..

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이 필요하다. 따라서..