공부해보잠
스케줄링 본문
스케줄링의 개요
스케줄링(Scheduling)은 프로세스가 생성되어 실행될 때 필요한 시스템 자원(CPU, 메로리, I/O 등)을 해당 프로세스에게 할당하는 작업입니다.
프로세스는 생성에서 종료까지 때까지 다양한 스케줄링 과정을 거칩니다
프로세서 스케줄링의 기법
| 비선점(Non-preemptive) 스케줄링 | 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 비선점 스케줄링의 종류에는 FCFS(FIFO), SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있습니다. |
| 선점(Preemptive) 스케줄링 | 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법입니다. 선점 스케줄링의 종류에는 Round Robin,SRT,선점 우선순위, 다단계 큐(MQ),다단계 피드백 큐(MFQ)등의 알고리즘이 있습니다. |
주요 스케줄링 기법
FCFS(First Come First Service, 선입 선출) = FIFO(First In First Out)
FCFS는 준비상태가 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘이다.
| 프로세스 | 도착 시간 (Arrival Time) | 실행 시간 (Burst Time) |
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |
위에 표를 이용하여 완료시간, 반환시간, 대기시간을 구해봅시다.
| P1 | P2 | P3 | P4 |
0 5 8 16 22
완료시간 : P1 : 5, P2: 8, P3 : 16, P4 22
완료 시간은 도착 시간이 빠른 순서대로 계산합니다.
먼저 도착 시간이 가장 빠른 프로세스의 도착 시간(0) + 실행 시간(5)으로 첫 번째 완료 시간을 구합니다.
이후 프로세스는 이전 프로세스의 완료 시간(5) + 실행 시간(3)을 더해서 완료 시간을 계산합니다.
도착 시간은 완료 시간 계산에 사용되지 않습니다.
반환시간 : P1 : 5, P2 : 7, P3 : 14, P4 : 19
반환시간을 구하는 방법은 완료시간-도착시간 입니다.
P1 : 도착시간(0)-완료시간(5)= 반환시간(5)
P2: 도착시간(1)-완료시간(8)= 반환시간(7)이 되겠습니다.
대기시간: P1 : 0, P2: 4, P3: 6, P4 =13
대기시간을 구하는 방법은 반환시간 - 실행시간 입니다
P1 : 반환시간(5)-실행시간(5) = 대기시간(0)
P2: 반환시간(7)-실행시간(3) = 대기시간(4)이 되겠습니다
SJF(Shortest Job First, 단기 작업 우선)
SJF는 준비상태 큐에서 기다리고 있는 프로세스 들 중에서 실행 시간이 가장 짦은 프로세스에게 먼저 CPU를 할당하는 기법입니다.
| 프로세스 | 도착 시간 (Arrival Time) | 실행 시간 (Burst Time) |
| P1 | 0 | 6 |
| P2 | 1 | 8 |
| P3 | 2 | 7 |
| P4 | 3 | 3 |
위의 표를 활용하여 평균실행시간, 평균 대기시간, 평균 반환시간을 구해봅시다.
| P1 | P4 | P3 | P2 |
0 6 9 16 24
완료시간은 도착시간 + 실행시간 = 완료시간이 됩니다
FCFS와 다른 점은 실행시간이 짦은 순서부터 처리하게 됩니다.
P1 : 도착시간(0) + 실행시간(6)=완료시간(6)
P4 : 이전의 완료시간(6)+실행시간(3)= 완료시간(9)
P3 : 이전의 완료시간(9)+실행시간(7) = 완료시간(16)이 되겠습니다.
P1 : 6, P2: 24, P3: 16, P4: 9
반환시간은 완료시간 - 도착시간 = 반환시간이 됩니다.
P1 : 완료시간(6)-도착시간(0) = 반환시간(6)
P2 : 완료시간(24)-도착시간(1) = 반환시간(23)입니다.
P1 : 6, P2: 23, P3 : 14, P4 : 6
대기시간은 반환시간 - 실행시간 = 대기시간이 됩니다
P1 : 반환시간(6) - 실행시간(6) =대기시간(0)
P2 : 반환시간(23) 실행시간(8) = 대기시간(15)입니다
P1 : 0, P2 : 15, P3 : 7, P4: 3
평균 반환시간(반환시간/프로세스의 실행개수)
$$\frac{6+23+14+6}{4}=12.25$$
평균 대기시간(대기시간/프로세스의 실행개수)
$$\frac{0+15+7+3}{4}=6.25$$
HRN(Highest Response-ratio Next)
HRN은 실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로, 대기시간과 서비스(실행)시간을 이용하는 기법입니다.
우선 순위 계산식을 이용하여 HRN기법으로 스케줄링 될 때 우선순위를 구해보겠습니다.
우선순위 계산식은
$$\frac우선순위 계산식={대기시간+서비스(실행)시간}{서비스(실행)시간}$$
| 프로세스 | 도착 시간 (Arrival Time) | 실행 시간 (Burst Time) | 대기 시간 (초기 값: 0) |
| P1 | 0 | 4 | 0 |
| P2 | 1 | 6 | 0 |
| P3 | 2 | 2 | 0 |
| P4 | 3 | 8 | 0 |
첫번째 사이클 (시간 =0~4) : P1
도착한 프로세스 : P1
실행시간이 짦으므로 P1으로 실행
대기시간 업데이트 : 대기시간 증가
두번째 사이클(시간 = 4~6) : P3
도착한 프로세스 : P2, P3, P4
우선순위 계산
$$\fracP2={3+6}{6}=1.5$$
$$\fracP3={2+2}{2}=2.0$$
$$\fracP4={1+8}{8}=1.125$$
세번째 사이클(시간 =6~12) : P2
남은 프로세스 : P2, P4
우선순위 계산:
$$\fracP2={5+6}{6}=2.0$$
$$\fracP2={3+8}{8}=1.375$$
네번째 사이클(시간 = 12~20) : P4
남은 프로세스 : P4
우선순위 계산 :
$$\fracP4={9+8}{8}=2.125$$
대기시간의 계산법은 이전에 도착한 사이클의 실행시간 - 도착시간 = 대기시간이 됩니다.
첫번째사이클의 공식 : 실행시간이 짦은 순서 = P1
두번째사이클의 공식 : 첫번째 사이클의 실행시간(4) - P3도착시간(2)+P3의 실행시간(2)/ P3의 실행시간(2) = P3우선순위(2.0)
세번째사이클의 공식 : 두번째 사이클의 실행시간(6) - P2도착시간(1)+P2의 실행시간(6)/P2의 실행시간(6) = P2우선수위(2.0)
네번째사이클의 공식 : 세번째 사이클의 실행시간(12) - P4의 도착시간(3)+P4의 실행시간(8)/P4의 실행시간(8)=P4우선순위(2.125)
RR(Round Robin)
RR은 시분할 시스템을 위해 고안된 방식으로, FCFS알고리즘을 선점(Preemptive) 형태로 변형한 기법이다.
할당되는 시간이 클 경우 FCFS기법과 같아지고 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생된다.
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 6 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
Time Slice(Time Quantum) : 2
첫번째 라운드 : 완료 P3, 대기P1,P2
P1 : 2 실행 남은 값 4
P2 : 2 실행 남은 값 2
P3 : 2 실행 남은 값0(완료)
두번째 라운드: 완료 P2, 대기P1
P1 : 2실행 남은 값 2
P2: 2실행 남은 값0(완료)
세번째 라운드 : 완료 P1
P1: 2실행 남은값 0(완료)
RR방식은 다른 방식과 다르게 마지막에 실행이 끝난 시점이 완료시점 입니다(완료시간 계산때만)
완료시간은 도착시간 + 실행시간 = 완료시간이 됩니다
P1 : 12, P2: 10 , P3: 6
반환시간은 완료시간 - 도착시간 = 반환시간이 됩니다.
P1 : 12, P2: 9 , P3 : 4
대기시간은 반환시간 - 실행시간 = 대기시간이 됩니다
P1 : 6, P2 : 5, P3: 2
평균반환시간
$$\frac{12+9+4}{3}=8.333$$
평균대기시간
$$\frac{6+5+2}{3}=4.333$$
출처 및 참조:
정보처리 산업기사 시나공(기본서)
