CPU 스케줄링

CPU 스케줄링

CPU스케줄링은 프로세서가 유휴시간없이 계속 프로세스에 할당되어 실행될 수 있도록 하기 위한 작업이다.

 

코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다. 다중 프로그래밍의 목적은 cpu 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다. 하나의 프로세스는, 어떤 I/O요청이 완료되기를 기다려야만 할 때까지 실행된다. 이렇게 되면 단순한 컴퓨터 시스템에서 cpu는 그저 놀고 있게 된다. 이러한 대기시간을 없애기 위해서 다중 프로그래밍에서는 이러한 시간을 생산적으로 활용하려고 시도한다. 어떤 프로세스가 대기해야 할 경우 운영체제는 CPU를 그 프로세스에서 회수해 다른 프로세스에 할당한다. 이러한 패턴은 반복된다.

 

이러한 종류의 스케줄링은 운영체제의 기본적인 기능이다. 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄 되므로 CPU의 스케줄리은 운영체제 설게의 핵심이 된다.

 

 

CPU-I/O 버스트 사이클

프로세스의 실행은 CPU 실행과 I/O대기 사이클로 구성되고 CPU 스케줄링은 이 두가지로 성공이 좌우된다. 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 한다. CPU 버스트로 프로세스는 실행된다. 뒤이어 I/O 버스트가 발생하고, 그 뒤를 이어 또다른 CPU 버스트가 발생하면 이 이후에도 계속 반복된다. CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가질 수 있고, I/O 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가진다. 이러한 분포는 CPU 스케줄링 알고리즘을 구현할 때 매우 중요하다.

 

 

CPU 스케줄러

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행한다. 그 선택 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다. 이 때, 준비 큐는 반드시 선입선출 방식의 큐가 아니다.

 

 

선점 및 비선점 스케줄링

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때(I/O의 요청이나 자식 프로세스가 종료되기를 기다리기 위해)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(인터럽트가 발생할 때)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(I/O 종료 시)
4. 프로세스가 종료할 때

1번과 4번의 경우 스케줄링 면에서는 선택의 여지가 없이 반드시 실행을 위해 새로운 프로세스가 선택되어야 한다. 그러나 2와 3을 위해서는 선택의 여지가 있다.

 

상황 1, 4 에서만 스케줄링이 발생할 경우, 이러한 스케줄링 방법을 비선점(nonpreemptive) 또는 협조적(cooperative)이라고 한다. 그렇지 않으면 그것은 선점(preemptive) 이라고 한다. 비선점 스케줄링 하에서는, CPU가 한프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.

 

 

디스패처(Dispatcher)

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

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

디스패처는 모든 프로세스의 문맥 교환 시 호출되므로 가능한 한 최고로 빨리 수행되어야 한다. 디스패척라 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연이라고 한다.

 

 

스케줄링 기준

CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되었다. 비교하는 데 사용되는 특성에 따라서 최선의 알고리즘을 결정하는 데 큰 차이가 발생한다.

• CPU 이용률: 우리는 가능한 CPU를 최대한 바쁘게 유지하기를 원한다. CPU의 이용륭은 실제 시스템에서 40%에서 90%까지의 범위를 가져야 한다.
• 처리량: CPU가 프로세스를 수행하느라고 바쁘다면, 작업이 진행되고 있는 것이다. 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이것을 처리량이라고 한다.
• 총처리 시간: 특정한 프로세스의 입장에서 보면, 중요한 기준은 그 프로세스를 실행하는 데 소요된 시간일 것이다. 프로세스의 제출 시간과 완료 시간의 간격을 총처리 시간이간이라고 한다.
• 응답 시간: 대화식 시스템에서, 총처리 시간은 최선의 기준이 아닐 수도 있따. 프로세스가 어떤 출력을 매우 일찍 생성하고, 앞서의 결과가 사용자에게 출력되는 사이에 새로운 결과를 얻으려고 연산을 계속하는 경우가 있다. 따라서 응답시간은 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간이다.

 

 

스케줄링 알고리즘

• 선입 선처리 스케줄링: CPU를 먼저요청하는 프로세스가 CPU를 먼저 할당 받는 가장 간단한 스케줄링 알고리즘. PCB를 원소로하는 선입선출 준비큐를 통해 쉽게 관리할 수 있다. 비선점형 알고리즘으로 써 한 프로세스가 CPU에 할당되면 종료되거나 I/O 처리를 요구될 때까지 CPU를 점유한다.

 

• 최단작업 우선 스케줄링(SJF): 버스트 길이가 가장 짧은 프로세스 부터 실행시킨다. 최적이긴 하지만 CPU 버스트이 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다. 

 

• 라운드 로빈 스케줄링(RR): 선입 선처리와 유시하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 시간 할당량 또는 타임슬라이스라고 하는 작은 단위의 시간을 정의해, CPU 스케줄러는 준비 큐를 돌면서 한번에 한 프로세스에 한번의 시간할당량 동안 CPU를 할당한다. 할당된 프로세스의 버스트 길이가 타임슬라이스보다 작으면 종료 후 다음 프로세스를 실행하고, 길 타임슬라이스 만큼 프로세스를 실행 한 후 상테를 PCB에 저장하고 다음 프로세스를 CPU에 할당한다. CPU 버스트의 80%는 타임슬라이스보다 작도록 설계해야 한다.

 

• 우선순위 스케줄링: 다양한 기준에 따란 프로세스별로 우선순위를 정하여 이 순서대로 먼저 처리한다.