프로세스 스케줄링(Scheduling)

1) 프로세스 스케줄링의 개념

(1) 프로세스 스케줄링의 정의

• CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 것이다.
• 장기, 중기, 단기 스케줄링이 있다.
  • 장기 스케줄링 : 어떤 프로세스를 커널에 등록할 것인가를 결정
  • 중기 스케줄링 : 어떤 프로세스에게 메모리를 할당할 것인가를 결정
  • 단기 스케줄링 : 어떤 프로세스에게 CPU를 할당할 것인가를 결정

(2) 프로세스 스케줄링의 원칙

• 공정하게 배정되어야 하며 처리 응답 시간이 신속해야 한다.
• 단위 시간당 가능한 최대의 처리가 될 수 있도록 해야 한다.
• 응답 시간과 자원 활용 간의 적절한 균형이 유지되도록 해야 한다.

(3) 바람직한 프로세스 스케줄링 정책

• CPU 이용률, 처리 능력을 높일 수 있도록 스케줄링한다.
• 대기 시간, 응답 시간, 반환 시간을 줄일 수 있도록 스케줄링한다.

2) 비선점형(Non Preemption) 스케줄링

(1) 비선점형 방식의 개념

• 현재 실행 중인 프로세스를 다른 프로세스가 강제적으로 중단시킬 수 없는 방식이다.
• CPU를 사용하는 현재 프로세스가 종료되면 다른 프로세스에 CPU를 할당한다.
• 응답 시간의 예측이 용이하며, 일괄 처리 시스템에 적당하다.
• FIFO, SJF, HRN 등이 있다.

(2) FIFO(First In First Out)

• 프로세스가 도착(입력)한 순서대로 처리한다.
• 알고리즘이 가장 간단하지만, 평균 반환 시간이 길다.
  • 평균 실행 시간 = 총 실행 시간 / 프로세스 개수
  • 평균 대기 시간 = 총 대기 시간 / 프로세스 개수
  • 평균 반환 시간 = 평균 실행 시간 + 평균 대기 시간

  작업	실행시간	도착 시간	대기 시간
  A	24	0	0
  B	6	1	24-1=23
  C	3	2	30-2=28
  평균 실행 시간	11	평균 대기 시간	17
  평균 반환 시간		28

(3) SJF(Short Job First)

• 실행 시간이 가장 짧은 프로세스 순으로 처리한다.

• 실행 시간이 긴 작업일 경우 무한 대기(기아) 상태가 발생할 수 있다.

• 짧은 시간의 작업들이 많은 경우에 FIFO보다 평균 대기 시간이 작다.

  작업	실행시간	도착 시간	대기 시간
  A	24	0	0
  B	6	1	27-1=26
  C	3	2	24-2=22
  평균 실행 시간	11	평균 대기 시간	16
  평균 반환 시간		27

(4) HRN(Highest Response-ratio Next)

• FIFO와 SJF의 단점을 보완하여 개발된 방법이다.

• 대기 시간이 긴 프로세스의 우선순위를 높여서 긴 작업과 짧은 작업간의 지나친 불평등을 해소할 수 있다.

• HRN 우선순위 공식의 계산 결과가 큰 작업에 높은 우선순위를 부여(Aging)한다.

  • 우선순위 = (실행 시간) + (대기 시간)/(실행 시간)

  작업	실행시간	대기 시간	우선 순위
  A	20	10	1.5
  B	4	20	6
  C	6	10	2.6

3) 선점형(Preemption) 스케줄링

(1) 선점형 방식의 개념

• 현재 실행 중인 프로세스를 다른 프로세스가 강제적으로 중단시킬 수 있는 방식이다.
• 다른 프로세스가 현재 사용 중인 프로세스를 중단시키고 CPU를 차지할 수 있다.
• 빠른 응답 시간을 필요로 하는 대화식, 시분할, 실시간 처리에 적당하다.
• RR, SRT, MFQ 등이 있다.

(2) RR(Round Robin)

• 동일한 Time Slice를 사용하는 시분할 처리 시스템에 효과적으로 적용된다.

• Time Slice 동안만 순서대로 프로세스를 처리하는 방식이다.

• Time Slice가 실행 시간보다 크면 FIFO와 동일한 결과를 보인다.

• Time Slice가 5초인 RR의 평균 반환 시간 계산

  작업	실행 시간	도착 시간
  A	10	0
  B	18	2
  C	5	5
  D	3	6

• 계산 공식은 FIFO의 공식과 같다.

  작업	A	B	C	D
  남은 시간	5	13	0	0

• C의 대기 시간 : 10 - 5 = 5

• D의 대기 시간 : 15 - 6 = 9

  작업	A	B	C	D
  남은 시간	0	8	0	0

• A의 대기 시간 : 15

  작업	A	B	C	D
  남은 시간	0	0	0	0

• B의 대기 시간 : 20

• 평균 실행 시간 = (10 + 18 + 5 + 3) / 4 = 9

• 평균 대기 시간 = (15 + 20 + 5 + 9) / 4 = 12.25

• 평균 반환 시간 = 9 + 12.25 = 21.25

(3) SRT(Shortest Remaining Tiime)

• 작업이 끝나지 않은 프로세스의 남아 있는 실행 시간이 가장 작은 프로세스를 먼저 실행하는 방식이다.
• SJF 기법을 선점 형태로 변경한 기법으로, 점유 시간이 길어도 중요한 프로세스를 먼저 할당할 수 있다.

(4) MFQ(Multilevel Feedback Queue)

• 짧은 작업이나 입출력 위주의 프로세스에 우선순위를 부여하기 위해 개발된 방식이다.
• 우선순위가 있는 각 큐(대기 리스트)가 있으며 큐마다 Time Slice가 존재한다.
• 낮은 큐일수록 Time Slice는 커지며, CPU 사용을 마친 프로세스는 낮은 큐로 이동된다.
• 맨 마지막 단계의 큐는 RR 스케줄링 방식을 사용한다.