PE4. Practice Exercises_5.2~5.7, 5.9, 5.12, 5.17, 5.18, 5.36_Text book

OS_운영체제 카테고리의 PE Series는

2021.10.20 - [학부공부/OS_운영체제] - 00. 운영체제 STUDY 시작

00. 운영체제 STUDY 시작

포스팅에서 소개한 text book의 연습문제를 풀이한 것을 정리한 것입니다. 해설을 참고하지 않았기 때문에 풀이에 오류가 있을 수 있습니다. 또한 운영체제 교과목 내용을 벗어나는 내용과 사견이 풀이에 포함되어 있을 수 있습니다.

 

 

5.2. Explain the difference between preemptive and nonpreemptive scheduling

선점형 스케쥴링은 OS가 CPU를 사용하고 있는 process의 수행을 강제적으로 정지할 수 있는 스케쥴링이고 비선점형 스케쥴링은 CPU burst time이 종료할 때 CPU의 제어를 스케쥴러가 가질 수 있는 스케쥴링이다.

 

선점형 스케쥴링의 경우 강제적인 process context switching이 일어나기 때문에 shared data에 대한 consistency issue가 있다. 따라서 user mode에서의 prremption은 user program이 OS가 제공하는 동기화 방식을 사용하여 data 일관성 문제를 해결할 수 있을 것이다. 선점형 kernel 내에서 shared data 접근에 대한 동기화를 kernel code에 작성되어 있어야 한다. 또한 실시간 시스템에서는 QoS가 deadline로 판단할 수 있는 real-time process를 지원하기 위해서는 선점형 스케쥴링이 필요하다.

 

 

 

5.6. What advantage is there in having different time-quantum sizes at different levels of a multilevel queueing system?

다단계 feedback queue에서 level마다 다른 time quantum을 부여한다는 것은 결국 priority에 따라 최초로 할당받는 CPU burst time이 달라진다는 것이다. Priority가 높은 process들은 더 빨리 CPU resource를 할당받는 대신 CPU burst time이 짧고 priority가 낮은 process들은 더 늦게 CPU resource를 할당받는 대신 CPU burst time을 길게 주어 형평성을 맞추는 역할을 할 수 있다. Time quantum이 priority가 높은 queue일수록 짧게 주는 가장 중요한 이유는 priority가 높은 process들이 한꺼번에 들어왔을 때 bottle neck을 줄이도록 유도할 수 있다는 것이다. 즉, priority가 높은 process는 다른 process들에 비해 더 짧게 수행되고 또 다른 priority가 높은 process에게 빠르게 CPU를 넘겨줄 수 있다. 이때 할당받은 짧은 time quantum동안 수행을 완료하지 못한 process는 feedback을 통해 더 긴 time quantum을 가지고 다른 스케쥴링 정책을 가진 queue로 가 충분한 time quantum을 할당받고 job을 완료할 수 있다. 이와 함께 service term이 긴 process에 대해 context switching을 좀 더 효율적으로 할 수 있다.

 

 

 

5.7. Many CPU-scheduling algorithms are parameterized. For example, the RR algorithm requires a parameter to indicate the time slice. Multilevel feedback queues require parameters to define the number of queues, the scheduling algorithms for each queue, the criteria used to move processes between queues, and so on. These algorithms are thus really sets of algorithms (for example, the set of RR algorithms for all time slices, and so on). One set of algorithms may include another (for example, the FCFS algorithm is the RR algorithm with an infinite time quantum). What (if any) relation holds between the following pairs of algorithm sets?

a. Priority and SJF

SJF는 CPU burst time을 기준으로 우선순위를 부여하는 일종의 priority 스케쥴링이다.(짧은 CPU burst time을 가질수록 높은 우선순위 부여)

 

b. Multilevel feedback queues and FCFS

Multilevel feedback queue에서 낮은 level의 queue는 FCFS로 동작할 수 있다.

 

c. Priority and FCFS

FCFS는 ready queue에 도착한 시간을 기준으로 우선순위를 부여하는 일종의 priority 스케쥴링이다.(도착한 시간이 빠를수록 높은 우선순위 부여) d. RR and SJF SJF는 비선점형이고 RR은 비선점형이기 때문에 서로 다른 스케쥴링이다.

 

 

 

5.9. Distinguish between PCS and SCS scheduling.

User thread는 user level에서 thread library의 지원의 받아 생성하므로 OS 스케쥴러 입장에서는 파악할 수 없다. 따라서 user thread는 process 단위(LWP)로 스케쥴링된다. PCS(process-contention scope). 즉, user thread는 process 내의 thread끼리 race 상태에 놓인다.

Kernel thread는 OS level에서 생성한 것이기 때문에 system(kernel)에서 모든 kernel thread를 관리할 수 있으므로 thread끼리 race 상태에 놓인다. SCS(system-contention scope).

 

 

 

5.12. Discuss how the following pairs of scheduling criteria conflict in certain settings. 

a. CPU utilization and response time

Ready queue의 size가 작다면 즉, CPU resource 할당을 대기하는 process의 수가 많지 않다면 CPU utilization은 response time과 반비례하는 경향을 가질 수 있지만 항상 그런 것은 아니다.

 

b. Average turnaround time and maximum waiting time

Average turnaround time이 짧을수록 maximum waiting time도 짧아질 수 있지만 SJF 스케쥴러를 사용한다면 긴 작업 시간을 가지는 process는 waiting time이 늘어나게 된다.

 

c. I/O device utilization and CPU utilization

I/O device utilization이 높아질수록 CPU utilization은 낮아지는 경향을 가질 수 있지만 ready queue의 size가 크다면, 즉 CPU resource 할당을 대기하는 process의 수가 충분하다면 스케쥴러가 CPU utilization을 높일 수 있다.

 

 

 

5.36. Explain why interrupt and dispatch latency times must be bounded in a hard real-time system.

Hard real-time system은 deadline을 strict하게 보장해야하는 system이다. Interrupt가 발생했을 때 handler가 동작하고 수행이 종료되면 return하는데 handler는 반드시 interrupt가 발생했을 때 수행되어야 하므로 deadline 내로 process를 수행하기 위해 굉장히 짧게 수행되어야 한다. 그 이후의 나머지 처리는 ISR이 담당해 별도의 task(process)를 생성해서 수행할 수 있다. 또한 새로운 real-time process가 시작되면 context switching이 될 때까지 context switching이 빨리 이루어져야 한다. 따라서 real-time system은 수행 주기가 짧은 process에게 더 높은 우선순위를 주는 우선순위 기반 선점형 스케쥴링을 이용하여 실행속도를 향상시킬 수 있다. (Rate Monotonic schduling).