Little Jay

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

Paging 지금까지 앞에서 Continous Allocation 기법들에 대해서 살펴보았다. 이제는 본격적으로 현대에서 만이 사용하는 Non-Continous Allocation에 대해서 살펴볼 것이다. Paging과 Segmentation은 기본적으로 Process들을 조각내는 기법이다. Paging은 고정된 사이즈로 나눈 반면에 Segmentation은 가변 사이즈로 Process를 나눈다. Paging에서의 그 조각이 page이다. 따라서 page는 Process의 chunk라고 할 수 있으며, 일반적으로는 4KB의 크기를 지니고 있다. Paging을 수행하기 위해서는 Main Memory역시 이 page들을 담을 수 있도록 Slot화 해야한다. Memory에서는 이를 page라는 단어를 사용하지..

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

Terminology 메모리에 대한 이야기를 하기에 앞서서 용어를 간단하게 정리하고 넘어가겠다. Static Allocation(고정할당): Program이 execute되기 전에 메모리를 할당한다. Pre-defined된 static이나 global variable등을 선언하면 compile time에 결정이 된다. Dynamic Allocation(동적할당): run time에 메모리가 할당되는 것이다. 필요에 의해서 할당이 되는 것이며 주로 memory의 Heap 영역을 사용하는 malloc, new 등이 이에 대당이 된다. Memory가 미래에 얼마나 사용이 될지 모르기에 이를 사용한다. Memory Management Main Memory는 크게 두 가지의 파트로 나뉜다. 첫 번째는 OS를 위한..

식사하는 철학자 문제 유명한 컴퓨터 공학자인 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) 위 그림을 보자. 이는 우리가 가장 간단하게 생각해볼..