05. CPU Scheduling (3/3) / 06. Process Synchronization (1/5)

1. Scheduling이 필요한 이유: CPU를 오래사용 하는 프로세스와 사용자와 상호작용하는 프로세스 등 종류가 많으므로

-> 작동방식이 다양하기 때문에 모두 똑같이 주는 것이 효율적이라 볼 수 없다.

2. Mulilevel Queue: 우선순위 별로 프로세스의 큐를 가지고 있음

-> 우선순위 우선, 같은 순서끼리는 먼저 온 순서

가. Ready queue를 여러 개로 분할: 각 큐마다 독립적인 스케줄링 알고리즘을 가짐

1) foreground (interactive): 라운드 로빈 방식

2) background (batch - no human interaction): fcfs 먼저 온 순서대로 하는 방식

다. 큐에 대한 스케쥴링이 필요

1) Fiexed priority scheduling

2) Time slice: starvation 문제 때문에 어느 정도 시간을 제한을 두는 방식 fore: 80, back: 20

3.  Multilevel Feedback Queue: Multilevel Queue에서 우선순위가 변하는 방식

가. 처음 들어오는 프로세스가 가장 높은 우선순위로 라운도로빈 (대신 시간이 짧음)

나. 아래 큐로 이동하면 할당 시간은 더 길어짐

다. 맨 마지막 큐는 FCFS 방식으로 작동

4. Multiple-Processor Scheduling: 스케쥴링이 더욱 복잡해짐

가. Homogeneous Processor: Queue에 한 줄로 세워거 각 프로세서가 알아서 꺼내가게 함

-> 반드시 특정 프로세서에 수행되어야 하는 프로세스가 있는 경우에 문제가 더 복잡해짐

5. Load Sharing: 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘

6. Symmetric Multiprocessing (SMP): 각 프로세스가 알아서 스케줄링

7. Asymmetric Multiprocessing: 하나의 CPU가 Control을 담당하고 나머지 CPU가 따르는 방식

8. Real-Time Scheduling: 정해진 시간내에 반드시 수행되어야 함(Deadline)

가. Hard real-time Systems: 반드시 정해진 시간 안에 끝내야 함

나. Sotft real-time Systems: 반드시 지킬 필요는 없어서 일반 프로세스보다 높은 우선순위로 조절

9. Thread Scheduling

가. Local Scheduling: 사용자 프로세스가 직접 관리 (운영체제는 모름)

나. Global Scheduling: Kernel levle thread로 커널의 단기 스케줄러가 어떤 thread를 스케줄할 지 결정

10. Algorithm Evaluation

가. Queueing models: 이론적인 방법, 빠른 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index 값을 계산

나. Implementation(구현) & Measurement(성능 측정): 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

->Queueing models 와 반대로 Queueing은 이론적 계산이고, 위는 실제 측정값으로 비교

다. Simulation(모의 실험): 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

---

1. Process Synchronization: 데이터가 저장되어 있는 위치에서 읽고 연산 결과를 반영하기 때문에 필요함

ex) CPU : Memory / 컴퓨터내부 : 디스크 / 프로세스 : 그 프로세스의 주소 공간

2. OS에서의 race condition(여러 프로세스들이 동시에 공유 데이터를 접근하는 상황) 일 때,

가. 작업이 한 공간에서 진행 중이면, 그 곳에서 interrupt를 발생시키지 못 하게 함

나. 커널 모드에서 수행 중일 때 CPU를 preempt 하지 않음(커널 모드에서 사용자 모드로 돌아갈 때 preempt)

다. (CPU가 여러개 일 때, 위 두 방법은 소용이 없음) 데이터에 lock을 걸음

-> 동기화가 잘 되어야 한다.