운영체제 Ch05_'CPU Scheduling-1'

Chapter 5, CPU Scheduling

CPU 스케줄링은 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 사용하게 한다. 일반적인 스케줄링 개념을 논의하는 경우 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가르키는 경우 스레드 스케줄링이라는 용어를 사용하기로 한다.

 

5.1 개본 개념(Basic Concepts)

 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행중인 프로세스를 가지게 하는데 있다.(Block 안된) 기본 아이디어는 하나의 프로세스가 I/O 요청이 완료되기를 기다려야 한다면, 시간을 낭비하지 않고 CPU 자원을 실행 가능한 다른 프로세스에게 할당을 해주는 것이다. 

 

5.1.1  CPU-I/O 버스트 사이클(CPU-I/O Burst Cycle)

 프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. 프로세스들은 이 두 상태를 번갈아 가며 실행한다.

 대부분의 실행은 CPU 버스트(Burst)로 실행된다. 뒤이어 I/O 버스트가 발생하고 반복한다. 이후 시스템콜을 이용해 종료한다.

CPU와 I/O 버스트의 교차

 

 프로세스마다 그리고 컴퓨터마다 지속 시간은 상이하지만, 유사한 빈도수 곡선을 갖는 경향이 있다. 즉, I/O 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가질 것이며 긴 CPU 버스트 시간은 적다.

CPU 버스트 히스토그램

 

5.1.2 CPU 스케줄러(CPU Scheduler)

 CPU가 유후(Idle)상태가 될 때마다, 운영체제는 Ready Queue에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스중에서 선택하여, 이들 중 하나에게 CPU를 할당한다. 또한 short-term scheduler라고도 칭한다.

 

5.1.3 선점 및 비선점 스케줄링(Preemptive and Nonpreemptive Scheduling)

 CPU 스케줄링 결정(Decision)은 아래 네가지 상황에서 발생할 수 있다.

 

 1. 프로세스는 Running state에서 Waiting state로 변할 수 있다.

  e.g. I/O request or call the wait()

 2. 프로세스는 Running state에서 Ready state로 변할 수 있다.

  e.g. I/O (timer)Interrupt occurs

 3. 프로세스는 Waiting sate에서 Ready state로 변할 수 있다.

  e.g. Completion of I/O

 4. Process Terminates

최근의 운영체제는 선점형(Preemptive)로 설계되어 있다.

 1, 4번의 경우, 스케줄링 면에서는 선택의 여지가 없다. 즉, 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다. 이 경우에서만 스케줄링이 발생하는 경우, 비선점(Nonpreemptive) 라고 한다. CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 도는 대기 상태로 전환해 CPU를 스스로 할당 해제할 때까지 점유한다는 뜻이다.

 선점(Preemptive)이라는 것은 하나의 프로세스가 CPU를 할당하고 있음에도 해당 할당을 외부에서 강제로 해제하고 다른 프로세스에게 할당 해줄 수 있다는 것이다.(뜻이 헷갈리지만, CPU가 선점한다고 생각하면 쉽다.)

 

 선점형 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다. 예를들면 하나의 프로스가 자료를 갱신하는 동안 선점되어 두 번째 프로세스가 실행 가능한 상태가 될 수 있다. 이때 두 번째 프로세스가 데이터를 읽으려 할 때, 데이터의 일관성(첫 프로세스의 쓰기 실패)은 이미 깨진 상태이다.(이러한 상황은 Ch.6에서 자세히 설명)

 

 운영체제의 커널 설계에 영향을 주기도 한다. 시스템콜을 처리할 동안, 커널은 한 프로세스를 위한 작업으로 바쁠수있다(Busy). 그러한 활동은(e.g. I/O Queue) 중요한(Critical) 커널 자료 변경을 포함할 수있다. 이러한 변경중에 프로세스가 선점된다면 혼란이 계속해서 일어나 시스템에 악영향을 끼칠것이다. 

 하나의 옵션은 시스템콜을 호출했을때 비선점 스케줄링을 하면된다는 것이다. 하지만 이는 실시간 컴퓨팅을 지원하기에 좋은 모델이 아니다.

 

-> Chapter 6 설명

 

5.1.4 디스패처(Dispatcher)

 CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처(Dispatcher)이다. CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 할당 해주는 모듈이며 아래와 같은 작업을 포함한다.

 

1. 하나의 프로세스에서 다른 프로세스로 문맥을 교환하는 일(Context Switch)

2. 사용자 모드로 전환하는 일

3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(Jump)하는 일

 

 디스패처는 시스템 성능에 큰 영향을 가하므로 아주 빠르게 실행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연(Dispatch Latency)이라고 한다.

Dispatch Latency

 

5.2 스케줄링 기준(Scheduling Criteria)

 서로 다른 CPU 스케줄링 알고리듬들은 다른 특성이 있으며 한 부류의 프로세스들을 다른 부류보다 더 선호하는 경향이 있을 수 있다. 아래에는 CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이다.

 

1. CPU 이용률(CPU Utilization) : 우리의 설계는 가능한 한 CPU를 최대한 바쁘게(Busy) 유지하기를 원한다. 개념상 0~100% 로 설계하지만, 실제 시스템에서는 40~90% 범위를 가져야 한다.

2. 처러량(Throughput) : 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로 이를 처리량이라고 한다. 긴 프로세스의 경우 이 비율은 몇 초동안 한 프로세스가 될 수 있고, 짧은 경우 처리량은 초당 수십 개의 프로스가 된다.

3. 총처리 시간(Turnaround time) : 프로세스를 실행하는 데 소요한 시간이다. 프로세스의 제출시간과 완료 시간의 간격을 총처리 시간으로 한다. Ready Queue에서 대기한 시간, CPU 실행 시간, I/O 시간을 합한 시간이다.

4. 대기 시간(Wating time) : 생각해보자면 CPU 스케줄링 알고리듬은 CPU 실행 시간, I/O 시간의 양에 영향을 미치지 않는다. 따라서 대기 시간은 Ready Queue에서 대기한 시간의 합이다.

5. 응답 시간(Response time) : 대화식 시스템(Interactive System)에서, 총 처리 시간은 최선의 기준이 아닐 수도 있다. 프로세스에게 하나의 요굴르 제출한 후 첫 번째 응답이 나올 때까지의 시간이다.

 

 CPU 이용률과 처리량을 최대화, 총처리 시간, 대기시간, 응답 시간을 최소화 하는 것이 바람직 하다.