4주차. CPU Scheduling (2) - FCFS, SJF, Priority, RR

FCFS (First come First Service)

• non-preemptive 방식, 먼저 잡으면 빼앗기지 않고 먼저 처리한다.
• 만약 첫 프로세스의 소요시간이 매우 길다면 뒤의 프로세스의 소요시간에 상관 없이 기다려야 하므로 매우 비효율적이다.
• 첫 프로세스의 소요시간에 매우 의존적이다.
• Convoy effect 가 발생할 수 있다. - short process behind long process

문제

P 프로세스 : burst Time

- P1 : 24

- P2 : 3

- P3 : 3

p1 → p2 → p3 순서로 매우 비슷한 시간에 왔다고 가정

Average wating time

• p1 (0) + p2 (24) + p3 (27) = 51 / 3 == 17

---

SJF (Shortest Job First)

• cpu burst time이 가장 짧은 프로세스부터 처리한다.
• average watng time이 최소임을 보장한다. (단, preemptive한 경우에만)

non-preemptive 버전

• 일단 가장 cpu burst시간이 짧은 프로세스를 처리중일 때, 남은 cpu burst time보다 짧은 프로세스가 와도 현재 cpu burst가 완료될 때까지 빼앗지 않는다.

 

preemptive 버전

• 위와 반대로 처리중에라도 cpu burst가 더 짧은 프로세스가 오면 중단하고 해당 cpu burst를 처리한다.
• SRTF (Shortest Remaining Time First)
• 남은 cpu burst타임을 비교해서 가장 짧은 것부터 처리한다. 따라서 평균 대기 시간이 가장 짧은 기법.
• 처리하다가 burst time이 더 짧은게 오면 변경, 남은 burst time은 다시 큐에 넣는다.
• 문맥교환 오버헤드에 대해 고려해봐야 한다.

 

SJF의 Starvation 문제

• 극단적으로 cpu 사용시간이 짧은 프로세스를 선호하므로 cpu사용 시간이 긴 프로세스는 무한정 기다려야하는 상황이 발생할 수 있다.
• 자신 보다 짧은 cpu burst를 가진 프로세스가 계속 유입된다면 해당 프로세스는 진행 될수가 없음.

-> 해결 방법 : Aging

• 대기를 할 수록 나이를 먹도록 한다. 일정 나이가 되면 먼저 진행하도록 하므로서 Starvation을 방지한다.
• 우선순위를 올리는 방식인 것. 단, 기준치를 어떻게 잡아야 할 지에 대한 문제가 있다. 완벽한 해결법이 될 수 없음.

 

CPU burst time 예측 문제

• SJF를 구현하기 위해서는 프로세스의 미래의 CPU burst time을 알아야 하는데 현재 처리할 cpu burst의 시간을 어떻게 알 수 있을까?
• 처리에 걸리는 시간을 알아야 그에 맞게 스케줄링이 가능하다.

→ 해결 방법 : 예측(추정)한다

• CPU bound job의 경우 일반적으로 CPU burst time이 길고, I/O bound job의 경우 CPU burst time이 짧다.
• 또한 이전에 해당 프로세스를 처리했을 때의 cpu burst time을 이용한다.
• 이 또한 부정확하다. 워드 프로세스를 켰다가 바로 끌 수도 있지만 한시간 동안 켜놓고 작업을 할 수도 있다.

결론 : 프로세스의 종료시간을 파악하기 어렵고 Starvation 현상이 일어날 수 있어서 잘 사용하지 않는다.

 

---

Priority Scheduling

• A priority number is associated with each process
• 우선 순위가 가장 높은 프로세스에게 CPU를 할당한다. (작은 수가 우선순위가 높음)

preemptive

• 처리중 우선순위가 더 높은 프로세스가 왔을 때 빼앗고 우선 순위가 더 높은 프로세스를 처리

non-preemptive

• 처리중 우선순위가 더 높은 프로세스가 와도 현재 처리중인 프로세스를 끝내고 다음 우선순위를 처리

 

Starvation 문제

• 우선순위가 낮은 process가 우선순위가 상대적으로 높은 프로세스의 유입으로 인해 수행되지 못하고 굶어죽는 현상

-> 해결책 : Aging

• as time progresses increase the priority of the process
• 오래 기다린 프로세스의 우선순위를 점차 올림으로서 처리할 수 있도록 한다.

 

Priority Inversion 문제

• process의 우선순위와 별개로 자원의 사용에 따른 우선순위 역전 현상이다

우선순위 : T(H) > T(M) > T(L)

1. (1) - T(L)이 먼저 왔기에 우선순위는 낮지만 다른 프로세스가 없어서 바로 실행된다.
2. T(L)이 특정 구간에 대한 Semaphore를 얻는다.
3. T(L)이 Semaphore를 가지고 ciritical section을 처리하고 있는 구간이다.
4. T(H)가 ready queue에 나타나서 T(L)은 preempted되고 T(H)가 바로 수행된다. 이때 T(L)은 Semaphore를 가지고 ready queue로 가게 된다.
5. T(H)가 Semaphore가 필요없는 구간을 수행하고있다.
   • <-- priority Inversion START -->
6. T(H)가 Semaphore가 필요한 구간에 왔다.
   • 하지만 해당 세마포어는 T(L)이 갖고있으므로 T(H)는 wating(blocked)된다.
   • runnig 중인 프로세스가 없어졌으므로 ready queue에 있던 T(L)이 다시 running 한다.
7. T(L)이 마저 critical section을 수행하는 구간이다.
8. T(M)이 ready queue에 왔다. 이로인해 T(L)은 다시 preempted되고 T(M)이 수행된다.
   • 그동안 T(H)은 T(L)의 Semaphore를 계속 wating 중이다.
   • T(L)은 Semaphore를 가진채 read queue에서 ready 중이다.
9. Semaphore와 무관한 T(M)의 수행 구간.
10. T(M)의 수행이 끝나고 T(H)는 blocked 되있으니 T(L)이 마저 running하게 된다.
11. T(L)이 마저 critical section을 수행을 한다
12. T(L)이 수행을 마치고 Semaphore를 반납한다. 그제서야 T(H)는 wating상태에서 ready 상태가 된다
    • <-- Priority Inversion END -->
13. T(H)가 Semaphore를 갖고 running한다

즉, T(H)는 우선순위가 가장 높음에도 Semaphore가 없어서 T(L)을 기다리고, T(L)은 우선순위가 낮으므로 T(M)에 밀려서 수행되었고 결과적으로 T(H)도 같이 Blocked 되면서 가장 늦게 수행되는 현상이 나타난다.

 

-> 해결책 : Priority Inheritance (Donation) Protocol

• 우선순위를 상속해줌으로서 해결할 수 있다.

T(H)에게 Semaphore가 없어서 T(L)을 기다리는 것은 정상적인 흐름이다. 하지만 T(L)이 T(M)등 다른 우선순위 프로세스에 밀리면서 T(H)도 같이 밀리는 현상이 나타나면 안된다.

 

이를 해결하기 위해 T(L)이 T(H)가 수행하려는 Semaphore를 갖고 수행하게 될 때 T(L)의 우선순위를 T(H)의 우선순위와 동일하게 임시로 변경해준다. 그렇게 함으로서 T(L)이 다른 프로세스에 밀리지 않도록 한다. T(L)의 임시우선순위는 Semaphore 를 반납할 때 되돌려준다.

 

즉, T(L)이 빨리 마저 Semaphore를 반납하게 하고 이어서 T(H)가 Semaphore를 받아서 수행될 수 있게하는 것.

여기서의 Priority Inversion 구간은 (7)구간만 해당되고, 기존 구간보다 훨씬 단축된 걸 볼 수 있다.

 

---

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다 (대략 10 ~ 100 millseconds)
• 할당 시간이 지나면 프로세스는 preempted되고 ready queue에 다시 들어가서 대기하게 된다.
• n개의 프로세스가 ready queue에 있고 할당시간이 q time unit인 경우 각 프로세스의 최대 수행 시간은 q time unit이고 프로세스끼리 총 CPU시간의 1/n을 사용하게 된다.
  • 어떤 프로세스도 (n - 1) x q time unit 이상 기다리지 않는다. Starvation이 발생하지 않는다
• q time unit 이하의 cpu burst time을 갖는다면 바로 처리 후 나오고, 그 이상이더라도 q time이 지나면 내쫒게 되는 구조
• CPU burst time이 긴 프로그램일 수록 총 대기시간이 길다. (반복적으로 대기하고 실행하게 되므로)
• 모든 프로세스가 일정 시간만 사용하고 CPU를 반납하므로 응답시간이 빠르다.

 

Time Quantum을 잘 잡는게 중요

• time quantum이 너무 크다면 → FCFS와 매우 유사해진다.
• time quantum이 너무 작다면 → 잦은 교환으로 Context Switch 오버헤드가 커진다.

 

SJF보다 turnaround time, wating time은 더 길어질 수 있지만, 최초로 cpu를 얻는 response time은 더 짧다.

 

cpu burst time이 같은 프로세스를 처리할 때의 특징

cpu burst time이 100초로 동일한 프로세스가 4개 있을 때, quantum time이 10초인 RR로 처리시 모든 cpu를 10초씩 번갈아가면서 처리하게 되고 결국 400초 대에 이르러야 4개의 프로세스가 한꺼번에 끝이난다.

• 즉, cpu burst time이 일정한 구조에서는 적절하지 못한 형태이다. 다같이 대기 시간이 길게 나올 수 있으므로

 

마치 동일한 음식 여러개를 내보내야 되는데 음식을 하나 먼저 만들고 내보내고 나머지를 진행하는 것이 아니라, 부분적으로 동시에 완성하면서 같이 대기하다가 끝에 동시에 나가게 된다.

• response time은 빠르고, wating time & turnaround time은 길어진다.

→ cpu burst 시간이 모두 동일한 프로세스라면 먼저 하나씩 처리해서 끝내는게 나을 수 있다. 전체 wating time이 줄어 든다.