그럴때는 패키지에서 지원하는 타입을 확인해서 사용할 수 있다!

우선 기본적으로 타입 스크립트를 지원하는 패키지들은

@types/<packagename>

으로 패키지의 타입을 지원하는 경우가 많다.

그래서 예를들어 express 패키지를 다운 받아서 사용한다고 했을 때

npm i express @types/express

2가지를 설치하면 express에서 사용되는 타입들을 같이 받아서 사용할 수 있다.

그리고 만약 @types/가 있는지 없는지를 모르는 경우에는

npm사이트에 들어가서 ****

다운받으려는 패키지를 검색한 후 이름 옆에 DT 라는 표시를 통해 타입이 들어있는 패키지가 있음을 알 수 있다.

그런데 만약 패키지의 이름 옆에

TS가 붙어있는 경우 패키지 자체에 타입이 포함되어있기 때문에 추가로

@types/를 받을 필요가 없다.

타입을 다운로드 받은 후에 역시나 어떤 타입을 써야할지 모르는 경우가 있을 수 있다.

그럴 때는 구글링을 해보고, vscode에서 알려주는 타입 추론을 활용하여 타입을 유추해본 후 작성하도록 하자.

Event-based Concurrency는 2가지 부분을 다루게 된다.

1. multi-threaded application에서 concurrency를 정확하게 다루는 것이 어렵다는 것이다. lock을 안하거나, deadlock이 발생하거나..
2. mutil-threaded application에서 개발자가 scheduling을 통제하지 못하거나, 할 수 없다는 점이다.

따라서 이번에 살펴볼 내용은 어떻게하면 thread 없이 concurrent server를 만들 수 있을까? 하는 내용이다.

The Basic Idea: An Event Loop

Event-based Concurrency는 간단하게 생각해서 어떤 일이 일어날 때 까지 기다리는 것이다.

그리고 그 일이 발생하면 event의 type에 따라서 행동을 수행한다. 위의 그림처럼 event loop라는 것을 통해 발생한 event에 따라서 event handler로 동작을 수행한다.

따라서 어떤 event를 수행 할 것인지에 대한 행동이 마치 스케줄링과 같은 기능을 한다.

An Important API: select() (or poll())

select(), poll()이 이벤트가 도달했을 때 우리가 원하는 대로 동작할 수 있게 만들어준다.

Blocking vs Non-Blocking interface Blocking(synchronous) interface는 caller에게 리턴을 하기 전에 작업을 모두 끝내고 리턴한다. 반면에 Non-blocking(asynchronous) interface는 작업을 하지만 그 즉시 리턴을 한다. 즉 어떤 작업이든 background에서 작업을 한다.

Using select()

select()함수는 위와같이 생겼으며 간단한 예시는 아래와 같다.

Why Simpler? No Locks Needed

event-based application에서는 thread가 하나뿐이고, 이벤트에 따라서 처리를 하기 때문에 lock도 필요가 없기 때문에 concurrent program에서 나타나는 문제들이 없다.

A Problem: Blocking System Calls

하지만 만약 block되는 system call을 호출하는 event가 발생한다면 어떻게될까...?

예를들어 클라이언트가 서버에서 디스크로부터 파일을 읽어서 내용을 리턴해주는 경우를 생각해보자.

이 작업을 위해서 파일을 open()하고 read()해야한다. 특히나 open(), read()는 storage시스템에 I/O 요청을 해야하므로 시간이 꽤나 걸리는 작업이다.

thread-based server에서는 이 작업이 문제가되지 않는다. thread1이 파일을 열고, 읽는동안 다른 thread2가 프로그램을 구동하면 되기 때문이다.

하지만 event-based server에서는 thread가 하나뿐이기 때문에 block이 발생하고, 모든 서버의 작업이 block되는 동안은 멈추게된다...

A Solution: Asynchronous I/O

이 문제를 해결하기 위해서 현대의 OS들은 asynchronous I/O라는 I/O 요청방식을 고안해냈다.

이 방법은 I/O request가 왔을 때 그 즉시 control을 caller에게 반환하고 또다른 interface들이 I/O request가 완료되었는지 아닌지를 결정할 수 있도록 한다.

예를들어 Mac에서 struct aiocb Asynchronous I/O control block이라는 용어로 잘 알려진 자료구조가 있다.

• 읽어야 하는 file discriptor(aio_fildes)
• file의 offset(시작지점) (aio_offset)
• 읽어야 하는 길이 (aio_nbytes)
• 읽은 파일을 저장 할 버퍼 (aio_buf)

이 자료구조를 채운 다음 asynchronus read API를 호출한다.

int aio_read(struct aiocb *aiocbp)

이 API를 호출 한 이후 그 즉시 control을 리턴하고, 작업은 background에서 진행되고 서버는 이어서 동작한다.

그렇다면 I/O 작업이 끝났음을 어떻게 알 수 있을까?

int aio_error(const strunct aiocb *aiocbp)

위의 API가 I/O 작업이 끝났다면 0을 리턴하고, 그렇지 않다면 EINPROGRESS를 리턴한다.

여기서 볼 수 있는 문제점은 만약 수백만 건의 I/O request가 동시에 온다면 그 모든 요청에 대해서 결과를 확인하는데도 엄청난 반복을 해야한다....

따라서 이 문제를 조금 완화하기 위해서 시스템에서는 interrupt를 허용한다. I/O가 완료되었을 때 signal을 보냄으로써 불필요하게 반복적으로 시스템에 I/O가 완료되었는지를 물어보지 않도록 한다.

Another Problem: State Management

event-based의 또다른 문제점은 전통적인 thread-based 방식보다 코드를 작성하기가 까다롭다는 점이다.

예를들어 event handler가 asynchronous I/O를 요구하고 나중에 그 작업이 완료했을 때 그 다음 event handler가 사용할 프로그램의 상태를 구성해줘야 한다.

프로그램의 상태가 stack에 존재했던 thread-based 방식에서는 처리하지 않아도 됐던 문제가 있는 것이다.

이 mutual-stack management가 event-based 방식에선 매우 중요하다.

좀 더 구체적으로 예시를 통해 살펴보자.

우선 thread-based 방식에서 데이터를 읽어서 읽은 데이터를 네트워크 소켓에 작성하는 작업을 생각해보자.

int rc = read(fd, buffer, size);
rc = write(sd, buffer, size);

thread-based 방식에서는 어떤 fd를 읽고, 어떤 fd에 write를 해야하는지 명확하기 때문에 까다로울게 없다.

하지만 event-based 방식에서는 AIO call을 통해 read를 asynchronous하게 수행하고, aio_error()를 통해 작업이 완료됐음을 알아야 한다.

그렇다면 작업이 완료되었을 때 event-based server는 어떻게 무엇을 할지 알 수 있을까?

우선 작업을 끝내는데 필요한 정보가 기록된 자료구조를 저장한 후, 끝났다는 event가 발생하면 이 자료구조를 살펴서 event를 처리한다.

위의 예제같은 경우에는 socket의 fd를 자료구조에 저장한 후 read가 끝났을 때 자료구조를 살펴서 행동을 수행 할 것이다.

출처 : OSTEP

위와같은 어플리케이션에서 deadlock은 총 31개 deadlock이 아닌 버그는 74개이다.

Non-Deadlock Bugs

Atomicity-Violation Bugs

첫번째 non deadlock 버그는 MySQL에서 발견한 atomicity-violation bug이다. 이 버그는 다른 2개의 thread가 proc-info라는 같은 데이터에 접근한다. 한 thread는 값이 null이 아닌것을 확인하여 출력하고, 다른 thread는 값을 null로 만든다. 분명 thread1이 fput을 호출하기 이전에 interrupt가 발생하여 thread2가 값을 null로 변경하고, 다시 thread1이 수행되어 fput을 하려고하면 이미 proc_info는 null이기 때문에 문제가 발생한다.

atomicity-violation은 다시말해서 여러개의 메모리에 접근하는 직렬화가 잘못된 경우를 말한다. 다시말해서 atomic하게 실행되도록 생각했지만 atomic하게 실행되지 않은 경우를 뜻한다.

위의 코드는 atomicity assumption을 하고 있기 때문에 우리가 critical section에 lock을 걸어서 이 문제를 해결할 수 있다.

Order-Violation Bugs

위의 코드에서 문제는 thread2에서 thread1에서 초기화 된 mThread가 당연히 null이 아닌 값으로 초기화되어 있을 것 이라는 가정을 하기 때문에 문제가 된다.

즉 다시말해서 ordering bug는 메모리에 접근해야하는 적절한 순서가 뒤집힌 경우를 말한다.그래서 이 문제를 해결하기 위해서 적절한 순서를 강제해야만 한다. 따라서 이전에 공부한 condition variable을 사용한다.

Deadlock bugs

위의 코드에서 만약 thread1이 L1을 lock한 이후에 thread2로 context switch가 발생하여 L2가 lock이된 후에 thread2에서 L1의 lock을 기다리게 되고 thread1에서도 이미 lock된 L2를 기다리므로 deadlock이 발생하게 된다.이를 그림으로 표현하면 32.7과 같은 그림이 된다. 이 그림에서 cycle이 바로 deadlock을 나타낸다.

Why Do Deadlocks Occur?

한가지 이유로는 구성요소들간의 의존성 문제가 점점 복잡해짐에 따라 deadlock이 발생한다는 점이다.

예를들어 운영체제에서 메모리 시스템은 디스크에 있는 block을 paging하기 위한 이유로 파일시스템에 접근해야한다. 그리고 파일시스템은 block을 읽기위해서 메모리 시스템의 page가 필요하다.

따라서 위와같은 circular dependency상황에서 deadlock이 발생하지 않도록 주의하는 것이 매우 중요하다.

또다른 deadlock의 원인은 encapsulation의 특징 때문이다. 개발자로서 자세한 실행은 숨기고, 프로그램이 쉽게 동작하도록 만들기 위해서 encapsulation이 필요하다.

하지만 이런 encapsulation, modular way가 locking과는 잘 맞지 않을 수 있다.

Conditions for Deadlock

• Mutual exclsion: thread가 필요한 자원을 독점해서 통제하려함.
• Hold-and-wait: thread가 추가적인 자원을 기다리는동안 thread에 할당된 자원을 지니고 있음
• No preemption: 자원을 지니고 있는 thread로 부터 강제로 자원을 제거할 수 없음
• Curicular wait: 다른 thread에서 필요로하는 자원을 하나 이상 하나의 thread에서 갖고있어서 circular chain이 존재함.

  preventation

  Circular wait

• lock의 전체 순서를 지정*하여 circular wait이 발생하지 않도록 한다.

또한 좀 더 복잡한 시스템의 경우 전체 순서를 지정하는 것이 까다롭기 때문에 부분적인 순서를 지정 하여 deadlock을 피할 수 있다.

Hold-and-wait

hold-and-wait은 모든 lock을 동시에 얻는 것을 atomically하게 막아준다.하지만 이 방법은 몇가지 단점이 존재한다.

예를들어 우리가 원하는 lock을 하기 위해선 반드시 앞서서 다른 lock이 충족되어야 하므로 concurrency를 감소시키는 문제가 있다.

No Preemption

pthread_mutex_trylock()을 활용하여 우리가 사용하려는 lock이 다른 lock의 조건을 기다리는 경우에 발생하는 문제를 해결 할 수 있다. 예를들어 L1이 lock을 시도할 때 L2에 따라서 lock이되거나, unlock이 되도록 만들 수 있다. 따라서 강제적인 순서가 생기게되서 deadlock-free한 코드를 만들 수 있다.

하지만 2개의 thread가 반복적으로 위의 상황을 시도하지만 계속 실패하는 livelock이라는 문제가 있다.

이 문제를 해결하기 위해서 loopback시(goto구문)에 약간의 random delay를 줘서 2개의 thread가 간섭되는 빈도를 줄여줌으로써 해결할 수 있다.

Mutual Exclusion

하드웨어의 도움으로 lock을 사용하지 않는 설계를 할 수 있다. 위의 코드가 하드웨어의 도움으로 atomically하게 동작할 때 lock을 얻지 않고, 값을 update함으로써 deadlock-free하게 동작할 수 있다. (단 livelock 문제는 존재할 수 있음.)좀 더 복잡한 list에 새로운 노드를 삽입하는 경우에도 위와같이 lock을 활용하지 않는 방법으로 해결할 수 있다.

Deadlock avoidance via scheduling

deadlock을 예방하는 것 보다 deadlock을 피하는 것이 유용할 때가 있다.예를들어 2개의 processor가 있고, 4개의 thread가 존재할 때 lock에 대한 수는 위와 같다고 하자.따라서 scheduler는 T1, T2를 동시에 동작시키지 않도록 스케줄링을 해야한다. 하지만 만약 T3도 2개의 processor를 모두 사용하는 경우라면 역시나 processor가 겹치지 않도록 스케줄링을 해야하기 때문에 아래와 같은 상황이 된다.따라서 위와같은 스케줄링 방법을 통해 deadlock을 막을 순 있지만 전체적인 프로세스의 처리시간이 길어지게된다.

따라서 위와같이 deadlock avoidance via shceduling 방식은 매우 제한된 경우에만 사용할 수 있다. (예를들면 embeded system..)

Detect and Recover

많은 데이터베이스 시스템에서는 deadlock을 탐지하고, 회복하는 기능을 갖고있다.

deadlock이 발생했을 때 시스템을 재부팅하여 문제를 해결한다.

출처: OSTEP

semaphore란 sem_wait()과 sem_post()로 우리가 조작할 수 있는 정수값을 갖는 object이다.위처럼 semaphore는 초기화를 해야만 한다. sem_init()으로 초기화를 수행하는데 s라는 semaphore를 1로 초기화 하고, 2번째 인자인 0은 이 semaphore는 하나의 프로세스안에서 thread들에 의해서 공유될 수 있음을 의미한다.sem_wait()은 semaphore의 값을 1씩 줄이고, 음수가 됐을 경우에는 0이 될 때까지 다시 기다리게된다.

그리고 sem_post()는 semaphore의 값을 1씩 증가시키고, 하나이상의 thread가 기다리고 있는 경우 그 thread를 깨운다.

Binary Semaphores (Locks)

semaphore를 우리에게 익숙한 lock으로 활용하는 방법부터 살펴보자. 이처럼 semaphore를 1로 초기화 해두면 당연하게도 lock처럼 동작할 수 있고, lock처럼 동작하는 semaphore를 binary semaphore라고 부른다.예를들어 2개의 thread가 동시에 동작할 때 critical section에서의 동작은 31.5를 통해 확인할 수 있다.

Semaphores For Ordering

semaphore는 concurrent programing에서 이벤트들의 순서를 지정할 때 유용하게 사용될 수 있다. 예를들어 이전에 살펴보았던 conditional variable처럼 사용될 수 있다. list가 채워질 때 까지 기다리는 thread, 그리고 채워진 list를 비우는 thread를 활용하는 예제처럼 말이다.따라서 초기의 semaphore를 0으로 초기화 한 후 실행하면 위와같은 흐름으로 동작하게된다. 그리고 만약 child thread가 먼저 종료되는 경우에는 parent thread에서는 31.8의 흐름처럼 sem_wait()이 바로 실행되어 즉시 종료된다.

The Producer/Consumer (Bounded Buffer) Problem

semaphore 역시 producer/consumer문제에도 사용될 수 있다. 하지만 concurrent programming에서 항상 염두해둬야 할 deadlock을 피하는 것을 주의해야한다. semaphore를 활용하는 producer/consumer 문제의 경우에는 위와같은 코드를 사용할 수 있다.

Reader-Writer Locks

좀 더 다양한 자료구조에 lock을 하려는 시도가 있었다. 예를들어 list에 원소를 삽입하거나, 살펴보는 concurrent한 작업이 있다고 하자. 원소를 삽입하는 과정은 list를 변화시키지만 살펴보는 행위는 list에 그 어떤 변화도 발생시키지 않는다.

이와같은 작업을 수행하기 위한 특별한 lock을 reader-writer lock이라고 부른다.

자료구조에 새로운 값을 작성하기 위해서는 rwlock acquire writelock()을 사용하고, 작성이 끝나면 rwlock release writelock()을 사용한다. write lock은 하나만 사용이 가능하다.

그리고 값을 읽을 땐 rwlockacquirereadlock()를 사용하는데 가장 첫번째 reader가 read lock을 수행할 때는 write도 같이 lock을 시킨다. 따라서 값을 읽는 동안에는 추가적인 값이 들어오지 못하게 만들고, 이러한 조치 덕분에 reader는 동시에 여러개의 값을 읽을 수 있다. 하지만 이 조치의 단점은 write를 하고자하는 thread가 생겼을 때 write가 즉시 수행될 수 없고, 모든 read가 끝날 때 까지 기다려야만 한다는 점이다.writer가 기다려야하는 문제 때문에 reader가 writer를 굶주리게하는 fairness문제가 있을 수 있다.

출처: OSTEP

concurrent program을 위한 유일한 요소는 lock뿐만이 아니다.

thread들이 실행을 계속할지의 여부를 결정하기 위해서는 condition을 확인해야한다.위의 코드처럼 부모 thread가 자식 thread의 종료를 기다리는 상황에서 단순하게 spin-base의 접근법을 생각해볼 수 있다. 하지만 spin-base 접근법의 문제인 CPU의 낭비가 발생한다는 문제를 피할 수 없다. 다른 방법으로는 자식 thread가 종료될 때 까지 부모 thread를 sleep 시켜두는 방식일 수 있다.

그렇다면 어떻게 thread가 그런 condition이 될 때까지 기다려야할까..?

Definition and Routines

condition을 기다리기 위해서는 condition variable이라는 것을 활용해야한다.

condition variable은 특정한 실행 상태(조건)가 원하는 상태가 아닐 때(예를들면 condition을 기다리는 상태) thread를 배치할 수 있는 thread queue이다. 즉 원하는 condition을 위해서 기다리는 thread를 저장해두기 위한 queue이다.

그래서 원하는 condition이 충족되면 signaling을 통해 하나 이상의 thread를 깨워서 실행할 수 있다.signal(), wait()과 관련된 * Pthread_cond_t c *;를 선언한다. 그리고 lock을 걸어서 condition을 기다리고, unlock시에 condition에 signal을 발생시킨다.

이 상황에서 고려해야할 상황은 2가지이다.

첫번째는 부모 thread에서는 자식 thread를 생성한 이후에 계속 진행되어 thr_join()을 호출한 후 자식 thread가 종료될 때 까지 계속 확인하며 기다려야 한다. 자식 thread가 종료된 이후에는 thr_exit()이 호출되고 condition variable done을 1로 변경한 후 부모 thread를 깨운다.

또는 자식 thread가 시작하자마자 done을 1로 만들어서 부모 thread가 thr_join()을 하자마자 종료될 수 있는 경우이다.

하지만 condition varible이 없는경우를 생각해 볼 수도 있다.하지만 위의 코드는 잘못된 접근법이다. 왜냐하면 예를들어 자식 thread가 즉시 thr_exit()을 호출하는 경우를 생각해보자. 자식 thread가 signal을 보내지만 잠들어있는 thread가 하나도 없다. 그리고 부모 thread는 계속해서 자식 thread를 기다리고 있을 뿐이다.

따라서 위의 경우를 고려하면 condition variable이 필요하다는 것을 알 수 있다.

또한 lock이 없는 경우를 생각해 볼 수도 있다.하지만 위와같은 경우에도 race condition을 다뤄야 한다. condition variable을 바꾸려는 찰나에 interrupt가 발생하여 condition variable을 변경하게 될 수 있는 문제가 있다.

따라서 위의 경우도 역시 condition variable이 필요함을 알 수 있다.

The Producer/Consumer (Bounded Buffer) Problem

이제 좀 더 복잡한 경우를 살펴볼 것이다.

하나 이상의 producet thread와 하나 이상의 consumer thread가 있다고 생각해보자. producer는 data item들을 만들고 buffer에 저장한다. consumer는 buffer에 있는 item들을 가져다가 사용한다.

예를들어 multi-threaded web server에서 producer thread는 http 요청을 작업 queue에 저장해두고, consumer thread가 이 queue에서 요청들을 가져다가 처리한다.

그리고 bounded buffer는 마치 pipe처럼 한 프로그램의 출력을 다른 프로그램으로 전달할 때 사용한다.

grep foo.txt | wc -l

bounded buffer는 shared resource라서 synchronized access가 필요하다. 오직 count가 0일 때만 buffer에 값을 넣을 수 있고, 오직 count가 1일 때만 buffer에서 값을 얻을 수 있다. producer가 loop번 만큼 buffer에 값을 입력하고, consumer는 buffer에서 값을 읽어온다.

하지만 위의 코드에는 lock이 없기 때문에 추가 해줘야 한다. p1p3는 producer가 buffer가 비어있을 때 까지 기다린다. c1c3는 consumer가 buffer가 채워질 때 까지 기다린다. 만약 buffer가 비어있다면 p4p6이 buffer에 값을 채우고, c4c6에서 채워진 데이터를 사용한다.

이처럼 하나의 producer, 하나의 consumer 상황에서는 위의 코드가 잘 동작할 것이라고 유추할 수 있다. 하지만 producer 혹은 consumer가 하나가 아닌 경우에는 어떻게 될까?30.9 그림처럼 consumer가 2개인 경우를 생각해보자.

1. consumer1이 먼저 실행되고 buffer에 값이 없으므로 data를 채울 때 까지 sleep에 빠진다.
2. 그 이후 producer가 버퍼에 값을 채우고
3. 이후에 consumer2가 실행된다면 이미 buffer에 값은 채워진 상태이므로 buffer에 있는 data를 처리하고
4. buffer에 값이 채워졌다는 signal을 받은 consumer1이 깨어나서 buffer를 사용하려고 보니 data가 이미 다 사용돼버렸다!

이처럼 깨어난 thread가 바람직한 상태에 있더라도 반드시 동작한다는 것을 보장할 수 없는 문제를 mesa semantic이라고 한다. 반대로 깨어난 thread가 반드시 즉각적으로 동작하는 것을 보장하는 용어로 hoare semantic이라고 부른다.

Producer/Consumer: Single CV And While

위의 문제를 while문을 결합하여 해결할 수 있다. buffer가 비어있는 경우에만 consumer가 잠에 들 수 있다.

하지만 이 방법에도 문제는 존재한다.예를들어 c1(consumer1), c2(consumer2)가 먼저 실행되고 나중에 p(producer)가 실행된다고 하자.

buffer가 비어있기 때문에 2개의 consumer모두 잠에 들 수 있고, p가 실행되어 buffer를 채우기 시작한다. 그리고 buffer를 모두 채우면 p는 잠든다. 그 후 c1, c2중 하나가 깨어나는데 c1이 깨어났다고 하자. 그래서 c1이 data를 사용한다. 이 data를 모두 다 사용했을 때 또다시 잠들어있는 thread중 하나를 깨워야만 하는데 지금 상황으로는 c2, p가 잠들어있다. 데이터를 모두 사용했을 때 당연히 p를 깨워야하지만 queue가 어떻게 구성되어있는지에 따라 c2가 깨어나는 것도 가능하기 때문에 만약 c2를 깨우는 경우에는 buffer가 이미 모두 사용된 상태기 때문에 다시 잠에 빠진다. 그래서 모든 thread가 잠에 빠지는 문제가 발생할 수 있다.

The Single Buffer Producer/Consumer Solution

그래서 이 문제를 해결하기 위한 방법으로는 2개의 condition variable을 활용하는 것이다.consumer와 producer thread 모두 empty, fill이라는 condition variable을 기다린다.

위의 코드에서 producer는 empty를 기다리고, fill signal을 보낸다. 반대로 consumer는 fill을 기다리고 empty signal을 보낸다.

The Correct Producer/Consumer Solution

더 뛰어난 동시성과 효율성을 위해서는 buffer를 추가하는 것이 도움이된다. 여러개의 buffer를 활용하여 동시에 producing, consuming을 할 수 있다.위의 코드에서 볼 수 있듯이 producer는 모든 buffer가 채워져있어야만 잠을 잘 수 있고, consumer는 모든 buffer가 비어있어야만 잠에 빠질 수 있다.

Covering Condition

위의 코드를 보면 allocate를 위해서는 할당할 수 있는 공간의 크기(byteLeft)가 할당하려는 크기(size)보다 더 큰 경우에 할당이 이루어질 수 있다.

그런데 만약 현재 메모리에 여유가 0 byte인 상태에서 thread a에서 100byte의 할당 요청이 있고, thread b에서 10byte의 할당 요청이 있을 때 두개의 thread는 모두 메모리가 확보될 때 까지 잠에 빠진다.

그런데 thread c가 50byte를 해제한 경우에 thread b는 10byte만 할당하면 되므로 깨어나도 되지만 thread a의 100byte에는 모자라므로 thread a가 깨어나서는 안된다.

하지만 컴퓨터는 둘중 어떤 thread를 깨워야하는지 알 수 없다.

그래서 이 문제를 해결하기위해서 pthread_cond_signal()을 pthread_cond_broadcast()로 대채하였다. 잠들어있는 모든 thread를 깨워서 50byte 크기에 만족하는 할당을 수행할 수 있도록 한 것이다.

하지만 이 방법은 모든 thread를 깨워서 상태를 체크하고 조건에 맞지않으면 다시 재우는 과정 때문에 성능에 악영향을 줄 수 있다.

그래서 이처럼 모든 thread를 다 깨우는 상황을 covering condition이라고 부른다.

출처: OSTEP

결론적으로 특정한 자료구조에 lock을 추가할 때 정확하게 동작하도록 만들기 위해서 무엇을 할 것인가?, concurrent를 위해서 어떻게 데이터구조에 lock을 추가할 것인가?를 생각해야한다.

Concurrent counter

counter라고 불리는 자료구조를 활용할 것이다.위의 lock이 없는 구조는 단순하지만 확장성이 없다. thread가 늘어나면 lock이 안되기 때문이다. 그렇다면 이를 어떻게 thread safe하게 만들 수 있을까?단순하게 single lock을 추가하였다. 이 방법은 쉽고 잘동작하지만 thread가 증가할 수록 성능이 낮아진다는 단점이 있다.위의 그림에서 precise 방법이 counter에 단순하게 lock을 추가하는 경우인데 thread가 많아질 수록 성능이 낮아짐을 알 수 있다. 즉, 확장성이 매우 떨어진다.

Scalable Counting

이 문제를 해결하기 위한 scalable한 counter중에 하나인 approximate counter에 대해서 알아보자. approximate counter는 CPU core마다 여러개의 local 물리적 카운터들 중에 하나로 표현된 논리적 카운터와 하나의 global counter로 동작한다. 예를들어서 4개의 CPU가 장착된 기계에 4개의 local counter와 1개의 global counter가 있다. 그리고 local counter하나마다 lock이 존재하고, global counter에도 lock이 존재한다.

thread가 counter를 증가시켜야 할 때는 자신의 local counter를 증가시킨다. 각각의 CPU는 자신의 local counter를 가지고 있으므로 각각의 CPU에서 thread는 간섭없이 counter를 증가시킬 수 있다. 따라서 counter update가 확장성을 갖는다. 하지만 주기적으로 global counter에게 local counter의 값을 전달해주어야한다. global counter를 local counter의 값 만큼 증가시키고, 다시 local counter를 0으로 초기화한다.

따라서 얼마나 local-to-global transfer가 발생하느냐에 따라서 counter의 상한선인 S(sloppiness)가 결정된다. 예를들어 위의 29.3을 보면 S가 5로 설정되어있다. 따라서 각각의 local counter가 상한선인 S에 도달하면 그 값을 global counter에게 전달해준다.위의 그림처럼 S가 클 수록 성능이 좋아지는 것을 확인할 수 있다. 하지만 S가 작을수록 local-global의 차이는 작고, S가 커질수록 local-global의 차이가 크다.

Concurrent Linked Lists

좀 더 복잡한 자료구조인 linked list와 lock을 결합하면 위와 같은 코드로 작성할 수 있다.

counter방식과 마찬가지로 가장 단순한 버전의 linked list도 확장성이 떨어지는 문제가 있다.

Scaling Linked Lists

이 문제를 해결하기 위한 방법으로 hand-over-hand locking (lock coupling)이라는 방법이 있다. 전체 리스트에서 하나의 lock을 활용하는 것이 아니라 각각의 node마다 하나의 lock을 지니고 있다.

리스트를 순회할 때 다음 노드에 대해서 lock을 걸고 현재 노드의 lock을 해제한다.

매우 높은 수준의 동시성을 지닐 수 있다. 하지만 매번 노드마다 lock을 얻고 해제하는데 드는 overhead 때문에 이 방법은 사용되진 않는다.

Concurrent Queues

이쯤되면 기본적으로 자료구조에 lock을 결합하는 방식이 전체 자료구조에 lock을 하나 생성한다는 것임을 알것이다.

그래서 이번에는 가장 쉬운 방법은 충분히 생각해볼 수 있으므로 넘어가고 Michael and Scott이 만든 queue (이후 concurrent queue)에 대해서 알아볼 것이다.

concurrent queue에는 queue의 head, tail에 2개의 lock이 있다. 이 2개 lock의 목표는 enqueue(queue에 데이터 생성시)에 tail에 lock을 거는 것과, dequeue(queue에서 데이터 출력시)에 head에 lock을 거는 것이다.그래서 이를 위해 dummy node를 하나 생성하여 head, tail이 항상 나눠질 수 있도록 만든다.

Concurrent hash table

리스트에서 활용되던 것 처럼 hash bucket마다 lock이 존재한다.

출처: OSTEP

• available 아무런 thread도 lock되지 않았음
• acquired critical section에서 한개의 thread가 lock이 되었음

lock을 만들기 위해서는 하드웨어와 OS의 도움이 모두 필요하다.

Evaluating locks

• Mutual exclusion 여러개의 thread가 critical section에 들어오는 것을 막아줄 수 있는가?
• Fairness lock이 해제된 이후 각각의 thread는 공정하게 lock을 얻을 기회가 주어지는가?
• Performance time overhead가 증가되는 문제가 있는가?

  Controlling Interrupts

  single processor 시스템에서 사용하던 초기의 mutual exclusion 방법이다.
• critical section*에서의 interrupt를 허용하지 않는다.

하지만 이 방법은 single processor 시스템에서 탐욕적인 프로그램이 processor를 독점하고 있다면 문제가 발생할 수 있고, multi processor 시스템에서는 동작하지 않는다.

A Failed Attempt: Just Using Loads/Stores

first attempt

lock이 되었는지 또는 되지 않았는지를 나타내는 flag를 활용하는 것이다. 하지만 이 방법은 2가지 문제점이 있다.

1. correctness 위의 그림에서 볼 수 있듯이 flag가 0에서 시작하고, thread 1이 flag를 1로 바꾸기 전에 switch가 발생하여 thread 2로 변경되고, 여기서 flag가 1로 바뀐 후 다시 thread 1로 되돌아왔을 때 멈춰진 thread 1의 작업을 이어서 진행하여 flag를 1로 만든다. 이와같은 방법은 mutual exclusion이라고 할 수 없다.
2. performance 그리고 spin wait이 시간을 낭비하게된다.

따라서 이러한 문제를 해결하기위해서 하드웨어가 필요하다.

Building Working Spin Locks with Test-And-Set

test-and-set (atomic exchange)라고 불리는 추가적인 하드웨어가 필요하다. TestAndSet의 동작 방식을 보면 old value를 리턴하고, 그와 동시에 new에 새로운 값을 update한다. 무엇보다도 이 작업이 atomically하게 이루어진다는 것이 중요하다.

Evaluating Spin Lock

• correctness 보장됨.
• fairness 보장되지 않음. 1개의 thread가 영원히 돌수도 있음
• performance single cpu에서는 오버헤드가 꽤나 치명적이다. 하지만 multi cpu에서는 꽤나 합리적인 방법이다.

  Compare And Swap

  ptr의 값이 expect와 같은지 다른지를 판별해서 같다면 값을 업데이트하고 예전값을 리턴, 같지 않다면 그냥 업데이트하지 않은 값을 리턴한다.

  Load-Linked and Store-Conditional

  MIPS architecture에서는 load-linked 와 store-conditional 명령쌍으로 lock을 구성하는데 도움을 줄 수 있다.load-linked는 단순하게 메모리위치의 값을 가져오는 것이고, store-conditional은 load-linked에 값이 업데이트된 경우가 없을 때 load-linked를 1로 업데이트하고 성공을 리턴하고, 그렇지 않으면 실패를 리턴한다.

  Fetch And Add

  atomically하게 메모리의 값을 1증가시키고, 이전 값을 리턴한다.

  Too Much Spinning: What Now?

  하드웨어 기반의 spin lock은 쉽고 잘 동작한다. 하지만 몇몇 경우에는 비효율적이다.

thread가 spinning하는 동안에는 값을 확인하는 것 외에는 별다른 행동을 하지 않으나, 이 행동이 time slicing을 낭비하게 만든다.

OS의 도움으로 이 문제를 해소할 수 있다.

A Simple Approach: Just Yield, Baby

단순하게 thread가 spin을 한다면 다른 thread에게 CPU를 양보한다.system call로 spin을 하는 thread의 상태를 running에서 ready로 변경시킨다. 만약 2개의 thread가 하나의 CPU에서 동작할 때는 yeild 방식이 잘 동작한다. 하지만 만약 thread의 수가 100개라면 어떻게될까...?

1개의 thread가 lock이 되어있다면 나머지 99개의 thread는 lock인 것을 확인하고, CPU를 yeild 해야한다. 즉, thread의 수가 많다면 이 방법 또한 효율적이진 않다.

그리고 여전히 thread들이 계속해서 critcal section에 들어왔다 나갔다하면 다른 thread들은 CPU를 yeild해야하므로 starvation문제가 해결되지도 않는다.

Using Queues: Sleeping Instead Of Spinning

yeild 방식은 scheduler가 어떤 thread를 다음에 돌려야할지 모르기 때문에 문제가 발생한다. 만약 lock을 위해 spin하는 thread 또는 바로 yeild 하는 thread라면 CPU의 낭비가 발생한다. 따라서 현재 thread가 release되면 다음에 lock을 가져야하는 thread를 관리할 필요가 있다. 이를 위해서 park() lock을 얻으려고 하는 thread를 sleep시키는 함수, unpark(threadID) threadID를 깨우는 함수를 활용한다.

이를 위해서 다음에 lock을 얻어야 할 thread를 저장 할 queue를 활용한다.

따라서 thread 1이 lock이 되려고할 때 interrupt가 발생하여 thread 2가 실행되는 경우 thread 2를 queue에 저장하고 thread 1을 재개한다. 그 후 thread 1이 release되면 queue에 있던 thread 2를 실행하는 방법이다.

하지만 만약 park()를 하기 이전에 이미 thread가 release가 되었다면 어떻게 될까?? 다음에 실행되어야 할 thread는 이미 실행가능한데 park()가 되지 않은 thread를 unpark() 해버리는 경우가 생기게된다.

그래서 이 문제를 방지하기 위해서 setpark()라는 것을 활용하여 문제를 해결한다.setpark()를 활용하므로써 OS에게 곧 park()를 할 것이라고 알려준다.

단일 thread는 프로세스와 매우 유사하다. program counter에 instructions를 저장해두고 활용한다. 하지만 single processor에 2개의 thread가 있는 경우 반드시 context switch가 발생해야만 한다. 프로세스의 context switch시에 PCB에 register를 저장하듯이, thread의 context switch에도 thread control block이 활용된다. single thread와 multi thread에서 찾아볼 수 있는 차이점은 stack영역의 차이이다.

multi thread환경에서는 thread마다 stack영역이 하나 더 존재한다.

Why Use Threads?

parelleism (병렬성)

예를들어 2개의 배열의 값을 증가시키는 경우가 있을 때 multi processor환경에서는 각 processor마다 작업을 할당하여 말그대로 동시에 작업을 수행하여 속도를 높일 수 있다. 1개의 thread에서는 a 배열의 값을 증가시키고, 또 다른 thread에서는 b 배열의 값을 증가시켜서 동시에 병렬적으로 작업을 처리할 수가 있다.

또 다른 이유는 I/O가 느리기 때문에 프로그램이 block되는 것을 막기 위해서이다. 상대적으로 느린작업인 I/O를 기다리는 동안 다른 thread에서는 좀 더 유용한 작업을 하여 프로그램을 overlap시킬 수 있다.

Why It Gets Worse: Shared Data

우리가 2개의 thread를 활용하여 전역변수를 각각 100000씩 증가시킨다고 하자. 원하는 것은 각각의 thread에서 100000씩, 총 200000을 얻는 것인데 실제 결과는 이와 다르다(determinate).

The Heart Of The Problem: Uncontrolled Scheduling

위의 예제에서 thread 1이 counter의 값을 50에서 51로 1 증가시킬 때 context switch가 발생하여 thread 2가 실행되었다고 가정하자 (race condition). 이때 thread 2도 역시 thread 1과 마찬가지로 같은 counter를 공유하고 있으므로 thread 2 입장에서 counter는 50이므로 1이 증가되어 51이 된다. 그 후 다시 thread 1이 이어서 동작을 할 때 역시 thread 1이 TCB에 저장해둔 내용은 counter가 50이므로 1을 증가시켜 51이 된다.

이처럼 multi thread program에서는 한 thread가 공유되는 데이터를 사용중일 때 다른 thread가 이 데이터를 활용하지 못하도록하는 mutual exclusion이 필요하다.

Atomic Operation

atomic이란 더이상 쪼개지지 않는다라는 의미이다. 따라서 실행되거나, 전혀 실행하지 않거나 둘중의 하나의 상태만 가능하다. 예를들어 atomic한 실행이 시작되면 하드웨어에 의해서 중간에 interrupt가 발생하지 않도록 한다. 그래서 이처럼 mutual exclusion과 같은 atomic한 방법이 필요하다.

기존의 page를 메모리에서 제거할 때 어떤 기준으로 page를 메모리에서 제거하는걸까?

Cache Management

page를 디스크로부터 가져올 때 cache miss가 최소화되도록 cache를 management한다.

cache hit, miss의 횟수를 통해 average memory access time(AMAT)를 알 수 있다.

AMAT = (메모리에 접근하는데 걸리는 시간 * cache hit의 확률) + (디스크에 접근하는데 걸리는 시간 * cache miss의 확률)

Optimal Replacement Policy

전체적인 cache miss의 수를 최대한으로 줄이는 것을 목적으로 한다.

이를 위해 지금으로부터 가장 나중에 접근할 page를 메모리에서 내보낸다. 가장 멀리있는 page를 참조하기 이전에 가까운 page들부터 참조할테니 총 cache miss의 수가 줄어든 것은 당연하다.

하지만 scheduling policy에서 봤듯이, 지금으로부터 가장 나중에 접근할 page를 알 수 있는 방법은 없다. 따라서 Optimal replacement policy는 우리가 완벽에 얼마나 가까운지를 결정하는 비교지표로써 사용된다.

Simple Policy: FIFO

page가 메모리에 적재될 때 queue에 올라가게 된다. 이후 page를 메모리에서 내보낼 때 queue에 가장 첫번째 page (first in)을 내보낸다.

하지만 FIFO 방식은 어떤 page block이 중요한지 알 수 없다. 예를들어 여러번 접근하는 page block이 queue의 첫번째에 있는 경우에 FIFO는 그 page의 중요성을 판단하지 못하고 내보낸다.

Simple Policy: Random

이름 그대로 random한 page를 내보내는 것이다.

random 방식은 내보낼 page를 고르는데 특별한 방법이 필요하지 않고, 무작위로 고를 뿐이다.

그럼에도 불구하고 성능이 매우 좋을 수 있다!

Using History: LRU (Least-Recently- Used)

최근에 page에 접근했을 수록 다시 그 page에 접근할 가능성이 높다.

Using History: LFU (Least-Frequetly--Used)

만약 page에 여러번 접근했다면, 중요한 page이므로 대체해서는 안된다.

Workload Example

만약 전체 workload를 담을 만큼 cache가 크다면 어떤 방법을 사용해도 좋은 결과를 얻을 수 있다.

Workload Example (80-20)

20%의 page가 전체 reference의 80%이고 (hot pages), 나머지 80%의 page가 남은 20%의 reference를 담당한다 (cold pages).이 경우에는 LRU 방식이 가장 우수함을 알 수 있다.

Workload Example : The Looping Sequential

예를들어 50개의 page sequence에 대한 10000번의 reference가 있다고 하자.

이 경우에는 LRU, FIFO가 가장 성능이 낮다.

Approximating LRU

LRU에 근사적으로 replacement를 활용하는 것이 많은 현대의 운영체제들이 수행하는 방법이다.

page가 reference될 때마다 하드웨어에 의해서 use bit가 1로 설정된다. 이 use bit는 하드웨어가 없앨 수 없고, OS만이 1에서 0으로 변경할 수 있다.

Clock Algorithm

모든 page들이 circular list의 형태로 존재한다. clock point가 특정한 page를 가리키면서 시작해서 use bit가 0인 page를 찾는다.

Considering Dirty Pages

하드웨어에는 modified bit (dirty bit)이 존재한다.

만약 page가 수정되었다면 해당 page를 디스크로 내보낼 때 다시 수정된 page를 디스크에 작성(write)해주어야 한다. 그래서 이 작업에 도움을 주기위해 modified (dirty) bit가 활용된다.

Other VM Policies

Prefetching

OS가 곧 사용될 page를 미리 가져오는 방법을 말한다. 예를들어 page 1번이 swap disk에서 메모리로 옮겨질 때 page 2번도 곧 쓰일 것으로 예측하고 같이 메모리로 옮기는 방법을 말한다.

Clustring, Grouping

매번 write요청이 있을 때마다 disk에 작성을 하는 것이아니라, 이 요청들을 모아서 한번에 처리하는 방법을 말한다. 따라서 작은 요청 여러개를 하나의 큰 요청으로 모아서 작업하는 방식이다.

Thrashing

실제 메모리 크기보다 더 많은 실행중인 프로세스의 요청이 들어온다면 어떻게해야할까?

이러한 문제를 thrashing이라고 부른다.

그래서 몇몇 프로세스 중 일부를 동작시키지 않게 함으로써 실제 메모리 크기에 맞출 수 있도록하여 thrashing을 해결하곤 했다.

이는 우리가 작업을 할 때 모든 작업을 안좋게 하기보다 더 적은 작업을 잘 하는 것이 낫다는 것을 시사한다.

좀 더 엄격하게 memory oversubscribed문제를 해결하기 위해서 out-of-memory killer라는 것을 동작시켜서 메모리를 많이 잡아먹는 프로세스를 감지하고 종료시킨다.

출처: OSTEP

하지만 크기가 큰 address space를 사용하기 위해서는 당장 필요하지 않은 address space들을 메모리에서 치울 필요가 있고, 이를 위해 hard disk drive에 이러한 역할을 맡긴다.

Swap Space

그래서 swap space가 필요하다. swap space는 디스크에 존재하며 page를 메모리에서 swap space로 swap space에서 메모리로 옮겨주는 공간이다. 따라서 OS는 swap space를 page-sized-unit으로 관리해야 한다. 위의 그림을 보면 실행중인 Proc 0, 1, 2는 메모리에 위치해 있는 반면 Proc 3은 현재 메모리에서 동작하고 있는 작업이 하나도 없으므로 swap space에 모든 프로세스가 위치해 있다. 이를 통해 어떻게 실제 물리적 메모리가 자신의 크기보다 더 큰 것처럼 동작하는지를 알 수 있다.

Present Bit

page와 디스크간의 swap을 지원하기 위해서 추가적인 하드웨어가 필요하다.

따라서 하드웨어가 page table entry(PTE)를 봤을 때 현재 이 page가 메모리에 존재하는지 아닌지를 나타내기 위한 present bit를 알고 있어야 한다.

1 -> page가 메모리에 존재하고 있음
2 -> page가 메모리에는 없고, 디스크에 존재하고 있음

Page Fault

page fault란 물리적 메모리에 존재하는 않는 page에 접근하려는 행위이다.

따라서 OS는 page fault가 발생한다면 page를 다시 swap space에서 메모리로 옮겨주어야 한다. OS는 곧 메모리로 가져올 page를 위한 새로운 공간을 마련하기 위해서 page out할 필요가 있다.

page out 기존에 사용중인 page를 swap space에 저장하고, 현재 page frame을 새로운 page에게 할당하는 것 page in swap space에 있는 page를 다시 메모리로 불러들이는 것

그래서 실행 할 page를 선택하거나, 교체하는 프로세스를 replacement policy라고 부른다.

그렇다면 언제 replacement policy를 수행할까?

Lazy Approach

OS는 메모리가 완전히 다 찰때까지 기다린다. 그 후에 새로운 page를 위해서 repace를 수행한다.

하지만 이 방법은 너무 비 현실적이다.

Swap Daemon, Page Daemon

따라서 사전조치를 위해 메모리의 작은 부분을 항상 free로 유지하는 여러가지 이유가 있다.

high watermark, low watermark 만약 OS가 사용할 수 있는 page의 수가 low watermark보다 더 적다는 것을 알았을 때 swap daemon, page daemon이라고 불리는 background의 메모리 free thread가 동작한다. 그래서 swap daemon은 사용가능한 page의 수가 high watermark와 같아질 때 까지 page들을 정리한다.

이러한 array-based page table(linear page table)의 문제를 해결하기위한 page table을 더 작게 만들 수 있는 방법은 무엇이며, 더 작아졌을 때 발생하는 비효율은 무엇일까...?

Simple Solution: Bigger Pages

page table의 크기를 줄이기 위한 간단한 방법은 page 자체의 크기를 늘리는 것이다.

32bit address space에 16KB의 page를 갖는다고 하면, 18bit의 VPN, 14bit의 offset을 갖는다. 각각의 PTE가 4byte라고 할 때 이번에는 $$2^{18}$$개의 entry를 갖고, 따라서 page table당 1MB 정도의 크기를 갖는다. page의 크기가 4KB인 경우엔 page table이 4MB였고 이와 비교하면 4배가 줄어든 것이다. 하지만 이 방법의 문제점은 각각의 page 내부에 낭비가 존재하는 internal fragmentation이 발생한다는 점이다. 그래서 대부분의 시스템이 4KB의 page table을 사용하는 이유이다.

Hybrid Approach: Paging and Segment

page table의 메모리 overhead를 줄이기 위해서 segmentation과 paging을 결합하려는 시도가 생겨났다. 크기 자체가 16KB인 address space와 1KB의 page가 있다고 가정하자.(address space의 크기가 16KB, bit로 표현하지 않았음)page는 위와같이 mappping되어있다. 그에 따른 page table은 위와같다. page table에서 볼 수 있듯이 대부분의 page는 valid bit가 0이고, 사용되지 않고있다. 만약 더 큰 크기의 32bit address space에서는 무려 백만개의 page table이 존재하므로 사용되지 않는 page는 더 많을 것이다.

따라서 어떤 하나의 프로세스에서 전체 page table을 갖는 것이 아니라 sement를 갖는 것이 hybrid approach이다. 예를들어 code, heap, stack의 3가지 segment를 갖고있다고 생각해보자. segmentation에서 우리는 segment가 물리적 메모리의 어디에 위치해 있는지를 나타내는 base register와 segment의 크기를 나타내는 bound register를 갖고있다. 하지만 hybrid approach에서는 base register는 sement를 가리키는 것이 아닌, segment에 있는 page table의 물리적 메모리 주소를 가리킨다. 그리고 bound register는 page table의 끝을 가리키는데 사용된다. 어떤 segment가 어떤 주소를 나타내는지 결정하기 위해 상위 2개비트를 활용할 것이다. 01은 code, 10은 heap, 11은 stack 영역이다. 각각의 code, stack, heap영역에 base and bound register가 있다. 프로세스가 동작하면 각각의 segment는 page table의 물리적 주소를 갖고있다. 따라서 3개의 page가 존재한다. 따라서 page table register를 활용하지 않고 base and bound register를 활용한다는 것을 제외하면 나머지 동작방식은 모두 동일하다. 예를들어 code영역에(0, 1, 2) 3개의 page가 존재하므로 code page table에는 3개의 entry가 존재하는 것이다. 그래서 bound register는 3으로 설정되고 이 bound를 넘는 access는 exception을 일으키고 프로세스를 종료시킨다.

stack, heap segment에서 할당되지 않은 page들은 page table에 없기 때문에 linear page table보다 hybrid approach를 활용함으로서 메모리를 많이 절약할 수 있다.

하지만 이 방법도 문제점은 있다.

1. flexible하지 않다는 문제점이 있는 segmentation을 활용해야한다는 점이다. 예를들어 사용될것에 대비하여 heap영역이 공간을 차지하고 있을 때 여전히 page table에서 낭비가 발생한다.
2. external fragmentation을 발생시킬 수도 있다. page의 크키가 다양해질 수 있기 때문에 메모리에서 free space를 찾는것이 매우 어려워질 수 있다.

   Multi-level Page Table

   segmentation에 의존하지 않고 같은 문제를 해결하는 또 다른 방법이 있다. 어떻게하면 메모리에 invalid한 page table을 저장하지 않고 해결할 수 있을까?

Multi-level page table이라는 방법을 활용한다. tree구조를 가지며 대부분의 modern system이 이 방법을 활용한다.

1. page table을 page-sized unit으로 나눈다. 그 후 전체 page table entry의 page가 invalid하다면 page table에 page를 하나도 할당하지 않는다. 따라서 page table에서 page가 valid한지 여부를 알기위해서 page directory를 활용한다. page directory는 page table에서 page가 어디에있는지를 알려주거나 또는 page table에 있는 모든 page들이 invalid한지도 알려준다.왼쪽에는 중간부분에 invalid한 영역이 있는 linear page table이 있다. linear page table에서는 invalid한 page에도 할당이 이루어져야한다. 반면에 오른쪽 Mulit-level page table에서는 page directory가 201, 204page만 valid함을 체크하고 있으므로 두 page에만 메모리 할당이 이루어진다. 그리고 page directory에서 사용되는 valid bit는 page table에서 해당 page가 valid함을 나타낸다는 것을 알아야한다.

multi-level page table의 장점은 아래와 같다.

1. 사용하는 page에 대해서만 할당이 이루어진다는 점에서 메모리 효율적이다.
2. 신중하게 셜계된 경우, page table과 page가 꼭 들어맞아서 메모리 관리가 효율적이다.
3. 연속적인 메모리에 존재해야하는 linear page table과 달리 multi-level page table은 물리적 메모리의 어느위치에 있건 간에 page directory를 활용하여 찾아갈 수 있으므로 level of indirection을 추가할 수 있다.

하지만 단점도 존재한다. linear page tabled은 transition information을 얻기위해 한번의 메모리 로드가 필요한 반면에, multi-level page table은 page directory에서 1번, page directory에서 page를 찾은 다음에 해당 page table entry로 1번, 따라서 총 2번의 메모리 로드가 필요하다.

그리고 성능향상을 위해 linear page table보다는 좀 더 복잡한 구조를 갖는다.

Detailed Multi-level table example

16kb 크기의 address space가 있고, 64byte의 page가 있다. 즉 14bit의 virtual address space에 8bit VPN, 6bit offset이다.linear page table은 위와같고 총 256개가 있다, 해당 page table을 2-level page table로 만들기 위해서 page sized unit으로 나눌 것이다. 하나의 page table entry는 4byte로 가정하면 총 page table의 크기는 1kb(256 * 4)이다. 그리고 page를 64byte라고 가정하였으므로 page table안에는 16개의 64byte page가 존재한다. 그리고 각각의 page는 16개의 page table entry를 갖고있다. 즉 page table안에 있는 256개의 PTE 중 16개를 합쳐서 1개의 64byte page를 구성한다.

이제 page directory를 살펴보자, page directory entry에도 page만큼 개수가 필요하므로 16개의 entry가 존재한다.그래서 이를 구성하기위해 VPN의 상위 4개 bit를 page directory index로 사용 할 것이다.

따라서 구성되는 과정은 다음과 같다.

1. page directory의 index를 통해 page directory entry를 찾는다.
2. page directory entry를 이용하여 page table에 있는 page를 찾는다.
3. 찾은 page를 통해 page table entry를 찾는다.
4. 물리적 주소로 translation한다.

따라서 paging이 너무 느리기 때문에 속도를 높일 방법, 추가적인 메모리 참조를 피할 방법이 필요하다.

address translation의 속도를 위해서 translation lookaside buffer(TLB)라는 것이 필요하다. TLB는 chip의 memory-management-unit(MMU)중 일부이고, 자주쓰이는 virtual-to-physical address translation에 자주쓰이는 하드웨어 cache이다. 그래서 address translation cache라고도 불린다. virtual memory참조가 발생하면 하드웨어는 첫번째로 TLB를 확인해서 참조하려는 address가 있는지를 살펴보고 있다면 빠르게 translation을 수행하고 반면에, TLB에 없다면 page table에서 address를 찾고 찾은 address를 TLB에 추가하여 다시 TLB에서 찾는다.

Example: Accessing An Array

예를들어 10개의 int원소를 담는 배열이 virtual address 100(01100100)에서 시작한다고 가정해보자. 그리고 추가적으로 page의 크기는 16byte인 8bit의 virtual space가 있다고 하자. 4bit는 VPN으로 나머지 4bit는 offset으로 활용되어 아래와같은 그림이된다.만약 첫번째 array[0]에 접근하는 경우에는 TLB에 아무런 address가 cache되지 않았기 때문에 page table에서 느리게 address를 찾아서 TLB에 추가해야 한다. 하지만 a[1]에 접근할 때는 이미 같은 page가 TLB에 cache되어있으므로 빠르게 TLB에서 address를 찾을 수 있다. 이처럼 TLB를 활용하면 공간적 인접성으로 퍼포먼스의 향상을 기대할 수 있다. 예제에서는 page의 크기가 16byte정도로 매우 작았지만 일반적인 page의 크기는 4KB 정도로 Array based TLB는 매우 효과가 좋다.

Who Handles The TLB Miss?

TLB miss를 다루는 것은 하드웨어일까 OS일까?

예전에는 hardware에 complex-instruction set computer(CISC)를 지니고 있어서 모든 TLB miss를 hardware가 관리하였다(hardware managed TLB). 하지만 요즘날에는 software managed TLB라고 알려진 방식을 사용한다. TLB miss시에 하드웨어는 현재 명령을 멈추고, 커널모드로 들어가서 trap handler로 점프한다. 여기서 trap handler가 OS에 코딩된 내용이다.

return from trap instruction과 return from trap system call은 조금 차이가 있다는 것을 알아야 한다. 후자의 경우 OS로 trap한 이후의(after) 명령을 재개한다. 반면에 전자의 경우 TLB miss hadling trap에서 돌아올 때 다음 명령이아닌 발생시킨(caused) 명령을 이어서 수행해야한다. 그래서 후자는 다시한번 TLB 명령을 수행하게 된다.

그리고 TLB miss handling code를 수행할 때 무한대로 TLB miss가 발생하지 않도록 각별한 주의를 기울여야 한다. 예를들면 TLB miss handler를 physical memory에 유지시키거나, TLB의 일부 항목을 영구적으로 유지시켜서 항상 그 TLB는 hit할 수 있도록 만드는 방식이다.

software managed TLB의 장점은 flexibility이다. 이는 OS로 하여금 하드웨어가 어떻게 변하던 간에 page table에 원하는 자료구조를 사용할 수 있도록한다. 그리고 두번째 장점은 19.1과 software managed TLB인 19.3의 코드를 보면 알 수 있듯이 simplicity이다.

TLB Contents: What's In There?

일반적인 TLB는 fully associative라 불리는 32 혹은 64 또는 128개의 entry를 갖고있다. 기본적으로 원하는 translation은 TLB의 어떤 위치에도 있을 수 있고, 이를 찾기 위해 병렬적으로 모든 TLB를 탐색한다.

TLB entry는

VPN | PFN | other bits

위와같은 형태이다. 각각의 entry에는 VPN, PFN이 모두 존재하는데 이는 위에서 언급했듯이 원하는 translation이 TLB의 어떤 위치에도 존재할 수 있기 때문이다.

좀 더 주목해야 할 것은 other bits이다. 일반적으로 TLB에는 valid bit, protection bit가 존재한다. 그밖에도 address-space identifier, dirty bit같은 것들도 존재한다.

TLB Issue: Context Switch

TLB는 현재 프로세스에만 적용되는 virtual-to-physical translation을 갖고 있기 때문에 다른 프로세스에서는 이 translation이 아무 쓸모가 없다. 따라서 하드웨어와 OS는 이전에 사용하던 translation을 현재 프로세스가 사용하지 않도록 해야만 한다.예를들어 프로세스 P1의 VPN10번이 PFN 100번과 mapping되어있고, P2의 VPN10번은 PFN 170번에 mapping되어있다. 그리고 OS는 P1에서 P2로 context switch를 할 계획이다. 두 프로세스 모두 VPN이 10이고 하드웨어는 이를 구분할 수 없기 때문에 문제가 될 수 있다.

첫번째 방법은 context switch시에 TLB를 flush(씻어내다)하여 다음 프로세스가 진행될 때 TLB를 비우는 것이다. software-managed TLB에서는 명시적인 하드웨어 명령을 통해서 이를 수행할 수 있고, hardware managed TLB에서는 page table base register가 변경될 때 flush가 수행될 수 있다. 두 경우 모두 valid bit을 0으로 만들고 TLB의 내용물을 제거한다. 이렇게함으로써 한 프로세스가 다른 프로세스의 TLB에 접근하지 않도록 만들 수 있지만 context switch가 발생할 때마다 flush를 하게되면 무조건적으로 새로운 프로세스의 code, data영역에선 적어도 한번은 TLB miss가 발생하게된다.

이러한 overhead를 줄이기 위해서, context switch시에 TLB를 공유할 수 있도록 하는 address space identifier(ASID)라는 추가적인 하드웨어를 추가하는 시스템도 있다.따라서 flush를 하지 않고, ASID를 활용하여 서로다른 프로세스에서 TLB 공유하면서도 구분할 수 있게된다. 한편 또다른 예시로 매우 유사한 TLB를 생각해 볼 수 있다. 예를들어 두개의 프로세스가 code영역을 공유하는 경우를 생각해 볼 수 있다.

Issue: Replacement Policy

다른 cache와 마찬가지로 TLB도 cache Replacement에 대해 생각해봐야한다. 특히 새로운 TLB를 추가할 때 예전 TLB를 대채해야한다. 이 문제에 대해서는 page를 disk로 swap할 때 다룰 것이다.

A Real TLB Entry

MIPS TLB는 32-bit address space, 4KB의 page를 갖고있다. 따라서 우리는 20bit VPN, 12bit offset이 있음을 알 수 있다. 하지만 위의 그림에서 볼 수 있듯이 실제 VPN은 19bit이다. 절반은 kernel이 사용하는 부분이고 나머지 절반이 유저가 사용하는 address space이므로 19bit만 사용한다고 한다. 그리고 VPN은 최대 24bit의 PFN으로 translate할 수 있으므로 최대 64GB 메모리까지 지원이 가능하다고 한다. 그리고 G라고 쓰여진 global bit는 프로세스가 공유되는 page를 나타낸다. 만약 G가 1로 설정되어있다면 ASID는 무시되고 프로세스가 공유된다.

그런데 만약 8bit 크기의 ASID를 넘어서는 동시에 256개 이상의 프로세스가 동작한다면 어떻게될까...?

우리는 하드웨어에 의해서 page가 어떻게 cache되었는지를 나타내는 3bit 크기의 Coherent bit(C)가 있다. 그리고 page가 다시 쓰여진 적이 있는지 여부를 나타내는 dirty bit(D) 그리고 valid한 translation이 존재하는지 여부를 나타내는 valid bit(V)가 존재한다.

출처 : OSTEP

1. virtual memory에서 본 segmentation이라고 하는 방식으로 다양한 크기로 메모리를 나누는 것이다. 하지만 이 방법은 메모리를 2개의 chunk로 나눌 때 fragmentation이라는 문제를 일으킬 수 있다는 단점이있다.
2. 메모리를 고정된크키로 나누는 것이다. virtual memory에서 우리는 이 방법을 paging이라고 부른다. 프로세스의 address space를 다양한 크기의 segment(code, stack, heap)로 나누지 않고, 고정된 크기의 page로 나눈다. 따라서 우리는 물리적 메모리를 고정된 크기의 page frame의 배열로 볼 수 있다.

Simple example and Overview

쉬운 이해를 위해 작은 크기의 메모리로 예들어보자 총 64byte의 크기이고, 각각 16byte크기인 4개의 page가 있다.18.2의 그림처럼 실제 물리적 메모리는 총 8개의 page로 구성되어있고, virtual space들은 물리적 메모리의 서로 다른 주소에 위치해있다.

paging은 여러가지 장점들이 존재한다.

1. flexibility 프로세스가 address space를 어떻게 사용하는지에 상관없이 추상화를 효과적으로 수행 할 수 있다. 우리는 heap, stack이 어떤 방향으로 크기가 커지는지 가정할 필요가 없다.
2. simplicity free space의 관리를 쉽게 만들어준다. 만약 64KB의 address space를 물리적 메모리의 8개 page에 저장하려고 할 때 1개의 page가 16KB이므로 OS가 관리하는 free list에서 4개의 page만 가져오면 된다.

물리적 메모리의 어떤 주소에 virtual page의 주소가 위치해 있는지를 알기위해서 OS는 프로세스마다 page table이라는 것을 지니고 있어야 한다. page table의 주 목적은 address space의 virtual page가 물리적 메모리에서 어떤 위치에 있는지를 나타내는 것을 위한 address translation을 저장하고 있는 것이다. 예를들어 18.2에서 볼 수 있듯이 virtual page 0은 physical page frame 3에 해당된다.

우선 프로세스가 생성되는 virtual address를 물리적 메모리의 주소로 변환하기 위해서 virtual page number, page의 offset 두개의 구성요소로 나누어야 한다. viftual address space가 64KB이므로 (2^6 = 64) 즉 6개의 bit가 필요하다. 한 page의 크기가 16KB이므로 우리는 4개의 page를 가져야하고 이를 나타내기 위해서는 segment에서 활용되는 것처럼 explicit approach로 상위 2개의 비트를 활용하여 4개의 page를 표현할 수 있다.

예를들어 virtual address 21을 물리적 메모리로 translate해보자.

movl 21, %eax

21은 이진수로 위와 같으므로 virtual address 21은 virtual page 1(VPN: "01")의 5(Offset: "0101")번째 위치에 있음을 알 수 있다. 따라서 18.2의 그림에서 알 수 있듯이 virtual page1은 물리적 page 7에 있다는 것을 알 수 있다.

Where the Page Table stored?

page table은 segment table, base and bound register보다 훨씬 크다. 4KB의 page, 32bit의 address space가 일반적이다. 그렇다면 32bit의 address space에는 4kb page가 거의 몇개가 들어갈까? 우선 4kb는 $$ 2^2 * 2^{10} $$ 이다. $$ 2^{32} / 2^{12} = 2^{20} (약 100만) $$ 따라서 약 100만개의 page가 존재한다. 따라서 상위 20개 bit가 VPN이 되고, 나머지 12개의 비트는 offset이다. 따라서 page table entry(PTE)하나에 약 physical translation, 기타 정보들을 보관하기 위해서 4kb의 메모리가 필요하다면, 100개의 프로세스가 동작하는 경우 PTE를 저장만하는데 무려 400MB가 필요하게된다. 요즘같은 64bit 환경에서는 더 크게될 것이다.

이렇게 Page table이 너무 크기때문에 실행중인 프로세스의 page table을 MMU on-chip 하드웨어에 저장하지 않는다. 그 대신 각 프로세스의 page table을 메모리에 저장한다.

What’s Actually In The Page Table?

page table이란 virtual address(virtual page number)를 physical address(physical page number)로 매칭시켜주는 자료구조이다.

가장 간단한 구조로는 linear page table이라고 불리는 배열이다. 배열처럼 OS가 VPN으로 배열을 인덱싱해서 PFN를 찾아낸다.

PTE에는 우리가 알아야 할 여러가지 bit들이 있다. valid bit는 특정한 translation이 valid한지 아닌지를 나타내는 비트이다. 예를들어 프로그램이 동작하면 code, stack, heap영역을 사용하고 그 외에 사용되지 않는 address space에는 valid bit가 invalid인 상태를 나타낸다. 만약 invalid한 address로 접근한다면 OS로 trap되어 프로세스가 종료된다. 따라서 valid bit는 남아있는 address space를 invalid로 표현하여 물리적 프레임을 할당하지 않음으로써 메모리를 절약한다.

그리고 특정한 page를 읽고, 쓰고, 실행할 수 있는지 여부를 나타내는 protection bit도 중요하다. 그리고 present bit는 현재 page가 디스크에 있는지 메모리에 있는지를 나타낸다. dirty bit는 page를 메모리로 가져온 이후 수정되었는지 여부를 나타낸다. reference bit는 page에 대한 접근이 있었는지 없었는지 여부를 추적할 때 사용되고, 특정한 page가 자주 사용되기 때문에 메모리에 남겨두어야하는지 그렇지 아닌지를 알려준다.

Paging: Also Too Slow

데이터를 적절하게 page에 전달하기 위해서는 먼저 virtual address를 physical address로 translate 해야한다. 이를 위해서 하드웨어는 반드시 현재 실행중인 프로세스의 page table을 갖고 있어야한다.

일단 page table base register에 page table의 실제 시작 위치가 저장되어있다고 가정해보자.PTE를 얻기위해서 위와같은 작업을 한다. 우리의 예제에서 전체 virtual address에서 VPN만을 가져오기 위한 VPN_MASK는 0x30(110000)이다. SHIFT는 offset의 bit값인 4로 설정한다. 만약 21(010101)이라는 virtual address인 경우 VPN은 01이므로 virtual page는 1에 해당되고 이를 인덱스로하여 PTE에서 page table base register를 얻어낼 수 있다. 이제 physical address를 알았으므로 하드웨어는 메모리로부터 적절한 데이터를 register eax에 보내는 것이 가능하다.

요약하자면 우리는 각각의 메모리 참조의 프로토콜에 대해서 알게되었다.18.6을 통해 우리는 paging을 통해 메모리에 접근하는 방법을 알 수 있다. 이때 모든 메모리 참조에 대해 paging은 page table에서 translation을 가져오기 위해서 한번의 추가적인 메모리 참조가 필요하다는 것을 볼 수 있다. 추가적인 메모리 참조는 고비용이고, 이 경우 프로세스가 2배 이상 느려질 수도 있다.

따라서 하드웨어와 소프트웨어를 둘 다 신중하게 설계하지 않는다면 page table은 메모리도 많이 필요하고 시스템을 너무 느리게 만들것이다.

출처 : OSTEP

관리하는 메모리 공간을 고정된 크기(fixed-size unit)로 나누면 쉽다. 고정된 크기의 메모리 리스트를 갖고있다가 요청이 오면 리스트의 첫번째 원소를 리턴하면 된다.

하지만 free-space가 다양한 크기의 메모리 유닛으로 구성되어진다면 관리하는 것이 어려워진다. 이것은 유저레벨에서의 메모리 할당과 해제( malloc(), free() ), virtual memory를 활용하기 위해 OS가 실행하는 segmentation, external-fragmentation등에서 찾아볼 수 있다.위의 그림에서 볼 수 있듯이 free-space는 총 20byte인데 *fragmented8되어있기 때문에 15byte의 할당이 필요한 요청은 실패하게된다.

Assumtion

void *malloc(size_t size), void free(void *ptr)에 대해서 알아볼 것이다. malloc()으로 지정한 크기 혹은 더 큰 사이즈의 메모리를 할당받는다. 그리고 free()를 통해 할당받은 메모리를 해제하는데 이때 얼마만큼의 크기를 해제해야하는지 인자로 넘겨주지 않아도 할당한 만큼 해제가 이루어지게된다. 이 부분에 대해서는 이 장의 뒷부분에서 이야기를 나눠 볼 것이다.

external-fragmentation에 대해 걱정한 것 처럼, Allocator들은 internal-fragmentation에 대해서 신경써야 한다. 만약 allocator가 요청한 것 보다 더 큰 메모리공간을 제공하는 경우 요청한 만큼을 사용하고 남는 메모리 공간에 대해서 internal-fragmentation이 발생한다. 하지만 이번에 우리는 external-fragementation에 대해서만 살펴 볼 것이다.

이제 아래와 같은 가정을 할 것이다.

1. 메모리를 할당하면 할당 한 메모리의 위치가 재조정되지 않는다. 프로그램이 malloc()으로 메모리를 할당받으면 free()를 할 때 까지 같은 메모리공간을 점유한다. 따라서 fragmentation을 해결하기 위한 유용한 방법인 compaction은 발생하지 않는다. 하지만 OS가 segmentation을 수행할 때 fragmentation을 해결하기 위해 compaction이 발생할 수는 있다.
2. allocator는 연속적인 메모리공간을 관리한다. 유저레벨에서 heap영역을 증가시켜야 하는 요청이 발생할 수도 있지만 이번에는 고정된 크기로 가정할 것이다.

   Low-level mechanism

   policy에 대해서 깊게 탐구하기 전에 기본적인 allocator들의 splitting(나누기), coalescing(합치기) 방법과 어떻게하면 빠르고 쉽게 할당한 메모리 크기를 알 수 있는지에 대해서 알아볼 것이다. 그리고 free-space를 파악할 수 있는 간단한 free list에 대해서 알아볼 것이다.

   Splitting and Coalescing

   위의 그림에서 볼 수 있듯이 총 30byte의 heap segment에서 0-9, 20-29byte가 free-space이다. 따라서 이 heap segment에 대한 free list는 아래와 같이 구성될 수 있다.언급했듯이 10byte 이상의 메모리 할당은 실패할 것이다. 정확하게 10byte의 요청이 오면 쉽게 성공 할 것인데 만약 10byte보다 더 작은 메모리 할당 요청이 온다면 어떻게될까...?

예를들어 free list에 10byte의 free chunk가 존재하는데 1byte의 할당 요청이온다면 이 경우 splitting이라는 방법을 활용하게된다. 그래서 1byte를 할당할 수 있는 free list에 존재하는 2개의 free chunk에서 allocator가 2번째(20-29)를 사용하기로 했다면 2번째 free chunk를 2개의 chunk로 splitting한다. 그래서 첫번째 chunk는 1byte를 할당하고 두번째 chunk는 그대로 free list에 남아있는다. 따라서 free list에서는 20-29byte를 차지하던 2번째 chunk가 21-29byte로 크기가 변하게된다. 이처럼 free chunk보다 요청되는 메모리의 크기가 더 작을 때 splitting이 유용하게 사용된다.

그렇다면 또다른 예시로 만약 사용중이던 10byte의 메모리를 free()한다면 어떻게될까?

그렇다면 단순하게 free list에 반환된 10byte만큼을 아래와같이 추가하면 된다.만약 10byte씩 3개의 chunk로 나뉜 상태에서 20byte의 할당 요청이 들어온다면 당연히 할당에 실패할 것이다. 이러한 문제를 해결하기위해서 allocator는 3개의 free chunk를 하나의 free chunk로 coalescing한다.

Tracking The Size Of Allocated Regions

free()에 해제해야 하는 메모리의 크기가 없다는 것을 알고있으므로, 우리는 해제 할 포인터를 매개변수로 받았을 때 해제되어야 할 크기를 파악하고, 해제된 메모리를 free list에 추가해야함을 알고있다.

이를 위해서 대부분의 allocator들은 약간의 메모리를 더 써서 head block이라는 곳에 추가적인 정보를 저장하고 있다.

예를들어 20byte의 메모리를 할당받았다고 하자, 이때 헤더에는 해제를 위한 포인터주소와, 무결성검사를 제공하기 위한 magic number 및 기타 다른 정보들을 갖고있다.

typedef struct
{
    int size;
    int magicNumber;
}    header_t;

간단하게 위와같은 헤더가 있을 때 우리는 포인터 연산을 활용하면 쉽게 header의 정보를 얻을 수 있다. 해제해야하는 ptr을 header_t로 형변환 한 후 포인터를 -1만큼 이동시키면 17.2와 같이 hptr의 위치를 얻을 수 있다(header_t는 8byte이므로). 그 후에는 무결성 검사를 위해 magicNumber와 예상되는 값이 맞는지를 확인하고 해제되는 메모리의 크기가 header+유저에게 할당된 메모리 크기가 맞는지를 확인하면 된다.

결론적으로 유저가 N만큼의 메모리 할당을 요청했을 때 allocator는 N만큼의 메모리공간을 찾는 것이 아닌, N + header만큼의 메모리공간을 찾는다.

Basic Strategies

free space를 관리하는 기본적인 방법들에대해서 알아보자.

이상적인 allocator는 빠르고, fragmentation을 최소화해야한다. 안타깝게도 malloc, free의 과정이 프로그래머의 의도에 따라서 수행되기 때문에 특정한 방법은 꽤나 안좋은 결과를 발생시킨다. 따라서 가장 좋은 방법에 대해서 말하기보단, 기본적인 방법들의 장단점에 대해 논해볼 것이다.

Best Fit

1. free list에서 요청된 크기보다 충분히 큰 free chunk들을 찾는다.
2. 충분히 큰 free chunk들 중에서 가장 작은 녀석을 free list에 추가한다.

간단하게 생각할 수 있는 쉬운 방법이다. 하지만 적합한 free chunk를 찾기위해서 모든 경우를 다 살펴봐야하므로 상당히 고비용이다.

Worst Fit

worst fit은 best fit의 반대이다. 가장 큰 free chunk를 free list에 추가한다. 하지만 역시나 적합한 free space를 찾기 위해 반복을 해야하므로 고비용이다. 그리고 더 나쁜것은 추가적인 fragmentation이 발생할 수 있다는 점이다.

First Fit

이름 그대로 요청을 만족할 수 있는 가장 첫번째 메모리 블록을 반환하는 것이다. first fit은 속도면에서 장점이 있다. 하지만 작은 크기의 메모리를 할당할 때는 free list를 훼손시킬 수 있다. 따라서 allocator는 free list의 순서를 어떻게 관리할 것인가가 매우 중요한 문제이다. 이를 위한 한가지 방법은 free space 주소의 순서를 유지하여 coalescing을 쉽게만들고, fragmentation을 줄이도록 하는address-based ordering기법이다.

Next Fit

항상 첫번째로 조건에 부합하는 결과를 찾는 first-fit과 달리, next-fit은 가장 마지막에 수행되었던 주소의 위치를 기억한다. 따라서 free list에 대한 검색을 좀더 균일하게 분산시켜 free list의 앞부분에서 fragmentation이 발생하지 않도록 한다.

segregated List

segregated List방법은 자주 사용되는 할당 크기만 전담하는 list가 따로 있고, 그 외의 경우에는 일반적인 allocator가 할당을 수행한다. 이렇게 함으로써 fragmentation의 위험이 크게 줄어들 수 있고, 자주 사용되는 메모리의 크기인 경우 free space를 찾지 않아도 되기 때문에 할당과 해제가 꽤나 빠르게 이루어질 수 있다.

하지만 이 방법에도 어느정도의 메모리를 자주 사용된다고 판단하여 할당할 것인지에 대한 문제는 남아있다. 이에 대한 해결책으로 간단하게, kernel이 시작할 때 object cache가 할당되는데, 이 object cache가 자주 할당되고 해제되기 때문에 object cache는 segregated list로 관리된다.

그리고 주어진 cache가 사용가능한 메모리 공간이 부족할 때 일반적인 allocator에게 메모리 slab를 요청하여 추가적인 메모리를 할당받고, 반대로 slab내의 참조 카운트가 0이되면 일반적인 allocator가 다시 메모리를 회수한다.

Buddy Allocator

예를들어 64KB의 free space가 7KB 요청에 부합하는 크기로 계속해서 splitting되어 아래와 같은 그림이 되었다고 하자.8KB는 할당되어 리턴되었지만 internal fragmentation이 발생한다. 그런데 할당한 메모리가 해제될 때 일반적인 allocator는 buddy allocator의 메모리가 해제되어있는지를 확인한다. 그래서 해제되어있다면 할당한 메모리 8KB + buddy allocator의 8KB를 coalescing하게된다. 또다시 16KB와 그 buddy allocator가 coalescing하여 결국 다시 원래의 64KB의 free space로 되돌아가게 된다.

출처 : OSTEP

Segmentaion: Generalize Base and Bound

이러한 문제를 해결하기 위해 segmentation이라는 방법이 나왔다. 이 개념은 쉽게 말해 CPU에만 한 쌍으로 존재하는 base and bound register를 address apce의 논리적인 segment마다 갖고 있는것을 말한다. segment란 address space에서의 연속적인 부분을 뜻하는데 우리는 이 부분들이 code, stack, heap의 3개의 논리적 segment를 알고 있다.

각각의 segment를 물리적 메모리의 서로 다른 부분에 독립적으로(independently)배치하여 사용되지 않는 virtual address space가 생기는 것을 막을 수 있다.

이 그림에서 알 수 있듯이 실제 물리적 메모리의 서로 다른 영역에 어떤 한 프로세스의 stack, code, heap segment가 독립적으로 존재하고, 또 다른 프로세스의 stack, code, heap이 사용되고 있지 않은 not in use space에 위치한다면 사용되지 않는 virtual address space가 생기는 것을 최대한 막을 수 있다.

따라서 각 segment마다 base and bound register가 존재하면 아래와 같은 모습이 된다.

Which segment Are We Referring to?

transition시에 하드웨어는 segment register를 사용한다. 그렇다면 어떻게 segment의 시작위치와, address를 아는 것일까?

explicit approach라 불리는 방법인데, virtual address의 상위 몇 비트를 기반으로 address space를 segment로 분할하는 기법이다.

우리는 stack, heap, code의 3가지 segment가 있기 때문에 2개의 비트가 필요하다. 만약 14비트의 virtual address에서 2비트를 segment로 잡으면 virtual address는 다음과 같아진다. 그래서 만약 상위 2개의 비트가 00이면 code영역으로 생각하고, 01이면 heap영역으로 생각하면 아래와 같은 그림이 된다. 따라서 상위 2개의 비트는 segment를 판별하는데 사용하고, 하위 12개의 bit는 offset으로 사용한다. base register에 offset을 더함으로써 실제 물리적 메모리에서의 위치를 알 수 있다. (base register에 virtual address를 더하는 것이 아니라는 점에 유의하자!) 하지만 2개의 비트를 사용하는 경우 00, 01, 10, 11을 사용할 수 있는데 우리는 3개만 사용하므로 1개의 segment 낭비가 발생한다. 그래서 이러한 낭비를 줄이기 위해서 code영역을 heap에 합쳐서 1개의 비트만 사용하는 경우도 있다. 그리고 segment를 지정하는데 상위 여러개의 비트를 사용하는 경우 virtual address space의 사용을 제한된다는 점이다. 특히 우리의 예제에서는 segment크기가 4KB로 고정되어있는데 만약 16KB의 address space의 경우 4조각으로 쪼개진다는 의미이며, stack, heap영역의 크기가 이보다 커져야 할 경우 문제가 발생할 수 있다.

그래서 하드웨어에서 segment를 결정하는 또 다른 방법이 있다. implicit approach라고하는 방법이고, 하드웨어는 address가 어떻게 구성되었는지를 파악해서 segment를 결정한다.

What about Stack?

stack은 16.2의 그림에서 28KB에 위치해있고, 더 작은 주소값으로 즉 0KB 방향으로 크기가 증가한다. 28KB -> 16KB -> 14KB....로 변한다. 그리고 추가적으로 base and bound register외에도 어떤 방향으로 segment가 증가하는지를 알기위한 하드웨가 필요하다. 예를들어 비트가 1로 설정되어있으면 positive방향으로 0이라면 negative방향으로 segment가 증가한다.

예를들어 virtual address 15KB 실제로는 physical address 27KB에 접근하려한다. 2진수로는 11 1100 0000 0000(hex 0x3C00)이다. 하드웨어는 상위 2개 비트를 사용하여 segment를 결정한다. 따라서 남은 offset은 3KB이다. 올바른 negative offset을 얻기위해서 3KB에서 최대 offset의 크기인 4KB를 빼야한다. base register인 28KB에서 negative offset인 -1KB를 더해서 물리적 메모리인 27KB를 알 수 있다. bound check는 negative offset의 절대값이 segment의 현재 크기보다 작거나 같은지를 확인하여 파악할 수 있다 (이 경우 2KB).

Support for Sharing

메모리를 절약하기 위해서 특정한 메모리 segment를 공유하는것이 효과적임을 알게되었다. 특히 code sharing은 여전히 유용하다.

sharing을 위해서 protection bits의 형태로 하드웨어의 도움이 필요하다. 기본적으로 프로그램이 segment를 읽거나 쓸 수 있는지 또는 segment내에 있는 코드를 실행할 수 있는지의 여부를 나타내는 segment당 몇개의 비트를 추가한다. code segment를 읽기전용으로 설정하므로써 multi-process에서 독립성을 훼손하지 않으면서 코드를 공유하는 것이 가능하고, 여전히 프로세스들은 자신만의 private 메모리를 소유하고있다고 생각한다. protection bit를 사용하면 virtual address가 bound내에 있는지 확인하는 것 말고도 특정 엑세스가 허용 가능한지를 확인해야 한다(읽기전용이면 공유될 수 있으므로). 또한 읽기전용 segment에 write를 하려고하거나, read-execute가 불가능한 segment에서 execute하려고 하는 경우 예외를 발생시켜야 한다.

Fine-grained vs Coarse-grained Segmentation

지금까지 살펴본 내용은 시스템에서 고작 몇개의 segment(code, stack, heap)만을 알아보았다. 이런 비교적 거대한 segment들을 I'm coarse-grained segmentation이라고 부른다. 반면에 초기의 시스템에는 flexible함이 필요했기 때문에 크기가 더 작고 개수가 더 많은 fine-grained segmentation이 필요했다.

많은 segment들이 더 많은 하드웨어의 지원과 메모리에 저장된 segment table이 필요하게 되었다. segment table을 활용함으로써 시스템은 좀 더 flexible한 방식으로 많은 개수의 segment를 만들어서 활용할 수 있게되었다.

OS Support

이제 segmentation이 어떻게 동작하는지를 알게되었다. 하지만 segmentation은 OS에게 몇가지 문제를 야기한다.

1. context switch시에는 어떻게 할 것인가? 이를 위해서 각각의 프로세스가 가지고 있는 virtual address의 base and bound register를 저장했다가 프로세스 재시작 전에 다시 불러와야 한다는 점을 알 수 있을 것이다.
2. segment의 크기가 커지거나, 줄어들 때 OS는 어떤 관련이 있는가? 예를들어 현재 heap segment의 크기만으로 malloc()을 감당할 수 있는 경우에는 할당을하면 되지만 이 크기를 넘어서는 새로운 메모리를 할당해야할 경우에는 sbrk()라는 시스템 콜을 해서 heap segment의 크기를 증가시킨다. 그래서 변화된 크기만큼을 다시 register에 등록하고 메모리 할당을 성공할 수 있다. 하지만 만약 물리적인 메모리 자체가 모자르다면 OS는 메모리할당을 거부할 수도 있다는 것을 명심히자.
3. 물리적 메모리의 free space를 어떻게 관리 할 것인가? 일반적으로 프로세스마다 segment가 생길 것이고 이 크기는 제각각일 것이다. 따라서 물리적 메모리의 중간 중간에는 free space의 구멍이 뻥뻥 뚫려있을 것이고 이는 새로운 segment의 할당을 어렵게 만들 것이다. 이러한 문제를 external-fragmentation라고 부른다. 따라서 segment들을 재조정하여 물리적 메모리를 compact하게 사용함으로써 문제를 해결할 수 있다. 하지만 segment들을 재조정하는 방식은 매우 무거운 작업이다. 예를들어 재조정이 끝난 이후에 중간에 있는 프로세스의 heap segment가 증가되야 한다면 또 다시 추가적인 재조정이 일어나야만 한다. 따라서 좀 더 간단한 방법은 할당에 필요한 큰 메모리 공간을 유지하려는 free-list를 관리하는 것이다. 이 외에도 여러가지 알고리즘을 통해서 external-fragmentation을 해결하기 위해 노력하지만 external-fragmentation을 없앨 수는 없고 최소화 할 뿐이다.

출처 : OSTEP

메모리 가상화를 제공할 때도 효율성과 통제권(Efficiency and Control)을 얻기위해서 비슷한 방법이 필요하다.

효율성을 위해서는 분명히 하드웨어가 뒷받침되어야 하고, 처음에는 레지스터 정도로 간단하지만 필요한게 더 많아지다보면 점점 복잡해지는 문제가 있다.

통제권을 위해서는 프로그램이 아무 메모리에 접근하지 못하도록 막을 필요가 있다. 따라서 역시 하드웨어가 뒷받침 되어야 한다.

마지막으로 Flexibility를 위해서 메모리 가상화 시스템이 필요하다. 왜냐하면 특히 우리는 프로그램이 물리적 메모리의 어디에 있건, address space에서 동작하길 원하기 때문이다.

이를 위해서 LDE와 같은 hardware-based address transition(address transition)이라고 불리는 방법을 사용해 볼 것이다.

address transition을 통해 하드웨어는 각각의 메모리 접근(명령 저장하기, 불러오기..)을 virtual address에서 실제 physical address로 변환한다. 그래서 모든 프로그램으로의 메모리 참조는 사실 하드웨어가 프로그램의 메모리 참조를 실제 물리적 메모리로 redirect한, address transition의 결과이다.

물론 하드웨어만으로는 메모리를 효율적으로 활용하기 위한 낮은 수준의 mechanisim만 제공할 뿐임으로 메모리 가상화를 수행할 순 없다. 따라서 OS가 적절한 때에 하드웨어를 호출하여 적절한 transition이 발생하도록 해야한다. 따라서 이를 위해 어떤 메모리가 비어있고, 어떤 메모리는 사용중인지를 추적하기 위한 메모리 관리가 필수적이다.

Assumption

1. address space는 physical memory의 연속적인 공간에 위치한다.
2. address space는 너무 크지 않다.
3. 모든 address space의 크기는 같다.

   Example

   address transition를 수행하기 위해 무엇을 해야하는지, 그리고 왜 이러한 mechanism이 필요한지를 알기위한 예제를 보자.

아래와 같은 코드가 있을 때 컴파일러가 이 코드를 아래와 같이 바꾼다. x의 주소는 ebx에 존재하고, eax에 3을 더하고, eax에 있던 값을 메모리로 옮긴다. 이 코드를 address space에서 살펴보면 위와 같다. 코드는 주소 128, 코드섹션에 있고, x는 3000, stack영역에 있다. 그리고 아래와 같은 메모리 엑세스를 수행한다. • 주소 128에 있는 명령을 가져온다. • 명령을 수행한다. (load from address 15 KB) • 주소 132의 명령을 가져온다. • 명령을 수행한다. (no memory reference) • 주소 135의 명령을 수행한다. • 명령을 수행한다. (store to address 15 KB)

프로그램의 관점에서 해당 프로그램의 address space는 0에서 시작해서 16KB의 크기를 갖고, 모든 메모리참조는 이 범위내에서 이루어진다. 그러나 OS는 메모리 가상화를 위해 이 address space에서의 참조를 실제 physical memory로 전달해주어야 한다.

그렇다면 어떻게 프로세스에 transparent하게 메모리에서 이 프로세스를 재배치 할 것인가? 또한 어딘가에 있는 실제 물리적 메모리가 0에서 시작하는 가상의 address space라는 환상을 어떻게 제공할 것인가?

Dynamic(hardware-based) relocation

1950년대 time-sharing 기계에서 소개된 base-and-bound, dynamic relocation라는 기술이다. 이를 위해서 CPU에 있는 base register, bound(limit)register라는 2가지 하드웨어가 필요하다. base-and-bound를 통해서 우리는 물리적 메모리가 어디에 있건 프로세스가 자신의 address space에 있는것 처럼 만들 수 있다. 프로그램은 자신이 0번 주소에 위치한 것 처럼 작성되고, 컴파일 된다. 그리고 프로그램이 실행될 때 OS는 물리적 메모리의 어떤 위치에 프로그램을 올리고, base-register에 해당 주소값을 할당해야 한다. 위의 그림에서 보면 OS는 물리적 메모리의 32KB에 프로그램을 올리고, base-register에 이 주소값을 할당한다. 따라서 메모리 참조가 발생할 때 이는 이렇게 해석될 수 있다.

physical address = virtual address + base(register value)

program counter(PC)가 128에 설정되어있고, OS는 프로그램이 위치하는 주소인 32KB(32768)를 base register로 만들고 해당 base register에 명령의 주소값(128)을 더해주어 물리적 메모리의 주소(32896)를 얻는다. 그 다음 하드웨어가 명령을 가져오고, 프로세서가 명령을 수행한다.

128: movl 0x0(%ebx), %eax

그 후 프로세서가 가상주소에서 15KB만큼 로드를 발행시킨다. 따라서 실제 물리적 메모리에서는 32KB + 15KB = 47KB까지의 메모리가 활용된다. 이러한 address relocation은 runtime시에 발생하기 때문에 프로그램이 실행중이더라도 수행될 수 있고 이러한 이유 때문에 dynamic relocation이라고 부른다.

그렇다면 base-and-bound에서 base의 역할은 알았는데 bound(limit)의 역할은 무엇일까? bound(limit) register는 protection을 위한 기능을 한다. 프로세서는 항상 bound 내부에서 메모리 참조가 이루어져야 하고, 이 예시에서는 bound가 16KB로 제한돼있기 때문에 이 bound보다 작거나, 큰 주소를 참조하려 할 경우에는 exception을 발생시키고 프로그램을 종료시킨다. 따라서 bound register는 2가지 기능을 한다고 할 수 있다.

1. address space의 크기를 나타낸다.
2. 물리적 메모리에서 address space의 끝을 나타낸다.

그리고 base, bound register는 CPU에 쌍으로 존재하는 하드웨어라는 점을 명심해야한다.

ASIDE : Software-base relocation

hardware-base relocation이 도입되기 이전엔 software-base relocation이 사용되었다. static-relocation이라고도 하며, ** loader라고** 불리는 소프트웨어가 실행되려고 하는 프로그램을 가져와서 실제 물리적 메모리의 적절한 시작위치에 메모리를 재배치 시킨다. 예를들어 명령이 1000번 주소에 있고 address space가 3000에서 시작한다면 loader는 프로그램을 0이 아닌 3000의 위치로 옮긴다. 따라서 명령행은 4000번 주소에 위치한다. 이러한 static-relocation은 다음과 같은 문제가 있다.

1. protection을 제공하지 못함
2. 한번 relocation이 이루어진 후 또다른 위치로 relocation을 수행하기 어렵다고 한다.

Operating System Issue

메모리 가상화를 달성하기 위해서 OS와 hardware가 결합되어야 한다. OS는 새로운 프로세스가 실행되면 free list라고하는 자료구조를 통해 어떤 메모리 공간이 비어있고, 어떤 메모리 공간이 사용중인지를 파악한다. 그래서 비어있는 메모리 공간에 새로운 프로세스를 할당하고 사용중으로 변경시킨다. 물론 프로세스마다 사용하는 address space의 크기가 다를것이고, 실행되는 기간도 다르겠지만 이러한 문제점들은 나중에 알아보도록하자.

15.2의 그림에서 볼 수 있듯이 OS는 물리적 메모리의 가장 처음부터 실행되며 2개의 free space가 존재한다. 따라서 free list에는 2개의 free list가 존재한다. 그리고 프로그램이 문제를 일으켜서 OS가 강제로 종료하게되는 경우 해당 메모리를 다시 free list에 추가 해 두어야 한다.

그리고 CPU에는 1쌍의 base-and-bound register만 있기 때문에 context switch마다 OS는 각각의 프로세스의 base, bound register의 값을 process structure 또는 Process Control Block(PCB)라고 불리는 자료구조에 저장하고, 불러올 수 있어야 한다.

프로세스의 address space를 옮기기 위해서 OS는

1. 프로세스를 deschedule한다.
2. 현재의 address space를 옮길 address space로 복사한다.
3. base register를 새로운 address space에 업데이트한다.

그리고 OS는 exception handler를 제공해야 한다.

출처 : OSTEP

메모리 사용이 다 끝나지 않았는데 해제를 해버린 경우를 일컬어 dangling pointer라고 부른다.

Why no memory is leaked once your process exits

어떤 짧은 프로그램을 작성하고, 메모리 할당을 한 후 종료전에 해제를 해야하는가? 해제를 안하는 것이 이상하겠지만, 해제를 하지 않아도 실제로는 메모리 누수가 없다.

그 이유는 다음과같다. 실제 메모리 관리 시스템에는 2가지 종류가 있다.

1. OS에 의해서 프로세스가 실행되면 메모리를 할당하고, 종료시에 다시 회수하는 메모리 관리 시스템이 있다.
2. 각각의 프로세스 안에서 실행되는 메모리 관리 시스템이 있다. 메모리를 해제하지 않더라도, 프로그램 실행이 완료되면 운영체제가 프로세스의 모든 (code, stack, heap등...) 메모리를 회수한다.

따라서 짧게 동작하는 프로그램은 메모리 누수가 문제를 일으키지 않는다, 물론 좋은 프로그램은 아니다. 만약 웹서버나, 데이터베이스같이 끝나지 않는 프로그램을 만들었을 때 메모리 누수는 프로그램의 메모리를 모두 소모하여 정말 큰 문제를 일으킨다.

출처 : OSTEP

초기의 컴퓨터는 메모리의 관점에서 사용자에게 많은 추상화(abstraction)를 주진 못했다. OS는 물리적인 메모리에 올라간 라이브러리 같은 것이였고, 다른 물리적인 메모리 위치에서는 프로그램이 동작하고 있었다.

Multiprogramming And Time Sharing

시간이 지난 후 컴퓨터가 비싸짐에 따라 사람들은 컴퓨터의 resource를 효율적으로 활용하기 시작했다. Multiprogramming의 시대가 열리면서 특정한 순간에 여러개의 프로그램이 실행될 수 있어야 했고, OS는 적절하게 프로세스들을 바꿔주어야 했다.

하지만 머지않아서 사람들은 더 많은 컴퓨터가 필요했고, 특히 batch computing의 한계를 느끼고 나서 time sharing의 시대가 오게되었다.

많은 사용자들이 적절한 시간에 컴퓨터로부터의 응답을 기다리고, 많은 작업을 동시에 수행할 수도 있기 때문에 interactivity가 중요해졌다.

하지만 메모리 크기가 커짐에 따라 time sharing은 너무 느리게되었다. register등의 상태를 저장하는 것은 그닥 오래걸리지 않았지만, 모든 메모리의 내용을 디스크에 저장하는 것이 상당히 오래걸렸다.

그래서 이를 해결하기 위해 프로세스를 메모리에 남겨두며 switching하면, OS가 time sharing을 효과적으로 수행할 수 있다.

그런데 위의 그림처럼 여러개의 프로세스가 동시에 진행될 때 어떤 프로세스가 다른 프로세스의 메모리를 침범하지 않도록 하는 protection이 가장 중요한 문제가 되었다.

프로세스가 마음대로 다른 프로세스의 메모리에 데이터를 읽거나, 쓰는것은 큰 문제가 될 수 있기 때문이다.

The Address Space

이를 위해 OS가 물리적 메모리를 사용하기 쉽도록 추상화할 필요가 있었다.

이 추상화를 address space라고 부른다.

이 address space는 실행중인 프로그램의 메모리상 위치를 나타낸다.

예를들어 프로그램의 code는 메모리의 어딘가에 위치해 있어야만 하고, 그 내용은 address space에 있다. 프로그램은 또한 stack을 함수가 불린 위치를 기억하고, 지역변수를 할당하고, 인자를 넘기고, return값을 위해서 사용한다. 또한 heap영역이 동적할당을 위해서 사용된다.

그림의 가장 상단에 code영역이 존재한다. code는 메모리에 위치하기 쉬운 static한 형태이며 프로그램을 동작하기 위해서 변하지 않는다. 그 다음으로는 프로그램이 동작함에 따라 늘어나기도 하고, 줄어들기도 하는 stack, heap영역이 있다. stack, heap영역은 address space양 끝단에 위치해 있다. 그래서 그림에서 보면 heap은 아래로, stack은 위로 메모리의 크기를 늘릴 수 있다. 그러나 stack, heap영역의 위치는 규칙일 뿐이고 address space의 공존(co-exist)이 가능한 multi thread환경에서는 그림과같이 깔끔하게 그 영역을 나누기 어렵다.

우리가 말하는 추상화라는 것은 OS가 실행중인 프로그램에게 부여하는 것이다. 프로그램은 실제로 그림처럼 0KB~16KB에 위치해있지는 않다. 실제로는 임의의 물리적 메모리 영역에 위치해 있다.

그래서 실행중인 프로그램이 특정한 메모리 주소에 위치하고, 아주 큰 address space를 지녔다고 생각하게 하기 때문에 OS가 메모리를 가상화(virtualizing memory)한다고 말한다.

예를들어 Figure 13.2의 프로세스 A가 실제로는 320KB에 위치해 있지만 프로세스 A는 스스로가 0KB에 위치해 있다고 생각한다.

Goal

Virtual Memory(VM)의 주요 목적중 하나는 transparency이다.

OS는 실행중인 프로그램이 볼 수 없는 메모리 가상화를 해야하고, 오히려 프로그램은 마치 자신이 실제로 해당 메모리를 갖고 있는 것 처럼 동작해야한다.

VM의 또 다른 목적은 efficiency이다.

OS는 프로그램이 느려지지 않고, 가상화를 하기위해 너무 많은 메모리를 사용하지 않도록 최대한 효율적으로 가상화를 수행해야 한다.

VM 마지막 목적은 protection이다.

OS는 하나의 프로세스가 다른 프로세스로부터 보호받을 수 있도록 해야한다. 그래서 OS는 프로세스의 isolation을 보장해아한다.

출처 : OSTEP