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

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』