[운영체제] 스케줄링과 Basic Algorithms

스케줄링

스케줄링

스케줄링은 프로세스의 Context Switching 시에 프로세스에 실행 단계를 
os 에서 제어하는 것을 의미한다.

스케줄링 정책의 기준과 종류 , 특정 카정이 중요 포인트 이다.

Workload

일련의 프로세스들이 실행하는 상황을 워크로드라 한다.

스케줄링의 기준

스케줄링에는 다양한 평가 기준이 있다.

성능 측면의 기준 중에서 반환 시간은

T ( 반환시간) = T (작업 완료시간) - T (작업이 시스템에 도착한 시간) 
을 의미한다.

또 다른 기준은 공정성이 있으며 공정성은 성능과 상충되는 개념이다

 

 

스케줄링 정책

FIFO

단순하다
먼저 도착한 작업이 먼저 실행

반환 시간은 = 20

FIFO의 단점?

매우 공정함 그러나 위와 같은 상황에 치명적인 단점이 생김

먼저 도착한 작업이 많은 작업시간을 가지면 최악임

SJF ( 최단 시간 우선 Shorted Job First)

동시에 도착했을 때 작업 잔여시간이 적은 작업 먼저 작업을 실행한다.

이는 모든 작업이 동시에 도착한다면 SJF가 최적의 스케줄링 알고리즘이다.

하지만 가정 자체가 비현실적이다.

SJF 단점

현실적인 가정으로 보자

만약 위와 같이 작업 시간이 긴 작업이 먼저 도착한다고 하면 SJF는 스케줄링 할 방법이 없다.
따라서 SJF의 이점을 살릴 수 없게 된다.

STCF : 최소 잔여 시간 우선 (Shotest Time to Completion First)

SJF의 단점이 극명한 이유는 비선점형 스케줄러이기 때문에 프로세스의 선점을 중제하지 못한다.
(타이머 인터럽트 같은)

STCF는 SJF 와 다른 점은 선점형이라는 것이다.

SJF와 똑같이 최단 잔여 시간을 우선으로 보지만
시간이 다르게 시스템에 도착한 프로세들과 비교하여 시간이 많이 소요되는 작업을 실행하고
있으면 중지하고 최단 잔여 시간을 우선적으로 실행한다.

한계점

STCF 는 작업의 길이를 미리 알고 있고 작업이 오직 CPU만 사용하며 , 평가 기준이 반환시간
하나라면 STCF는 매우 훌륭한 정책이다.

하지만 시분할 컴퓨터의 등장으로 사용자가 터미널에서 작업하게 되어 시스템에게
상호작용을 원활히 하기 위한 성능을 요구하게 되었다.

 

새 평가 기준 : Response time

사용자와의 상호작용을 위한 새 평가 기준
응답시간 = 스케줄링 되기 시작한 시간 - 시스템에 도착한 시간

FIFO나 SJF STCF는 응답시간 측면에서는  좋지 않을 수 있다
위와 같은 알고리즘들을 사용하면 단지 프로세스를 실행하고 가만히 앉아서
다른 프로세스가 끝나기를 기다려야한다....

 

Round Robin(RR)

라운드 로빈은 하나의 작업은 하나의 time slice 만큼 수행되고 다른 작업과 교한되어

ready queue 로 이동한다.

이때 타임슬라이스는 타이머 인터럽트 간격의 배수이어야 한다.

응답시간 vs 반환시간

적당한 길이의 응답 시간이 유일한 측정 기준인 경우 RR 은 매우 훌륭한 알고리즘이다.

하지만 반환 시간이 측정 기준이라면 RR은 최악이다. 어느 경우는 FIFO 보다도
안좋은 알고리즘일 수 있다.

일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게
CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 나쁘다

우리는 다음부터 이거에 대한 해결에 초첨을 맞춰야한다.

아직 풀지 못한 가정

위 가정들은 IO 작업이 없다는 가정과 각 작업의 실행 시간을 알고 있다는 가정하에
알고리즘을 분석하였다.

위 2개의 가정을 풀면 또 다른 알고리즘을 생각해봐야 한다.

입출력 연산 고려

이때까지 입출력 연산을 고려하지 않았다는 가정하에 알고리즘을 배워 보았다.

하지만 입출력이 없는 작업은 없을 수 없다.

만약 입출력이 있는 작업이 있다면 과연 스케줄러는 어떻게 기존 알고리즘을 적용할까

IO 작업이 시작돼면 커널은 제어권을 얻어 작업을 blocked 대기 상태로 전환한다.
그러면 원래라면 Busy Waiting 처럼 그냥 한없이 대기할 것이다.

하지만 요즘날에 os는 IO 작업 같은 대기 상태에 돌입하면 다른 작업을 스케줄링한다.

작업의 실행 시간은 미리 알려져 있다????

그럴 수 없다.

프로세스의 작업은 항상 일정하지 않은 길이의 실행 시간을 갖는다.

따라서 과거를 이용한 미래 예측(근사치) 같은 거로 예측하곤한다 SJF 같은것들은..