OSTEP 07-cpu-sched(CPU Scheduling) 문제 풀이

잘못된 풀이가 있다면 댓글 부탁드립니다.

숙제

scheduler.py 프로그램은 응답 시간, 반환 시간, 총 대기 시간의 관점에서 여러 스케 줄러가 어떻게 동작하는지를 볼 수 있게 한다.

자세한 내용은 README를 참조하시오.

 

문제

1. 길이가 200인 세 개의 작업을 SJF와 FIFO 스케줄링 방식으로 실행할 경우 응답
시간과 반환 시간을 계산하시오.

[SJF]
job0: 응답 시간: 0, 반환 시간: 200
job1: 응답 시간: 200, 반환 시간: 400
job2: 응답 시간: 400, 반환 시간: 600

[FIFO]
job0: 응답 시간: 0, 반환 시간: 200
job1: 응답 시간: 200, 반환 시간: 400
job2: 응답 시간: 400, 반환 시간: 600

2. 같은 조건이지만 작업의 길이가 각각 100, 200 및 300일 경우에 대해 계산하시오.

[SJF]
job0: 응답 시간: 0, 반환 시간: 100
job1: 응답 시간: 100, 반환 시간: 300
job2: 응답 시간: 300, 반환 시간: 600

[FIFO]
job0: 응답 시간: 0, 반환 시간: 100
job1: 응답 시간: 100, 반환 시간: 300
job2: 응답 시간: 300, 반환 시간: 600

3. 2번과 같은 조건으로 타임 슬라이스가 1인 RR 스케줄러에 대해서도 계산하시오.

job0: 응답 시간: 0, 반환 시간:
3 // 병행되는 작업 수 (job0, job1, job2)
* (100 - 1)
= 297 // job0, 1, 2가 99초 만큼 실행됐을 때의 시간
+ 1 // job0이 100초 실행됐을 때의 시간
= 298

job1: 응답 시간: 1, 반환 시간:
(298 + 2) 
= 300 // job1과 2도 100초만큼 실행됐을 떄의 시간
+ (
	2 // 병행되는 작업 수 (job 1, job2)
    * (100 - 1)
    = 198 // job1과 2가 199초 실행됐을 때의 시간
    + 1 // job1이 200초 실행됐을때의 시간
)
= 499

// 사실상 job2 단일 작업만 남은 상황
job2: 응답 시간: 2, 반환 시간:
(499 + 1) 
= 500 // job2도 200초 만큼 실행됐을 떄의 시간
+ (
	1 // 병행되는 작업 수 (job2)
    * (100 - 1)
    = 99 // job2가 299초 실행됐을 때의 시간
    + 1 // job1이 300초 실행됐을때의 시간
)
= 600

4. SJF와 FIFO가 같은 반환 시간을 보이는 워크로드의 유형은 무엇인가?

작업이 작은 순대로 들어오는 상황
(위 상황대로라면 동시에 들어오는 것이 아니더라도 반환 시간이 동일)

5. SJF가 RR과 같은 응답 시간을 보이기 위한 워크로드와 타임 퀀텀의 길이는 무엇인가?

작업의 길이가 같거나 작은 순으로 들어오면서
타임 퀀텀(타밍 슬라이스)의 길이가 가장 긴 작업의 길이와 같거나 큰 경우

6. 작업의 길이가 증가하면 SJF의 응답 시간은 어떻게 되는가? 변화의 추이를 보이기
위해서 시뮬레이터를 사용할 수 있는가?

비선점형 스케줄링이기 때문에
작업이 끝까지 실행되고 나서 다음 작업이 실행되므로
작업의 길이가 증가할수록 다른 작업의 응답 시간이 길어집니다.

7. 타임 퀀텀의 길이가 증가하면 RR의 응답 시간은 어떻게 되는가? N 개의 작업이
주어졌을 때, 최악의 응답 시간을 계산하는 식을 만들 수 있는가?

타임 퀀텀(타임 슬라이스)의 길이가 선점의 주기가 되는 스케줄링이므로
길이가 증가하면 모든 작업의 응답시간이 길어집니다.

최악의 경우는 타임 슬라이스가 가장 긴 작업의 길이보다 길어서 선점할 수 없는 경우

출처

원서

http://www.ostep.org

 

번역본

https://github.com/remzi-arpacidusseau/ostep-translations

 

문제

https://github.com/remzi-arpacidusseau/ostep-homework