[정보처리기사 실기] 프로세스 스케줄링

0. 비선점형 스케줄링 (우기 HFS) , 선점형 스케줄링 (SMMR)

비 선점형 스케줄링 (우기HFS) 우리 기업은 홈패밀리서비슬르 한다.	한 프로세스가 CPU를 할당 받으면 작업 종료 전까지 다른 프로세스는 CPU 점유 불가능한 스케줄링
	우선순위 (Priority)	프로세스별 우선순위에 따라 CPU 할당 우선순위가 높은 프로세스가 먼저 CPU사용, 우선순위가 같은 프로세스는 FCFS방식 처리
	기한부 (Deadline)	작업들이 명시된 기한 내에 완료되도록 계획 실시간 시스템에서 중요
	HRN (Highest Response Ratio Next)	대기중인 프로세스 중 현재 응답률이 가장 높은 것을 선택, 기아 현상 최소화 기법 프로세스의 우선순위를 CPU처리기간과 대기시간을 동시에 고려해 결정함 * 우선순위 = (대기시간+서비스시간)/서비스시간
	FCFS (First Come First Service)	프로세스가 대기 큐에 도착한 순서에 따라 CPU할당 = FIFO
	SJF (Shortest Job First)	가장 짧은 작업부터 수행, 평균 대기 시간 최소화, 기아현상 발생

선점형 스케줄링 (SMMR) 쇼 미더 머니 라운드 진출!	우선 순위가 높은 프로세스가 CPU를 점유하는 스케줄링
	SRT (Shortest Remaining Time First)	가장 짧은 시간이 소요되는 프로세스를 먼저 수행 CPU를 점유하고 있는 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 준비 큐에 들어오면서 새로운 프로세스가 CPU를 선점할 수 있다.
	RR (Round Robbin)	프로세스는 같은 크기의 CPU할당 프로세스들에게 정해진 시간 할당량을 주고 그 시간안에 작업을 수행하게함 시간 할당량이 끝나면 다른 프로세스에게 CPU를 넘기고 맨 뒤에가서 다시 기다림
	다단계 큐 (Multi Level Queue)	여러개의 큐를 이용하여 상위 단계 작업에 의한 하위단계 작업이 선점 준비 큐를 여러개의 큐로 나누고 각 큐에 우선순위를 부여하는 스케줄링 방식 ex) 대화형 프로세스 , 장기 실행 배치 프로세스 각각 다른 그룹 배치
	다단계 피드백 큐 (Multi Level Feedback Queue)	큐마다 서로 다른 CPU시간 할당량을 부여, FIFO+라운드로빈 스케줄링 기법 혼합 프로세스들이 큐를 갈아탈 수 있는 스케줄링 방식

1. FCFS(First Come First Served)

비선점형 스케줄링

프로세스가 대기 큐에 도착한 순서에 따라 CPU할당 = FIFO

 

 

1) 예제

다음은 CPU에 서비스를 받으려고 도착한 순서대로 프로세스와 그 서비스시간을 나타낸다. FCFS CPU Scheduling에 의해서 프로세스를 처리한다고 했을 경우 프로세스의 평균 대기시간은 얼마인가?

프로세스	버스트 시간(초)
P1	24
P2	3
P3	3

17초 

---

P1은 대기가 없기 때문에 0초

P2은 P1대기해서 24초

P3은 24 + 3  = 27초 기다림 

평균 = 24 + 27 = 51 / 3으로 나누면 = 17초

 

 

2) 예제

다음과 같은 3개 작업에 대하여 FCFS알고리즘을 사용할 때 임의 작업순서로 얻을 수 있는 최대 평균 반환시간을 T, 최소 평균반환시간을 t라고 가정했을때 T-t값은?

프로세스	실행시간
P1	9
P2	3
P3	12

6

---

최대 평균 반환시간 

실행시간이 높은거 부터 실행한다. 따라서 12초 부터 실행하고 그다음에 9초 그다음에 3초

12초의 대기시간 0  , 반환시간 12

9초의 대기시간 12 , 반환시간 21

3초의 대기시간 21, 반환시간 24

그래서 최대 평균 반환시간은 24 + 21 + 12 = 57 / 3 = 19초

 

최소 평균 반환시간

실행시간이 짧은 것 부터 실행한다. 따라서 3초 실행, 9초 실행, 12초 실행한다.

3초의 대기시간 0, 반환시간 3

9초의 대기시간 3, 반환시간 12

12초의 대기시간 12, 반환시간 24

그래서 최소 평균 반환시간은 24+12+3 = 39 / 13초 

 

19-13 = 6

 

 

3) 예제

다음과 같은 3개의 작업에 대하여 FCFS알고리즘을 사용할 떄 임의의 작업 순서로 얻을 수 있는 최대 평균 반환시간을 T, 최소 평균 반환 시간을 t 라고 가정했을 때 T-t값은?

프로세스	실행시간
P1	9
P2	6
P3	12

4초

---

최대 평균 반환시간 실행시간이 긴것 부터

12초 , 대기시간 0, 반환시간 12

9초, 대기시간 12, 반환시간 21

6초, 대기시간 21, 반환시간 27

12 + 21 + 27 = 60 / 3 = 20초

 

최소 평균 반환시간 실행시간 짧은 것 부터

6초, 대기시간 0, 반환시간 6

9초, 대기시간 6, 반환시간 15

12초, 대기시간 15, 반환시간 27

6 + 15 + 27 = 48 / 3 = 16 초

20 - 16 = 4

 

 

2. SJF(Shortest Job First)

비선점형 스케줄링

가장 짧은 작업부터 수행, 평균 대기 시간 최소화, 기아현상 발생

 

1) 예제

다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔을 경우 SJF 스케줄링 기법을 이용하여 제출시간이 없는 경우의 평균 실행 시간은?

프로세스	P1	P2	P3
실행시간(초)	18	6	9

11초

---

18 + 6+ 9 = 33 / 3 = 11

 

 

2) 예제

대기하고 있는 프로세스 P1, P2, P3, P4 처리시간은 각각  24, 9, 15, 10 초일 때 최단작업우선 SJF 스케줄링으로 처리했을 때 평균 대기시간은 얼마인가? 

15.5초

---

P2 9초, 대기시간 0초, 반환시간 9초

P4 10초, 대기시간 9초, 반환시간 19초

P3 15초, 대기시간 19초, 반환시간 34초

P1 24초, 대기시간 34초, 반환시간 58초

34 + 19 + 9 = 62/4 = 15.5초

 

 

3) 예제

SJF 스케줄링에서 다음과 같은 작업들이 준비 상태 큐에있을 때 평균 반환시간과 평균 대기시간은?

프로세스	실행시간
P1	6
P2	3
P3	8
P4	7

평균반환시간 = 13, 평균 대기시간 7

---

P2 3, 대기시간 0, 반환시간 3

P1 6, 대기시간 3, 반환시간 9

P4 7, 대기시간 9, 반환시간 16

P3 8 , 대기시간 16, 반환시간 24

 

평균 반환시간 = 24+16+9+3 = 52 / 4 = 13

평균 대기시간 = 16 + 9 + 3 = 28 / 4 = 7

 

 

4) 예제

다음과 같은 Task List 에서 SJF방식으로 Scheduling 할 경우 Task 2의 종료시간을 구하면?

Task	도착시간	실행시간
Task1	0	6
Task2	1	3
Task3	2	4

9초

---

SJF 즉 비선점형 방식을 생각해보면 먼저 도착하고 짧은것 부터 들어간다. 따라서

T1 6초, 대기시간 0초, 반환시간 6초

하고있는 동안 1, 2초에 T2와 T3이 도착했다. 그런데 실행시간이 짧은것을 실행해야하니 T2가 실행된다.

T2 3초, 대기시간 6초, 반환시간 9초

T3 4초, 대기시간 9초, 반환시간 13초 

 

 

 

3. HRN(Highest Response-ratio Next)

대기중인 프로세스 중 현재 응답률이 가장 높은 것을 선택, 기아 현상 최소화 기법
프로세스의 우선순위를 CPU처리기간과 대기시간을 동시에 고려해 결정함
* 우선순위 = (대기시간+서비스시간)/서비스시간 이 높은걸 먼저 실

 

1) 예제

HRN 방식으로 스케줄링 할 경우 입력된 작업이 다음과 같을 때 우선순위가 가장 높은 작업은?

작업	대기시간	서비스시간
A	8	2
B	10	6
C	15	7
D	20	8

A

---

A의 우선순위 = 8 + 2 = 10/2 = 5

B의 우선순위 = 10 + 6 = 16/ 6 = 2.66666..7

C의 우선순위 = 15 + 7 = 22/7 = 3.1

D의 우선순위 = 20 + 8 = 28/8= 3.5

 

 

 

2) 예제

HRN 스케줄링 방식에서 입력된 작업이 다음과 같을 떄 우선순위가 가장 높은 것은?

작업	대기시간	서비스시간
A	5	20
B	40	20
C	15	45
D	20	2

D

---

A = 25/20 = 1.25

B = 60/20 = 3

C = 15+45 = 60 / 1.3

D = 22 / 2 = 11

 

 

3) 예제

HRN방식으로 스케줄링 할 경우 입력된 작업이 다음과 같을 댸 우선순위가 높은 순서부터 차례로 옳게 나열한 것은?

작업	대기시간	서비스시간
A	40	20
B	20	20
C	70	10
D	120	30

C D A B

---

A = 40 + 20 = 60 / 20 = 3

B = 20+20 = 40/20 = 2

C = 80/10 = 8

D = 150/30 = 5

 

 

 

4. SRT(Shortest Remain Time)

가장 짧은 시간이 소요되는 프로세스를 먼저 수행
CPU를 점유하고 있는 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 준비 큐에 들어오면서 새로운 프로세스가 CPU를 선점할 수 있다.

 

- 반종도 대반서

반환시간 = 종료시간 - 도착시간

대기시간 = 반환시간 - 서비스시간

 

예제1)

다음표는 단일 CPU에 진입한 프로세스의 도착시간과 처리하는데 필요한 실행 시간을 나타낸 것이다. 프로세스간 문맥교환에 따른 오버헤드는 무시한다고 할 때 SRT스케줄링 알고리즘을 사용한 경우 네 프로세스의 평균 반환시간은?

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

7초

---

0초        2초       4초          5초         7초        11초         17초

P1         P2        P3            P2          P4          P1

             P1(6)    P2(2)

 

 

P1 : 도착시간 0초 , 종료시간 17초, 반환시간 17-0 = 17초

P2 : 도착시간 2초,  종료시간   7초 , 반환시간 7-2 = 5초

P3 : 도착시간 4초,  종료시간 5초 , 반환시간 1초

P4 : 도착시간 6초,  종료시간 11초 , 반환시간 5초

 

평균 반환시간 17 + 5 + 1 + 5 = 28/4 = 7초

 

 

 

예제2) 

다음 표는 단일 CPU에 진입한 프로세스의 도착시간과 처리하는데 필요한 실행 시간을 나타낸 것이다. 프로세스간 문맥 교호나에 따른 오버헤드는 무시한다고 할 때 SRT스케줄링 알고리즘을 사용한 경우 네 프로세스의 평균 반환시간은?

 

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

 

 

 0               2            4            5            7                11                       16

P1(7)     P1(5)                                                       P1(5)

              P2(4)       P2(2)     P2(2)      

                              P3(1)

                                            P4(4)     P4(4)

 

반 = 종 - 도

P1 반 = 16초 - 0 = 16

P2 반 =  7초 - 2 = 5

P3 반 = 5초 - 4 = 1

P4 반 = 11초 - 5 = 6 

16 + 5 + 1 + 6 = 28/4 = 7

 

 

https://www.youtube.com/watch?v=AIbzzUXZN8k&t=657s