[운영체제] CPU Scheduling (1) - What is CPU Scheduling?

CPU 내에서 하나의 core에서는 한 번에 단 하나의 process만 실행이 가능합니다. 그 말인즉슨 하나의 process가 실행되고 있으면, 다른 process는 실행이 되고 싶어도 사용 가능한 core가 생길 때까지 대기를 해야 한다는 뜻입니다. 만약 CPU에 진입한 process의 실행이 모두 완료가 되어야 다음 process가 CPU를 차지할 수 있다고 가정해봅시다. Process는 실행 중에 입출력 요청이 완료되기를 기다릴 때가 있습니다. 이러한 상황에서 CPU는 아무 작업도 실행하지 못하며 시간과 자원을 낭비하는 결과를 초래합니다. 또는 꼭 지금 수행해야 하는 process가 있는데 앞에서 수행 중인 process의 작업이 너무 길어서 한참을 대기해야 하는 경우에도 비효율적인 결과가 만들어집니다.

 

그래서 운영체제는 운영체제마다의 정책으로 스케쥴링을 수행해 줍니다. 즉, 어떤 process가 지금 CPU에서 실행될 것인지를 정해주는 알고리즘들을 가지고 있습니다. 이 것이 오늘 공부할 내용인 이 CPU 스케쥴링입니다.

 

1. CPU 스케쥴링?

CPU 스케쥴링이란 CPU를 process들 사이에서 교환해주는 작업을 의미합니다. 물론 실제로는 바로 앞에서 배운 thread를 이용해서 실행이 됩니다. 즉 CPU에서 현재 실행될 thread를 골라주는 작업이라는 뜻입니다. 실제로는 thread로 실행되지만 여기서는 그냥 process라고 표현하겠습니다.

 

그렇다면 왜 CPU 스케쥴링이 필요할까요? 정답은 바로 CPU의 활용성(utilization)을 높이기 위해서입니다. Process들은 통상적으로 CPU 작업과 입출력 작업을 반복해서 수행합니다. 사실 CPU를 사용하는 시간보다 입출력 장치에서 데이터를 읽어오는 데 사용하는 시간이 훨씬 많습니다. 이 말은 process 실행 도중에 CPU를 사용하지 않는 시간대가 꽤 많이 존재한다는 뜻이고, 따라서 이 시간에 다른 process가 CPU를 사용할 수 있도록 해줌으로써 CPU의 활용도를 높일 수 있습니다. 

 

실행 중이던 process가 CPU를 사용하지 않아 CPU가 할 일이 없어지게 되면 운영체제의 스케쥴링을 담당하고 있는  CPU 스케쥴러는 ready queue에서 대기하고 있는 여러 process 중에 지금 CPU에서 실행될 process를 선택하여 주어야 합니다. Ready queue는 process의 상태에 대해서 공부할 때 ready 상태에 있는 process들이 대기하는 queue라고 앞에서 process를 공부할 때 설명을 했었습니다. 앞에 공부했던 내용을 기억하신다면 아마 밑의 그림도 기억하시고 계실 것 같습니다. 

 

Process State

위 그림에서 숫자가 부여된 화살표로 process가 이동할 때 CPU 스케쥴러는 다음에 실행될 process를 선택해주는 스케쥴링을 수행하게 됩니다. 예시를 들면서 각각의 상황을 알아보겠습니다.

 

1. Running --> Waiting : Process가 입출력 신호를 기다리거나 부모 process가 자식 process의 종료를 기다릴 때. 

2. Running --> Ready : Interrupt가 발생했을 때. 

3. Waiting --> Ready : Waiting 상태에서 ready queue로 이동해온 process의 우선순위가 현재 CPU에서 실행되고 있는  process의 우선순위보다 높을 때. 

4. Running --> Terminated : Process가 종료되었을 때.

 

2. Preemptive vs. Nonpreemptive

CPU 스케쥴러에도 두 가지 종류가 있습니다. 바로 선점 스케쥴러 (Preemptive Scheduler)와 비선점 스케쥴러 (Nonpreemptive Scheduler)입니다. 이름의 뜻 그대로, 선점 스케쥴러는 CPU에서 다른 process가 실행되고 있더라도, 우선 순위에 따라 CPU를 선점하여 뺏어올 수 있는 스케쥴러입니다. 여기서 CPU를 뺏을 때는 interrupt를 이용합니다. Process가 실행 중에 CPU를 빼앗기면, 실행 중인 프로그램은 자연스럽게 분할되어 나중에 실행되게 되겠죠? 이는 실행 시간이 긴 process들의 CPU 독점을 막아 결과적으로 프로그램의 동시성(Concurrency)을 높여줄 수 있게 됩니다. 

 

반대로 비선점 스케쥴러는 현재 실행되고 있는 process가 실행을 완료할 때 까지 기다려주는 스케쥴러이죠. 물론 비선점 스케쥴러도 ready queue에서 대기 중인 process들 간의 우선순위는 존재합니다. 하지만 우선순위야 어쨌든 지금 실행되고 있는 CPU를 강제로 빼앗지는 않습니다. 지금 실행되고 있는 process가 실행을 끝내면 그때 누가 CPU를 차지할 것인지에 대한 우선순위이죠. 그래서 비선점 스케쥴러는 위에서 알아본 4가지 상황 중에서 1번째와 4번째 상황에서만 스케쥴링을 실행하면 됩니다. 다시 말해서 process가 자발적으로 CPU를 반납하는 상황에서만 스케쥴링을 실행합니다. 

 

3. 선점 스케쥴러의 약점

바로 위에서 선점 스케쥴러는 프로그램의 동시성을 높여줄 수 있는 장점을 가진다고 공부했습니다. 그렇다면 선점 스케쥴러가 무조건 좋은 것일까요? 선점 스케쥴러에게도 고려해야할 사항들이 있습니다. 그중에 가장 민감한 문제는 바로 Race Condition이라는 문제가 발생할 수 있다는 점입니다. 

 

꼭 운영체제라는 과목이 아니더라도, 다른 과목들에서 Race Condition이라는 개념은 꾸준히 들어보셨을 것이라 생각합니다만, 혹시 모르는 분들을 위해 간단히 설명하도록 하겠습니다. 한국말로 굳이 번역을 하면 '경쟁 상태'라는 뜻으로 번역이 가능한데, 즉 '둘 이상의 입력이나 조작의 순서 또는 타이밍이 결괏값에 영향을 줄 수 있는 상태'라는 정의를 가집니다. 컴퓨터 과학에서는 대부분 공유 메모리나 공유 변수와 같은 공유 자원에 대해 여러 개의 process가 동시에 접근을 시도할 때 그 타이밍이나 순서로 인해 결괏값이 영향을 받는 상태를 말합니다. 만약 두 process들이 메모리를 공유하고 있는데, 한 process가 메모리에 새로운 데이터를 업데이트하고 있는 중에 선점을 당해 실행을 멈추게 되면, 두 process가 서로 다른 데이터를 가지게 될 수도 있다는 것입니다.

 

예를 들어 설명하자면, A와 B라는 process들이 메모리를 공유하고 있는데 A가 CPU를 할당받아 연산을 수행하다가 공유 변수인 원래 0이었던 num이라는 변수의 값을 1로 변경하였습니다. 그리고 공유 메모리에 있는 num의 값도 1로 바꿔주려는 순간 선점을 당해 CPU를 뺏기는 바람에 공유 메모리의 num 값은 미처 바꾸지 못하는 상황이 오게 된다면, A는 num의 값을 1로 생각하고 있지만, B는 공유 메모리의 num 값이 업데이트되지 못한 채 여전히 0이라는 값을 가지고 있기 때문에 num 값을 0으로 알고 있게 되는 상태를 말합니다. 뒤에서 process synchronization 파트에서 상세하게 공부하게 될 것이기 때문에 간단하게 이해만 하고 넘어가면 되겠습니다. 

 

다른 문제로는 system call의 실행 중에 선점이 되는 경우가 있습니다. 앞에서 계속 공부했듯이, system call이 호출되었다는 말은 현재 CPU 모드가 kernel 모드로 변경되어 kernel 내부에서 작업이 수행되고 있다는 것이고, 이때 CPU를 빼앗겨 kernel 내부의 데이터 구조들이 일관성이 없어지는 상태가 생기면 더 큰 문제가 생길 수 있습니다. 그래서 system call의 호출 중에는 선점을 금지하는 등의 방법이 있지만, 완벽한 방법으로 볼 수는 없습니다.

 

4. Dispatcher

Dispatcher란 스케쥴러에 의해 선택된 process에게 주어지는 모듈로써, context switch와, user 모드로의 전환을 담당하며, 프로그램을 다시 실행하기 위해 프로그램 내부의 적절한 위치로 이동 하는 일을 합니다. Process 간의 context switch는 앞에서 공부했듯이 굉장히 많은 시간이 드는 작업이기 때문에 이 dispatcher는 가능한 한 최대한 빨라야 합니다. 이렇게 Dispatcher에 의해 실행 중이던 process가 실행을 멈추고 새로운 process가 CPU에서 실행을 시작하기까지 걸리는 시간을 Dispatch Latency라고 부릅니다.

 

 

 

 

 

오늘은 우선적으로 CPU 스케쥴링에 대한 소개를 해보았습니다. 제일 위 문단에서 운영체제는 각각의 스케쥴링 알고리즘들을 가지고 스케쥴링을 수행한다고 했던 것을 기억하시는지 모르겠습니다. 그래서 다음 글에서는 이 스케쥴링 알고리즘들에는 어떤 것들이 있는지 공부해보려고 합니다. 읽어주셔서 감사합니다.