프로세스 스케줄링 RR 문제 모음

[김지훈JH]

라운드로빈은 선점형 스케줄링

2011 국가

프로세스들의 도착시간과 실행시간이 다음과 같다.

CPU 스케줄링 정책으로 라운드로빈 (round-robin) 알고리즘을 사용할 경우 평균 대기시간은 얼마인가?

(단, 시간 할당량은 10초이다.)

프로세스 번호	도착 시간	실행 시간
1	0초	10초
2	6초	18초
3	14초	5초
4	15초	12초
5	19초	1초

① 10.8초

② 12.2초

③ 13.6초

④ 14.4초

답:2

평균 대기시간:61/5=12.2초

작업	1	2	3	4	5	2	4
시간	10	20	25	35	36	44	46

1. 작업순서별 나열(작업2가 끝나는 시간이 20초, 그 안에 3,4,5가 모두 대기큐에 도착함으로 가능한 풀이 방법)

2. 시간 할당량 안에 미작업 프로세스는 작업의 맨 끝으로 차례대로 이동

대기시간:해당 작업의 끝난 시간 - 도착시간 - 실행시간

P1 10-0-10:0초

P2 44-6-18:20초

P3 25-14-5:6초

P4 46-15-12:19초

P5 36-19-1:16초

대기시간 합:61초

2016 계리

<보기>의 프로세스 P1, P2, P3을 시간 할당량(time quantum)이 2인 RR(Round-Robin)알고리즘으로 스케줄링할 때

평균 응답시간으로 옳은 것은?

(단, 응답시간이란 프로세스의 도착 시간부터 처리가 종료될 때까지의 시간을 말한다.

계산 결과값을 소수점 둘째자리에서 반올림한다)

프로세스	도착시간	실행시간
P1	0	3
P2	1	4
P3	3	2

① 5.7

② 6.0

③ 7.0

④ 7.3

답:1

작업	P1	P2	P1	P3	P2
시간	2	4	5	7	9

응답시간 구하기(문제상 정의는 프로세스의 도착 시간부터 처리가 종료될 때까지의 시간)

시간-도착시간

P1 5-0:5(P1은 5초에 처리가 종료되었음)

P2 9-1:8(P2는 9초에 처리가 종료되었음)

P3 7-3:4(P3는 7초에 처리가 종료되었음)

(5+8+4)/3=5.66666

원래 응답시간은 프로세스가 운영체제에게 작업 요청하고 그에 대한 첫! 응답을 받기 까지의 시간이라고 함

작업이 완료될때까지의 시간은 아니라고 함

2017 국가

다음 프로세스 집합에 대하여 라운드 로빈 CPU 스케줄링 알고리즘을 사용할 때 프로세스들의 총 대기시간은?

(단, 시간 0에 P1, P2, P3 순서대로 도착한 것으로 하고, 시간 할당량은 4밀리초로 하며, 프로세스 간 문맥교환에

따른 오버헤드는 무시한다)

프로세스	버스트 시간(밀리초)
P1	20
P2	3
P3	4

① 16

② 18

③ 20

④ 24

답:2

작업	1	2	3	1	1	1	1
시간	4	7	11	15	19	23	27

버스트시간==실행시간

대기시간:해당 작업의 끝난 시간 - 도착시간 - 실행시간

P1 27-20:7초

P2 7-3:4초

P3 11-4:7초

대기시간 합:18초

2017 서울시

다음과 같이 3개의 프로세스가 있다고 가정한다. 각 프로세스의 도착 시간과 프로세스의 실행에 필요한 시간은 아래표와 같다.

CPU 스케줄링 알고리즘으로 RR(Round Robin)을 사용한다고 가정한다. 3개의 프로세스가 CPU에서 작업을 하고 마치는 순서는?

(단, CPU를 사용하는 타임슬라이스(time slice)는 2 이다.)

프로세스	도착시간	프로세스의 실행에 필요한 시간
P1	0	5
P2	1	7
P3	3	4

① P2, P1, P3

② P2, P3, P1

③ P1, P2, P3

④ P1, P3, P2

답:4

라운드로빈은 시간할당량안에 도착한 프로세스들만 대기큐에 존재함

1. 대기큐:없음

2. P1 2초간 실행(1~2)

   P2 대기큐 도착(1초 지난 시점)

대기큐:1<-2

3. P1 미완료로 대기큐의 맨 뒤로 이동

   P2 2초간 실행(3~4)

   P3 대기큐 도착(3초 지난 시점) 작업 도중 도착한 프로세스도 대기큐의 맨 뒤에 존재하게 됨

대기큐:2<-1<-3

4. P2 미완료로 대기큐의 맨 뒤로 이동

   P1 2초간 실행(5~6)

대기큐:1<-3<-2

5. P1 미완료로 대기큐의 맨 뒤로 이동

   P3 2초간 실행(7~8)

대기큐:3<-2<-1

6. P3 미완료로 대기큐의 맨 뒤로 이동

   P2 2초간 실행(9~10)

대기큐:2<-1<-3

7. P2 미완료로 대기큐의 맨 뒤로 이동

   P1 1초간 실행(11)

대기큐:1<-3<-2

8. P1 작업완료

   P3 2초간 실행(12~13)

대기큐:3<-2

9. P3 작업완료

   P2 2초간 실행(14~15)

10. P2 미완료로 대기큐의 맨 뒤로 이동

    그러나 대기큐에는 P2밖에 없음

    P2 1초간 실행(16)

    P2 작업완료