평범한 컴퓨터공학도의 블로그 :)

CHAPTER 9 - 가상 메모리(Vritual Memory)

CH 9에서는,
- 첫째로, 가상 메모리 시스템의 이점에 대해 알 수 있다.
- 둘째로, Demand Paging과 페이지 교체 정책 등에 대해서 알 수 있다.
- 셋째로, shared memory와 memory-mapping file의 관계에 대해서 알 수 있다.

​- 가상 메모리라는 것은 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.
- 이 기법의 주요 장점 중 하나는 사용자 프로그램이 물리 메모리보다 커져도 된다는 점이다.

9.1 배경

- 8장에서 살펴본 메모리 관리 알고리즘들은 현재 실행되고 있는 코드는 반드시 물리 메모리에 존재해야 한다.
- 이 요구 조건을 만족시키는 방법은 전체 프로세스를 메모리에 올리는 것이다.

- 프로그램 전체가 한꺼번에 메모리에 올라와 있어야 하는 것은 아니라는 것을 아래 예를 보며 알 수 있다.
   (1) 프로그램에는 잘 발생하지 않는 오류 상황을 처리하는 코드가 존재한다. 이 코드는 거의 실행되지 않는다.
   (2) 배열, 리스트, 테이블 등은 필요 이상으로 많은 공간을 점유할 수 있다.
   (3) 프로그램 내의 어떤 옵션이나 기능들은 거의 사용되지 않는다.

- 만약 프로그램을 일부분만 메모리에 올려놓고 실행할 수 있다면, 다음과 같은 장점들이 있다.
   (1) 프로그램이 물리 메모리 크기에 의해 제약받지 않게 된다.
   (2) 각 사용자 프로그램이 더 작은 메모리를 차지하므로, 더 많은 프로그램을 수행할 수 있게 된다.
   (3) 프로그램을 메모리에 올리고, 스왑하는데 필요한 입출력 횟수가 줄어들어서 프로그램이 보다 빨리 실행된다.

- 논리 메모리를 물리 메모리부터 분리시켜주는 것 외에 가상 메모리는 페이지 공유를 통해 파일이나 메모리가
   둘 또는 그 이상의 프로세스들에 의해 공유되는 것을 가능하게 한다. 이는 아래와 같은 장점들이 있다.
   (1) 시스템 라이브러리가 여러 프로세스들에 의해 공유될 수 있다.
   (2) 프로세스들이 메모리를 공유할 수 있다.

9.2 요구 페이징(Demand Paging)

- 프로그램을 디스크에서 메모리로 load 하는 가장 간단한 방법은 프로그램 시작 시에 프로그램의 전부를 물리 메모리에 load 하는 것이다.
- 다른 방법으로는 초기에 필요한 것들만 메모리에 load 하는 요구 페이징(Demand Paging) 전략이 있을 수 있다.
- Demand Paging을 사용하는 가상 메모리에서는 페이지들이 실행 과정에서 필요로 할 때 load 된다.​

- Demand Paging 기법은 프로세스를 실행하고 싶으면 메모리로 읽어들인다 (Swap in)
- 이때, 전체 프로세스를 읽어오지 않고, 필요하지 않은 페이지는 메모리에 load 하지 않는다.
- 이 역할을 게으른 스와퍼(Lazy Swapper) 또는 페이저(Pager)가 수행한다.
- 페이저(Pager)는 프로세스 내의 개별 페이지들을 관리한다.

​

* 기본 개념(Basic Concept)

- Swap-in 시에 Pager는 프로세스가 swap-out 되기 전에 실제로 사용될 페이지들이 어떤 것인지를 추측한다.
- Pager는 프로세스 전체를 swap-in 하는 대신에 실제 필요한 페이지들만 메모리로 읽어온다.
- 사용되지 않을 페이지를 메모리에 가져오지 않음으로써 시간과 메모리 낭비를 줄일 수 있다.

- 이를 위해 8.4.3절에서 언급한 valid/invalid bit를 사용할 수 있다.
- Demand Paging에서 이 비트가 valid 하면, 해당 페이지가 메모리에 있다는 의미이다.
- Demand Paging에서 이 비트가 invalid 하면, 해당 페이지가 유효하지 않거나, 디스크에 존재한다는 의미이다.

- 만약 프로세스가 메모리에 올라와 있지 않은 페이지를 접근하려고 하면, 페이지 부재 트립(Page-fault trap)이 발생한다.

​- 페이지가 적재되고 나면 프로세스는 수행을 계속하는데, 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 페이지 부재(Page Fault)가 발생한다. 이후, 일단 필요한 모든 페이지가 load 되고 나면, 더 이상 fault는 발생하지 않는다.

- 이는 어떤 페이지가 필요해지기 전에는 해당 페이지를 메모리로 적재하지 않는 "pure demand paging"이다.

​- 프로그램들은 한 명령어에서도 여러 page fault를 일으킬 가능성이 있지만, 실제 프로그램들은 어느 한 특정

작은 부분만 집중적으로 참조하는 경향이 있기 때문에, demand paging은 만족할만한 성능을 보인다.

* 요구 페이징의 성능(Performance of Demand Paging)

​- page fault의 확률이 p라고 하면, 실질 접근 시간(Effective access time)은

effective access time = ((1-p) * ma) + (p * page fault time)

- Page fault를 처리하는 시간은 아래 3가지의 큰 요소로 이루어져 있다.
1. 인터럽트의 처리 (Service the page-fault interrupt.)
2. 페이지 읽기 (Read in Page)
3. 프로세스 재시작 (Restart the process.)

 - 실질 접근 시간(Effective access time) 페이지 부재율(Page fault rate)에 비례한다.
- 이에 페이지 부재율(Page fault rate)를 낮추는 것이 성능을 높이는 데 중요하다.

​- Demand Paging의 또 다른 특성 중 하나는 스왑 공간의 관리이다.
- 스왑 공간에서의 디스크 입출력은 일반적인 파일 시스템에서의 입출력보다 빠르다.
- 그 이유는 스왑 공간은 파일 시스템보다 더 큰 블록을 사용하기 때문이고,
   또 스왑공간과 입출력을 할 때는 lookup이나 간접 할당 방법 등은 사용하지 않기 때문이다.

 

---

9.3 쓰기 시 복사(Copy-on-write)

- fork() 이후 exec()를 호출할 자식 프로세스에서는 부모로부터 복사해온 페이지들은 다 쓸모가 없어진다.
- 이에, 부모의 페이지들을 다 복사해오는 대신 쓰기 시 복사(copy-on-write) 방식을 사용할 수 있다.
- 이 방식에서는 자식 프로세스가 시작할 때 부모의 페이지를 당분간 함께 사용하도록 한다.
- 이때, 공유되는 페이지를 쓰기 시 복사(copy-on-write) 페이지라고 표시하며,
"두 프로세스 중 한 프로세스가 공유 중인 페이지에 쓸 때 그 페이지의 복사본이 만들어진다."라는 의미이다.
- 수정되지 않는 페이지들은 자식과 부모 간에 계속 공유 될 수 있는 것이다.

​

- copy-on-write 처리 과정에서 페이지 복사본을 만들 때, 보통 OS는 zero-fill-on-demand 기법을 사용한다.
- zero-fill-on-demand 기법에서는 페이지를 할당할 때 그 내용을 다 0으로 채워 이전 내용을 지우게 된다.

9.4 페이지 교체(Page Replacement)

* 기본적인 페이지 교체

- 페이지 교체(Page Replacement)는 아래와 같이 행해진다.
(1) 만약 빈 frame이 없다면, 현재 사용되고 있지 않은 프레임을 찾아서 비운다.
(2) 해당 프레임의 내용을 swap space에 쓰고, 페이지 테이블을 변화시킨다. (프레임이 비어있음을 나타냄)
(3) 비워진 프레임을 page fault를 발생시킨 프로세스에게 할당하여 사용한다.

- 빈 frame이 없는 경우에 디스크를 두 번 접근해야 하므로 page fault service time이 2배 소요된다.
- 이러한 overhead는 modify bit 또는 dirty bit를 사용해서 감소시킬 수 있다.

- Demand Paging 시스템은 아래 두 가지 중요한 문제를 해결해야 한다.
(1) 프레임 할당 알고리즘(Frame Allocation Algorithm)
(2) 페이지 교체 알고리즘(Page-replacement Algorithm)
- 즉, 각 프로세스에게 얼마나 많은 frame을 할당해야 하는지와 어떤 page를 교체해야 하는지를 결정해야 한다.
- 일반적으로, page-fault rate가 가장 낮은 페이지를 선정하여 교체한다.

​- 이후 설명할 페이지 교체 알고리즘의 설명을 위해 3개의 프레임을 가진 메모리를 가정하고, page reference string은 아래와 같다.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

​

* FIFO 페이지 교체(FIFO Page Replacement)

- 가장 간단한 페이지 교체 알고리즘은 FIFO(First in, First out) 알고리즘이다.
- 메모리에 가장 오래 올라와 있던 page를 바꾸는 방법이다.
- 예시 page reference string에 대해 15개의 page fault를 일으킨다.

- FIFO 알고리즘은 성능이 항상 좋지 않은데, 아래와 같은 경우에 그렇다.

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

- 이 경우, 4개의 frame을 사용하면 page fault가 10번, 3개의 frame을 사용하면 page fault가 9번 일어난다.
- 이러한 결과는 모순적이며, 이를 Belady의 모순(Belady's anomaly)라고 부른다.
- Belady의 모순은 프로세스에게 frame을 더 주었음에도, page fault가 더 증가하는 것을 의미한다.

* 최적 페이지 교체(Optimal Page Replacement)

- 최적 교체 정책(Optimal page replacement algorithm)은 항상 최적의 결과를 가져온다.
- 이 정책은 "앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체"하는 방법이다.
- 이 알고리즘은 할당된 frame 수가 고정된 경우, 가장 낮은 page fault rate를 보장한다.
- 예시 page reference string에 대해 9개의 page fault를 일으킨다.

- 하지만, 실제로 최적 페이지 교체 알고리즘은 구현하기 힘들다.
- 이 방식은 프로세스가 메모리를 앞으로 어떻게 참조할 것인지를 미리 알아야 하기 때문이다.

* LRU 페이지 교체(LRU Page Replacement)

- LRU(Least Recently Used) 페이지 교체 알고리즘은 최근의 과거를 가까운 미래의 근사치로 보는 알고리즘이다.
- LRU는 각 페이지마다 마지막 사용 시간을 유지하고, 페이지 교체 시에 가장 오랫동안 사용되지 않은 페이지를 교체한다.
- 예시 page reference string에 대해 12개의 page fault를 일으킨다.

- LRU 알고리즘은 페이지 교체 알고리즘으로 자주 사용되며, 좋은 알고리즘으로 인정받고 있다.
- 하지만, 이 알고리즘을 구현하기 위해서는 하드웨어의 지원이 필요하며, 아래 두 가지 방법이 가능하다.
   (1) 계수기(Counters) : 각 페이지 항목마다 time-of-use field를 넣는다.
   (2) 스택(stack) : 페이지 번호에 대한 스택을 유지하여, top이 가장 최근, bottom이 가장 오래된 페이지가 된다.

* LRU 근사 페이지 교체(LRU Approximation Page Replacement)

- LRU page replacement를 충분히 지원할 수 있는 하드웨어는 거의 없다.
- 그러나, 많은 시스템들이 참조 비트(Reference bit)의 형태로 어느 정도의 지원을 하려고 한다.
- 처음에 모든 참조 비트는 0으로 초기화 고, 프로세스가 실행되면서 참조되는 페이지의 비트는 1로 바뀐다.

​(1) 부가적 참조 비트 알고리즘(Additional-Reference Bits Algorithm)
- 일정한 간격마다 참조 비트를 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다.
- 각 페이지에 대해 8비트의 참조 비트를 사용하며, 가장 최근 8구간 동안의 해당 페이지의 사용 기록을 담는다.

(2) 2차 기회 알고리즘(Second-Chance Algorithm)
- 2차 기회 알고리즘의 기본은 FIFO 교체 알고리즘이다. 이와 함께 페이지가 선택될 때마다 참조 비트를 확인한다.
- 참조 비트가 0이면 페이지를 교체하고, 1이면 다시 한번 기회를 준 뒤 FIFO로 넘어간다.​

(3) 개선된 2차 기회 알고리즘(Enhanced Second-Chance Algorithm)
(0, 0) : 최근에 사용되지도 변경되지도 않은 경우 (교체하기 가장 좋은 페이지)
(0, 1) : 최근에 사용되지는 않았지만, 변경은 된 경우 ( 교체에 적당하지 않은 페이지)
(1, 0) : 최근에 사용은 되었으나, 변경은 되지 않은 경우 ( 다시 사용될 가능성이 높은 페이지)
(1, 1) : 최근에 사용도 되었고, 변경도 된 경우 (다시 사용될 가능성이 높으며 교체에 적당하지 않은 페이지)

​

* 계수 기반 페이지 교체(Counting-Based Page Replacement)

- 아래 두 가지 기법이 있다.
(1) LFU (Least Frequently Used) : 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
(2) MFU (Most Frequently Used) : 참조 횟수가 가장 큰 페이지를 교체하는 알고리즘

​- 이 두 가지 알고리즘은 구현하는 데 비용이 많이 들고, OPT 알고리즘을 근사하지 못하기 때문에 잘 쓰이지 않는다.

​​

* 페이지 버퍼링 알고리즘(Page-Buffering Algorithm)

- 페이지 교체 알고리즘과 병행하여 여러 가지 버퍼링 기법이 사용될 수 있다.

(1) 시스템이 available frame을 여러 개 가지고 있다가, page fault가 발생하면 교체될 페이지를 기다리지 않고
  새로운 페이지에 먼저 읽어 들이게 하는 방법

(2) available frame pool을 유지하지만, 그 pool 속 각 frame의 원래 임자 페이지가 누구였었는지를 기억하는 방법

9.5 프레임의 할당(Allocation of Frames)

- 여러 개의 프로세스들에 대해 제한된 메모리를 어떻게 할당할 것인가에 대한 문제이다.

​​

* 최소로 할당해야 할 프레임의 수 (Minimum Number of Frames)

- 페이지 공유가 없다면, avilable frame 수보다 더 많이 할당할 수는 없지만, 너무 작게 할당해서는 안 된다.
- 각 프로세스에 할당되는 frame 수가 줄어들면 page fault rate는 증가하고, 프로세스 실행은 늦어지게 된다.

​

* 할당 알고리즘(Allocation of Algorithms)

- 가장 쉬운 할당 방법은 모든 프로세스에게 똑같이 할당해 주는 방법이다.
- 예를 들어 93개의 frame과 5개의 프로세스가 있을 경우, 각 프로세스는 18개의 frame을 할당받는다.
- 나머지 3개의 frame은 free frame buffer pool로 활용한다.
- 이런 방법을 균등 할당(Equal Allocation)이라고 한다.

​- 그러나, 10KB와 132KB의 프로세스가 있을 경우, 균등 할당은 좋은 방법이 아니다.
- 이에, 각 프로세스의 크기 비율에 맞춰 frame을 할당하는 비례 할당 방식(Proportional allocation)을 사용할 수 있다.
- 균등 할당과 비례 할당은 모두 프로세스의 우선순위를 고려하지 않는 방법이다.

​

​* 전역 대 지역할당(Global Veersus Local Allocation)

- 다수의 프로세스가 frame 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 크게 두 가지 범주로 나뉜다.
  (1) 전역 교체(Global Replacement) (2) 지역 교체 (Local Replacement)

​- 전역 교체는 프로세스가 교체할 frame을 다른 프로세스에 속한 frame을 포함한 모든 프레임을 대상으로 찾는 경우이다.
- 지역 교체는 각 프로세스가 자기에게 할당된 frame들 중에서만 교체될 victim을 선택할 수 있는 경우이다.

​- 지역 교체 방법에서는 프로세스에 할당된 프레임의 수는 변하지 않는다.
- 전역 교체 아래에서는 한 프로세스에 할당된 프레임의 수는 바뀔 수 있다.

​- 전역 교체 알고리즘에서의 한 가지 문제점은 한 프로세스가 그 자신의 page fault rate를 조절할 수 없다는 것.
- 한 프로세스의 page fault rate는 그 프로세스가 어떤 프로세스들과 함께 실행되느냐에 영향을 받는다.
- 지역 교체 알고리즘의 경우는 다른 프로세스에게 영향을 받지 않는데, 유일하게 그 프로세스의 페이징 형태에만 영향을 받기 때문​

- 일반적으로 전역 교체가 지역 교체 알고리즘보다 더 좋은 성능을 보이며, 더 자주 쓰인다.

​

* 비균등 메모리 접근(Non-Uniform Memory Access)

- 메모리 접근 시간이 현저하게 차이가 나는 시스템을 모두 비균등 메모리 접근(NUMA)라고 한다.
- 이러한 시스템에서 메모리를 동등하게 대하면, NUMA 구조를 고려한 메모리 할당 알고리즘을
  사용하는 시스템에서보다 CPU가 메모리를 접근할 때 대기 시간이 매우 길어지게 된다.

9.6 스레싱(Thrashing)

- 충분한 frame을 할당받지 못한 프로세스는 page fault가 바로 발생하게 된다.
- 이미 활발하게 사용되는 페이지들로만 이루어져 있으므로, 어떤 페이지가 교체되든 바로 다시 필요해진다.
- 이런 과도한 페이징 작업을 스레싱(Thrashing)이라고 한다.

​

* 스레싱의 원인(Cause of Thrashing)

- 스레싱(Thrashing)은 심각한 성능 저하를 유발한다.
- 운영체제는 CPU 이용률(Utilization)을 검사하게 되는 데, 만약 CPU 이용률이 너무 낮아지면 새로운 프로세스를
  시스템에 더 추가해서 다중 프로그래밍의 정도(Degree)를 높인다.

​- 만약 많은 프로세스들이 실행을 위해 추가의 프레임을 원한다면, 계속해서 page fault가 발생할 것이다.
- 이에 따라, 프로세스들이 paging device를 기다리는 동안 CPU 이용률은 계속해서 떨어진다.
- CPU 스케줄러는 CPU 이용률이 떨어지는 것을 보고, 계속 새로운 프로세스를 추가하려고 할 것이다.
- 계속해서 더 많은 page fault와 더 긴 pageing device waiting time이 생기게 된다.
- 이에 스레싱(Thrashing)이 발생하게 되고, 시스템의 처리율이 상당히 낮아지게 된다.

- 다중 프로그래밍의 정도가 높아짐에 따라, 계속해서 CPU 이용률이 최댓값까지 증가하기는 한다.
- 하지만, 그 뒤 급격하게 감소하며 스레싱(Thrashing)이 이 일어나게 된다.
- 따라서 최고점에서 다중 프로그래밍의 정도를 낮춰야 한다.

​- 스레싱(Thrashing)은 지역 교환 알고리즘이나 우선순위 교환 알고리즘을 사용하면 제한할 수 있다.
- 지역 교환 알고리즘을 사용하면, 한 프로세스가 스레싱을 유발하더라도 다른 프로세스로부터 frame을
  뺏어올 수 없으므로, 다른 프로세스는 스레싱(Thrashing)으로부터 자유로울 수 있다.

- 스레싱(Thrashing) 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 한다.
- 프로세스가 실제로 사용하고 있는 프레임의 수가 몇 개인가를 알아보는 것은 프로세스 실행의 지역성 모델(Locality model)을 기반으로 한다.
- 지역성 모델이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말한다.

- 이러한 방식을 사용하면 파일이 매번 access 될 때마다, system call을 해야 한다.

- 이와 같이 하는 대신에 디스크 입출력을 메모리 참조 방식으로 대신할 수 있다.

- 이러한 방식을 메모리 사상(memory-mapping)이라고 한다.

9.8 커널 메모리의 할당

- 커널 메모리는 보통 사용자 모드 프로세스에게 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당받는다.
  그 이유는 아래 2가지와 같다.

​ (1) 커널은 다양한 크기의 자료 구조를 위해 메모리를 할당받는다. 이 자료구조들은 페이지 크기보다 작은 크기를 갖기도 한다. 때문에
       커널은 메모리를 조심스럽게 사용하여야 하고, 단편화에 의한 낭비를 줄여야 한다.

​ (2) 사용자 모드 프로세스에 할당되는 페이지는 물리 메모리 상에서 꼭 연속적일 필요가 없다.
        하지만, 특정 하드웨어 장치는 물리적으로 연속적인 메모리를 요구할 수 있다.

​

* 버디 시스템

- 버디 시스템은 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당한다.

- 메모리는 이 세그먼트로부터 2의 거듭제곱 단위로 할당된다.

- 예를 들어 11KB가 요청되면, 16-KB 세그먼트가 할당된다.

​

- 버디 시스템의 장점 중 하나는 합병(Coalescing)라고 부르는 과정을 통해 서로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다는 점이다.

- 버디 시스템의 분명한 단점은 2의 거듭제곱 단위로 메모리를 할당받기 때문에, 단편화를 불러올 수 있다.

* 슬랩 할당(Slab Allocation)

- 두 번째 커널 메모리 할당 정책은 슬랩 할당(Slab Allocation)이다.

- 슬랩(Slab)은 하나 이상의 연속된 페이지들로 구성되어 있으며, 캐시(Cache)는 하나 이상의 슬랩들로 구성된다.

9.9 기타 고려 사항

* 프리 페이징(PrePaging)

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 8 - 메모리 관리 전략(Memory Management Strategies)

CH 8에서는,
- 첫째로, Memory Hardware를 구성하는 다양한 방법에 대해 알 수 있다.
- 둘째로, 프로세스에게 Memory를 할당하는 다양한 기법들에 대해 알 수 있다.
- 셋째로, 현대 컴퓨터 시스템의 Paging의 동작 방법에 대해서 알 수 있다.

​- 성능을 향상시키기 위해서는 여러 프로세스들이 주 메모리(Main Memory)를 공유해야 한다.
- 메모리를 관리하는 방법은 단순 hardware 방식에서 paging, segment 방법까지 다양하게 존재한다.

8.1 배경(Background)

- Memory는 각각 주소가 할당된 byte들의 array로 구성된다.

​

* 기본 하드웨어

- Main Memory와 processor 자체에 내장되어 있는 register들은 CPU가 직접 접근할 수 있는 유일 general-purpose storage이다.
- 따라서, 모든 실행되는 instruction과 data들은 CPU가 직접적으로 접근할 수 있는 main memory와 register에 있어야 한다.

​- CPU에 내장되어 있는 register들은 일반적으로 CPU clock의 1 cycle 내에 접근이 가능하다.
- 대부분의 CPU들은 register에 있는 instruction의 decode와 간단한 operation을 이 시간 내에 처리한다.

- memory bus를 통해 전송되는 main memory의 경우, main memory에 대한 접근을 완료하기 위해서는 많은 CPU clock tick cycle이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고, 지연(Stall) 되는 현상이 발생하게 된다.
- 이 문제를 해결하기 위해 CPU와 main memory 사이에 빠른 속도를 가진 Cache를 추가하는 것이다.
- Cache는 보통 빠르게 접근할 수 있도록 하기 위해 CPU 안에 있으며, Memory 접근 속도를 향상시킨다.

​- 시스템이 올바르게 동작하기 위해서는 운영체제 영역을 보호해야 하며, Multi-user System인 경우
  추가적으로 다른 user program이 특정 user program을 접근하는 것을 막아야 한다.
- OS가 이를 행하면 성능이 떨어지기 때문에, hardware가 이를 지원해야 한다.
- base와 limit register를 사용하여 Memory 보호 기법을 제공할 수 있다.

* 주소의 할당

- 프로그램은 원래 binary executable file로 disk에 저장되어 있어야 한다.
- 프로그램이 "Main Memory"로 올라오게 되면, 프로세스가 되어야 한다.
- 디스크에서 Main Memory로 들어오기를 기다리고 있는 프로세스들의 집합은 input queue를 구성한다.

- 보통 single-tasking의 작업 절차는 input queue의 프로세스 중 하나를 선택해서, Memory로 load 한다.
- 이 프로세스가 종료되면, 해당 프로세스가 사용했던 memory space가 available space가 된다.

- 대부분의 시스템은 user 프로세스가 memory 내 어느 부분으로도 올라올 수 있도록 지원한다.
- 대부분의 경우 user pgoram은 아래 그림과 같이 여러 단계를 거쳐 실행되기 때문에 이들 단계를 거치는 동안
  주소들은 여러 가지 다른 표현 방식을 거치게 된다.

- 전통적으로 Memory 주소 공간에서 instruction과 data의 binding은 그 binding이 이루어지는 시점에 따라 다음과 같이 구분된다.

(1) 컴파일 시간(Compile time) 바인딩 : 만일 프로세스가 memory 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 absolute code를 생성할 수 있다.

(2) 적재 시간(Load time) 바인딩 : 만약 프로세스가 memory 내 어디로 올라오게 될지를 compile 시점에 알지 못하면, 컴파일러는 일단 이진 코드를 relocatable code로 만들어야 한다.

(3) 실행 시간(Execution time) 바인딩 : 만약 프로세스가 실행하는 중간에 Memory 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면, "바인딩이 실행 시간까지 허용되었다"라고 한다.

​

* 논리 대 물리 주소 공간(Logical-Versus Physical-Address Space)

- CPU가 생성하는 주소를 논리 주소(Logical Address)라고 하며, memory가 취급하게 되는 주소를 일반적으로
  물리 주소(Physical Address)라고 한다.
- 앞의 binding 분류에서 compile time과 load time의 bind은 논리 주소와 물리 주소가 같다.
- Execution time의 binding의 경우 논리 주소를 가상 주소(Virtual Address)라고 한다.

​- 프로그램의 실행 중에는 가상 주소를 물리 주소로 바꿔주어야 하는데, 이 변환 작업은 hardware인 MMU(Memory Management Unit)에 의해 실행된다.
- base register는 relocation register라고도 불린다.

- 만약, relocation register 값이 14000이라면, 346번지를 access 할 때, 실은 14346 번지를 access 하게 된다.
- 이에, user program은 실제적인 물리 주소(Physical Address)를 절대 알 수 없다.
- 단지 346번지에 대한 pointer를 생성해서 그것에 대한 저장, 연산, 비교 등의 작업을 수행할 수 있다.

* 동적 적재(Dynamic Loading)

- 지금까지 프로세스가 실행되기 위해서는 그 프로세스 전체가 미리 memory에 올라와 있어야 했다.
- 이 경우, 프로세스의 크기는 memory의 크기보다 커서는 안 된다.

​- 이에, memory 공간의 보다 효율적인 이용을 위해서는 동적 적재(Dynamic Loading)이 필요하다.
- 동적 적재(Dyanmic Loading)의 장점은 Routine이 필요한 경우에만 적재되는 것이다.
- 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우에 유용하다.

​

​

* 동적 연결 및 공유 라이브러리(Dynamic Linking & Shared Libaries)

- 동적 연결 라이브러리(Dynamically linked libraries)는 사용자 프로그램이 실행될 때, 해당 프로그램에 연결되는 시스템 라이브러리이다.

- 동적 연결에서는 library를 부르는 곳마다 stub이 생기게 된다.
  (stub : 라이브러리를 어떻게 찾을 것인가에 대해 알려주는 small code piece)

8.2 스와핑(Swapping)

- 프로세스가 실행되기 위해서는 memory에 있어야 하지만, 프로세스는 실행 중에 임시로 예비 저장 장치(backup store)로 내보내어졌다가 실행을 계속하기 위해 다시 Memory로 되돌아올 수 있다.

- 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 memory 크기보다 큰 경우에도 swapping을 사용하면, 동시에 실행하는 것이 가능하여 Multi-programming의 사용도를 높일 수 있다.

​

​* 기본 스와핑(Standard Swapping)

- 기본 스와핑(Standard Swapping)은 Main Memory와 backing store 사이에서 프로세스를 이동시킨다.
- backing store는 일반적으로 fast disk를 사용한다.
- 이 저장 장치의 크기는 모든 사용자의 memory image를 저장할 만큼 커야 하며, 직접 접근이 가능해야 한다.

- 시스템은 실행할 준비가 된 모든 프로세스를 모아 ready queue에 가지고 있어야 하며, CPU 스케줄러는 다음 프로세스를 고를 때 dispatcher를 호출한다.

- dispatcher는 이 queue에 있는 다음 프로세스가 memory에 올라와 있는지를 확인하여, 만약 안 올라와 있다면 디스크에서 불러들어야 한다.

- 이 프로세스를 위한 공간이 memory에 없다면, 공간을 만들기 위해 현재 memory에 올라와 있는 프로세스를 내보낸다.(Swap out)

​- 만약 사용자 프로세스의 크기가 100MB이고, backing store는 50MB/s의 전송률을 가진 디스크라고 하면, backing store로부터 100MB 프로세스를 전송하는 데 걸리는 시간은 100MB/(50MB/s) = 2s이다.

- Swap in과 Swap out을 해야 하므로 총 걸리는 시간은 2s X 2 = 4s이다.

- 한 프로세스가 스왑(swap)하기를 원한다면, 그 프로세스가 완전히 idle 하다는 것을 보장해야 한다.
- 해당 프로세스가 I/O 장치의 어떤 신호를 주고받는 동안이라면, 그동안은 스왑(Swap)해서는 안 된다.

​- 현대 운영체제들은 보통 기본 스와핑(Standard Swapping)을 사용하지 않는다.
- 스와핑 시간이 오래 걸리므로, 실행에 할당되는 시간이 적어지기 때문이다.
- 이에, 변형하여 swapping을 사용하는데 free memory가 threashold보다 부족하게 될 때만 swapping을 수행한다.
- 또 다른 변형 Swapping은 프로세스 전체를 Swapping 하지 않고, 일부만을 Swapping 하여 사용한다.

8.3 연속 메모리 할당(Contiguous Memory Allocation)

- (Main) Memory는 일반적으로 두 개의 부분으로 나뉘는데, 하나는 Memory에 존재하는 운영체제를 위한 것이며, 다른 하나는 User Process를 위한 것이다.

* 메모리 보호(Memory Protection)

- 만일 시스템이 limit register와 relocation register를 가지고 있다면, 프로세스가 자신이 소유하지 않은 memory를 접근할 수 없게 강제할 수 있다.

- CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 context switch의 부분으로 relocation register와 limit register에 정확한 값을 load 한다.

​

​* 메모리 할당(Memory Allocation)

- 가장 간단한 memory allocation 방법은 memory를 똑같이 고정된 크기로 분할(partition) 하는 것이다.
- 각 분할(Partition)마다 한 프로세스를 가지고, 이때 분할의 개수를 Multi-programming degree라고 부른다.

- 가변 분할(Variable-partition) 기법에서 운영체제는 memory의 어떤 부분이 사용되고 있고, 어떤 부분이 사용 되지 않고 있는가를 파악할 수 있는 테이블을 유지한다.
- 초기에 모든 memory 공간은 한 개의 큰 사용 가능한 블록으로 구성되어 있으며, 이때 1개의 hole이 있다고 한다.

​
- 일반적으로 memory에는 다양한 크기의 free space가 여기저기 존재하게 된다.
- 이런 memory에서는 동적 메모리 할당 문제(Dynamic Storage Allocation problem)이 있을 수 있다.
- 이 문제는 free hole의 list로부터 size n의 block을 요구하는 것을 어떻게 만족시킬 것인가에 대한 문제이다.
- 이 문제의 해결책은 대표적으로 아래 3가지가 있다.

(1) 최초 적합(first-fit) : 첫 번째 사용 가능한 가용 공간에 할당한다.

(2) 최적 적합(best-fit) : 사용 가능한 공간들 중에서 가장 작은 공간에 할당한다.

(3) 최악 적합(worst-fit) : 사용 가능한 공간들 중에서 가장 큰 공간에 할당한다.

​

* 단편화(Fragmentation)

- 앞에서 기술한 방법들은 외부 단편화(External fragmentation)가 발생한다.
- 프로세스들이 memory에 load 되고, 제거되는 일이 반복되다 보면, 일부 free space는 사용하지 못할 만큼 작아진다.

- 최초 적합(first-fit)의 경우, 통계적인 분석을 통해 N 개의 block이 할당되었을 때 0.5N 개의 block이
  단편화(Fragmentation) 때문에 손실될 수 있다고 알려져 있으며, 이를 50% 규칙이라고 한다.

​- 18,464B의 free space에서 어느 한 프로세스가 18,462B를 요구하면, 2B의 hole이 남게 된다.
- 이 경우, 2B의 hole을 위해 시스템이 더 큰 부담을 가진다.
- 이에 일반적으로 memory를 작은 공간들로 분할한 뒤에, 이 공간 크기의 정수 배로 만 공간을 할당하는 것이 일반적이다.

- 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있는데, 이 두 공간의 크기 차이를 내부 단편화(Internal fragmentation)이라고 한다.

​- 외부 단편화 문제를 해결하는 방법으로는 압축(Compaction)이 있다.
- 이 방법은 memory의 모든 내용을 한 군데로 몰고, 모든 free space들을 다른 한 군데로 몰아서 큰 block을 만드는 방법이다.

- 세그먼테이션은 프로그래머가 인지하는 memory의 모습을 실제 physical memory의 모습으로 변환해주는 기법을 제공한다.

​

* 기본 방법(Basic Method)

- 프로그래머가 생각하는 프로그램의 모습은 아래 그림과 같이 가변적인 길이를 가지는 모습이다.

- 세그먼테이션(Segmentation)은 위와 같이 프로그래머가 생각하는 모양을 그대로 지원하는 메모리 관리 기법.
- 프로그래머가 생각하는 논리 구조 공간(Logical address space)은 세그먼트들의 집합으로 이루어진다.

​

* 하드웨어(Hardware)

- Segment table의 각 항목은 Segment의 base와 limit를 가지고 있다.
- Segment base는 Segment의 시작 주소를 나타내며, Segment limit은 Segment의 길이를 명시한다.
- 세그먼테이션(Segmentation)의 예시는 아래와 같다.

8.5 페이징(Paging)

- 세그먼테이션(Segmenation)은 프로세스가 load 되는 물리 주소 공간이 연속적이지 않더라도 load를 허용한다.
- 페이징(Paging)은 위의 이점을 가지면서, 단편화에 따른 압축 작업이 필요 없다.
- 또한, 페이징(Paging)은 swap-out 되는 다양한 크기의 세그먼트를 backing storage에 저장해야 하는 문제도 해결한다.

​

* 기본 방법(Basic Method)

- 물리 메모리(Physical Memory)는 프레임(Frame)이라 불리는 같은 크기의 block으로 나누어진다.
- 논리 메모리(Logcial Memory)는 페이지(Page)라 불리는 같은 크기의 block으로 나누어진다.

- 프로세스가 실행될 때, 그것의 페이지는 파일 시스템이나 예비 저장 장치로부터 가용한 main memory frame으로 load 된다.

- CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 변위(d) 두 개의 부분으로 이루어진다.
- 페이지 번호(p)는 페이지 테이블(Page Table)을 access 할 때 사용되며, 페이지 테이블은 main memory에서 각 page가 점유하는 주소를 가지고 있다.

- 아래 그림에서 논리 주소 0은 페이지(page) 0, 변위(offset) 0이다.
- 페이지 테이블을 색인으로 찾아서 페이지(page) 0이 프레임(frame) 5에 있다는 것을 알아낸다.
- 이에 논리 주소 0은 실제 주소 20 ( = (5 X 4) + 0)에 mapping 된다.

- 페이징(Paging) 그 자체는 동적 재배치의 한 형태이다.
- 페이징 기법을 사용하면 외부 단편화는 발생하지 않지만, 내부 단편화는 발생될 수 있다.
- 예를 들어, 페이지 크기가 2048 Byte이고, 프로세스가 72,766 Byte를 요구한다면, 35개의 Page Frame을 할당하고, 1086Byte가 남게 된다.

- 이때, 36개의 Page Frame을 할당하면 36번째 Page Frame은 2048-1086 = 962Byte의 내부 단편화가 발생한다.

- 이에 작은 페이지 크기가 바람직할 수 있지만, 너무 작게 되면 페이지 테이블의 크기가 커지게 될 수 있다.

​- 한 프로세스가 실행되기 위해 도착하면, 그 프로세스의 크기가 페이지 몇 개 분에 해당하는가를 조사한다.
- 각 사용자 페이지(Page)는 한 프레임(Frame) 씩을 필요로 한다.

​- 페이징의 가장 중요한 특징은 memory에 대한 프로그래머의 인식과 실제 내용이 서로 다를 수 있다는 점이다.
- 프로그래머는 memory가 하나의 연속적인 공간으로 이루어졌다고 생각할 수 있다.
- 그러나, 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램들이 존재하고 있다.

- 운영체제는 memory를 관리하기 때문에, 물리 Memory에 Allocation Details에 대해 파악하고 있어야 한다.
- 어느 프레임이 사용 가능 한지, 총 프레임이 몇 개인지에 대한 정보가 프레임 테이블(Frame Table)에 존재한다.
- 운영체제는 모든 프로세스들의 주소들을 실제 주소로 mapping 할 수 있어야 한다.

* 하드웨어 지원(Hardware Support)

- 각 운영체제는 페이지 테이블을 저장하기 위한 고유의 방법을 가지고 있다.
- 몇몇 OS는 각 프로세스마다 하나의 page table을 할당한다.

- 페이지 테이블이 작은 경우에 register들의 집합으로 구현될 수 있다.
- 페이지 테이블의 크기가 큰 경우에는 페이지 테이블을 주 메모리(Main Memory)에 저장하고,
  페이지 테이블 기준 레지스터(PTBR)로 하여금 페이지 테이블을 가리키도록 한다.

- 이 방식은 context switch 시간을 줄일 수 있지만, 메모리 접근 시간을 늘릴 수 있다.
- 이에 TLB(Translation Look-aside Buffers)로 불리는 특수한 소형 hardware cache가 사용된다.

- 접근하려는 memory의 page 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)라고 한다.
- 예를 들어, 80%의 적중률이란 TLB에서 원하는 page 번호를 발견할 횟수가 80%라는 것을 의미한다.

- Main memory를 접근하는데 총 100ns가 소요된다면, 원하는 데이터를 접근하는 데 총 100ns가 걸린다.
- 만약 TLB에서 페이지 번호를 찾지 못하면, 페이지 테이블에 접근(100 ns), 원하는 데이터를 메모리에서 읽어야(100ns) 하므로 (100ns + 100ns = 200ns)의 시간이 소요된다.

- 만약 hit ratio가 80% 라면 실제 접근 시간은 0.80 X 100 + 0.20 X 200 = 120 ns가 된다.
- 만약 hit ratio가 99% 라면, 실제 접근 시간은 0.99 X 100 + 0.01 X 200 = 101 ns가 된다.

​

* 보호(Protection)

- 페이지화된 환경에서 memory 보호는 각 페이지에 붙어 있는 protection bits에 의해 구현된다.
- 각 비트는 이 페이지가 읽기 전용인지 쓰기가 가능한지를 정의할 수 있다.

- 페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트가 더 있다.
- 이 비트가 유효로 설정되면, 관련된 페이지가 프로세스의 합법적인 페이지임을 나타낸다.
- 이 비트가 무효로 설정되면, 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.​

- 몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR)을 제공한다.
- 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR과 비교된다.

* 공유 페이지(Shared Pages)

- 페이징(Paging)의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점이다. (Multi-tasking에서 중요)
- 재진입 가능 코드는 수행하는 동안 절대 변하지 않고, 두 개나 그 이상의 processor들이 동시에 같은 코드를 수행할 수 있다.

8.6 페이지 테이블의 구조(Structure of Page Table)

* 계층적 페이징(Hierarchical Paging)

- 많은 컴퓨터들이 매우 큰 주소 공간을 가지므로, 페이지 테이블의 크기도 맞춰서 커지고 있다.

- 만약 32bit 논리 주소 공간을 가진 시스템에서 페이지의 크기가 4KB라면, 페이지 테이블은 (2^32 /2^12)로
  대략 100만 개의 항목으로 구성될 것이다.

- 이에 커지는 페이지 테이블을 Main memory에 연속적으로 할당하기 보다, 페이지 테이블을 여러 개로 나누어 사용하는 방법이 가능하다.

- 대표적인 방법 중 하나는 2단계 페이징 기법(Two-level paging scheme)로 페이지 테이블 자체를 다시 페이지화하는 것이다.

* 해시 페이지 테이블(Hash Page Tables)

- 주소 공간이 32비트보다 커지면, 가상 주소를 hash로 사용하는 hash page table을 많이 쓴다.

​- 해시 페이지 테이블(Hash Page Table) 알고리즘은 다음과 같이 작동한다.

(1) 가상 주소 공간으로부터 페이지 번호가 오면 그것을 hashing 한다.
(2) 그 값으로부터 hash page table에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.
(3) 일치되면, 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.

* 역 페이지 테이블(Inverted Page Table)

- 운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 이 테이블에 와서 그것을 실제 페이지 주소로 변환해 주어야 한다.
- 이때 테이블이 오름차순으로 정렬되어 있기 때문에, 페이지 테이블이 클 경우 많은 메모리 공간을 점유한다.​

- 이 문제를 해결하는 방법 중 하나는 역 페이지 테이블(Inverted Page Table)을 사용하는 것이다.
- 역 페이지 테이블(Inverted Page Table)에서는 메모리 frame마다 한 항목씩을 할당한다.
- 각 항목은 그 frame에 올라와 있는 페이지 주소, 페이지를 소유하고 있는 프로세스의 ID를 표시한다.

- 역 페이지 테이블을 사용하는 시스템에서 Memory의 공유는 더 어렵다.
- Memory의 공유는 보통 하나의 physical memory에 mapping 되는 여러 개의 가상 주소를 통해 구현된다.
- 이 방법은 모든 physical page에 대해 하나의 가상 주소를 갖게 하는 이 구조에서는 사용할 수 없다.

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 7 - 교착상태(Deadlocks)
CH 7에서는,
- 첫째로, 교착상태(Deadlock)에 대해서 알 수 있다.
- 둘째로, 교착상태(Deadlock)을 예방하거나 회피하는 방법에 대해서 알 수 있다.

​- 대기 중인 프로세스들이 다시는 그 상태를 변경시킬 수 없는 상황을 교착상태(Deadlock)이라고 한다.

7.1 시스템 모델(System Model)

- 시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 수의 resource로 구성된다.​

- 정상적인 작동 모드이면, 프로세스는 다음 순서로만 resource를 사용할 수 있다.
1. 요청(Request) : 프로세스가 resource을 요청한다. 만약 얻지 못하면, resource을 얻을 때까지 대기해야 한다.
2. 사용(Use) : 프로세스가 resource에 대해 작업을 수행할 수 있다.
3. 방출(Release) : 프로세스가 resource를 방출한다.

- 한 프로세스 집합 내의 모든 프로세스가 집합 내의 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면,
  그 프로세스 집합은 교착상태(Deadlock)에 있다.

7.2 교착상태의 특징(Deadlock Charcterization)

- 교착상태(Deadlock)에 있는 프로세스들은 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어서 다른 작업을 시작하는 것도 불가능하다.

​

* 필요조건들(Necessary Conditions)

- 교착상태(Deadlock)은 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생​할 수 있다.

1. 상호 배제(Mutual Exclusion) : 최소한 하나의 resource는 nonsharable mode로 점유되어야 한다.
nonsharable mode에서는 한 번에 하나의 프로세스만이 해당 resource를 사용할 수 있다.

2. 점유하며 대기(Hold-and-wait) : 프로세스는 최소한 하나의 resource를 점유한 채, 현재 다른 프로세스에
의해 점유된 resource를 추가로 얻기 위해 반드시 대기해야 한다.

3. 비선점(No preemption) : resource들을 선점할 수 없어야 한다. 즉, resource가 강제적으로 방출될 수 없고,
점유하고 있는 프로세스가 task를 종료한 후, 그 프로세스에 의해서만 resource가 자발적으로 방출될 수 있다.

4. 순환 대기(Circular wait) : 대기하고 있는 프로세스의 집합 {P(0), P(1), ... , P(n)}에서 P(0)는 P(1)이 점유한
resource를 대기하고, P(1)은 P(2)가 점유한 resource을 대기하고, .... , P(n)은 P(0) 가진 resource을 대기한다.

​

* 자원 할당 그래프(Resource-Allocation Graph)

- deadlock은 시스템 자원 할당 그래프(system resource-allocation graph)로 보다 정확하게 기술될 수 있다.
- P(i) → R(j)는 요청 간선(Request Edge)이고, R(j) → P(i)는 할당 간선(Assignment Edge)이다.

- 자원 할당 그래프에서 사이클(Cycle)을 포함하지 않으면, 시스템 내에 어느 프로세스도 교착상태(Deadlock)이
  아니라는 것을 보일 수 있다.

- 하지만, 만일 각 resource type이 여러 개의 instance를 가지면, cycle이 반드시 교착상태(Deadlock)이 발생했음을
  의미하지는 않는다.

- 요약하자면, 자원 할당 그래프에서 사이클이 없다면 시스템은 교착상태(Deadlock)이 100% 아니다.
- 반면에, 사이클이 있다면 시스템은 교착상태에 있을 확률이 있는 상태이다.

7.3 교착상태 처리 방법(Methods for Handling Deadlocks)

- 원칙적으로 교착상태(Deadlock) 문제를 처리하는데 다음과 같은 세 가지 방법이 있다.

​

(1) 교착상태(Deadlock)을 예방하거나 회피하는 protocol을 사용한다.
- 교착상태(Deadlock) 예방은 앞서 언급한 4가지 조건 중 적어도 하나가 성립하지 않도록 하는 방법이다.
- 교착상태(Deadlock) 회피는 프로세스가 일생 동안 요구하고 사용할 resource에 대한 부가적인 정보를 얻은 뒤
  그 정보를 바탕으로 프로세스를 기다려야 할지 결정할 수 있다.​

(2) 시스템이 교착상태(Deadlock)가 가능하도록 허용한 다음에 회복시키는 방법이 있다.
- 교착상태(Deadlock) 예방이나 회피를 사용하지 않으면, 교착상태가 발생할 수 있다. 이에 교착상태가 진짜로
발생했는지에 대한 여부를 조사하는 알고리즘과 교착상태 복구 알고리즘을 사용할 수 있다.

​
(3) 문제를 무시하고, 교착상태(Deadlock)이 시스템에서 절대 발생하지 않는 척한다.
- 오히려 발생한 교착상태를 해결하는 데 더 비용이 많이 들 수 있으므로, 무시해버릴 수도 있다.
- 이 경우, 계속된 교착상태로 시스템 성능을 저하시킬 가능성도 있기 때문에, 수작업으로 다시 시작할 필요가 있다.

7.4 교착상태 예방(Deadlock Prevention)

- 앞서 언급한 4가지 교착상태 발생 조건들 중에 적어도 하나가 성립하지 않도록 하여 교착상태를 예방할 수 있다.

​

* 상호 배제(Mutual Exclusion)

- 상호 배제는 적어도 하나의 resource는 공유 불가능한 resource 여야 한다는 조건이다. 이에 공유 가능한 resource에 대해서는 교착상태(Deadlock)이 일어나지 않는다. (ex) 읽기-전용 파일

​

* 점유하며 대기(Hold and Wait)

- 프로세스가 resource를 요청할 때, 다른 resource들을 점유하지 않을 것을 보장하면 교착상태 예방이 가능하다.

​- 첫 번째 방법은 프로세스가 전혀 resource를 갖고 있지 않을 때만, resource을 요청하도록 허용하면 된다.

- 위 방법에서 다른 추가 resource를 요청하려면, 현재 자신에게 할당된 resource를 모두 방출해야 한다.

​- 두 번째 방법은 프로세스가 초기에는 DVD drive와 Disk file만 요청하도록 허용하는 방법이다.

​

- 이 두 protocol에는 2가지 단점이 있다.

(1) 많은 resource들이 할당된 후 오랫동안 사용되지 않기 때문에, resource의 이용도가 낮을 수 있다.

(2) 기아(Starvation) 문제가 발생할 수 있다. (특정 프로세스는 무한정 대기하는 상황이 나올 수 있다.)

​

* 비선점(No Preemption)

- 교착상태(Deadlock)을 보장하는 세 번째 조건은 할당된 resource이 선점되지 않아야 한다는 점이다.

- 이 조건을 성립하지 않게 하기 위해, 어떤 resource을 점유하고 있는 프로세스가 즉시 할당할 수 없는

다른 resource을 요청하면, 현재 점유하고 있는 모든 resource들이 선점되게 할 수 있다.

​

* 순환 대기(Circular Wait)

- 교착상태(Deadlock)을 보장하는 네 번째 조건은 순환 대기(Circular wait) 조건이다.

- 이 조건을 성립하지 않게 하기 위해, 모든 resource type에 대해 전체적인 순서를 부여하여,

각 프로세스가 열거된 순서대로, 오름차순으로 resource을 요청하도록 요구하게 할 수 있다.

7.5 교착상태 회피(Deadlock Avoidance)

- 교착상태 예방 방법을 쓰면, 장치의 이용률이 저하되고 시스템 처리율(Throughput)이 감소될 수 있다.

- 교착상태 회피는 resource가 어떻게 될지 추가 정보를 통해서 이루어진다.

​

* 안전 상태(Safe State)

- 시스템 상태가 안전(Safe) 하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 resource를
교착상태(Deadlock)을 발생시키지 않고, 차례로 모두 할당해 줄 수 있다는 것을 의미한다.

- 시스템이 안전 순서(Safe Sequnece)를 찾을 수 있다면 시스템은 안전(safe) 하다고 말할 수 있다.
- 시스템이 안전하다는 것은 교착상태(Deadlock)가 발생하지 않는다는 것을 의미한다.

- 시스템이 안전 순서(Safe Sequence)를 찾을 수 없다면 시스템은 불안전(unsafe) 한 상태에 있다.
- 시스템이 불안전하다는 것은 반드시 교착상태(Deadlock)으로 간다는 것을 의미하지 않는다.
- 대신, 시스템이 불안전하다는 말은 "앞으로 교착상태로 갈 확률이 있다."라는 뜻을 의미한다.​

- 예를 들어, 시스템에는 12개의 tape가 있고 세 개의 프로세스 상황은 아래와 같을 때,

(1) 먼저 tape 3개(12 - (5+2+2)) 중 2개를 P(1)에 할당하여 P(1)을 완료시킨 뒤, tape 4개를 돌려받는다.
(2) 이제 여분의 5개의 tape를 P(0)에 모두 할당하여, P(0)를 완료시키고 tape 10개를 돌려받는다.
(3) P(2)를 완료시킨다.

- 이에 안전 순서(Safe Sequence) <P(1), P(0), P(2)>가 있으므로, 위 시스템은 안전(safe) 하다고 할 수 있다.
- 하지만, 위의 시스템에서 P(2)의 현재 사용량이 3이었다면 시스템은 불안전(unsafe) 한 상태로 변경된다.

- 시스템을 항상 안전(Safe) 한 상태로 유지하게 하여 교착상태(Deadlock)을 회피할 수 있다.
- 하지만, 이 방법은 프로세스가 요청한 resource보다 시스템이 더 많은 resource을 갖고 있더라도 때에 따라
  그 프로세스를 기다리게 할 수 있으므로, resource의 utilization이 더 낮아질 수 있다.

* 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

- 자원 할당 그래프를 그려보면서 cycle이 안 생기게 하여 교착상태(Deadlock)을 회피할 수 있다.
- 요청 간선, 할당 간선과 함께 점선으로 예약 간선을 사용할 수 있다.
- 그래프에서 cycle이 없다면, resource를 할당해도 시스템은 안전 상태가 된다.
- cycle이 발생하게 되면, 시스템은 불안전한 상태가 되므로 교착상태를 회피할 수 없게 된다.

* 은행원 알고리즘(Banker's Algoirthm)

- 자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.
- 은행원 알고리즘(Banker's Algorithm)에서는 자원이 여러 개씩 있더라도 사용할 수 있다.

- 은행원 알고리즘에서는 아래와 같은 자료구조를 사용한다. (n : 프로세스의 수, m : resource의 수)

(1) Available : 각 종류 별로 available 한 resource의 개수를 나타내는 벡터이다. Available[j] = k 이면,
현재 R(j)를 k 개 사용할 수 있다는 뜻이다.

​(2) Max : 각 프로세스가 최대로 필요로 하는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Max[i][j] = k 이면, P(i)가 R(j)를 최대 k 개까지 요청할 수 있음을 나타낸다.

​(3) Allocation : 각 프로세스에게 현재 나가있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Allocation[i][j] = k 이면, 현재 P(i)가 R(j)를 k 개 사용 중임을 나타낸다.

​(4) Need : 각 프로세스가 이후 요청할 수 있는 resource의 개수를 나타내는 행렬로, 크기가 n X m이다.
Need[i][j] = k라면, 이후 R(j)를 k 개까지 더 요청할 수 있음을 나타낸다.

​- Need[i][j] = Max[i][j] - Allocation[i][j]의 관계가 있다.

- 안전성 알고리즘(Safety Algorithm)
(1) Work와 Finish는 각각 크기가 m과 n인 vector이다. Work를 Available 값으로 초기화해주고,
i = 0, 1, ... , n-1에 대하여 Finish[i] = false를 초깃값으로 준다.

(2) 다음 두 조건을 만족하는 i 값을 찾는다.  (a . Finish[i] == false b. Need(i) <= Work)

(3) Work = Work + Allocation(i) Finish[i] = true로 한 뒤에 두 번째 단계로 간다.

(4) 모든 i 값에 대해 Finish[i] = true 이면, 이 시스템은 안전 상태에 있다.

- 자원 요청 알고리즘(Resource-Request Algorithm)
(1) 만약 Request(i) <= Need(i)이면, 두 번째 단계로 가고, 아니면 오류로 처리한다.

(2) 만약 Request(i) <= Available 이면, 세 번째 단계로 가고, 아니면 프로세스는 기다려야 한다.

(3) 마치 시스템이 P(i)에게 resource를 할당해준 것처럼 시스템 상태 정보를 아래처럼 바꾼다.

Available = Available - Request;

Allocation_i = Allocation_i + Request;

Need_i = Need_i - Request;

- 예시 (Example)

​Allocation, Max, Available 배열이 아래와 같을 때,

Need 배열은 아래와 같다. (Max - Allocation = Need)

- 위의 시스템은 안전하다(Safe)라고 할 수 있는데, <P(1), P(3), P(4), P(2), P(0)>의 sequence가 있기 때문이다.

7.6 교착상태 탐지(Deadlock Detection)

- 만약 시스템이 교착상태(Deadlock) 예방이나 회피 알고리즘을 사용하지 않는다면, 교착상태가 발생할 수 있다.
- 이러한 환경에서는 시스템이 아래 알고리즘들을 반드시 지원해야 한다.
  (1) 교착상태(Deadlock)이 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
  (2) 교착상태(Deadlock)으로부터 회복하는 알고리즘

​

* 각 자원 타입이 한 개씩 있는 경우(Single Instance of Each Resource Type)

- 모든 자원들이 한 개의 instance만 있다면, 대기 그래프(wait-for graph)를 이용하여 교착상태(Deadlock) 탐지 알고리즘을 정의할 수 있다.

7.7 교착상태 회복(Deadlock Recovery)

- 또 다른 방법은, 자동적으로 교착상태(Deadlock)로부터 회복(Recovery) 하게 하는 것이다.

- 자동적인 회복을 위해 프로세스를 종료시키는 것과 자원을 선점하는 것 두 가지 종류가 있을 수 있다.

​

* 프로세스 종료(Process Termination)

- 종료된 프로세스로부터 할당되었던 모든 자원을 회수하게 한다.

(1) 교착상태(Deadlock) 프로세스를 모두 중지 : 이 방법은 확실하게 교착상태(Deadlock)의 cycle을 깨트리지만, 관련된 모든 프로세스를 중지시키므로 비용이 커진다.

(2) 교착상태(Deadlock)가 제거될 때까지 한 프로세스 씩 중지 : 각 프로세스가 중지될 때마다, 탐지 알고리즘을 통해 교착상태(Deadlock)이 존재하는지를 확인해야 하므로, 상당한 overhead를 유발할 수 있다.

​
- 어떤 프로세스를 먼저 중지시켜야 하는가는 아래와 같은 기준들이 있을 수 있다.
(1) 프로세스의 우선순위가 어떠한지
(2) 지금까지 프로세스가 수행된 시간과 종료하는 데까지 더 필요한 시간
(3) 프로세스가 종료하기 위해 필요한 추가 resource의 수
(4) 프로세스가 사용한 resource type과 수

​

* 자원 선점(Resource Preemption)

- 자원 선점(Resource Preemption)을 이용하여 교착상태(Deadlock)을 제거하려면, 교착상태가 깨어질 때까지 프로세스로부터 Resource을 계속적으로 선점해 이들을 다른 프로세스에게 주어야 한다.​

- 교착상태(Deadlock)을 해결하기 위해 선점이 필요하다면, 다음의 세 가지 사항을 고려해야 한다.
(1) 희생자 선택(Selection of a victim) : 어느 resource와 process가 선점될 것인가?
(2) 후퇴(Rollback) : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
(3) 기아 상태(Starvation) : 기아(Starvation) 상태가 발생하지 않는다는 것을 어떻게 보장해야 하는가?

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 6 - CPU 스케줄링(CPU Scheduling)

CH 6에서는,
- 첫째로, Multi-Programmed OS의 기반인 CPU 스케줄링에 대해서 알 수 있다.
- 둘째로, 다양한 CPU 스케줄링 알고리즘에 대해서 알 수 있다.
- 셋째로, CPU 스케줄링 알고리즘을 선택하는 평가 기준에 대해서 알 수 있다.
​
- 운영체제는 CPU를 프로세스들 간에 교환함으로써, 컴퓨터를 more productive으로 만든다.
- 운영체제는 사실 process가 아니라 kernel-level의 thread를 스케줄하는 것이다.
- "proess scheduling"와 "Thread scheduling"라는 용어는 서로 interchangeably 사용된다.

6.1 기본 개념(Basic Concepts)

- single-processor system에서는 한 순간에 오직 하나의 프로세스만이 실행될 수 있다.
- 나머지 프로세스들은 CPU가 free 상태가 되어, 다시 스케줄 될 수 있을 때까지 기다려야 한다.

- Multi-programming의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 갖게 하는 것이다.
- 이 방식에서, 어느 한 순간에 다수의 프로세스들을 메모리 내에 유지한다.
- 이후에 어떤 프로세스가 대기해야 하는 경우, 운영체제는 CPU를 해당 프로세스로부터 회수해서 다른 프로세스에 할당한다.

* CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)

- 프로세스 실행은 CPU 실행(CPU Execution)과 입출력 대기(I/O wait)로 구성된다.
- 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 하며, 프로세스 실행은 CPU burst로 시작된다.
- (CPU burst, I/O burst, CPU burst, I/O burst , ...) 순으로 순차적으로 burst가 발생하게 된다.
- 마지막 CPU burst는 I/O burst가 뒤따르는 대신, 실행을 종료하기 위한 system request와 함께 끝난다.

- I/O-bound 프로그램(I/O 지향 프로그램)은 짧은 CPU burst를 가질 것이다.
- CPU-bound 프로그램(CPU 지향 프로그램)은 긴 CPU burst를 가질 것이다.

* CPU 스케줄러(CPU Scheduler)

- CPU가 idle 일 때마다, 운영체제는 ready queue에 있는 프로세스들 중에서 하나를 선택해 실행해야 한다.
- 선택은 단기 스케줄러(Short-term Scheduler, CPU scheduler)에 의해 수행된다.
- 스케줄러는 실행 준비가 되어있는 메모리 내의 프로세스들 중에서 하나를 선택하여 CPU를 할당한다.

* 선점 스케줄링(Preemptive Scheduling)

- CPU 스케줄링 결정은 아래 4가지 상황 아래에서 발생할 수 있다.
(1) 한 프로세스가 running state에서 waiting state로 전환될 때 (wait를 호출할 때)
(2) 프로세스가 running state에서 ready state로 전환될 때 (interrupt가 발생할 때)
(3) 프로세스가 waiting state에서 ready state로 전환될 때 (completion of I/O)
(4) 프로세스가 종료될 때 (When a process terminates)

​- (1)과 (4)의 경우에서만 스케줄링이 발생하면 비선점(non-preemptive) 또는 협조적(Cooperative)하다.
- 비선점(non-preemptive) 스케줄링에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지 또는
   waiting state로 전환해 CPU를 방출할 때까지 CPU를 점유한다.

​- (2)와 (3)의 경우가 함께 있게 되면, 스케줄링이 선점(preemptive)형 일 수 있는데, 선점 스케줄링(Preemptive
scheduling)은 data가 다수의 프로세스에 의해 공유될 때 race condition을 발생시킬 수 있다.

* 디스패처(Dispatcher)
- CPU 스케줄링 기능에 포함된 요소들 중 하나는 디스패처(dispatcher)이다.
- 디스패처(dispatcher)는 CPU의 control을 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다.
- 디스패처(dispatcher)는 아래와 같은 작업을 수행할 수 있다.
    (1) 문맥을 교환하는 일(Switching context)
    (2) 사용자 모드로 전환하는 일(Switching to user mode)
    (3) 프로그램을 다시 시작하기 위해 user program을 적절한 위치로 이동시키는 일
    (Jumping to the proper location in the user program to restart that program)

​- 디스패처(dispatcher)는 모든 프로세스의 switching 시에 호출되므로, 가능한 최고로 빨리 수행되어야 한다.
- 디스패처(dispatcher)가 하나의 프로세스를 정지하고, 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을
   디스패치 지연시간(dispatch latency)라고 한다.

6.2 스케줄링 기준(Scheduling Criteria)

(1) CPU 이용률(Utilization)
  - 가능한 한 CPU를 최대한 바쁘게 유지시키는 것을 원할 수 있다.
  - CPU 이용률(utilization)은 이론적으로 0에서 100%까지 이를 수 있다.
  - 실제 시스템 상에서는 40%(부하가 적은 시스템) ~ 90%(부하가 큰 시스템)까지의 범위를 가져야 한다.

​

(2) 처리량(Throughput)
  - 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 처리량(Throughput)이라고 한다.
  - 처리시간이 긴 프로세스의 경우, 처리량은 시간당 한 프로세스가 될 수 있다.
  - 처리시간이 짧은 프로세스의 경우, 처리량은 초당 10개의 프로세스가 될 수 있다.

(3) 총처리 시간(Turnaround time)
  - 특정 프로세스의 입장에서 보면, 중요한 기준은 그 프로세스를 실행하는 데 소요되는 시간이다.
  - 프로세스의 submission과 completion 사이의 interval을 총 처리 시간(Turnaround time)이라고 한다.
  - 총처리 시간은 메모리에 들어가기 위해 기다리며 소비한 시간, ready queue에서 대기한 시간, CPU에서 실행한 시간,
    I/O 시간을 합한 시간이다.

​

(4) 대기 시간(Waiting time)
  - CPU 스케줄링 알고리즘은 프로세스가 ready queue에서 대기하는 시간의 양에만 영향을 준다.
  - 대기 시간(Waiting time)은 ready queue에서 대기하면서 보낸 시간의 합이다.

​

(5) 응답 시간(Response time)
  - 응답시간(Reponse time)이란, 한 request를 제출한 후, 첫 번째 response가 나올 때까지의 시간이다.
  - 응답시간의 기준은 응답이 시작되는 데까지 걸리는 시간으로, 응답이 출력하는 데까지 걸리는 시간이 아니다.

- CPU utilization과 throughput을 최대화하는 것이 바람직하다.
- 총 처리시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

6.3 스케줄링 알고리즘(Scheduling Algoirthm)

* 선입 선처리 스케줄링(First-Come, First Served Scheduiling, FCFS)

- 가장 간단한 CPU 스케줄링 알고리즘은 선입 선처리(FCFS) 스케줄링 알고리즘이다.
- 선입선처리(FCFS) 스케줄링 알고리즘은 비선점형(non-preemptive) 알고리즘이다.
- CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 방식이다.
- 이 방법은 FIFO(First in, First out) Queue로 쉽게 관리, 구현할 수 있다.
- 이 방법의 단점은, 평균 대기 시간이 때에 따라 매우 길어질 수 있다는 점이다.
- 만약 프로세스 3개가 아래와 같을 때,

- 프로세스가 P(1), P(2), P(3)로 도착할 때, P(1)의 대기시간은 0ms이며, P(2)는 24ms, P(3)는 27ms이다.
  이에 평균 대기 시간은 (0 + 24 + 27) / 3 = 17ms이다.

- 프로세스가 P(2), P(3), P(1)로 도착할 때, P(1)의 대기시간은 6ms이며, P(2)는 0ms, P(3)는 3ms이다.
  이에 평균 대기 시간은 (6 + 0 + 3) / 3 = 3ms이다.

- 이에, FCFS 방법을 사용했을 때, 평균 대기 시간은 일반적으로 최소가 아니며, 프로세스 CPU burst time이
크게 변할 경우에는 평균 대기 시간도 크게 변할 수 있다.

​- 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위효과(convoy effect)라고 한다.
- 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU와 장치 이용률이 저하되는 결과를 발생시킨다.

* 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)

- 최단 작업 우선 스케줄링(SJF) 알고리즘은 각 프로세스에 다음 CPU burst 길이를 연관시킨다.
- CPU가 available해지면, 가장 작은 next CPU burst를 가진 프로세스에게 CPU를 할당한다.
- 만약 프로세스 4개가 아래와 같을 때,

- SJF 알고리즘을 적용하면, P(4), P(1), P(3), P(2) 순으로 스케줄링을 하게 된다.
- P(1)의 대기시간은 3ms, P(2)의 대기시간은 16ms, P(3)의 대기시간은 9ms, P(4)의 대기시간은 0ms이다.
- 이에 평균 대기 시간은 (3 + 16 + 9 + 0) / 4 = 7ms이다.

- SJF 방식을 사용하면, 최소의 평균 시간을 가지게 할 수 있다.
- 하지만, 실제적으로 SJF를 구현할 때의 어려운 점은 다음 CPU 요청의 길이를 파악해야 한다는 점이다.​

- SJF 스케줄링은 long-term scheduling에 자주 사용된다.
- short-term scheduling는 다음 CPU burst의 길이를 알 수 있는 방법이 없기 때문에, short-term scheduling
  에는 사용할 수 없다.

- SJF 알고리즘은 선점형(preemptive)이거나 비선점형(Non-preemptive) 일 수 있다.
- 선점형 SJF 알고리즘은 최소 잔여 시간 우선(Shortest remaining time first) 스케줄링이라고도 불린다.

- 만약 프로세스 4개가 아래와 같을 때,

- 선점형 SJF 알고리즘의 평균 대기 시간은 ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 26/4 = 6.5 ms이다.

* 우선순위 스케줄링(Priority Scheduling)

- SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다.
- 우선순위 스케줄링 알고리즘에서 CPU는 가장 높은 우선순위를 가진 프로세스에게 할당된다.
- 우선순위가 같은 프로세스들은 FCFS 순서로 스케줄 된다.

​- 만약 프로세스 5개가 아래와 같을 때,

- 우선순위 스케줄링을 이용하면, 아래와 같이 스케줄 된다. (평균 대기시간은 8.2ms이다.)

- 우선순위는 내부적인 요인과 외부적인 요인으로 결정된다.
- 내부적으로는 시간제한, 메모리 요구 비율 등이 있으며, 외부적으로 프로세스의 중요성, 비용 등이 있다.​

- 우선순위 스케줄링은 선점형이거나 비선점형일 수 있다.
- 선점형 방식에서는 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스의 우선순위보다 높다면, CPU를 선점한다.

- 우선순위 스케줄링 알고리즘의 주요 문제는 indefinite blocking 또는 Starvation 문제이다.
- 우선순위 스케줄링 알고리즘을 사용할 경우, 낮은 우선순위 프로세스들이 CPU를 무한히 대기할 수도 있다.
- 이 문제를 해결하는 방법 중 하나는 노화(Aging)이다.
- 노화(Aging)는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 높인다.

* 라운드 로빈 스케줄링(Round-Robin Scheduling)

- 라운드 로빈(Round-robin) 스케줄링은 특별히 time-sharing system을 위해 설계되었다.
- 이 방식에서는 시간 조각(Time Slice)라고 하는 작은 단위의 시간을 정의하여 사용한다.
- ready queue는 circular queue로 동작하며, CPU 스케줄러는 ready queue를 돌면서 한 번에 한 프로세스에게 한 번의 시간 조각(Time slice) 동안 CPU를 할당한다.

​- 프로세스의 CPU burst가 한 번의 Time Slice보다 작은 경우, 실행이 끝나면 CPU를 자발적으로 방출한다.
- 프로세스의 CPU burst가 한 번의 Time Slice보다 큰 경우, Context Switch가 일어나게 되고, 실행하던 프로세스는 ready queue의 꼬리(Tail)에 넣어지게 된다.

​- Round-robin 스케줄링 방식은 최적의 결과를 가져오지 않는다.
- 만약 프로세스 3개가 아래와 같을 때,

평균 대기 시간은 17/3 = 5.66ms이다.

- Round Robin 알고리즘의 성능은 Time Slice의 크기에 매우 많은 영향을 받는다.
- Time Slice이 매우 클 때의 Round Robin 방식은 FCFS와 같아지게 된다.
- Time Slice이 매우 작을 때의 Round Robin 방식은 매우 많은 Context Switch를 발생시킨다.
- 보통 Time slice의 크기가 Context Switch 시간에 비해 더 커야 한다.
- 하지만 Time Slice의 크기가 너무 크게 되면 FCFS 방식이 되므로, CPU burst의 80%는 시간 할당량보다 짧아야 한다.

* 다단계 큐 스케줄링(Multilevel Queue Scheduling)

- 다단계 큐 스케줄링 알고리즘은 ready queue를 다수의 별도의 queue로 분류한다.
- 각 queue들은 자신의 스케줄링 알고리즘을 가지고 있을 수 있다.
- 예를 들어, foreground는 라운드 로빈 알고리즘으로 background는 FCFS에 의해 스케줄 될 수 있다.

* 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

- 다단계 큐 스케줄링 알고리즘은 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.
- 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

6.4 스레드 스케줄링(Thread Scheduling)

- 운영체제에서 스케줄링 되는 대상은 kernel-level threads이다.

* 경쟁 범위(Contention Scope)

- 동일한 프로세스에 속한 thread들 사이에서 CPU를 경쟁하면, 프로세스-경쟁-범위(PCS)이다. 
  PCS : Process-Contention Scope

​- CPU 상에서 어느 kernel thread를 스케줄 할 것인지를 결정하기 위해서 kernel은
  시스템-경쟁 범위(System-contention scope, SCS)를 사용한다.

6.5 다중 처리기 스케줄링(Multiple-Processor Scheduling)

- 위의 방법들은 single-processor를 가진 시스템에서 CPU를 스케줄 하는 방법에 대한 내용이다.
- 만일 여러 개의 CPU가 사용 가능하다면, 부하 공유(load sharing)이 가능하지만, 스케줄링에 어려움이 있다.

​
* 다중 처리기 스케줄링에 대한 접근 방법

- 비대칭 다중 처리기(Asymmetric multiprocessing)은 단지 한 processor만 시스템 자료구조를 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다.
- 대칭 다중 처리기(Symmetric multiprocessing)의 경우, 각 processor가 독자적으로 스케줄링을 한다.

​​

* 처리기 친화성(Processor Affinity)

- 대부분의 SMP 시스템은 한 processsor에서 다른 processor의 이주를 피하고, 같은 processor에서 프로세스를 실행하고자 한다.
- 이 현상을 처리기 친화성(Processor Affinity)라고 하며, 프로세스가 현재 실행 중인 processor에 친화성을 가진다는 것을 의미한다.

​- 운영체제가 동일한 processor에서 프로세스를 실행시키려고 노력하는 정책을 가지고 있지만 보장하지 않을 때,
   연성 친화성(soft affinity)를 가진다고 한다. ( 이에 다른 processor로의 이주가 가능하다.)

- 몇몇 시스템은 강성 친화성(hard affinity)를 지원하는 system call을 제공한다. 이 system call을 사용하여 프로세스는 자신이 실행될 processor 집합을 명시할 수 있다.

​- 시스템의 main memory의 구조가 processor affinity issue에 영향을 줄 수 있다.
- 아래 그림은 NUMA(Non-uniform Memory Access) 특성을 가지는 구조를 묘사하고 있다.

* 부하 균등화(Load Balancing)

- SMP 시스템에서 processor이 하나 이상이라는 것을 최대한 활용하려면, load를 모든 processor에
   균등하게 배분하는 것이 매우 중요하다.
- load balancing은 SMP 시스템의 모든 processor 사이에 load가 고르게 배분되도록 시도한다.

​- load balancing에는 push migration과 pull migration이 있다.
- push migration은 과부하인 processor에서 쉬고 있는 processor로 process를 이동시킨다.
- pull migration은 쉬고 있는 processor이 바쁜 processor로 process를 pull 할 때 일어난다.

* 다중 코어 프로세서(Multicore Processor)

- 하나의 물리적인 chip 안에 여러 개의 processor core를 장착하는 구조를 multicore processor라고 한다.
- 이 방식을 사용하는 SMP 시스템은 기존 방식에 비해 속도가 빠르고 작은 전력을 소모한다.

​6.6 실시간 CPU 스케줄링(Real-time CPU Scheduling)

- dispatch latency는 스케줄링 dispatch가 하나의 프로세스를 블록 시키고 다른 프로세스를 시작하게 하는 데 걸리는 시간임.

* 우선순위 기반의 스케줄링(Priority-Based Scheduling)

- real-time 운영체제에서 가장 중요한 기능은 real-time 프로세스가 CPU를 필요로 할 때, 바로 응답해주는 것.
- 따라서, real-time 운영체제의 스케줄러는 선점을 이용한 우선순위 기반의 알고리즘을 제공해야 한다.

* Rate-Monotonic 스케줄링 (task의 길이가 짧은 process에게 우선순위 할당)

- Rate-Monothic 스케줄링 알고리즘은 선점 가능한 정적 우선순위 정책을 이용하여 주기 task를 스케줄 한다.
- 낮은 우선순위의 프로세스가 실행 중에 있고, 높은 우선순위의 프로세스가 실행 준비가 되면, 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 선점한다.
- 프로세스 P(1)과 P(2)의 주기와 수행 시간이 아래와 같을 때,

- P(2)가 P(1)보다 우선순위가 높게 되면, 스케줄러는 P(1)의 마감시간을 지키지 못하게 된다. (50 < 55)

- Rate-monotonic 스케줄링을 사용하면, P(1)의 주기가 P(2)의 주기보다 짧기 때문에, P(1)의 우선순위가 P(2)의 우선순위보다 높다.

- Rate-monotonic 스케줄링 기법은 최적이기는 하지만, 많은 제약을 가지고 있다.
- CPU 이용률은 한계가 있기 때문에 CPU 자원을 최대화해서 사용하는 것은 불가능하다.
- 시스템에 한 개의 프로세스만 존재할 때, CPU 이용률은 100%이지만, 최소 69%까지 떨어지게 된다.

* Earliest-Deadline-First 스케줄링

- Earliest-Deadline-First(EDF) 스케줄링 기법은 deadline에 따라서 우선순위를 동적으로 부여한다.
- deadline이 빠를수록 우선순위는 높아지고, 늦을수록 낮아진다.
- EDF 정책에서는 프로세스가 실행 가능하게 되면 자신의 deadline을 시스템에 알려야 한다.
- 우선순위는 새로 실행 가능하게 된 프로세스의 deadline에 맞춰서 다시 조정된다.
- 이 점이 우선순위가 고정되어 있는 rate-monotonic 스케줄링 기법과 다른 점이다.
- 프로세스 P(1)과 P(2)의 주기와 수행 시간이 아래와 같을 때,

- 맨 처음, P(1)의 deadline이 P(2)보다 짧으므로 더 높은 우선순위를 가지게 되어 실행을 시작하게 된다.
  그 뒤, P(1)의 실행이 끝나고 P(2)의 수행이 계속된다. (P(2)의 deadline이 P(1) 보다 짧으므로)

- EDF 알고리즘은 프로세스들이 주기적일 필요도 없고 CPU 할당 시간도 상숫값으로 정해질 필요가 없다.
- 그러나, 프로세스가 실행 가능해질 때, 자신의 deadline을 스케줄러에게 알려주어야 한다.
- 이론적으로 CPU 이용률이 100%가 될 수 있지만, 실제로는 프로세스 사이의 context switch 비용 등에 의해 100%의 CPU 이용률은 불가능하다.

* 일정 비율의 몫 스케줄링(Proportionate Share Scheduling)

- 일정 비율의 몫(Proportionate share) 스케줄러는 모든 application에게 T 개의 시간 몫을 할당하여 동작한다.
- 예를 들어, T = 100인 시간 몫이 있다고 할 때, 3개의 프로세스 A, B, C에게 각각 50, 15, 20을 할당하였다.
- 이 경우, A는 모든 processor 시간의 50%, B는 15%, C는 20%를 할당받는 것이다.

6.7 운영체제 사례들

- Linux, Windows, Solaris에서 스케줄링이 일어날 수 있다.
- Windows와 Solaris의 경우, kernel thread 스케줄링에 대해 설명하고, Linux의 경우 task 스케줄링에 대해 설명한다.

6.8 알고리즘의 평가(Algorithm Evaluation)

* 결정론적 모델링(Deterministic Modeling)

- 평가 방법의 한 중요한 부류로 분석적 평가(Analytic evaluation)가 있다.
- 분석적 평가의 한 가지 유형은 결정론적 모델링(Deterministic Modeling)이다.
- 만약 아래와 같은 작업 프로세스들이 있다고 할 때,

선입 선처리(FCFS) 알고리즘의 경우, 평균 대기시간은 (0 + 10 + 39 + 42 + 49) / 5 = 28 ms이다.

비선점 SJF 알고리즘의 경우, 평균 대기시간은 (10 + 32 + 0 + 3 + 20) / 5 = 13 ms이다.

라운드 로빈(RR) 알고리즘의 경우, 평균 대기시간은 (0 + 32 + 20 + 23 + 40) / 5 = 23 ms이다.

- 이에, 위의 경우에는 SJF > RR > FCFS 순으로 평균 대기시간이 적게 든다는 것을 비교할 수 있다.

* 큐잉 모델(Queueing Models)

- 결정론적 모델을 사용할 수 있는 정적인 집합이 존재하는 경우가 드물기 때문에, 결정할 수 있는

CPU와 입출력의 분포를 사용하는 방법이다.

​

* 모의실험(Simulation)

- 스케줄링 알고리즘을 더욱 정확하게 평가하기 위해 모의실험(Simulation)을 사용할 수 있다.

- 모의실험을 하는 것은 컴퓨터 시스템의 모델을 프로그래밍 하는 것을 포함한다.

​

* 구현(Implementation)

- 스케줄링 알고리즘을 완벽히 정확하게 평가하는 유일한 방법은 실제 코드로 작성해 운영체제에 넣고

실행해 보는 것이다.

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 5 - 프로세스 동기화(Process Synchronization)

CH 5에서는,
- 첫째로, 임계 구역 문제(Critical-section problem)와 해결책에 대해서 알 수 있다.
- 둘째로, 여러 전통적인 프로세스 동기화(Process Synchronization) 문제에 대해서 알 수 있다.
- 셋째로, 프로세스 동기화(Process Synchronization)를 해결하기 위해 사용되는 여러 도구들을 알 수 있다.

5.1 배경(Background)

- n 개의 프로세스 {P(0), P(1), ... , P(n-1)}가 있는 시스템에서 각 프로세스는 임계 구역 (Critical Section)이라고 
  부르는 코드를 포함하고 있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하는 등의 작업을 수행한다.

​- 이 시스템의 중요한 특징은 "한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역 안에서 실행할 수 없다"라는 점이다.

- 임계 구역 문제(Critical-section problem)은 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것.

- 각 프로세스는 자신의 임계 구역으로 진입하기 위해 허가를 요청해야 하는데, 이러한 요청을 구현하는 코드 부분을
  진입 구역(Entry Section)이라고 하며, 임계 구역 뒤에는 퇴출 구역(Exit Section)이 있을 수 있다.

- 코드의 나머지 부분은 나머지 구역(Remainder Section)이라고 한다.

- Critical Section Problem에 대한 해결안은 아래 세 가지 요구 조건을 충족시켜야 한다.

1. 상호 배제(Mutual Exclusion) : 프로세스 P가 자신의 임계 구역(Critical Section)에서 실행된다면,  다른 프로세스들은 그들 자신의 임계 구역(Critical Section)에서 실행될 수 없다.

2. 진행(Progress) : 자신의 임계 구역(Critical Section)에서 실행되는 프로세스가 없는 상황에서 그들 자신의 임계 구역으로 진입하려는 프로세스들이 있다면, 나머지 구역(Remainder section)에서 실행 중이지 않은 프로세스들만 다음에 누가 해당 임계 구역(Critical Section)으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무제한으로 연기될 수 없다.

3. 한정된 대기(Bounded Waiting) : 프로세스가 자신의 임계 구역(Critical Section)에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그 들 자신의 임계 구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.

​- 임의의 한순간에 많은 Kernel-mode process들이 운영체제 안에서 사용될 수 있으며, 그 결과 운영체제를 구현하는 코드(Kernel Code)는 Race Condition이 발생하기 쉽다.
- 예를 들어, 메모리 할당을 관리하는 자료구조, 프로세스 리스트를 관리하는 자료구조 등에서 race condition이 많이 발생할 수 있다.

​
- 운영체제 내에서 임계 구역을 다루기 위해 선점형 커널(preemptive kernels)과 비선점형 커널(non-preemptive kernels)의 두 가지 일반적인 접근법이 사용된다.

- 선점형 커널(preemptive kernels)는 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
- 비선점형 커널(nonpreemptive kernels)는 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고

- 커널 모드 프로세스는 커널을 빠져나갈 때까지, 봉쇄될 때까지, 자발적으로 CPU의 control을 돌려줄 때까지 계속 수행된다.
- 비선점형 커널에서는 경쟁 조건에 대해 고려를 하지 않아도 되지만, 선점형 커널에서는 경쟁 조건이 발생하지 않도록 하기 위해 신중한 설계가 필요하다.
- 선점형 커널은 real-time process가 현재 kernel을 점유하고 있는 process를 선점할 수 있기 때문에 real-time programming에 더 적합하다.

5.3 피터슨의 해결안(Peterson's Solution)

- 임계 구역 문제를 해결하는 고전적인 소프트웨어 기반 해결책으로 Peterson's Solution이 있다.
- 현대 컴퓨터 구조가 load, store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson's solution이
  항상 올바르게 작동한다고 보장할 수는 없다.

​- Peterson's Solution은 임계 구역(Critical Section)과 나머지 구역(Remainder Section)을 번갈아 가며 실행하는
  두 개의 프로세스로 한정된다. ( P(0)와 P(1)으로 한정하여 설명)

- Perterson's solution은 두 프로세스가 아래 두 개의 데이터 항목을 공유하도록 하여 임계 구역 문제를 해결한다.

int turn;
boolean flag[2];

- 변수 turn은 임계 구역으로 진입할 순번을 나타낸다.
- (turn == i)이면, 프로세스 P(i)가 임계 구역에서 실행될 수 있음을 나타낸다.

​- flag 배열은 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 의미한다.
- flag[i]가 참이라면, P(i)가 임계 구역으로 진입할 준비가 되었다는 것을 나타낸다.

​- 임계 구역으로 진입하기 위해서는 P(i)는 먼저, flag[i]를 True로 만들고 turn을 j로 지정한다.
- 이렇게 함으로써, 프로세스 j가 임계 구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.
- turn의 값이 궁극적으로 어떤 프로세스가 먼저 임계 구역으로 진입할 것인가를 결정한다.

- Peterson's solution에서 P(i)의 구조는 아래와 같다.

do {
  flag[i] = TRUE;
  turn = j;

  while(flag[j] && turn == j);

  [CRITICAL SECTION]

  flag[i] = FALSE;

  [REMAINDER SECTION]

} while (TRUE);

​

- Peterson's solution이 임계 구역 문제를 해결한다는 것을 보장하기 위해 3가지 조건을 만족해야 한다.

​1. 상호 배제(Mutual Exclusion)이 제대로 지켜진다는 조건
(1) 이 조건을 만족하기 위해서는, 각 P(i)가 임계 구역(Critical Section)에 들어가기 위해서는
     반드시 flag[i] == false거나 turn == i이어야 한다.

(2) 만약 flag[0]과 flag[1]의 값이 모두 true라고 하더라도, turn의 값에 따라 임계 구역에 한 프로세스만
    진입 가능하므로, 위 코드의 while 문을 두 프로세스가 모두 통과할 수 없다.

(3) 정해진 process가 임계 구역에 있을 동안 flag와 turn 값이 변경되지 않으므로, 상호 배제 조건은 지켜진다.

2. 진행(Progress)에 대한 요구 조건을 만족한다는 조건

3. 대기 시간이 한없이 길어지지 않는다는 조건 (Bounded Waiting)
(1) 2와 3을 증명하기 위해 Peterson's solution에서 임계 구역을 보호하는 방법은 while 문을 이용하는 것이라는 점에 주목해야 한다.

(2) P(j)가 임계 구역에 들어갈 준비가 안 되어 있을 때 flag[j] == false인 상태이고, P(i)는 임계 구역에 진입할 수 있다.

(3) P(j)의 flag[j] == true 일 때는, turn 값에 따라 P(i) 혹은 P(j)가 자신의 임계 구역에 진입하게 될 것이다.

(4) 위의 코드에서 P(i)(혹은 P(j))는 while 문을 수행하는 동안 turn 값을 바꾸지 않기 때문에, P(i)는 P(j)가
    지난번에 진입했다면, 이번에는 자신도 한 번은 (Bounded Waiting) 들어갈 수 있게 보장된다. (Progress)

5.4 동기화 하드웨어(Synchronization Hardware)

- Peterson's Solution와 같은 Software 기반 해결책은 현대의 컴퓨터 구조에서 올바르게 작동한다는 것을 보장하지 못한다.
- 이에 5.4에서는 프로그래머가 사용할 수 있는 Hardware에서부터 Software 기반 API를 아우르는 기법을 
  사용한 임계 구역 문제(Critical Section Problem)의 해결책들에 대해서 알아본다.
- 이 모든 해결책들은 임계 구역을 보호하기 위해 Lock을 사용한다는 점에 기반을 둔다.

- single-processor 환경에서는 공유 변수가 변경되는 동안 interrupt 발생을 허용하지 않음으로써 임계 구역 문제(Critical Section Problem)을 간단히 해결할 수 있다.
- 명령어들이 순차적으로 수행되기 때문에, 공유 변수에 예기치 못한 변화가 생기지 않기 때문이다.
- 비선점형 커널(Nonpreemptive kernel)이 이 방법을 사용한다.

- Multi-processor 환경에서는 위의 해결책을 사용하면, 시스템 효율이 떨어지기 때문에 사용하지 않는다.
- 많은 modern computer들은 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어를 제공한다.
- 예를 들어, test_and_set()과 compare_and_swap()이 있으며 코드는 아래와 같다.

​- test_and_set 명령어는 원자적(atomically)으로 실행된다는 점이 특징이다.

boolean test_and_set(boolean *target){
  boolean rv = *target;
  *target = true;
  return rv;
}

- 만일 기계가 test_and_set() 명령을 지원한다면, false로 초기화되는 Boolean type의 lock 변수를 선언하여
  아래 코드와 같이 상호 배제(Mutual Exclusion)을 구현할 수 있다.

do {
   while (test_and_set(&lock))
        ;   // do nothing
        // critical section

    lock = FALSE;
 
        // remainder section
} while (TRUE);

- compare_and_swap() 명령어는 세 개의 피연산자를 parameter로 전달받는다.
- 피연산자 value는 오직 (*value == expected) 수식이 참일 때에만, new_value로 지정된다.
- compare_and_swap() 명령어는 언제나 원래의 value 값을 return 한다.

int compare_and_swap(int *value, int expected, int new_value){
   int temp = *value;

   if(*value == expected)
      *value = new_value;

   return temp;
}

- 위의 알고리즘들은 상호 배제(Mutual Exclusion) 조건은 만족하지만, 한정된 대기(Bounded Waiting)을 만족하지 못한다.
- 이에 임계 구역 요구 조건을 모두 만족시키기 위해 아래와 같이 코드를 작성할 수 있다.
- 맨 처음에, waiting 배열과 lock 변수는 false로 초기화되어 있다.

boolean waiting[n] = {0};
boolean lock = FALSE;

do {
  waiting[i] = true;
  key = true;
  
  while(waiting[i] && key)
    key = test_and_set(&lock);

  waiting[i] = false;

  // critical section

  j = (i+1) % n;
  while((j != i) && !waiting[j])
    j = (j+1) % n;

  if(j == i)
    lock = false;
  else
    waiting[j] = false;

  // remainder section
} while (true);

- 위의 코드는 임계 구역 조건 3가지를 모두 만족한다.

- 5.4에서 설명했던 임계 구역에 대해 하드웨어 기반 해결책은 복잡한 형태를 가지고 있다.
- 이에 간단한 소프트웨어 도구들을 개발했으며, 대표적으로 Mutex Lock이 있다.
- 임계 구역에 들어가기 전에 lock을 획득해야 하고, 임계 구역을 빠져나올 때 lock을 반환해야 한다.
- acquire()를 통해 lock을 획득하고, relase()를 통해 lock을 반환한다.
- mutex lock에서는 available이라는 변수를 통해 lock의 가용 여부를 표시한다.

do {
     acquire lock
         [CRITICAL SECTION]
     release lock
         [REMAINDER SECTION]
} while(true);

acquire(){
  while (!available)
    ; /* busy waiting */
  available = false;
}

release() {
  available = true;
}

- 지금까지 설명한 방식들의 단점은 바쁜 대기(Busy Waiting)을 해야 한다는 점이다.
- 즉, 한 프로세스가 임계 구역에 있는 동안에 다른 프로세스들은 계속해서 반복문을 호출해야 한다.
- 위의 유형의 mutex lock은 lock이 가용되기를 기다리며 계속 회전하므로 spinlock이라고도 부른다.
- 이는 다중프로그래밍(Multiprogramming system)에서 CPU 사이클을 낭비하게 만든다.

​- 그러나, lock을 기다리는 동안 시간을 소모하는 Context switch를 전혀 필요로 하지 않는다는 장점이 있다.
- 따라서, 프로세스들이 짧은 시간 동안만 lock을 소유할 것이라고 예상되면, spinlock이 좋을 수 있다.
- spinlock은 multi-processor 시스템에서 많이 사용된다. (한 processor는 임계 구역, 다른 processor들은 반복)

5.6 세마포(Semaphores)

- Semaphore S는 정수 변수로서, wait()와 signal()로 접근이 가능하다.

wait(S) {
   while(S <= 0)
        ; // busy waiting
   S--;
}

signal(S) {
   S++;
}

* 세마포 사용법(Semaphore Usage)

- Counting Semaphore와 Binary Semaphore(Mutex Lock과 유사하게 동작)로 사용할 수 있다.
- Coutning Semaphore는 제한 없는 domain을 가지며, binary Semaphore는 0과 1의 값만 가능하다.

​- Binary Semaphore는 종종 상호 배제(Mutual Exclusion)을 보장하기 위해 사용된다.

​- Counting Semaphore는 유한한 개수를 가진 resource에 대한 접근을 제어하는 데 사용되며, semaphore는 가용한 자원의 개수로 초기화된다.
- wait() 연산을 수행하면 sempahore 값이 감소되며, signal() 연산을 수행하면 semaphore 값은 증가한다.
- semaphore 값이 0이 되면, 모든 자원이 사용 중임을 나타낸다.
- 이후 자원을 사용하려는 프로세스는 semaphore 값이 0보다 커질 때까지 blocking 된다.

* 구현 (Semaphore Implementation)

- 간단한 Semaphore에서는 wait() 연산시에 반복문을 통해 Busy Waiting을 해야 한다.
- 효율적인 연산을 수행하기 위해, wait()와 signal()을 다음과 같이 변경할 수 있다.

tyepdef struct{
  int value;
  struct process *list;
}semaphore;

void wait(semaphore *S){
  S->value--;
  if(S->value < 0){
    add this process to S->list;
    block();
  }
}

void signal(semaphore *S){
  S->value++;
  if(S->value <= 0){
     remove a process P from S->list;
     wakeup(P);
  }
}

- wait() 연산에서 busy waiting 대신 자신을 blocking 시킨다.
- block() 함수에서 프로세스를 semaphore에 연관된 waiting queue에 넣고, 프로세스의 상태를 waiting으로 전환한다.
  그 후, control이 스케줄러에게 넘어가고 스케줄러는 다른 프로세스를 실행하기 위해 선택한다.
- block() 함수는 자신을 호출한 프로세스를 중지시킨다.

​- blocking된 process는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다.
- 프로세스는 wakeup() 연산에 의하여 재시작되고, 프로세스의 상태를 waiting에서 ready 상태로 변경한다.
- 프로세스는 ready queue에 넣어지게 된다.
- wakeup(P)는 blocking 된 process P의 실행을 재개시킨다.

​- busy waiting을 하는 semaphore에서 semaphore는 음수의 값을 가질 수 없다.
- 하지만, 위와 같이 구현한 semaphore에서는 semaphore가 음수의 값을 가질 수 있으며, 해당 값은
  semaphore를 대기하고 있는 프로세스들의 수를 나타낸다.

​- 원칙적으로, semaphore는 두 프로세스가 동시에 wait()와 singal() 연산들을 수행할 수 없도록 반드시 보장해야 한다.
- Single-Processor 환경에서는 두 연산들이 실행되는 동안 인터럽트를 금지시키면 된다.
- Multi-Processor 환경에서는 모든 processor의 인터럽트를 금지시킴으로써 구현할 수 있으나,
  성능을 매우 감소시킬 수 있기 때문에 compare_and_swap()과 같은 locking 기법을 사용해야 한다.

* 교착 상태와 기아(Deadlock and Stravation)

- waiting queue를 통한 semaphore의 구현은 두 개 이상의 프로세스들이 대기 중인 프로세스의 사건을
  무한정 기다리는 상황이 발생할 수 있다. (Deadlock)

- 예를 들어, P(0)와 P(1)이 모두 wait()를 실행하게 되면, P(0)는 P(1)이 signal()을 실행할 때까지 기다리며,
  P(1)은 P(0)가 signal()을 실행할 때까지 기다리게 된다. 이에 P(0)와 P(1)은 deadlock 상태가 된다.

- deadlock과 관련된 다른 문제는 무한 봉쇄(indefinite blocking) 혹은 기아(starvation) 문제이다.
- 이는 프로세스들이 semaphore에서 무한정 대기하는 것이다. (LIFO 순서에서 발생할 수 있음.)

* 우선순위 역전(Priority Inversion)

- 높은 우선순위의 프로세스가 낮은 우선순위 프로세스들에 의해 접근되고 있는 kernel data를 읽기/수정해야 할 필요가 있을 때, 스케줄링에 어려움이 있다.

​- 보통 kernel data의 경우, lock에 의해 보호되기 때문에 낮은 우선순위 프로세스가 resource 사용을 마칠 때까지
  높은 우선순위의 프로세스가 기다리는 상황이 발생한다.

- 예를 들어, L<M<H의 우선순위를 가지는 프로세스가 존재한다고 할 때, 프로세스 H가 프로세스 L의 자원을 필요한
  상황에서 프로세스 M 이 프로세스 L을 선점하게 되면, 프로세스 M 이 프로세스 H의 실행 시간에 영향을 준다.

- 이런 문제를 우선순위 역전(priority inversion)이라고

- 이 문제는 셋 이상의 우선순위를 가진 시스템에서만 발생하므로 두 개의 우선순위만을 사용하여 해결할 수 있다.
- 하지만, 범용 운영체제에서는 그것이 힘드므로, priority-inheritance protocol을 사용한다.

5.7 고전적인 동기화 문제들 (Classic Problems of Synchronization)

* 유한 버퍼 문제(The Bounded-Buffer Problem)

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

do {
  wait(full);
  wait(mutex);
     ...
  // remove an item from buffer to nextc
     ...
  signal(mutex);
  signal(empty);
     ...
  // consume the item to nextc
     ...
} while (TRUE);

- mutex semaphore는 buffer pool을 접근하기 위한 mutual exclusion 기능을 제공한다.
- empty와 full semaphore는 각각 비어 있는 buffer의 수와 꽉 찬 buffer의 수를 기록한다.

* Readers-Writers 문제(The Readers-Writers Problem)

- 프로세스들 중 읽기만을 원하는 프로세스, 쓰기를 원하는 프로세스가 존재할 수 있다.
- 만약 두 reader가 동시에 공유 데이터에 접근하더라도, 문제는 발생하지 않는다.
- 하지만, 하나의 writer와 다른 reader(혹은 writer)가 동시에 접근하면 문제가 발생할 수 있다.
- 이에, writer가 쓰기 작업을 공유 데이터에 하는 동안 exclusive 한 access를 가지도록 해야 한다.
- 이 동기화 문제를 readers-writers problem라고 한다.
​
- readers-writers problem은 여러 가지 변형이 존재한다.
- 첫 번째, writer가 공유 object에 대한 허가를 아직 얻지 못했다면 어느 reader도 기다리게 해서는 안 된다.
- 두 번째, writer가 객체를 접근하려고 기다리고 있다면, 새로운 reader들은 읽기를 시작하지 못한다.

- 첫 번째 방식은 writer에 대한 starvation, 두 번째 방식은 reader에 대한 starvation을 발생시킬 수 있다.
- 첫 번째 reader-writer problem의 해결책에서, reader 프로세스는 아래와 같은 자료구조를 공유한다.

semaphore rw_mutex = 1; 
semaphore mutex = 1;
int read_count = 0;

- rw_mutex semaphore는 reader와 writer가 모두 공유한다.
- mutex semaphore는 read_count를 갱신할 때, mutual exclusion을 보장하기 위해 사용된다.
- read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려준다.

- writer process의 구조는 아래와 같다.

do {
   wait(rw_mutex);
      ...
   /* writing is performed */
      ...
   signal(rw_mutex);
} while (true)

- reader process의 구조는 아래와 같다.

do {
   wait(mutex);
   read_count++;
   
   if(read_count == 1)
     wait(rw_mutex);
   signal(mutex);
     ...
   /* reading is performed */
     ...
   wait(mutex);
   read_count--;

   if(read_count == 0)
      signal(rw_mutex);

   signal(mutex);
} while (true)

- Readers-writers problem을 해결하기 위해, 몇몇 시스템에서는 reader-writer lock을 제공한다.
- 다수의 process들이 reader mode의 reader-writer lock을 획득할 수 있다.
- 하나의 process만이 writer mode의 reader-writer lock을 획득할 수 있다.

* 식사하는 철학자들 문제(The Dining-Philsophers Problem)

- 5명의 철학자들은 원형 테이블을 공유하며, 테이블 중앙에는 밥이 있고, 테이블에는 5개의 젓가락이 놓여있다.
- 철학자가 생각할 때는 다른 동료들과 상호작용하지 않으며, 배가 고파지면 자신에게 가장 가까이 있는 젓가락
  두 개를 집으려고 시도하게 된다. (철학자는 한 번에 한 개의 젓가락만 집게 될 수도 있다.)
- 철학자는 이미 옆 사람의 손에 들어간 젓가락을 집을 수는 없으며, 젓가락 2개를 집게 되면 식사를 할 수 있다.
- 식사를 마치면, 두 개의 젓가락을 놓은 뒤, 다시 생각하기 시작한다.

- 식사하는 철학자(Dining philsophers) 문제는 고전적인 동기화 문제이다.
- 한 가지 해결책은 갓 젓가락을 하나의 semaphore로 표현하는 것이다.
- 철학자는 각 semaphore(젓가락)에 wait() 연산을 수행하여 젓가락을 집으려고 시도한다.
- 철학자는 각 semaphore(젓가락)에 signal() 연산을 수행하여 자신이 집었던 젓가락을 놓는다.

​- 위의 해결책은 deadlock 상태를 유발할 수 있다.
- 이에 deadlock 문제를 해결하기 위해 아래 해결책을 사용할 수 있다.
   (1) 최대 4명의 철학자들만이 테이블에 동시에 앉을 수 있게 한다.
   (2) 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.
   (3) 홀수 번호의 철학자들은 먼저 왼쪽 젓가락을 집게하고, 짝수 번호는 오른쪽 젓가락을 먼저 집게 한다.

​- deadlock 상태를 제거한다고 해서, 꼭 starvation의 가능성을 제거하는 것은 아니다.

5.8 모니터(Monitor)

- 아래의 경우, 임계 구역에 많은 프로세스들이 실행될 수 있어 mutual exclusion이 지켜지지 않는다.

signal(mutex);
   ...
   critical section
   ...
wait(mutex);

- 아래의 경우, deadlock 상태가 발생하게 된다.

wait(mutex);
   ...
   critical section
   ...
wait(mutex);

- 프로그래머들이 semaphore를 잘못 사용하면 다양한 오류가 발생할 수 있다. 이에 monitor를 사용한다.

5.9 동기화 사례(Synchronization Examples)

* Windows의 동기화

5.10 대체 방안들

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 4 - 스레드(Threads)

CH 4에서는,
- 첫째로, CPU 이용의 기본 단위인 Threads에 대해서 알 수 있다.
- 둘째로, Pthreads API로 대표되는 Thread Library에 대해서 알 수 있다.
- 셋째로, Multi-Threaded Programming에 관련된 issue에 대해서 알 수 있다.

4.1 개요 (Overview)

- Thread는 CPU 이용의 기본 단위이다.
- Thread는 Thread ID, Program Counter, Register set, stack으로 구성된다.
- Thread는 같은 프로세스에 속한 다른 Thread와 Code, Data Section 등을 공유한다.
- Single Threaded process와 Multi-threaded process가 있다.

* 동기(Motivation)

- 현대의 컴퓨터에서 동작하는 거의 모든 Software application들은 multi-threaded이다.

- 한 Application이 여러 개의 similar 한 task를 처리해야 할 때도 존재한다.
- 예를 들어, Web server는 client로부터 web page, image 등에 대한 요청을 받는다.
- 만일 Web server가 Single-threaded하다면, 한 번에 하나의 클라이언트만 서비스할 수 있게 되어
  클라이언트는 자신의 요구가 서비스되기까지 매우 긴 시간을 기다려야 한다.​

- 한 해결책은 서버에게 서비스 요청이 들어오면, 프로세스는 그 요청을 수행할 별도의 프로세스를 생성하는 방법이다.
- 하지만, 프로세스 생성 작업은 매우 많은 시간과 자원을 소비해야 하기 때문에 오버헤드가 많아지게 된다.
- 따라서, 이보다는 프로세스 안에서 여러 Thread를 만들어 나가는 것이 더 효율적이다.

- Thread는 RPC(Remote Procedure Call)에서도 매우 중요한 역할을 담당한다.
- RPC는 IPC를 마치 일반적인 함수나 procedure call을 하는 것처럼 할 수 있게 한다.
- RPC Server들은 대부분 Multi-Threaded System이다.

​- 많은 운영체제 kernel들은 현재 multi-threaded의 형태를 갖추고 있다.
- kernel 안에서 다수의 Thread들이 동작하고, 각 thread는 인터럽트 처리 등 특정 작업을 수행한다.

​

* 장점(Benefits)

- Multi-threaded programming의 benefit은 크게 4가지 부류로 나눌 수 있다.

1. 응답성(Responsiveness)
- interactive application을 Multithreading 하면, 일부분이 blocking 되거나 긴 작업을 수행하더라도  
  프로그램의 수행이 계속되도록 하여, user에 대한 Responsiveness를 향상시킨다.
- 이 특성은 user interface를 설계하는데 유용하다.

2. 자원 공유(Resource sharing)
- 프로세스는 공유 메모리(Shared Memory)와 메시지 전달(Message Passing) 기법을 통하여 자원을 공유할 수 있다.
- Thread는 자동적으로 그들이 속한 프로세스의 resource 들과 memory를 공유한다.
- Code와 Data 공유의 이점은 한 application 이 같은 address space 내에 여러 개의 다른 작업을 하는 Thread를 가질 수 있다는 점이다.

3. 경제성(Economy)
- 프로세스 생성을 위해 memory와 resource를 할당하는 것은 비용이 많이 든다.
- Thread는 자신이 속한 process의 자원들을 공유하기에 Thread를 생성하여 Context-swtich를 하는 것이 경제적이다.
- 일반적으로 Thread를 사용하는 것보다 새로운 process를 생성하고 관리하는 것이 훨씬 더 많은 시간을 소모한다.

4. 규모 적응성(Scalability)
- Multithreading의 이점은 multi-processor 구조에서 더욱 증가할 수 있다.
- 해당 구조에서는 각각의 Thread가 다른 processor에서 parallel 하게 수행될 수 있기 때문이다.

4.2 다중 코어 프로그래밍(Multicore Programming)

- core가 여러 CPU chip 형태를 띠거나, 칩 안에 여러 개가 존재하게 될 때,
  이러한 시스템을 다중 코어(multicore) 또는 다중 처리기(Multiprocessor) 시스템이라고 부른다.

- Single computing core 상에서, concurrency는 단순히 Thread의 실행이 시간에 따라 교대로 실행된다는 것을 의미한다.

- Multiple core System 상에서는 시스템이 개별 Thread를 각 core에 배정할 수 있기 때문에 concurrency는 Thread들이 parallel 하게 실행될 수 있다는 것을 의미한다.

​- 하나 이상의 task를 동시에 수행할 수 있는 시스템에 대해 병렬적(parallel)이라고 말한다.

- 병행(Concurrent) 실행 시스템은 모든 task가 진행하게끔 함으로써 하나 이상의 task를 지원한다.

​

- 따라서 병렬(Parallel) 실행 없이 병행(Concurrent) 실행하는 것이 가능하다.
- CPU 스케줄러는 시스템의 프로세스 사이를 빠르게 오고 가며 모든 프로세스를 진행시켜 마치 병렬 실행하는 듯한 착각을 주게 한다.
  (실제는 병행 실행을 수행하는 것)

* 프로그래밍 도전과제(Programming Challenges)

- Multi-core System을 위해 Programming 하기 위해서는 다섯 개의 주의점이 있다.

(1) 태스크 인식(Identifying tasks)
- Application을 분석하여 separate, concurrent task로 나눌 수 있는 영역을 찾는 작업이 필요하다.

(2) 균형(Balance)
- 찾아진 부분들이 전체 작업에 균등한 기여도를 가지도록 task를 나누는 것도 중요하다.

(3) 데이터 분리(Data spliting)
- Application이 여러 task로 나뉘는 것처럼, task가 접근하는 data 또한 각 core에서 사용할 수 있도록 나누어져야 한다.

(4) 데이터 종속성(Data dependency)
- task가 접근하는 데이터는 둘 이상의 task 사이에 dependency가 없는지 검토되어야 한다.

(5) 시험 및 디버깅(Testing and debugging)
- program이 multi-core에서 parallel 하게 실행될 때, 디버깅의 어려움이 높아진다.

* 병렬 실행의 유형 (Type of Parallelism)

1. 데이터 병렬 실행(Data Parallelism)은 동일한 data의 부분집합을 다수의 계산 코어에 분배한 뒤,
각 코어에서 동일한 연산을 수행하는 데 초점을 둔다. (하나의 일을 여러 core가 함께 수행함.)

2. 태스크 병렬 실행(Task Parallelism)은 data가 아니라 task(Thread)를 다수의 코어에 분배한다.
각 thread는 고유의 연산을 수행하므로, 동일한 데이터에 대해 연산을 수행할 수도 있다.

​- 즉, data parallelism은 data가 core에 분배되어야 하고, task parallelism은 task가 분배되어야 한다.
- 보통 이 두 가지 유형(Data Parallelism, Task Parallelism)을 혼합하여 사용한다.

4.3 다중 스레드 모델(Multithreading Models)

- Thread는 사용자 수준에서는 user Thread와 kernel 수준에서 사용되는 kernel thread로 제공될 수 있다.
- User Thread는 Kernel 위에서 지원되며, kernel의 지원 없이 관리된다.
- Kernel Thread는 운영체제에 의해 직접 지원되고 관리된다.

​

* 다대일 모델(Many-to-One Model)

- 많은 user-level Threads들을 하나의 kernel thread로 mapping 한다.

(장점)
- Thread management는 user space의 thread library에 의해 행해지고, 효율적이다.

(단점)
- 하지만, 한 thread가 blocking system call을 하면 전체 process가 block 된다.
- 또한, 한 번에 한 thread만이 kernel에 접근할 수 있기 때문에 multiple thread가
  multi-core system에서 병렬적(parallel)으로 실행될 수 없다.

* 일대일 모델(One-to-One Model)

* 다대다 모델(Many-to-Many Model)

- 여러 개의 User-level thread를 그보다 작은 수 혹은, 같은 수의 kernel thread로 multiplex 한다.
- kernel thread의 수는 Application이나 특정 기계에 따라 결정된다.

* 두 수준 모델(Two-level Model)

- (Many-to-Many model)과 (One-to-One Model)을 결합한 모델이라고 할 수 있다.

4.4 스레드 라이브러리(Thread Library)

- Thread Library는 프로그래머에게 Thread를 생성하기 관리하기 위한 API를 제공한다.​

- Thread Library를 구현하는 데에는 크게 2가지 방법이 있다.
(1) kernel의 지원 없이 완전히 사용자 공간에서만 라이브러리를 제공하는 방법
(2) OS에 의해 지원되는 kernel 수준에서의 library를 구현하는 방법

- 세 종류의 Thread Library가 주로 사용된다.
(1) POSIX Pthreads (2) Windows (3) Java

- 쓰레딩(Threading)에는 2가지 종류가 있다.

(1) 동기 쓰레딩(Synchronous threading)
- 부모 thread가 하나 이상의 자식 thread를 생성하고 자식 thread가 모두 종료할 때까지 기다렸다가 자신의
실행을 재개하는 방식을 말한다. 이 방식은 '포크-조인(fork-join)' 전략이라고 불린다.
- 부모가 생성한 Thread들은 병행하게(concurrently) 실행되지만 부모는 자식들의 작업이 끝날 때까지 실행을 계속할 수 없다.
- 동기 쓰레딩(Synchronous threading)은 상당한 양의 데이터를 공유하게 된다.
- 예를 들어, 부모 thread는 자식들이 계산한 결과를 통합할 수 있어야 한다.

(2) 비동기 쓰레딩(Asynchronous threading)
- 부모 thread가 자식 thread를 생성한 후, 부모는 자신의 실행을 재개하여 두 thread를 병행하게 실행한다.
- 각 Thread는 모든 다른 Thread와 독립적으로 실행하기 때문에, 부모 thread는 자식의 종료를 알 필요가 없다.
- 각 Thread들은 독립적이기 때문에, thread들 사이의 데이터 공유는 거의 없다.

4.5 암묵적 스레딩(Implicit Threading)

- Multi-core processing이 발전함에 따라, 수백 또는 수천 개의 Thread를 가진 Application이 등장하였다.

- Threading의 생성과 관리 책임을 Application developer로부터 compiler와 run-time libraries에게 넘겨주는 '암묵적 스레딩(implicit threading)'을 사용하여 multi-thread application를 효율적으로 설계할 수 있다.

- 암묵적 스레딩(implicit threading)을 사용하여 multicore processor를 활용할 수 있는 multi-thread program을 설계하는 3가지 접근법은 다음과 같다. (1) Thread Pool (2) OpenMP (3) Grand Central Dispatch

* 스레드 풀(Thread Pool)

웹 서버는 요청을 받을 때마다 그 요청을 들어주기 위해 새로운 Thread를 생성한다.
- 이 방법에는 크게 2가지 문제가 있을 수 있다.
  (1) 서비스를 할 때마다 Thread를 생성하는 데 일정 시간이 소요된다.
  (2) 모든 요청마다 Thread를 생성하므로, 동시에 실행할 수 있는 최대 Thread의 수를 정해놓아야 한다.

- Thread를 무한정 만들면 언젠가는 CPU 시간, 메모리 공간과 같은 System Resource가 고갈될 수 있다.
- 이러한 문제들을 해결해줄 수 있는 방법 중 하나가 '스레드 풀(Thread pool)'이다.​

- Thread pool의 기본 아이디어는 프로세스를 시작할 때 아예 일정한 수의 Thread를 미리 pool로 만들어 놓는 것이다.
- pool에 만들어진 Thread들은 일(work)이 없을 때는, 일(work)을 계속 기다리게 된다.
- 이후 request가 들어오게 되면, pool에서 한 Thread에게 해당 request를 할당한다.
- 만약 pool에 남아 있는 Thread가 없다면, server는 free thread가 하나 생길 때까지 기다려야 한다.​

- Thread Pool은 아래와 같이 3가지의 장점을 가진다.
(1) 새 Thread를 만들어 주는 것보다 생성된 Thread를 사용하여 서비스해 주는 것이 더 빠르다.
(2) Thread pool은 임의의 시간에 존재할 수 있는 Thread 개수에 제한을 둔다.
(3) task를 생성하는 방법을 분리하여, task를 일정 시간 후에 실행되도록 하거나, 주기적으로 실행시킬 수 있다.

​- Thread pool에 존재하는 Thread의 개수는 CPU 수, Physical Memory 용량 등을 고려하여 정해질 수 있다.

4.6 스레드와 관련된 문제들(Threading Issues)

* Fork() 및 Exec() System call

- Multithreaded Program에서는 fork()와 exec()의 의미가 달라질 수 있다.

Q) 만일, 한 프로그램의 Thread가 fork()를 호출하면, 새로운 프로세스는 모든 Thread를 복제해야 하는가?
한 개의 Thread만 가지는 프로그램이어야 하는가?

A) 몇몇 UNIX는 이 두 가지 버전의 fork()를 모두 지원한다.

* 신호처리(Signal Handling)

- Signal은 UNIX에서 프로세스에게 어떤 사건이 일어났음을 알려주기 위해 사용된다.
- Signal은 알려줄 event의 source나 reason에 따라 동기식 또는 비동기식으로 전달될 수 있다.

​- 모든 신호는 다음과 같은 형태로 전달된다.
1. 신호는 특정 사건이 일어나야 생성된다.
2. 생성된 신호가 프로세스에게 전달된다.
3. 신호가 전달되면 반드시 처리되어야 한다.

​- 동기식 신호(Synchronous signal)의 예로는 불법적인 메모리 접근, 0으로 나누기 등이 있다.
- 비동기식 신호(Asynchronous signal)의 예로는. (Ctrl+C)와 같은 키를 눌렀을 때가 해당된다.

​- 모든 신호는 둘 중 하나의 handler에게 처리된다.
   1. 디폴트 신호 처리기(Default signal handler)
   2. 사용자 정의 신호 처리기(A user-defined signal handler)
- deafult singal handlers는 user-defined signal handler에 의해 대체될 수 있다.

​- 동기적 신호는 해당 신호를 발생시킨 Thread에게 전달되어야 하고, 다른 Thread에게는 전달되면 안 된다.
- 비동기적 신호는 누가 신호를 발생시켰는지 명확하지 않으므로, 모든 Thread에게 신호가 전달된다.

​

​* 취소 (Cancellation)

- 스레드 취소(Thread Cancellation)은 Thread가 끝나기 전에 그것을 강제 종료시키는 작업을 말한다.
- 예를 들어, 여러 Thread들이 데이터베이스를 병렬로 검색하고 있다가 한 Thread가 원하는 결과를 찾게 되면 나머지 Thread들은 취소되어도 된다.
- 이처럼 취소되어할 Thread들을 목적 스레드(Target Thread)라고 부른다.​

- 취소(Cancellation)은 아래 두 가지와 같은 방식으로 발생할 수 있다.
(1) 비동기식 취소(Asynchronous cancellation) : 한 Thread가 즉시 Target Thread를 강제 종료시킨다.
(2) 지연 취소(Deferred cancellation) : Target Thread가 주기적으로 자신이 강제 종료되어야 할지 점검한다.

​- Thread 취소를 어렵게 만드는 것은 취소 Thread에게 할당된 Resource의 문제이다.
- 또한, Thread가 다른 Thread와 공유하는 자료구조를 갱신하는 과정에서 취소 요청이 와도 문제가 될 수 있다.
- 이에, 비동기식으로 Thread를 취소하면 필요한 시스템 자원을 다 사용 가능한 상태로 만들지 못할 수도 있다.
- 지연 취소의 경우, Thread는 자신이 취소되어도 안전하다고 판단될 때 취소 여부를 검사할 수 있다.

​- Cancellation의 Default 유형은 지연 취소(Deferred Cancellation)이다.

​

* 스레드 국지 저장소(Thread-Local Storage)

- 한 프로세스에 속한 Thread들은 그 프로세스의 data를 모두 공유한다.
- 그러나, 상황에 따라 각 Thread는 자기만 Access 할 수 있는 데이터를 가져야 할 필요가 있을 수 있다.
- 이러한 data를 스레드 국지 저장소(Thread-Local Storage, TLS)라고 부른다.

​- TLS를 local variable과 혼동하기 쉽다.
- Local Variable이 하나의 함수가 호출되는 동안에만 보이는 반면에 TLS는 전체 함수 호출에 걸쳐 보인다.
- TLS는 static data와 유사한데, 차이점은 TLS data는 각 Thread의 고유한 정보를 저장한다는 점이다.

* 스케줄러 액티베이션(Scheduler Activation)

- Multithread Program에서는 Thread Library와 kernel의 통신 역시 고려해야 한다.
- 이 통신은 Many-to-Many, Two-level Model에서 반드시 해결해야 하는 문제이다.
- 이러한 통신을 통해 Kernel Thread의 수를 동적으로 조절하여 Application이 최고의 성능을 보이도록 보장할 수 있다.

​- Many-to-Many 또는 Two-level model을 구현하는 많은 시스템들은 user와 kenrel thread 사이에  
  중간 자료 구조를 둔다. 이 자료구조는 보통 lightweight process, or LWP라고 불린다.
- LWP는 하나의 kenrel thread에 속해있으며, kernel thread가 block 되면 LWP 역시 함께 block 된다.

- user thread library와 kernel thread 간의 통신 방법 중의 하나는 Scheduler Activation이다.

- Scheduler Activation은 아래와 같이 동작한다.
(1) kernel은 application에게 virtual processor(LWP)의 set을 제공한다.
(2) Application은 virtual processor로 user thread를 schedule 한다.
(3) kernel은 application에게 certain event에 대해 알려줘야 한다. (이를 'upcall'이라고 한다.)

4.7 운영체제 사례(Operating-System Examples)

* Windows 스레드 (Windows Threads)

- Thread를 위해 아래와 같은 자료구조를 가지고 있다.
(1) ETHREAD : 실행 스레드 블록(Executive Thread block):
    Thread가 속한 프로세스를 가리키는 포인터, Thread가 실행을 시작해야 할 루틴의 주소 등을 가짐.

(2) KTHREAD : 커널 스레드 블록(Kernel Thread Block):
    Thread의 스케줄링 및 동기화 정보, kernel mode에서 실행될 때 사용되는 kernel stack 등을 가짐.

(3) TEB : 스레드 환경 블록(Thread Environment Block):
    Thread identifier, user-mode stack, thread-local storage를 위한 array 등을 가짐.

* Linux 스레드 (Linux Threads)

- 프로세스를 복제하는 fork() system call을 제공하며, clone() system call을 통해 Thread를 생성할 수 있다.
- Linux에서는 프로세스(process)와 스레드(Thread)를 구분하지 않으려고 한다.

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 3 - 프로세스(Process)

CH 3에서는,
- 첫째로, 프로세스의 개념과 다양한 특성들에 대해서 알 수 있다.
- 둘째로, Shared Memory와 Message Passing을 통한 프로세스 간 통신에 대해서 알 수 있다.
- 셋째로, Client-Server System에서의 통신에 대해 알 수 있다.

3.1 프로세스 개념(Process Concept)

* 프로세스(The Process)

- Informally, 프로세스는 실행 중인 프로그램이다. (process is a program in execution.)
- 프로세스는 program counter의 값과 같은 현재 활동을 나타내는 것들을 include 한다.
- 프로세스는 temporary data(function의 parameter, return address, local variable)를 가지는
   process stack을 include 한다.

- 프로세스는 global variable들을 contain 하는 data section을 include 한다.
- 프로세스는 프로세스 실행 중에 동적으로 할당되는 memory인 heap을 include 한다.

- 프로그램은 디스크에 저장된 파일(executable file[실행파일])과 같이 수동적인 존재(Passive entity)
- 프로세스는 다음에 실행할 명령어를 지정하는 PC와 관련 resource의 set을 가진 능동적인 존재(Active entity)
- executable file가 memory에 load 될 때, 프로그램이 프로세스가 된다.

* 프로세스 상태(Process State)

- 프로세스는 실행되면서 상태(State)가 변화하며, 프로세스의 상태는 현재의 활동에 따라 정의된다.

(1) New : 프로세스가 생성 중이다.
(2) Running : 명령어(Instructions)들이 실행되고 있다.
(3) Waiting : 프로세스가 어떤 event가 일어나기를 기다린다.
(4) Ready : 프로세스가 processor에 할당되기를 기다린다.
(5) Terminated : 프로세스의 execution이 종료되었다.

- 어느 한순간에 한 processor에서는 오직 하나의 process만이 실행된다.
- 이에 많은 프로세스가 Ready, Waiting 상태에 있을 수 있다.

* 프로세스 제어 블록(Process Control Block)

- PCB(Process Control Block)은 특정 프로세스와 연관된 여러 정보를 가지고 있다.

(1) Process State(프로세스 상태): new, ready, running, waiting, halted 등의 상태를 가진다.
(2) Program Counter(프로그램 카운터): 이 프로세스가 다음에 실행할 명령어의 주소를 가리킨다.
(3) CPU Registers: Accumlator, index register, stack register, general-purpose register 들과 condition code가 포함된다.
(4) CPU 스케줄링 정보: process priority, 큐에 대한 포인터 등과 같은 scheduling parameter들을 포함한다.
(5) Memory 관리 정보: base register와 limit register 값, page table과 segment table의 정보를 포함한다.
(6) Accounting 정보: CPU 사용시간, real time used, time limit, process number 등을 포함한다.
(7) 입출력 상태 정보: 해당 프로세스에게 할당된 I/O device 들과 open file 목록 등을 포함한다.

3.2 프로세스 스케줄링(Process Scheduling)

- Multi-Programming의 목적은 CPU utilization을 최대화하기 위하여 항상 어떤 프로세스가 실행되도록 하는 것이다.

- Time-Sharing 방식의 목적은 각 프로그램이 실행되는 동안 user가 interact 할 수 있도록 프로세스들 사이에서 CPU를 자주 switching 해주는 것이다.

- 프로세스 스케줄러(Process Scheduler)는 CPU에서 실행 가능한 여러 프로세스들 중 한 프로세스를 선택한다.

- Single-Processor 환경에서, 실행 중인 프로세스는 한 개 이상 있을 수 없다.

- 만일, 프로세스들이 여러 개가 있다면, 나머지 프로세스들은 CPU가 자유로워질 때까지 대기해야 한다.

​

* 스케줄링 큐(Scheduling Queues)

- 프로세스가 시스템에 들어오면, 이들은 job queue에 놓이게 된다. job queue는 시스템의 모든 프로세스가 있다.
- Main Memory에 존재하며, Ready 상태에서 실행을 대기하는 process들은 ready queue라 불리는 리스트에 있게 된다.
- 특정 입출력 장치를 대기하는 프로세스들의 리스트를 device queue라고 한다.

​

* 스케줄러(Schedulers)

- 프로세스들은 life-time 동안 다양한 스케줄링 큐들 사이에 있게 된다.
- 프로세스들은 대용량 메모리에 저장되어 실행될 때까지 기다리게 된다.

​- long-term Scheduler(Job Scheduler)은 대용량 메모리에서 프로세스들을 선택하여 실행하기 위해 Memory로 load 한다.
- short-term Scheduler(CPU Scheduler)은 실행 준비가 완료된 프로세스들 중에서 선택하여, 해당 프로세스에게 CPU를 할당한다.

- long-term Scheduler은 short-term Scheduler에 비해 실행 빈도수가 적은 편이다.
- long-term Scheduler은 degree of Multi-Programming(메모리에 있는 프로세스들의 수)를 control 한다.

- Short-term Scheduler은 CPU를 위해 자주 새로운 프로세스를 선택해야 한다. (빈도수가 높다.)
- 100ms마다 한 번씩 실행되기도 하므로, short-term Scheduler은 실행 속도가 매우 빨라야 한다.

​- I/O Bound Process는 연산보다 입출력 실행에 더 많은 시간을 소요하는 프로세스이다.
- CPU Bound Process는 연산에 더 많은 시간을 소요하고, 입출력 요청을 드물게 발생시키는 프로세스이다.
- long-term Scheduler은 두 가지 Process들을 적절히 혼합하여 선택하는 것이 중요하다.

​

* 문맥 교환(Context Switch)

- interrupt가 발생하면, 시스템은 interrupt 처리가 끝난 후에 context를 복구할 수 있도록
  현재 실행 중인 프로세스의 context를 저장할 필요가 있다.

- context는 프로세스의 PCB에 표현된다. (CPU 레지스터 값, 프로세스 상태, 메모리 관리 정보 등)

- CPU를 다른 프로세스로 switch 하기 위해서는, 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 보관된 상태를 복구하는 작업이 필요하다. 이 작업을 Context Switch라고 한다.

- Context Switch가 일어나면, 커널은 과거 프로세스의 context를 PCB에 저장하고 실행할 프로세스의 saved context를 복구한다.

- Context Switch가 진행되는 동안, 시스템은 어떤 useful work도 할 수 없기 때문에 이 시간은 overhead이다.

3.3 프로세스에 대한 연산(Operation on Processes)

* 프로세스 생성(Process Creation)

- 실행되는 동안 프로세스는 여러 개의 새로운 프로세스를 생성할 수 있다.
- 생성하는 프로세스를 '부모(parent) 프로세스', 새롭게 생성되는 프로세스를 '자식(child) 프로세스'라고 한다.
- 자식 프로세스는 또 새롭게 다른 프로세스를 생성할 수 있으며, 그 결과 '프로세스의 트리'를 형성한다.

- UNIX, LInux와 같은 대부분의 현대 운영체제들은 프로세스 식별자(pid)를 사용하여 프로세스를 구분한다.
- pid는 보통 정수이며, 시스템의 각 프로세스에게 고유한 값을 가지도록 할당된다.

​- 프로세스가 새로운 프로세스를 생성할 때, 두 프로세스를 실행시키는 데 두 가지 가능한 방법이 존재한다.
(1) 부모는 자식과 병행하여 실행을 계속한다. (continues to execute concurrently)
(2) 부모는 일부 또는 모든 자식이 실행을 종료할 때까지 기다린다.

​- 새로운 프로세스들(자식 프로세스들)의 주소 공간 측면에서 볼 때 아래와 같이 두 가지 경우로 나타날 수 있다.

(1) 자식 프로세스는 부모 프로세스의 복사본이다.
- UNIX에서 새로운 프로세스는 'fork()' system call을 통해 생성된다.
- 새로운 자식 프로세스는 부모 프로세스의 주소 공간의 복사본으로 구성된다.
- 기존의 부모 프로세스와 새롭게 생성된 자식 프로세스는 fork() 후의 명령어에서부터 실행을 계속한다.
- 한 가지 차이점은 부모 프로세스는 자식 프로세스의 pid, 자식 프로세스는 0이 return 된다.

(2) 자식 프로세스가 자신에게 load될 새로운 프로그램을 가지고 있다.
- fork() system call 다음에 생성되는 두 프로세스 중에 한 프로세스가 exec() system call을 사용하여
  자신의 memory 공간을 새로운 프로그램으로 교체할 수 있다.

​

* 프로세스 종료(Process Termination)

- 프로세스가 마지막 문장의 실행을 끝내고, exit() system call을 사용하여 프로세스를 종료할 수 있다.
- 이 시점에서 프로세스는 자신의 부모 프로세스에게 wait() system call을 통해 status를 return 할 수 있다.

​- 부모는 여러 가지 이유로 인해 자식 프로세스들 중 하나의 실행을 종료할 수 있다.
(1) 자식이 자신에게 할당된 자원을 초과하여 사용하는 경우
(2) 자식에게 할당된 task가 더 이상 필요가 없는 경우
(3) 부모가 exit() 하는데, 운영체제는 부모가 exit 한 후에 자식이 실행하는 것을 허용하지 않는 경우

​- 종료되었지만, 부모 프로세스가 아직 wait()를 호출하지 않는 프로세스를 '좀비(Zombie) 프로세스'라고 한다.
- 부모 프로세스가 wait()를 호출하지 않고, 종료해버린 프로세스를 '고아(Orphan) 프로세스'라고 한다.
- Linux와 UNIX는 Orphan Process의 새로운 부모 프로세스로 init 프로세스를 지정함으로써 문제를 해결한다.

3.4 프로세스 간 통신(Interprocess Communication)

3.5 IPC 시스템의 사례

1. Shared Memory를 위한 POSIX API
2. Mach OS의 Message Passing System
3. Message Passing을 사용하기 위해 Shared Memory를 사용하는 Windows

- 3.4에서 공유 메모리와 메시지 전달 기법을 사용하여 프로세스들이 통신하는 방법에 대해 알 수 있었다.
- 이 기법들은 클라이언트-서버 시스템의 통신에도 사용할 수 있다.
- 이 경우에 사용할 수 있는 통신 전략은 3가지로, '소켓(Socket)', 'RPCs', '파이프(Pipe)'이다.
   (RPCs : Remote Procedure Calls)

​

* 소켓(Socket)

- 소켓은 통신의 end-point이며, 두 프로세스가 네트워크 상에서 통신을 하기 위해 두 개의 소켓이 필요하다.
- 서버는 지정된 port에 클라이언트 요청 메시지가 도착하기를 기다리게 된다.
- 요청이 수신되면, 서버는 클라이언트 소켓으로부터 연결 요청을 수락함으로써 연결이 이루어진다.
- 소켓을 이용한 통신은 스레드들 간에 구조화되지 않은 바이트 스트림만 통신하기 때문에 너무 저 수준이다.
- 이에 대한 대안으로, 보다 고 수준인 RPC와 Pipes가 존재한다.

​

* 원격 프로시저 호출(Remote Procedure Calls, RPC)

- RPC는 네트워크에 연결되어 있는 두 시스템 사이의 통신을 연결하기 위한 프로시저 호출을 추상화하기 위한 방안으로 설계되었다.
- RPC는 분산 파일 시스템(Distributed File System)을 구현하는데 유용하다.

​

* 파이프 (Pipes)

- 파이프(Pipe)는 두 프로세스가 통신할 수 있게 하는 전달자(conduits)로서 동작한다.

​

▶ 일반 파이프(Ordinary Pipes)

- 일반 파이프는 생산자-소비자 형태로 두 프로세스 간의 통신을 허용한다.
- 생산자는 파이프의 한 end 단에서 write를 하고, 소비자는 반대 end 단에서 read를 한다.
- 결과적으로 한쪽으로만 데이터를 전송할 수 있는 단방향 통신만이 가능하다.
- 만일 양방향 통신이 필요하다면, 두 개의 파이프를 사용해야 한다.

​

▶ 지명 파이프(Named Pipes)

- 일반 파이프는 오직 프로세스들이 통신하는 동안에만 존재하지만, 지명 파이프는 통신이 종료돼도 계속 존재한다.
- 지명 파이프의 경우, 양방향으로도 통신이 가능하며 부모-자식 관계도 필요하지 않다.
- 지명 파이프가 구축되면, 여러 프로세스들이 이를 사용하여 통신할 수 있다.

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』

CHAPTER 2 - 시스템 구조 (System Structures)

CH 2에서는,
- 첫째로, 운영체제가 제공하는 서비스와 System Call이란 무엇인가에 대해서 알 수 있다.
- 둘째로, 운영체제 설계 및 구현 시에 고려해야 하는 점에 대해서 알 수 있다.
- 셋째로, 운영체제의 여러 구조들에 대해서 알 수 있다.

2.1 운영체제 서비스(Operating System Service)

- 운영체제는 프로그램 실행 환경을 제공하며, 특정 서비스를 사용자에게 제공한다.

1. 사용자 인터페이스(User interface)
  1-(1) CLI(Command Line Interface) : 문자열로 명령하는 인터페이스를 제공함.
  1-(2) Batch Interace : 디렉티브가 파일 형태로 입력되고, 파일을 통해 인터페이스를 제공함.
  1-(3) GUI(Graphical User Interface) : 가장 보편적. 그래픽 요소들을 통해 인터페이스를 제공함.​

2. 프로그램 수행(Program Execution)
  - System은 Program을 메모리에 load 해서 실행할 수 있어야 한다.
  - 프로그램이 정상적이든, 비정상적이든 실행을 끝낼 수 있어야 한다.

3. 입출력 연산(I/O Operation)
  - 수행 중인 프로그램은 입출력을 요구할 수 있다.
  - 사용자는 보통 입출력 장치를 직접 제어할 수 없으므로, 운영체제가 입출력 수행의 수단을 제공해야 한다.

4. 파일 시스템 조작(File System Manipulation)
  - 프로그램은 파일을 읽고 쓸 수 있어야 하며, 이름에 의해 파일 생성/삭제/검색 등을 할 수 있어야 한다.
  - 이에 많은 OS들은 다양한 specific feature와 Performance feature를 제공하기 위해 다양한 파일 시스템을 제공한다.

5. 통신(Communication)
  - 한 프로세스가 다른 프로세스와 정보를 교환해야 할 필요가 있는 상황이 많다.
  - 이러한 통신은 두 가지 방법(Shared Memory, Message Passing)에 의해 구현될 수 있다.

6. 오류 탐지(Error Detection)
  - 운영체제는 모든 가능한 Error를 항상 의식하고 있어야 한다.
  - Error는 CPU, Memory Hardware, I/O, 또는 user program에 의해 일어날 수 있다.​

7. 자원 할당(Resource Allocation)
  - 다수의 User가 존재하거나 다수의 작업들이 동시에 수행될 때, Resource를 적절히 할당해주어야 한다.
  - 예를 들어, CPU를 최대한 효율적으로 이용하기 위해 운영체제는 CPU Scheduling Routine이 CPU의 속도, 사용 가능한 레지스터 수 등의 다양한 요인을 고려하여 자원을 할당한다.

8. 회계(Accounting)
- 사용자가 컴퓨터 자원을 어떻게, 얼마나 많이 사용하는지를 알 수 있도록 해야 한다.

9. 보호(Protection)와 보안(Security)
- 보호(Protection) : 시스템 자원에 대한 모든 접근이 통제되도록 보장하는 것
- 보안(Security) : 각 사용자가 자원에 대한 접근을 원할 때, 시스템에게 자기 자신을 인증하는 것에서부터 시작.

2.2 사용자 운영체제 인터페이스 (User OS Interface)

* 명령 해석기(Command-Interpreter)
- 선택할 수 있는 명령어 해석기를 여러 개 제공하는 시스템에서는 이 해석기를 "셸"이라고 부른다.
- 명령어 해석기의 중요한 기능은 사용자가 지정한 명령을 가져와서 그것을 수행하는 것이다.

* GUI(Graphical User Interface)
- CLI 방식보다 사용자 친화적인 방식으로, 사용자는 마우스를 통해 아이콘을 클릭함으로써 프로그램을 수행할 수 있다.
- 스마트폰이나 태블릿에서는 마우스를 사용하지 않고, '터치스크린 인터페이스'를 사용한다.

2.3 시스템 호출(System Calls)

- System Call은 OS에 의해 사용 가능하게 된 서비스에 대한 인터페이스를 제공한다
- 간단한 프로그램(파일 복사, 이동)의 경우도 많은 System Call을 수행하게 된다.

- 대부분, 프로그래머들은 API(Application Programming Interface)를 통해 System Call을 호출한다.
- API 사용자는 System Call이 어떻게 구현되고, 실행 중 무슨 작업을 하는지 알지 못해도 되며, 단지 API를 준수하고, 시스템 호출의 결과로서 운영체제가 무엇을 할 것인지 만을 파악하면 된다.

- 운영체제에 매개변수를 전달하는 방법은 크게 3가지가 있다.
1. 매개변수를 레지스터 내에 전달하는 방법
2. 매개변수를 메모리 내의 블록이나 테이블에 저장하고, 블록의 주소가 레지스터 내에 저장되는 방법
3. 매개변수를 블록이나 스택에 저장하는 방법 (매개변수의 길이를 제한하지 않는 장점이 있음.)

2.4 시스템 호출의 유형 (Types of System Calls)

- 시스템 호출은 5가지 중요한 범주로 묶을 수 있다.
1. Process Control (프로세스 제어)
2. File Manipulation (파일 조작)
3. Device Manipulation (장치 조작)
4. Information Maintance (정보 유지 보수)
5. Communication (통신)과 Protection (보호)

​

* 프로세스 제어(Process Control)

(1) 끝내기(end), 중지(abort)
- 실행 중인 프로그램은 수행을 정상적으로(end()), 혹은 비정상적으로(abort()) 종료할 수 있어야 한다.

(2) 적재(load), 수행(execute)
- 한 프로그램을 실행하고 있는 process나 job이 다른 프로그램을 load 하고, execute 하기를 원할 수 있다.
- load된 프로그램이 종료 되었을때, 어디로 Control을 Return해야 하는가에 대한 질문이 생길 수 있다.
- 만약 Control이 기존 프로그램으로 돌아간다면, 기존 프로그램의 Memory image를 save 해놔야 한다.
- 만약 두 프로그램이 병행하게 수행된다면, Multi-programming 될 새로운 job이나 process를 생성한 것이다.

(3) 프로세스 생성, 프로세스 종료
- new job, process 혹은 set을 생성한다면, 이들의 execution을 control 할 수 있어야 한다.

(4) 프로세스 속성 획득, 속성 결정
- job의 priority, maximum allowable execution time 등을 포함하여 속성을 결정할 수 있어야 한다.

(5) 시간 기다리기(wait for time)
- new job이나 process를 생성한 후에는, 이들의 실행을 끝나기를 기다릴 필요성이 있을 수 있다.

(6) wait event, signal event
- 특정 사건이 일어날 때까지 기다릴 수 있을 수 있어야 한다.(wait event)
- 그 사건이 일어나면 신호를 보낼 수 있을 수 있어야 한다. (Signal event)

(7) Allocate and free memory
- 둘 이상의 프로세스들이 공유하는 데이터들에 대해 일관성을 보장해야 할 필요성이 있을 수 있다.
- 이에 운영체제는 종종 프로세스가 공유 데이터를 lock 할 수 있는 System Call을 제공한다.

* 파일 조작(File Manipulation)

(1) 파일 생성(Create File), 파일 삭제(Delete File)
- 이 System Call은 보통, 파일 이름이나 파일 속성의 일부를 요구한다.

​(2) 열기 (Open), 닫기(Close)
- 생성된 파일들을 사용하기 위해서는 열기(Open) System call을 사용한다.
- 파일을 더 이상 사용하지 않을 때는, 파일 닫기(Close) System Call을 사용한다.

(3) 읽기, 쓰기, 위치 변경(Reposition)
- 파일을 열은 뒤에, 읽기(Read()), 쓰기(Write())를 할 수 있다.
- 위치 변경(Reposition(), (ex) 파일의 끝으로 건너뛰기)를 할 수 있다.

​(4) 파일 속성 획득 및 결정 (get file attributes, set file attributes)
- 파일 속성에 대한 정보를 얻을 수 있고, 변경할 수 있다.

* 장치 조작(Device Manipulation)

- 프로세스는 작업을 계속 수행하기 위해 Main Memory, Disk Drive 등의 추가 자원을 필요로 할 수 있다.​

(1) 장치를 요구(Request Devices), 장치를 방출(Release Devices)
- 다수의 사용자가 동시에 사용하는 시스템은 독점적인 device 사용을 보장받기 위해 Request 해야 한다.
- device의 사용이 끝나면, 반드시 Release 해야 한다.

(2) 읽기, 쓰기, 위치 변경(Reposition)
- 일단 device를 request 하여 Allocated 되면, 해당 device를 Read, Write, Reposition 할 수 있다.
- I/O 장치와 파일들 간에는 유사성이 많기 때문에, UNIX를 포함한 많은 운영체제가 이들 둘을 통합한 파일-장치 구조(file device structure)로 결합하였다.

​(3) 장치 속성 획득, 장치 속성 결정 (get device attributes, set device attributes)

(4) 장치의 논리적 부착 또는 분리 (Logically attach or detach devices)

* 정보의 유지(Information Maintenance)

​(1) 시간과 날짜의 설정과 획득 (get time or date, set time or date)
- 대부분의 시스템은 현재 시간(time()), 날짜(date())를 되돌려 주는 System Call을 가지고 있다.

(2) 시스템 데이터의 설정과 획득 (get System data, set System data)
- 현재 사용자 수, OS의 Version number, Free Memory와 같은 시스템에 관한 정보를 알려주기도 한다.

(3) 프로세스, 파일, 장치 속성의 획득 (get process, file, or device attributes)
- 운영체제는 현재 실행되고 있는 프로세스들에 관한 정보를 가지고 있다.

​(4) 프로세스, 파일, 장치 속성의 설정 (set process, file, or device attributes)
- 운영체제는 현재 실행되고 있는 프로세스들에 관한 정보에 접근하여 재설정할 수 있다.

* 통신(Communication)

- Communication에는 Message Passing과 Shared Memory model이 있다.​

1. Message Passing Model
- 통신하는 두 process가 정보를 교환하기 위해 서로 메시지를 주고받는다.
- Message는 두 프로세스 사이에서 직접 교환되거나, mailbox를 통해 간접적으로 교환될 수 있다.

2. Shared Memory Model
- process는 다른 process가 소유한 Memory 영역에 대한 접근을 하기 위해 System call을 사용한다.
- 정상적으로, OS는 한 process가 다른 process의 memory를 접근하는 것을 막으려고 한다.
- 이에, Shared Memory Model에서는 이런 제한을 제거해야 할 필요성이 있다.

​- 대부분의 System은 두 가지(Message Passing, Shared Memory) 모두를 구현한다.
- Message Passing은 Conflict가 없기 때문에, 소량의 데이터를 교환하는데 좋다.
- Shared Memory는 최대 속도와 편리한 통신을 할 수 있지만, 동기화 부분에서 문제점이 있다.

(1) 통신 연결의 생성, 제거 (create, delete communication connection)

(2) 메시지의 송신, 수신 (Send, Receive Messages)

(3) 상태 정보 전달 (Transfer status information)

(4) 원격 장치의 부착(Attach) 및 분리(Detach)

* 보호(Protection)

- 과거에, Protection은 다수의 사용자를 가지는 다중 프로그램 시스템에서만 고려되는 문제였다.
- Networking과 Internet의 출현으로, 서버에서 휴대용 컴퓨터까지 모든 컴퓨터 시스템에서 고려해야 한다.

2.5 시스템 프로그램(System Programs)

- 시스템 프로그램은 시스템 유틸리티(System Utility)로 알려져 있으며, 프로그램 개발과 실행을 위해
보다 편리한 환경을 제공한다.

- 시스템 프로그램(System Program)은
파일 관리, 상태 정보, 파일 변경, 프로그래밍 언어 지원, 프로그램 적재와 수행, 통신, 백그라운드 서비스
의 범주로 분류할 수 있다.

- 대부분의 운영체제는 시스템 프로그램과 함께 일반적인 문제점을 해결하거나, 일반적인 연산을 수행하는 데 유용한 프로그램들도
제공한다.
- 이러한 Application Program에는 Web Browser, Word Processor, Database System 등이 포함된다.

2.6 운영체제 설계 및 구현

* 설계 목표 (Design Goals)

- 요구 조건은 근본적으로 사용자 목적과 시스템 목적의 두 가지 기본 그룹으로 나눌 수 있다.
- 사용자 입장에서, 시스템은 사용하기에 convenient to use, easy to learn, Reliable, safe, fast 해야 한다.
- 시스템적 입장에서, 운영체제는 설계, 구현, 유지 보수가 쉬워야 하며, 적응성, 신뢰성, 효율성 등을 가져야 한다.

* 기법과 정책 (Mechanisms and Policies)

- 기법(Mechanism)은 how to do something(어떻게 할 것인가)을 결정하는 것이다.
- 정책(Policy)는 what will be done(무엇을 할 것인가)를 결정하는 것이다.

* 구현 (Implementation)

- 초창기 운영체제는 어셈블리어로 작성되었으며, 현재 대부분의 운영체제는 고급 언어로 작성된다.
- 운영체제를 고급 언어로 구현하는 것에 대한 단점은 속도가 느리고, 저장 장치가 많이 소요되는 것이다.
- 하지만, 고급언어를 통한 sophisticated optimization을 수행하고, 좋은 자료구조와 알고리즘을 사용함으로써 위의 문제를 해결하고, 성능 향상을 이룰 수 있다.

2.7 운영체제 구조 (Operating-System Structures)

* 간단한 구조(Simple Structure)

- 간단한 구조를 가지고 있는 운영체제로, MS-DOS가 있다.
- MS-DOS는 interface와 functionality 계층이 잘 분리되어 있지 않다.
- 예를 들어, Application Program은 basic I/O routine을 통해 display와 disk drive에 직접 쓰기가 가능하다.
- 따라서, User Program이 고장 나게 되면 시스템 전체가 고장 나게 된다.

* 계층적 접근(Layered Approach)

- 적절한 hardware support가 있을 경우, 운영체제는 보다 적절하게 분할될 수 있다.
- 계층적 접근 방식에서는, 운영체제가 여러 층으로 나누어진다.
- 최하위 층(Layer 0)는 Hardware이고, 최상위 층(Layer N)은 User Interface이다.|
- 계층적 구조에서, 특정 층 M은 자료구조와 상위 층에서 호출할 수 있는 루틴의 집합으로 구성된다.
- 층 M은 다시 자신의 하위 층에 대한 연산을 호출할 수 있다.

- 계층적 접근 방식의 장점은 구현과 디버깅이 간단하다는 점이다.
- 각 층들은 자신의 하위층들의 서비스와 연산들만을 사용하도록 되어 있으며, 이 점이 디버깅을 단순화한다.
- 하위 층부터 구현을 시도하고, 완벽히 디버깅이 끝난 뒤에 상위 층의 구현을 시도하게 된다.
- 이에, 디버깅 시에 오류가 나게 되면, 그 하위 층들은 모두 디버깅이 완료되었기 때문에 해당 층에 오류가
  있다는 것을 알 수 있다.

- 계층적 접근 방식의 어려운 점은 여러 층을 적절히 정의하기가 어렵다는 것이다.
- 각 층은 자신의 하위 계층들만 사용할 수 있기 때문에, 설계 시에 신중하게 고려해야 한다.​

- 계층적 구현 방법의 또 다른 문제점은 다른 유형의 구현 방법보다 효율성이 낮다는 점이다.
- 각 층에서, 매개 변수들이 변경되거나, 데이터가 전달될 필요가 있는 상황이 발생할 수 있다.
- 이에 System Call에 Overhead를 추가하며, 다른 구조들보다 System Call 수행 시간이 오래 걸릴 수 있다.

* 마이크로 커널(Microkernels)

- 1980년대 중반에, Carnegie-Mellon 대학교의 연구자들이 MicroKernel 접근 방식을 사용하여 Kernel을 모듈화한 Mach를 개발하였다.
- 이 방법은 중요치 않은 구성 요소들을 커널로부터 제거하고, 그것들을 System 및 User level Program으로 구현하여 운영체제를 구성하는 방법이다.

- 마이크로 커널의 주 기능은 Client Program과 User Space에서 수행되는 다양한 서비스 간에
Communication을 제공하는 것이다. (통신은 Message Passing을 통해 제공된다.)

- 마이크로 커널의 장점은 운영체제의 확장이 용이하다는 점이다.

- 모든 새로운 서비스는 사용자 공간에 추가되므로, Kernel의 변경을 필요로 하지 않는다.
- 불가피하게 커널이 변경되어야 할 때에도, 비교적 커널의 크기가 작아 변경할 대상이 작은 경우가 많다.

​- 마이크로 커널의 단점은 system-function overhead가 증가하여, 성능이 나빠진다는 점이다.

* 모듈(Modules)

- 이 방법에서 커널은 핵심적인 구성요소의 집합을 가지고 있고, 부팅 시에 또는 실행 중에 부가적인 서비스들을 모듈을 통하여 link 한다.
- 설계 시 중요한 점은, 핵심 서비스를 제공하고 다른 서비스들은 커널이 실행되는 동안 동적으로 구현하는 것이다.

​- 전체적인 결과는 각 부분이 정의되고 Protected Interface를 가진다는 점에서 계층적 구조와 비슷하다.
하지만, Module에서 임의의 다른 Module을 호출할 수 있다는 점에서 계층적 구조보다 유연하다.

- 중심 모듈은 단지 핵심 기능만을 가지고 있고, 다른 모듈의 적재 방법과 모든 모듈들과 어떻게 통신하는지 안다는 점에서 MicroKernel과 유사하다. 하지만, 통신하기 위하여 메시지 전달을 호출할 필요가 없기 때문에 더 효율적이다.

* 혼용 시스템(Hybrid Systems)

- 하나의 구조만을 채택한 운영체제는 거의 존재하지 않으며, 보통 여러 구조를 결합한 혼용 구조로 구성된다.
- Linux와 Solaris는 Monolithic 구조면서, 새로운 기능을 동적으로 추가할 수 있는 Module을 사용한다.
- Windows는 Monolithic 구조면서, 동적으로 적재 가능한 커널 모듈도 지원한다.

2.8 운영체제 디버깅(Operating-System Debugging)

- 디버깅(Debugging)란 Hardware와 Software에서의 시스템 오류를 발견하고, 수정하는 행위이다.

​

* 장애 분석(Failure Analysis)

- 프로세스가 실패했을 때, 운영체제는 프로세스가 사용하던 메모리를 캡처한 뒤 'core dump'를 취하고 이후의 분석을 위해 파일로 저장한다.
- 커널 장애는 Crash라고 불린다. 해당 오류 정보는 로그 파일에 저장되고, 메모리의 상태가 'Crash dump'에 저장된다.

​

* 성능 조정(Performance Tuning)
- 병목(Bottlenecks) 지점을 제거함으로써 성능을 향상시키려고 하는 것도 디버깅에 포함된다.
- 이에 병목 지점을 발견하기 위하여 시스템 성능을 감시할 수 있어야 하며, 시스템 동작을 측정하고 표시할 수 있는 방법을 가지고 있어야 한다. ((ex) Windows 작업 관리자.)

2.9 운영체제 생성(Operating-System Generation)

- 운영체제는 다양한 주변 구성을 가진, 여러 부류의 기계에서 수행되도록 설계되는 것이 일반적이다.
- 이 경우, 시스템은 각 specific computer site를 위해 구성되거나 또는 생성되어야 한다.
- 이 절차를 시스템 생성(SYSGEN)이라고 한다.

2.10 시스템 부트(System Boot)

- 운영체제가 생성된 이후에는, 하드웨어에 의해 사용 가능해야 한다.
- 대부분의 컴퓨터 시스템에서는 Bootstrap Program이 커널을 찾은 뒤, Main Memory에 load 하고, 수행을 시작한다.
- PC와 같은 일부 컴퓨터 시스템은 단순한 Bootstrap Program이 좀 더 복잡한 Bootstrap Program을 디스크로부터 적재하고, 이 Bootstrap Program이 다시 커널을 load 하는 2단계 절차를 사용한다.

​- 컴퓨터가 전원을 켜거나, 재부팅 등의 사건을 받으면 명령 레지스터는 미리 지정된 메모리 위치를 가리키고, 그곳에서부터 실행을 시작한다. (해당 위치에는 최초의 Bootstrap Program이 존재한다.)
- RAM은 시스템 시작 시에 알 수 없는 상태가 되기 때문에, Bootstrap Program은 ROM 안에 저장된다.

​- bootstrap program은 먼저, 기계의 상태를 진단하여 이상이 없는지 확인한다.
- 이후, CPU Register, device Controller, Main Memory 등 시스템 전반에 걸쳐 초기화한다.
- 위의 작업이 끝나면, bootstrap program은 운영체제를 시작한다.

​- 휴대전화, 태블릿 등의 시스템들은 운영체제의 크기가 작은 경우가 많아서 운영체제 전체를 ROM에 저장한다.
- 이 방식은 bootstrap code가 변경되면, ROM을 변경해야 한다는 점이다.
- 이 문제를 해결하기 위해 쓰기가 가능한 EPROM을 사용할 수 있다.

-Reference-
Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』