단일 CPU 코어가 있는 시스템에서는 한 번에 하나의 프로세스만 실행할 수 있다. 다른 프로세스는 CPU 코어가 비어서 다시 스케줄링될 수 있을 때까지 기다려야 한다. 멀티프로그래밍의 목적은 CPU 활용도를 극대화하기 위해 항상 일부 프로세스를 실행하는 것이다. 프로세스는 일반적으로 일부 I/O 요청이 완료될 때까지 기다려야 실행된다. 간단한 컴퓨터 시스템에서는 CPU는 그냥 유후 상태로 있다. 이 모든 대기시간은 낭비되고 유용한 작업은 수행되지 않는다. 멀티프로그래밍에서는 이 시간을 생산적으로 사용하려고 한다. 여러 프로세스가 한 번에 메모리에 보관되고, 한 프로세스가 기다려야 할 때 운영체제는 CPU를 해당 프로세스에서 떼어 내고 다른 프로세스에 CPU를 제공하는 패턴이 계속된다. 멀티코어 시스템에서 CPU를 바쁘게 유지하는 이 개념은 시스템의 모든 처리 코어로 확장된다.
이런 종류의 스케줄링은 운영체제의 기본적인 기능이다. 거의 모든 컴퓨터 리소스는 사용 전에 예약되는데, CPU는 주요 컴퓨터 리소스 중 하나다. 따라서 스케줄링은 운영 체제 설계의 핵심이다.
5.1.1 CPU-I/O Burst Cycle
CPU 스케줄링의 성공은 프로세스의 관찰된 속성에 달려있다. 프로세스 실행은 CPU실행돠 I/O 대기의 사이클로 구성된다. 프로세스는 이 두 상태를 번갈아 가며 실행한다. 프로세스 실행은 CPU 버스트로 시작하고, I/O 버스트가 이어지고, 그 다음에 또 다른 CPU 버스트가 이어지고, 그 다음 또 다른 I/O 버스트가 이어지는 식으로 계속된다. 결국 마지막 CPU 버스트는 실행을 종료하라는 시스템 요청으로 끝난다.(그림 5.1)
CPU burst의 지속시간은 광범위하게 층정된다. 프로세스와 컴퓨터마다 크게 다르지만, 그림 5.2와 유사한 주파수 곡선늘 갖는 경향이 있다. 곡선은 일반적으로 지수적 또는 초지수적이며, 짧은 CPU burst가 많고, 긴 CPU burst가 적다.
I/O 바운드 프로그램은 일반적으로 짧은 CPU burst가 많고, CPU 바운드 프로그램은 긴 CPU burst가 몇 개 있을 수 있다. 이 분포는 CPU 스케줄링 알고리즘을 구현할 때 중요할 수 있다.
5.1.2 CPU Scheduler
CPU가 유휴 상태가 될 때마다 운영체제는 실행될 ready 큐에 있는 프로세스 중 하나를 선택해야 한다. 선택 프로세스는 CPU 스케줄러에 의해 수행되며, CPU 스케줄러는 메모리에 있는 실행 준비가 된 프로세스 중에서 프로세스를 선택하여 CPU를 할당한다.
ready 큐는 반드시 FIFO 큐가 아니다. 다양한 스케줄링 알고리즘을 고려할 때 알 수 있듯이, ready 큐는 FIFO 큐, 우선 순위 큐, 트리 또는 순서 없는 linked list로 구현될 수 있다. 그러나 개념적으로 ready 큐늬 모든 프로세스는 CPU에서 실행될 기회를 기다르며 줄 서 있다. 큐의 레코드는 일반적으로 프로세스의 process control blocks(PCBs)이다.
5.1.3 Preemptive and Nonpreemptive Scheduling
CPU 스케줄링 결정은 다음 네 가지 상황에서 이루어질 수 있다.
- 프로세스가 실행 상태에서 대기 상태로 전환될 때(ex: I/O 요청이나 자식 프로세스 종료를 위한 wait() 호출의 결과)
- 프로세스가 실행 상태에서 준비 상태로 전환될 때(ex: 인터럽트 발생)
- 프로세스가 대기 상태에서 준비 상태로 전환될 때(ex: I/O 완료 시)
- 프로세스가 종료될 때
1번과 4번의 경우 스케줄링 측면에서 선택의 여지가 없다. 실행을 위해 새 프로세스를 선택하야 한다. 그러나 2번과 3번은 선택의 여지가 있다.
스케줄링이 1과 4에서 일어날 때, 스케줄링 체계가 비선점적 또는 협력적이라고 한다. 그 반대는 선점적이다. 비선점적 스케줄링에서 CPU가 프로세스에 할당되면 프로세스는 종료하거나 대기 상태로 전환하여 CPU를 해제할 때까지 CPU를 유지한다. Windows, macOS, Linux, UNIX를 포함한 거의 모든 최신 운영 체체는 선점적 스케줄링 알고리즘을 사용한다.
선점적 스케줄링은 여러 프로세스 간에 데이터가 공유될 때 경쟁을 초래할 수 있다. 데이터를 공유하는 두 프로세스의 경우, 한 프로세스가 데이터를 업데이트하는 동안, 선점되어서 두 번째 프로세스가 실행될 수 있다. 그런 다음 두 번째 프로세스는 일관되지 않은 상태의 데이터를 읽으려고 한다. 이 문제는 Chpater 6에서 자세히 설명한다.
선점은 운영체제 커널의 설계에도 영향을 미친다. 시스템 호출을 처리하는 동한, 커널은 프로세스를 대신하여 활동으로 바쁠 수 있다. 이러한 활동에는 커널의 데이터를 변경하는 것이 포함될 수 있다. 이러한 변경 중에 프로세스가 선점되고 커널이 동일한 structure를 읽거나 수정해야 하는 경우에는 혼란이 뒤따른다.
운영 체제 커널은 비선점적 또는 선점적으로 설계할 수 있다. 비선점형 커널은 컨텍스트 스위칭을 수행하기 전에 I/O가 완료될 때까지 시스템 호출이 완료되거나 프로세스가 차단될 때까지 기다린다. 이 방식은 커널 데이터 구조가 일관되지 않은 상태에 있는 동안, 커널이 프로세스를 선점하지 않으므로 커널 구조가 간단하다는 것을 보장한다. 이 커널 실행 모델은 task가 주어진 시간 프레임 내에서 실행을 완료해야 하는 실시간 컴퓨팅을 지원하기에 적압하지 않다. 선점형 커널에는 공유 커널 데이터 구조에 엑세스할 때 경쟁 조건을 방지하기 위해 mutex lock 같은 메커니즘이 필요하다. 대부분 최신 운영 체제는 커널 모드에서 실행될 때 완전히 선점형이다.
뮤텍스 락(Mutex Locks)
임계 구역을 보호하고 경쟁 상태(race condition)를 예방한다. mutex lock을 이용하는 프로세스들은 임계구역 입장 전 Lock을 얻어야 하고 임계 구역을 나가게 되면 Lock을 해제해야 한다.
경쟁 상태(race condition)
2개 이상의 프로세스가 공유 자원을 병행적으로 읽거난 쓰는 상황을 말하며, 공유 자원 접근 순서에 따라 실행 결과가 달라지는 상황.
임계 구역(Critical Section)
공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 코드 영역. 임계 구역 안에서 race condition이 발생.
인터럽트는 언제든지 발생할 수 있고 커널에서 항상 무시할 수 없기 때문에 인터럽트의 영향을 받는 코드 섹션은 동시에 사용되지 않도록 보호해야 한다. 운영 체제는 거의 항상 인터럽트를 허용해야 하는데, 그렇지 않으면 입력이 손실되거나 출력이 덮어쓰일 수 있다. 이러한 코드 섹션이 여러 프로세스에서 동시에 엑세스되지 않도록 진입 시 인터럽드를 비활성화하고 종료시 인터럽트를 다시 활성화한다. 인터럽트를 비활성화하는 코드 섹션은 자주 발생하지 않으며, 일반적으로 명령어가 거의 없다.
5.1.4 Dispatcher
CPU 스케줄링 기능에 관련된 또 다른 구성요소는 디스패처이다. 디스패처는 CPU 스케줄러가 선택한 프로세스에 CPU 코어의 제어권을 주는 모듈이다. 이 기능은 다음을 포함한다.
- 한 프로세스에서 다른 프로세스로의 컨텍스트 스위칭
- 사용자 모드로 전환
- 사용자 프로그램에 적절한 위치로 점프하여 해당 프로그램 재개
디스패처는 모든 컨텍스트 스위칭 중에 호출되므로 가능한 빨라야 한다. 디스패처가 한 프로세스를 중지하고 다른 프로세스를 실행하는 데 걸리는 시간을 디스패치 latency(지연)이라고 하며 그림 5.3에 나와있다.
컨텍스트 스위치가 얼마나 자주 발생하는 가를 고려해야한다. 시스템 전체 레벨에서, 컨텍스트 스위치의 수는 Linux 시스템에서 사용할 수 있는 vmstat 명령을 사용해서 얻을 수 있다.
// 명령
vmstat 1 3//출력
----cpu----
24
255
339첫 번째 줄은 시스템이 부팅된 이후 1초 동안의 평균 컨텍스트 스위치 수를 나타내고, 다음 두 줄은 두 개의 1초 동안의 컨텍스트 스위치 수를 나타낸다. 이 머신이 부팅된 이후, 초당 24개의 컨텍스트 스위치가 발생했고, 지난 1초 동안 255개의 컨택스트 스위치가 이루어졌고, 그 전 1초 동안 339개의 컨택스트 스위치가 이루어졌다.
/proc 파일 시스템을 사용하여 주어진 프로세스에 대한 컨텍스트 스위치 수를 결정할 수도 있다. 예를 들어, 파일 /proc/2166/status의 컨텐츠는 pid = 2166인 프로세스에 대한 다양한 통계를 나열한다.
//명령
cat /proc/2166/status//출력
voluntary_ctxt_switches 150
nonvoluntary_ctxt_switches 8이 출력은 프로세스 수명 동안 컨텍스트 스위치의 수를 보여준다. 자발적 컨텍스트 스위치는 프로세스가 현재 사용할 수 없는 리소스(ex: I/O 차단)를 필요로 하기 때문에 CPU 제어를 포기했을 때 발생한다. 비자발적 컨텍스트 스위치는 CPU가 프로세스에서 제거 되었을 때, 예를 들어 시간 슬라이스가 만료되었거나 우선순위가 더 높은 프로세스가 CPU를 선점했을 때 발생한다.
해야하는 일을 정하는 것까지가 Scheduler의 일, 실제로 cpu를 프로세스에 할당하는 것이 Dispather의 일.
따라서 넓은 의미의 Scheduling은 Scheduler와 Dispatcher 기능을 동시에 말한다.
