프로세스 스케줄링

프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재한다.

• Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합
• Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.

장기스케줄러(Long-term scheduler or job scheduler)

메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다.

• 메모리와 디스크 사이의 스케줄링을 담당.
• 프로세스에 memory(및 각종 리소스)를 할당(admit)
• degree of Multiprogramming 제어(실행중인 프로세스의 수 제어)
• 프로세스의 상태new -> ready(in memory)

cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system 에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.

단기스케줄러(Short-term scheduler or CPU scheduler)

• CPU 와 메모리 사이의 스케줄링을 담당.
• Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
• 프로세스에 CPU 를 할당(scheduler dispatch)
• 프로세스의 상태ready -> running -> waiting -> ready

중기스케줄러(Medium-term scheduler or Swapper)

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
• 프로세스에게서 memory 를 deallocate
• degree of Multiprogramming 제어
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
• 프로세스의 상태ready -> suspended

Process state - suspended

Suspended(stopped) : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스 전부 디스크로 swap out 된다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다.

 

 

프로세서 스케줄링의 기법에는 크게 아래와 같이 선점(preemptive)/비선점(non-preemptive) 형태가 있다.

먼저, 비선점(non-preemptive) 은 이미 할당된 CPU 를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.
프로세스가 CPUS 를 할당 받으면 해당 프로세스가 완료될 때 까지 CPU 를 사용하지 않는다. RDS 로 따지면 테이블에 Lock 을 걸어둔다 이해하면 편하다. 매우 공정한 방법이지만 priority 가 높은 프로세스에 대응하기에는 비효율적인 기법이다.

 

 

비선점 스케줄링법

 

1) FIFO (First In First Out) = FCFS (First-Come First-Served)

     : 준비 큐에 맨 처음 오는 프로세스를 맨 처음에 실행

       응답시간 차가 적어 예측이 쉬움

       구현은 가장 쉽지만, 효율성이 많이 떨어진다.

 

2) SJF (Shortest Job First)

     : 대기 중인 작업 중 수행시간이 가장 적은 프로세스에 CPU를 할당하는 기법

       평균 대기 시간 최소화// 각 프로세스의 CPU 요구시간 알기 어려움

 

 

3) HRN (Highest Response Ratio - next)

     : SJF 기법의 약점 ‘긴 작업과 짧은 작업의 지나친 불평등’ 을 보완한 기법

       응답률= (대기 시간+ 실행 시간)/ 실행 시간

 

 

4) 우선순위 (Priority)

     : 준비상태 큐에서 대기중인 각 프로세스마다 우선 순위를 부여

       -> 우선 순위가 가장 높은 프로세스에 먼저 CPU를 할당

       우선 순위가 같을 경우 FIFO 또는 SJF를 도입

 

 

5) 기한부 (Deadline)

     : 프로세스에게 일정한 시간을 주고 그 시간 안에 완료하도록 하는 기법

 

 

 

 

선점 스케줄링법

 

1) RR (Round Robin)

     : FCFS + 선점 방식

       FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받음

       시간을 할당해서 할당시간 종료 후 완료하지 못하면 폐기

       우선순위의 형평성을 위해 타임 슬라이스 or 시간 할당량에 의해 시간 제한을 받음

       - 시간할당량이 클 경우: FIFO 스케줄링 방법과 차이 X

       - 시간할당량이 작을 경우: 문맥교환 오버헤드가 상대적 ↑

 

 

2) SRT (Shortest Remaining Time)

     : SJF + 선점 방식

       준비상태 큐에 새로 도착한 프로세스의 실행 시간과 현재 실행중인 프로세스의 남은 시간을 비교, 수행시간이 적은 프로세서       

       에 CPU를 할당하는 기법

 

 

3) 다단계 큐 (Multi Level Queue)

     : 프로세스를 특정 그룹으로 분류할 수 있을 경우

       그룹에 따라 각기 다른 준비상태 큐를사용, 큐 사이에 우선순위를 부여하는 기법

 

 

4) 다단계 피드백 큐 (Multi Level Feedback Queue)

     : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다 단계 큐 기법을 

준비상태 큐 사이를 이동할 수 있도록 개선한 기법

다양한 특성의 작업이 혼합된 경우 매우 유용