[운영체제] 비선점 스케줄링 기법

운영체제가 작업을 처리하는 방식으로 비선점 스케쥴링과 선점 스케줄링의 방식이 있습니다.

오늘은 비선점 스케줄링에 대해 포스팅을 해보려 합니다.

 

비선점 스케줄링에는

선입선출(FCFS), 단기 작업 우선 처리(SJF), 최상 응답 비율 순서(Highest response-ratio next, HRN), 기한부(Deadline), 우선순위(Priority)의 방식이 있습니다.

 

선입선출(First Come First Service)

FIFO(First In First Out)이라고도 부르며 준비상태 큐(Queue)에 도착한 순서대로 CPU를 할당하는 방법입니다. 가장 간단한 방식이며 구현하기가 쉽습니다. 

선입선출의 특징은 도착한 순서대로 작업 처리 순번이 부여가 되기에 공평성을 제공합니다. 하지만, 중요한 작업 또는 작업 시간이 오래 걸리는 작업들도 작업 순번이 올 때까지 기다려야 합니다. FCFS 처리 방식에는 대기시간 그리고 반환시간을 확인해야 됩니다. 아래의 예시를 통해 확인해 보겠습니다.

작업 순번	P1	P2	P3
처리시간	20	4	6
처리순서	1	2	3

실행시간 : 작업을 처리하는데 소요되는 시간입니다.

 *P1 실행시간 : 20  /  P2 실행시간 : 4  /  P3 실행시간 : 6

 *평균 실행 시간 : (20 + 4 + 6) / 3

 

대기시간 : 프로세스가 작업 처리에 들어가기까지 대기한 시간입니다.

 *P1 대기시간 : 0  /  P2 대기시간 : 20  /  P3 대기시간 : 24

  -> 평균 대기시간 = (0 + 20 + 24) / 3

  -> 총 대기시간 = 0 + 20 +24

 

반환시간 : 프로세스의 대기시간과 실행시간의 합

 -> (20 + 24 + 30) / 3

 

단기 작업 우선인 SJF(Shortest Job First)

큐(Queue)에서 기다리고 있는 프로세스들 중에서 처리시간이 가장 짧은 프로세스들에게 CPU를 우선 할당하는 방식입니다. 특징으로는 평균 대기 시간이 가장 적은 최적의 알고리즘입니다. 하지만 처리시간이 짧은 프로세스들이 계속 오면 처리시간이 긴 프로세스는 무한히 대기해야 되는 상태가 발생할 수도 있습니다.

작업 순번	P1	P2	P3
처리시간	20	4	6
처리순서	3	1	2

실행시간 : 작업을 처리하는데 소요되는 시간입니다.

 *P2 실행시간 : 4  /  P3 실행시간 : 6  /  P1 실행시간 : 20

 *평균 실행 시간 : (4 + 6 + 20) / 3

 

대기시간 : 프로세스가 작업 처리에 들어가기까지 대기한 시간입니다.

 *P2 대기시간 : 0  /  P3 실행시간 : 4  /  P1 실행시간 : 10

  -> 평균 대기시간 = (0 + 4 + 10) / 3

  -> 총 대기시간 = 0 + 4 +10

 

반환시간 : 프로세스의 대기시간과 실행시간의 합

 -> (4 + 10 + 30)

 

최상 응답 비율 순서(Highest response-ratio next, HRN)

SJF의 단점을 보완하기 위한 기법으로 대기시간과 서비스 시간을 이용해 우선순위를 부여하는 방식입니다. 2개의 변수를 이용해 우선순위를 도출 후 처리시간이 짧거나 대기시간이 긴 프로세스에게 높은 우선순위를 부여 후 CPU를 통해 작업처리를 진행합니다. 우선순위가 높은 순번부터 작업을 처리하는 방식입니다.

우선순위는 아래와 같이 계산합니다.

-> 우선순위 = (대기시간 + 작업시간) / 작업시간

HRN방식을 적용한 작업처리 순번은 아래와 같습니다.

작업 순번	P1	P2	P3
처리시간	20	4	6
대기시간	10	20	10
우선순위	(10 + 20) / 20 = 1.5	(20 + 4) / 4 = 6	(10 + 6) / 6 = 2.5XX

우선순위 도출 결과 P2 -> P3 -> P1의 순서로 CPU가 처리합니다.

 

기한부(Deadline)

프로세스에게 일정 시간을 부여하여 제한시간 안에 작업을 완료하도록 임무를 주는 방법입니다. 만약 제한시간 내에 작업을 처리하지 못하면 해당 작업은 제거되거나 처음부터 다시 실행을 합니다. 따라서 시스템은 CPU가 낭비되지 않도록 정확한 시간을 예측해야 되지만 여러 작업들이 동시에 진행이 되는 상황에서는 스케줄링이 복잡해짐에 따라 자원 관리에 오버헤드가 발생할 가능성이 있습니다.

 

우선순위(Priority)

큐(Queue)에서 기다리는 각 작업들에게 우선순위를 부여하여 가장 높은 우선순위를 가진 작업을 먼저 CPU에 할당하는 방법입니다. HRN의 방식과 유사하지만 우선순위 방식은 작업시간, 대기시간을 고려해서 우선순위를 부여하는 게 아닌 기본적으로 설정해둔 프로세서들 개별의 알고리즘을 통해 부여를 하는 방식으로 운영됩니다. 만약 우선순위가 동일하다면 FIFO방식으로 CPU에 할당을 합니다.

 

*에이징(Aging) 기법

시스템에서 특정 작업들의 우선순위가 낮아 계속해서 기다리게 되는 경우, 순번이 한 번이라도 밀렸던 작업들의 우선순위를 한 단계씩 높여 빠른 시간 내에 작업처리가 되도록 하는 일종의 보완기법입니다. SJF, 우선순위의 작업 방식에서 활용이 되며 무한 연기 상태를 예방하는 역할을 합니다.

 

이상으로 비선점된 자료들을 처리하기 위한 스케줄링 방식에 대해 알아보는 포스팅을 마치겠습니다.

 

오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.