[OS/운영체제] CPU 스케줄링 (CPU Scheduling) - (1)

CPU 스케줄링 (CPU Scheduling)

단일 프로세서 시스템에서는, 한 번에 단 하나의 프로세스만 실행될 수 있다. 다른 모든 프로세스들은 CPU가 사용 가능해지고 자신이 다시 스케줄링될 때까지 반드시 기다려야만 하는 것이다.

멀티프로그래밍 시스템에서는 CPU 사용을 최대화하기 항상 몇 개의 프로세스들이 돌아가고 있다. 하지만 프로세스는 일반적으로 입출력 요청 등이 들어오면 그 요청이 완료될 때까지 대기해야 한다.

만약 컴퓨터 시스템이 CPU를 단순히 idle상태로 존재하도록 둔다면, 요청이 끝나길 기다리는 동안 아무것도 하지 않는 것이다. 이 때의 대기 시간은 그저 낭비될 뿐이다. 따라서 멀티프로그래밍 시스템은 이 필연적인 대기 시간을 효율적으로 사용하려 한다.

실행 중인 프로세스가 대기해야 할 때, 운영체제는 원래 실행 중이던 프로세스를 내리고 다른 프로세스를 실행하도록 올린다. 이러한 과정을 반복해 최대한 아무것도 하지 않는 시간을 줄이려는 것이다.

이러한 CPU 스케줄링은 운영체제의 핵심 기능이다.

CPU는 컴퓨터 자원 중 가장 중요한 것들 중 하나이기 때문에, 이를 스케줄링 하는 것이 운영체제 설계의 중심이 된다.

 

CPU-I/O Burst Cycle

CPU Burst와 I/O Burst가 번갈아가며 발생

CPU 스케줄링은 프로세스에 대한 관찰이 이루어져야만 성공할 수 있다.

프로세스의 실행은 CPU Execution(CPU 실행) 과 I/O wait(입출력 대기) 상태의 순환으로 이루어지는데, CPU 실행에서 발생하는 것을 CPU Burst, 입출력 대기에서 발생하는 것을 I/O Burst라 한다. 즉 프로세스의 실행은 CPU Burst, I/O Burst가 번갈아 발생하는 것으로 이해할 수 있다.

 

CPU Burst의 길이는 컴퓨터에 따라 광범위하게 측정되지만, 일반적으로는 다음과 같은 빈도를 가진다.

CPU Burst가 짧을수록 일반적으로 더 많이 발생하고, 길수록 더 적게 발생하는 것을 확인할 수 있다.

이는 CPU 스케줄링에 적합한 알고리즘을 선택하는 데에 있어 중요하다.

 

선점/비선점 스케줄링 (Preemptive/Nonpreemptive Scheduling)

CPU 스케줄링은 다음과 같은 상황에서 결정을 내린다.

1. 프로세스가 Running 상태에서 Waiting 상태로 전환될 때

2. 프로세스가 Running 상태에서 Ready 상태로 전환될 때

3. 프로세스가 Waiting 상태에서 Ready 상태로 전환될 때

4. 프로세스가 Terminate될 때

1번과 4번 상황에서는 다른 선택지가 없다. 실행을 위한 다른 프로세스가 Ready Queue에서 선택된다.

하지만 2, 3번 상황에서는 다른 선택지가 존재한다.

 

1, 4번과 같은 상황만 존재할 때, 우리는 이를 비선점 스케줄링(Nonpreemptive Scheduling)이라고 부른다.

그렇지 않을 경우, 선점 스케줄링(Preemptive Scheduling)이라 부른다.

 

비선점 스케줄링에서는 한번 할당된 프로세스는 종료, 대기 상태가 되기 전까진 계속 CPU를 차지하고 있게 된다. 하지만 선점 스케줄링에서는 스케줄링에 의해 한 프로세스가 실행되는 도중에 다른 프로세스와 교체될 수 있다.

즉, "현재 Running 상태의 프로세스에 대해 Reschedule 할 수 있는가?" 에 따라 선점/비선점을 구분한다.

 

선점 스케줄링의 문제

다음과 같은 상황을 생각해보자.

"서로 데이터를 공유하는 두 프로세스가 있다. 

한 프로세스가 데이터를 갱신하는 도중, 다른 한 프로세스가 선점되어 데이터를 읽는다."

데이터가 갱신되는 도중에 읽기가 선행되었으므로, 읽게 되는 데이터는 불완전한 데이터가 된다.

 

또한 이는 운영체제의 커널을 설계하는 데에도 영향을 준다.

만약 커널이 자신의 시스템 콜에 의해 중요 데이터를 다루는 도중에 다른 프로세스가 선점된다면?

시스템 콜을 다루는 동안에만 선점을 막는 방법을 생각해볼 수 있지만,

시스템 콜은 앞서 설명했듯 각종 사소한 작업에도 호출되기 때문에

선점을 통한 실시간 및 멀티프로세스 기능의 향상을 기대하기 어렵게 된다.

 

디스패처 (Dispatcher)

디스패처는 스케줄러에 의해 선택된 프로세스에게 CPU를 제어할 권한을 주는 모듈이다.

Switching context, Switching to user mode, 사용자 프로그램의 특정 부분으로 점프 또는 재시작의 기능을 수행할 수 있다.

따라서 디스패처는 모든 프로세스의 전환에 대해 가능한 빠른 속도로 동작해야 한다. 한 프로세스를 멈추고 다른 프로세스를 실행하는 데 걸리는 시간을 Dispath latency라 한다.

 

스케줄링의 기준 (Scheduling Criteria)

서로 다른 CPU 스케줄링 알고리즘은 각자 다른 이점을 갖는다.

따라서 특정 알고리즘을 선택하는 데에는 그에 따른 기준이 필요할 것이다.

 

CPU Utilization

우리는 가능한 CPU가 바쁘게 일하는 것을 원하므로, CPU의 사용량은 스케줄링의 기준이 될 수 있다.

이상적으로는 0 ~ 100%의 값을 가지지만, 현실적으로는 40 ~ 90%의 값을 갖는다.

 

Throughput

한 시간단위에 종료되는 일을 마치는 프로세스의 갯수를 측정한 것이다. (단위 시간동안 완료된 일의 양)

 

Turnaround Time

프로세스에 일이 할당되고(Submission) 그 일이 종료되기까지의 시간을 의미한다.

즉, 메모리 내에서 대기하는 시간, 준비 큐에서 대기하는 시간, 입출력 시간, 실행 시간을 모두 더한 값이다.

 

Waiting Time

CPU 스케줄링 알고리즘은 프로세스의 실제 실행시간이나 입출력 시간에는 영향을 주지 못한다.

준비 큐에서 프로세스가 대기하는 데 쓰이는 시간에만 영향을 준다.

 

Response Time

상호작용 시스템에서는 Turnaround Time은 좋은 기준이 되지 못할 수도 있다.

프로세스에서 발생한 출력이 모두 즉시 보여질 것이란 보장이 없기 때문이다.

(응답은 만들어졌으나, 사용자가 필요로 하기 전까지는 보여지지 않는 상황을 생각해보자.)

따라서, 프로세스의 Submission부터 최초의 응답이 만들어질 때까지의 시간을 기준으로 둔다.

 

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.