[ OS ] 3. CPU Scheduling

1. CPU Scheduling

이제는 운영체제가 어떤 기준과 정책으로 스케줄링을 진행하는지에 대하여 이야기 해볼 것이다.

여러가지 정책을 공부하기위해 가정을 세워두고 조금씩 바꿔가며 설명할 것이다.

 

1.1 Turnaround time

Turnaround time = job이 생성된 시간 - 종료된 시간 (완성되는데 얼마나 걸렸냐)

Response time = job 이 도착한 시간 - 실행하기 시작한 시간 (얼마나 기다리게 했냐)

 

1.2 First In, First Out (FIFO)

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

위의 목록들을 가정하고 FIFO 정책을 따르면 아래 그림과 같이 프로세스가 실행된다

FIFO 정책은 선착순이라고 이해해도 될 것 같다.

각 프로세스의 Turnaround time 은 10, 20 , 30 이 되고 평균 Turnaround time 은 20이 된다.

하지만 각 작업은 동일한 시간동안 실행된다는 가정을 제거한다면 

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

각  Turnaround time 은 100 110 120 가되고 평균  Turnaround time 은 110가 된다. 

효율이 되게 별로게 됐다.

 

 

1.3 Shortest Job First (SJF)

이 때는 SJF 정책이 이를 해결해줄 수 있다. 이 정책은 짧은 것부터 실행시키는 정책이다.

그럼 위와 같은 그래프가 나오고 이번 경우의  Turnaround time은 각 10 20 120 이 되고  평균 Turnaround time은 50이 된다.  

 

하지만 여기서 모든 작업은 동시에 도착한다는 가정을 지운다면

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

이와 같은 그림이 나온다. 이 그림은 A가 가장 먼저 도착하고 B,C가 한발 늦게 도착했을 때 효율이 너무 떨어진다는 문제점을 갖고있다. 이의 turnaround time은 103.33 이다.

 

 

1.3 Shortest Time-to-Completion First (STCF)

위의 문제를 해결하기 위해서는 '일단 시작이 되면, 각 작업이 완료될때까지 실행된다' 라는 항목을 지우면 된다.

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

그렇다면 다른 프로세스를 실행하기 위해 프로세스의 실행을 중지하고 컨텍스트 스위치를 진행해 효율적으로 운영할 수 있다.

A 프로세스가 실행중이었지만, B,C가 도착했을 때 다시 판단을 하여 짧은 것 부터 실행시켜준 그림이다.

이의 평균 turnaround time은 50이다. 하지만 Response time 은 3.33 으로 좋지 않다.

 

1.4 Round-Robin (RR)

이를 해결하기 위해 프로세스를 쪼개서 번갈아가며 스케줄링 하는 방법이 있다.

 

이것의 response time은 2이다. 하지만 turnaround 은 별로다.

위 그림은 time slice를 2로 설정한 그림이다. time slice는 얼마나 쪼갤것이냐에 대한 용어이고 이를 크기를 정할 때에는 응답시간과 컨텍스트 스위치의 절충이 있기 때문에 결정하기 어렵다.

 

1.5 Incorporating I/O

 

모든 작업이 CPU만 사용한다는 가정을 삭제해보겠다. 

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

그럼 프로세스가 I/O작업도 할거고 Disk에 가고 Block도 될 것이다. 한 프로세스가 dick에 갈 동안 다른 프로세스 작업을 한다면 더 효율적일 것이다.

 

 

1.6 모든 가정을 삭제 했을 때

• 각 작업은 동일한 시간동안 실행된다
• 모든 작업은 동시에 도착한다
• 일단 시작이 되면, 각 작업이 완료될때까지 실행된다
• 모든 작업은 CPU만 사용한다.
• 각 작업의 실행시간을 알 수 있다.

총 작업시간을 모른다고 하면 SJF/STCF 은 사용하지 못한다. 그나마 쓸 수 있는 건 FIFO 와 RR 이다. 하지만 FIFO는 극 비효율적이므로 RR을 가장 많이 사용한다.