[운영체제 공부] 스케줄링

스케줄링은 다중프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.

운영체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

스케줄링의 목표는 다음과 같다.

• 단위시간당 처리량 최대화
  
• 자원할당의 공정성 보장
• 적절한 반환시간 보장
• 자원 사용의 균형 유지
• 서비스 사용기회 확대
• 예측 가능성 보장
• 실행 대기 방지
• 서비스 수 감소 방지
• 오버헤드 최소화
• 우선순위 배정

단위시간당 처리량을 최대화하는것은 가장 중요한 목표중 하나지만, 이 때문에 자원이 균등하게 할당되지 않아 무한대기에 빠질 수 있다. 그렇기 때문에 자원을 할당하는데에 있어서 공정성이 보장되어야한다.

 

스케줄링의 기준 요소 - 버스트

프로세서(CPU) 버스트 -> 프로세스를 프로세서에서 실행할 때
입출력(I/O) 버스트 -> 프로세스가 추가로 실행하려고 입출력을 기다리고 있을 때

프로세서 버스트가 길면 CPU 바운드, 입출력 버스트가 길면 I/O 바운드이다.

스케줄링을 할 때, 어떤 버스트가 길게 걸리는지에 따라 우선순위에 영향을 미친다.

 

스케줄링의 단계

1단계 스케줄링 (장기 스케줄링)
-어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다.

2단계 스케줄링 (중기 스케줄링)
-어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화하는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 이로써 시스템을 적절히 운영한다.

3단계 스케줄링 (단기 스케줄링)
-CPU가 사용 가능한 경우 어느 프로세스에게 배당할지를 결정한다.

스케줄링 큐

준비 큐(ready queue)는 프로세서를 할당받아 실행하려고 기다리는 프로세스들이 대기하는 큐다.
장치 큐(device queue)는 장치를 사용하려는 프로세스들이 대기하는 큐다.

스케줄링에서는 여러개의 큐가 우선순위에 따라 번갈아가며 자원을 사용한다.

큐잉 도표

프로세스에 프로세서가 할당되면 다음 상황이 일어난다.

1. 프로세스가 I/O 요청을 보내고 I/O 큐에 들어간다.
2. 프로세스가 Sub-process를 생성하고(fork) 생성한 프로세스의 종료를 기다린다.
3. 프로세스가 인터럽트되어 다시 준비큐에 들어간다.
4. 프로세스가 시간 할당량을 초과해 준비큐로 들어간다.

장기 스케줄러와 단기 스케줄러

장기 스케줄러는 작업 스케줄러라고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.

단기 스케줄러는 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정하는 프로세스 스케줄링을 한다. 이때는 프로세스가 실행하는 데 필요한 자원의 요청을 만족해야 한다.

장기 스케줄러와 단기 스케줄러의 가장 큰 차이는 실행 빈도이다. 단기 스케줄러는 실행할 프로세스를 수시로 선택한다.
반면에 장기 스케줄러는 시스템에 새로운 작업이 분단위로 들어오므로 단기 스케줄러에 비해 상대적으로 드물게 수행된다.

대부분의 작업이 입출력 중심 작업(I/O bound)과 프로세서 중심 작업(CPU bound)으로 구성되므로 스케줄러가 작업을 선택한 두 종류의 작업을 잘 혼합하여 선택해야 시스템의 성능을 높일 수 있다.

중기 스케줄러

중기 스케줄러는 프로세스들이 프로세서를 서로 차지하려고 할 때 프로세스를 별도의 기억장소에서 빼낼 수 있어 다중프로그래밍의 정도를 줄일 수 있다. 시간이 흐른 후 빼낸 프로세스는 다시 메모리에 들어가 실행을 중단했던 곳부터 다시 실행한다. 이 방법을 스왑이라고 하는데, 스왑 인과 스왑 아웃을 중기 스케줄러가 결정한다. 스왑은 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용할 수 있게 하는 데 필요하다.

선점 스케줄링과 비선점 스케줄링

비선점 스케줄링(Non-Preemptive scheduling)은 이미 할당된 cpu를 다른 프로세스가 강제로 빼앗아 사용할 수 없게 하는 기법이다.

반면에 선점 스케줄링(Preemptive scheduling)은 하나의 프로세스가 cpu를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 cpu를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

선점 스케줄링은 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다. 따라서 우선순위가 높은 프로세스들이 긴급 처리를 요청할 때 용이하다.

하지만 선점 스케줄링은 오버헤드가 커질 수 있어 이를 효과적으로 이용하려면 메모리에 프로세스가 많이 적재되어 있어야 한다. 즉, 프로세서를 사용 가능할 때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다. 따라서 선점 스케줄링에서는 우선순위라는 개념을 반드시 고려해야 하는데, 우선순위는 의미 있게 부여하지 않으면 효과가 없다.