Limited Direct Execution, CPU scheduling(RR, MLFQ)

Direct Execution

 

OS가 program을 시작할 때

① process list에 process entry를 만들고

② memory를 할당하고

③ program code를 memory에 load하고

④ 진입점을 찾아 그 지점으로 분기한다.

 

program을 cpu상에서 직접 실행시키므로 빠르게 실행된다. 그러나 한번에 한 프로그램만 실행할 수 있다는 단점을 가지고 있다.

한번에 한 프로그램만 돌릴 수 있다는 것은, 일단 프로그램이 시작되면, cpu는 현재 프로그램이 cpu를 자발적으로 반환할 때까지 기다려야 한다는 의미이다. 

이 경우에 time sharing이 힘들어지고, Limited direct execution이 등장했다.

 

 

 

 

 

 

Limited Direct Execution

1. 제한된 연산

 

프로세스가 특수한 종류의 연산을 수행하길 원할 때, application의 execution mode를 두 가지 제공한다.

kernel mode : I/O와 같은 privileged operation을 수행할 수 있다. machine의 full resource에 접근 가능

user mode : privileged operation을 수행할 수 없다. user process는 보통 이 mode에서 동작한다.

 

 

user process가 privileged operation을 수행해야 하는 경우도 존재할 것이다. 이 경우를 위해 두가지 명령어가 있다.

trap과 return-from-trap이다.

 

system call을 실행하기 위해서 trap 명령어 수행

trap: kernel 안으로 분기하는 동시에 특권 수준을 kernel mode로 상향조정

 

호출한 process의 register를 kernel stack에 저장한다. return-from-trap이 불리면 k-stack(kernel stack)에서 pop하는 방법으로 돌아간다.

 

return-from-trap: 특권수준을 user mode로 하양조정하면서 호출한 사용자 프로그램으로 return

 

trap이 발생하면 어떤 code를 실행할 지가 중요하다. 주소를 명시해줘버리면 kernel 내부의 원하는 지점을 접근할 수가 있기 때문!(위험...)

그래서 kernel은 부팅 시에 trap table을 만든다. OS는 특정 명령어를 이용해 하드웨어에게 trap handler의 위치를 알려준다.

 

2. 프로세스 간 전환

 

OS는 cpu를 다시 획득하여 process를 전환해야 한다. 운영체제가 cpu를 획득하는 방법에는 크게 두 가지가 있다.

 

Cooperative

 

OS가 user application이 cpu control을 줄 것이라고 믿는 것. 즉 application 자체에서 system call을 호출해 cpu를 반환해 준다.

* 이 방법은 악의적, 혹은 버그가 있어 process가 무한 루프에 빠져 system call을 호출하지 않는 경우에 문제가 생긴다.

 

Non-Cooperative

 

이름에서 알 수 있다시피, cooperative 방법과 정 반대이다. OS는 timer interrupt를 이용해 cpu 제어권을 다시 획득한다. 즉 hardware support가 필요한 방법. 

interrupt가 발생하면 실행되던 process는 중단되고 interrupt handler가 발생한다.

 

timer interrupt가 일어나면

① 실행되던 process의 register를 그 process의 k-stack에 저장한다.

② kernel mode로 이동

③ trap handler로 jump

 

 

 

 

 

 

CPU Scheduling

 

주어진 runnable processes의 집합 중에서 다음에 어떤 process를 동작시켜야 하는지 결정한다.

스케쥴링 접근 방법에는 non-preemptive scheduling, preemptive scheduling 두 가지가 있다.

 

 

1. Non-preemptive scheduling

 

running process가 자발적으로 yield하기를 기다린다. 이 경우 process가 OS에 cooperative 해야 한다.

말 그대로 OS가 다른 프로세스를 마음대로 멈추게 할 수 없다.

 

 

2. Preemptive scheduling (현대 스케쥴러)

 

scheduler가 process를 interrupt하고 context switching을 강요할 수 있다. 이 경우에도 문제점이 있다.

만약 공유 데이터의 update중에 process가 preempt된다면? 공유 데이터가 손실된다면 해당 데이터를 참조하고 있던 모든 process의 동작에 문제가 생길 수 있다.

또는 만약 system call이 preempt된다면? 

(뒤에 소개되는 알고리즘으로 해결할 수 있음)

 

 

스케쥴링에도 여러가지 알고리즘이 있다. 여기에서 알고리즘들의 퀄리티를 측정할 식은 아래와 같다.

 

 

scheduling 되기까지 기다린 시간

 

 

 

● FIFO

 

First-In, First-Out. 말 그대로 온 순서대로 scheduling이 된다.

당연히 non-preemptive한 스케쥴링 방법이다.

job이 동등하게 다뤄지므로 starvation 문제는 발생하지 않지만 convoy effect는 발생할 수 있다.

 

starvation은 굶주림이란 뜻이다. 여기서는 한 프로세스가 실행되지 못하고 계속 기다리는 상황을 의미한다.

convoy effect가 발생하면, 현재 처리중인 일보다 더 짧은 일이 도착해도 기다려야 한다. 이는 짧은 시간의 job에게 공정하지 못한 scheduling 방법이다.

 

● SJF

 

Shortest Job First. 말 그대로 현재 도착한 process들 중 가장 짧은 일부터 수행하는 스케쥴링 기법이다.

모든 작업이 동시에 도착한다면, optimal turnaround time임을 증명할 수 있다.

non-preemptive한 스케쥴링 방법

그러나 이 방법에도 문제점이 있다.

작업들이 동시에 도착하지 않고 아무때나 도착한다면 optimal한 방법이 아니다.

또 잠재적으로 starvation이 발생할 수 있다. 만약 매우 오래 걸리는 프로세스가 도착했는데, 이 후에 계속 짧은 프로세스가 도착한다면 이 긴 프로세스는 영원히 실행되지 않을 수도 있다...

 

● STCF

 

Shortest Time to Completion First

이는 SJF의 preemptive 버전이다. running job의 remaining time과 new arrival job의 run time을 비교해 new job이 더 짧으면 running job을 preempt한다.

 

● RR

 

Round-Robin

위의 수식들 중 turnaround보다는 response time에 포커스를 둔 알고리즘이다. 

preemptive한 스케쥴링 방법

time slice 동안 실행한 후 실행 queue의 다음 작업으로 전환.

이 때 time slice가 너무 짧다면 context switching cost가 전체 성능이 큰 영향을 끼진다. 너무 자주 process가 바뀌기 때문이다.

반대로 또 너무 길다면 덜 responsive하게 된다.

어떤 크기의 slice가 좋느냐는 정확한 optimal한 값이 존재하지 않는다. 그냥 heuristic한 방법으로 가장 좋은 성능의 크기로 정한다. 보통 10~100ms를 사용한다고 한다.

이 방법은 starvation이 없으며 response time을 향상시키고, 따라서 time-sharing에 좋은 방법이다.

 

 

그러나 모든 작업이 CPU'만' 사용하는 것은 아니다. 우리는 입출력 연산도 고려해 주어야 한다. 

예를 들어 process A는 10ms동안 실행 후 입출력을 수행하고, process B는 I/O 연산이 없는 경우를 생각해보자. 각 작업은 50ms의 CPU time을 필요로 한다.

가장 간단한 해결책은 A를 먼저 끝낸 다음 B를 끝내는 것이다.

한 눈에 보기에도 매우 비효율적인 방법이다. A와 B를 모두 끝내는 데 140ms가 소요된다.

 

이제 STCF를 이용해 조금 더 효율적으로 바꿔보자. A가 5개의 10ms의 작은 작업으로 분할되고, B는 하나의 50ms 덩어리라는 사실을 활용해보자.

A의 각 10ms를 독립적으로 다뤄보면 어떨까? 그러니까 시스템이 시작될 때 10ms 작업들과 50ms 작업을 스케줄하는 것이다. STCF의 경우 가장 짧은 작업을 선택하므로 이 경우에는 A가 된다. 10ms A가 완료되면 B만 남게되므로 B가 실행된다. 그 후에 A의 입출력이 완료된다면 실행되고 있던 B를 preempt해서 10ms A를 다시 실행한다. 이 과정을 그림으로 그려보면 다음과 같다.

 

시간을 정말 많이 절약할 수 있다. 이렇게 한 프로세스의 입출력이 끝나기를 기다리는 동안 CPU가 다른 프로세스에 의해 사용되는 것을 overlap(중첩)이라고 한다. overlap이 있다면 cpu의 활용률은 더 올라간다.

 

 

스케줄러의 최종 목표는 무엇일까?

turnaround time을 optimize하고

interactive job에 대한 response time을 최소화하고

workload에 대한 priori knowledge 없이 스케줄링 할 수 있는 것이다.

아래의 MLFQ가 해결할 수 있을 것이다.

 

● MLFQ

 

Multi-level Feedback Queue

말 그대로 process간 level이 존재해 높은 level, 즉 더 높은 우선순위를 가지면 그 process를 실행하겠다는 것이다. (Rule 1)

이 우선순위는 process의 behavior에 따라 결정된다.

 

Rule 1. If Priority(A) > Priority(B), A runs

 

같은 우선순위를 가진다면 어떨까? 이때는 RR scheduling을 사용한다. (Rule 2)

 

Rule 2. If Priority(A) = Priority(B), scheduling with RR

 

프로세스가 영영 같은 priority를 가질 수는 없다. 그럴경우 starvation problem이 발생하기 때문이다. 높은 priority의 작업만 계속 들어온다면, 상대적으로 낮은 priority를 가진 job은 영원히 수행되지 않는 경우가 생긴다. 그렇기때문에 MLFQ는 priority를 주기적으로 바꿔줘야한다.

Priority를 바꿔주기 위해 Rule 3과 Rule 4가 있다.

 

Rule 3. 작업이 system에 진입하면, 가장 높은 priority queue에 놓인다.

Rule 4a. 주어진 time slice를 모두 사용하면 한 단계 낮은 queue로 이동한다.

Rule 4b. time slice를 다 쓰기 전에 cpu를 포기하면 같은 priority level을 유지한다

 

이 Rule의 경우 문제점이 생긴다.

 

1. Starvation Problem

오래 실행되는 job은 너무 많은 interactive job 때문에 starve(리소스를 오랜기간 할당받지 못함)할 수 있다.

보통 workload는 interactive job과 cpu-intensive job이 함께 있다. interactive job은 실행 시간이 짧고, 짧은 response time을 요구한다. 반대로 cpu-intensive job은 많은 cpu time 을 요구하고 response time은 상대적으로 덜 중요하다.

 

2. 프로그래머가 자신의 프로그램에 유리하게 프로그램을 작성할 수 있다.

Rule 4a와 4b가 이 문제에 기여한다. 만약 time slice 직전에 micro sleep system call을 호출하게 되는 경우를 생각해보면 OS는 해당 application을 top level queue에 배치하게 된다.

 

3. 시간에 흐름에 따라 behavior가 변할 수 있다

 

Starvation을 피하기 위해 가장 간단하게 Rule을 수정하는 방법은 주기적으로 모든 작업의 우선순위를 상향 조정(Priority Boost) 하는 것이다.

 

Rule 5. 일정 time period가 지나면 시스템의 모든 작업을 topmost queue로 이동시킨다.

 

Rule 5를 통해 1번의 starvation problem을 해결할 수 있다.

저 `일정 time period`는 어떻게 정하는 것일까? John Ousterhout는 이런 값을 voo-doo constants(부두 상수)라고 불렀는데, 너무 크면 starvation이 있을 수 있고, 너무 작으면 interactive job이 적절한 양의 cpu 시간을 사용할 수 없게 된다. 부두상수는 가능한 한 피하는 것이 좋다.

 

위의 문제점 2를 극복하기 위해서는 Rule 4를 고쳐야 한다. MLFQ의 각 단계에서 총 CPU 사용 시간을 측정한다는 아이디어로 Rule 4a, 4b는 아래와 같이 수정된다.

 

Rule 4. 주어진 단계에서 time slice를 소진하면(CPU를 몇 번 양도했는지는 신경쓰지 않음), 우선 순위는 낮아진다 (한 단계 아래 queue로 이동).

 

정리해보자면 MLFQ는

• Preemptive priority scheduling 이고,
• Time slice에 기반한 time-shared 이고,
• process의 priority들이 다이나믹하게 바뀌며,
• Starvation Problem이 발생하지 않는다.