#프로세스 스케줄링

프로세스 스케줄링

운영체제에는 오직 하나의 프로세스만 등록되지 않는다. 굉장히 많은 프로세스가 큐에 등록되면서 다중프로그래밍 환경이 발생하는데, 이 때 프로세스의 스케줄링 방법에 따라서 성능에 차이가 나타난다. 스케줄링에는 단계에 따라 장기, 중기, 단기 스케줄링으로 나뉜다.

장기 스케줄링에서는 시스템에 입력되는 작업이나 명령들에 대해 이들 중 어느 작업(또는 명령)부터 커널에 등록시켜 프로세스화 할 것인가를 결정한다. 이 단계에서는 주로 다중프로그래밍 정도를 고려하여 한 개의 프로세스가 종료될 때 작업 큐에서 대기 중인 작업들 중 가장 우선순위가 높은 프로세스를 선정하여 커널에 등록시키는 기법을 사용하지만, 시스템 오버헤드를 줄이기 위해 임계치를 정해 놓고 다중프로그래밍 정도가 그 임계치에 도달했을 때 장기 스케줄링을 수행하여 여러 개의 작업들을 한꺼번에 커널에 등록시키는 방법을 사용하기도 한다. 장기 스케줄링의 목적은 입출력 위주의 프로세스와 연산 위주의 프로세스들을 적절히 혼합하여 시스템 전체의 자원 활용 면에서 균형을 맞출 수 있는 형태로 프로세스들을 생성시키고자 하는 데 있다.

중기 스케줄링 단계에서는 주기억장치의 자원을 할당받지 못한 프로세스들에 대해 어느 프로세스에 자원을 할당할 것인가를 결정한다. 주기억장치에 할당 가능한 자원이 없다면 프로세스에 자원을 할당하지 않는 작업 스케줄러와는 달리, 중기 스케줄링 단계의 스케줄러는 주기억장치의 공간을 점유하고 있는 준비 상태의 프로세스를 보조기억장치로 스왑인(swap in)하여 여유 자원을 확보한다.

단기 스케줄링 단계에서는 준비 큐(ready queue)의 준비 상태(ready state)에 있는 프로세스들을 대상으로 어느 프로세스에게 프로세서를 할당할 것인지를 결정하며, 이는 프로세스 스케줄러(process scheduler) 또는 디스패처(dispatcher)에 의해 수행된다. 단기 스케줄링을 프로세스 스케줄링이라고도 하며, 이는 임의의 시점에 프로세서를 사용하던 프로세스가 일시 중단되거나 종료되었을 때 프로세서를 할당받을 새로운 프로세스를 선정하기 위해 수행된다. 일반적으로 단기 스케줄링은 장기 스케줄링보다 빈번하게 발생하며, 세밀하게 수행된다. 스케줄링 기법은 선점 방식이냐, 비선점 방식이냐에 따른 분류와 각 알고리즘의 특징은 다음과 같다.

선점	● RR(Round-Robin) ● SRTN(Shortest-Remaining-Time-Next), SRTF(Shortest-Remaining-Time)
비선점	● FIFO(First-In-First-Out), FCFS(First-Come-First-Served) ● SPN(Shortest-Process-Next), SJF(Shortest-Job-First) ● HRRN(Highest-Response-Ratio-Next) ● MFQ(Multilevel-Feedback-Queue)

RR (Round-Robin)	● FIFO의 선점형 ● 프로세서 독점 방지, 문맥 교환에 따른 오버헤드 발생 ● 대화형 시스템, 시분할 시스템 ● 시간 할당량에 따라 성능 좌우
SRTN (Shortest-Remaining-Time-Next),	● SRTF(Shortest-Remaining-Time) ● SPN의 선점형 ● 잔여 시간 계산에 따른 오버헤드 발생
FIFO (First-In-First-Out),	● FCFS(First-Come-First-Served) ● 긴 시간을 요구하는 프로세스가 프로세서 독점할 수 있음 ● 일괄처리시스템에 적합
SPN (Shortest-Process-Next),	● SJF(Shortest-Job-First) ● 총 실행시간이 가장 짧은 프로세스부터 스케줄링 ● 실행시간이 긴 프로세스가 무한정 대기할 수 있음 → 에이징(aging) 기법 ● 프로세스 실행 시간 추정이 어려움 ● 시스템 내에 대기하는 프로세스 수를 최소화할 수 있음
HRRN (Highest-Response-Ratio-Next)	● SPN의 실행 시간이 다른 프로세스 간 불평등이 심화되는 것을 방지하기 위한 기법 ● 준비 상태의 프로세스들 중 응답률이 가장 높은 프로세스에게 우선권 주는 방식 ●  ● 총 실행시간을 계산해야 하므로 오버헤드 발생

■ MFQ(Multilevel-Feedback-Queue)

● 프로세스들에 대한 특성이나 총 실행 시간 등의 정보가 전혀 없을 때 효율적인 스케줄링을 하기 위해 사용

● 선점 기반, 동적 우선순위 기반

- 짧은 실행 시간을 필요로 하는 프로세스 선호

- 입출력 위주의 프로세스 선호

: 입출력 위주의 프로세스는 일반적으로 짧은 시간 동안 프로세서를 사용

  → 프로세서를 비롯한 각종 자원들의 활용도를 극대화할 수 있음

- 프로세스의 성격을 신속하게 분석하여 시스템 상태를 반영하여 스케줄링

● 피드백 

- 현재까지 프로세서를 사용한 시간을 근거로 스케줄링

- 다단계 피드백 큐(multilvel feddback queue) : 준비 큐를 여러 개 두어 준비 상태로 들어오는 프로세스들이 디스패치될 당시와 다른 큐로 진입할 수 있게 함

● 스케줄링 절차

① 총 n+1개의 준비 큐()들에 대해 각 큐에 우선순위 부여하며, i가 j보다 작은 경우 의 우선순위가 의 우선순위보다 높다고 가정 → Priority() > Priority(), if i < j ② 처음 입력되는 프로세스는 준비 큐 에서 대기 ③ 에서 디스패치된 프로세스가 프로세서에서 시간 할당량을 모두 소모 → 다음 단계의 큐()로 이동 ④ 에서 디스패치된 프로세스가 시간 할당량이 모두 소모되기 전에 입출력 등의 이유로 프로세서를 반납 → 다시 원래 큐()로 이동 ⑤ 마지막 단계의 큐에서 디스패치될 때에는 RR스케줄링 기법 따름 ⑥ 프로세스는 자신이 진입하는 큐의 우선순위를 배정받게 되며, 자신보다 우선순위 높은 프로세스가 없을 경우에만 디스패치. 즉, 에서 대기하는 프로세스  ~ 이 모두 비어있을 때에만 디스패치

● 변형

- 각 준비 큐마다 시간 할당량을 배정하여 어느 한 큐에서 디스패치된 프로세스는 해당 큐에 할당된 만큼의 시간 할당량을 배정받도록 함 → 하위 단계에 있는 준비 큐에 시간 할당량을 크게 하여 하위 단계의 큐에 존재하는 프로세스들이 디스패치될 가능성이 적어지는 대신, 한번 디스패치 되었을 때 더 많은 시간 할당량을 배정받도록 함

- 입출력 위주의 프로세스들을 상위 단계의 큐로 이동시켜 이들의 우선순위를 높여줌 → 시스템 전체 평균 응답 시간 줄이고, 입출력 작업 분산

- 대기 시간이 커진 프로세스의 우선순위를 높이기 위해 대기 시간이 지정된 시간을 초과할 경우 다단계 큐에서 프로세스의 위치를 상향조정하는 에이징(aging) 기법 사용 → 특정 프로세스가 지나치게 오랜 시간을 준비 큐에서 대기하지 않게 함

참조 자료

엄영익·정태명 공저, 『컴퓨터 운영체제론』, 생능출판사

http://metro9780.tistory.com/4