[운영체제] CPU 스케줄링 | KOCW 2017 이화여대 반효경 교수님

* 강의를 듣고 복습하며 정리한 내용입니다.

 

CPU

프로그램의 기계어 명령을 수행하는 컴퓨터 내 중앙 처리 장치

 

CPU 스케줄링

Ready Queue에 있는 프로세스 중 CPU를 줄 프로세스를 고르는 것. 운영체제 코드인 CPU 스케줄러에 의해 수행된다.

 

CPU 스케줄링의 필요성

사용자 프로그램은 CPU 작업과 I/O 작업의 반복으로 이루어진다. 

• CPU Burst: 사용자 프로그램이 CPU를 가지고 빠른 명령을 수행하는 작업.
• I/O Burst: I/O 요청이 발생한 후 커널을 통해 입출력을 수행하는 비교적 느린 작업.

 

 

 

프로세스는 이런 특성에 따라 두 가지로 나눌 수 있다.

• CPU-bound process: I/O 요청이 거의 발생하지 않아 CPU 버스트가 길게 나타나는 프로세스.
• I/O-bound process:  I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스.

 

우리가 사용하는 시분할 시스템내에는 다양한 CPU 사용 패턴을 가진 프로세스들이 있어 효율적으로 자원을 사용하기 위해서는 CPU 스케줄링이 꼭 필요하다.

 

 

 

CPU-burst time 분포를 보면 CPU를 한 번에 오래 사용하기보다는 짧게 사용하고 I/O 작업을 하는 프로세스들이 많다. 

* Interactive job에 조금 더 빠른 응답을 해줘야 한다.

 

CPU 스케줄링 방식

• 비선점형(nonpreemptive): CPU를 획득한 프로세스가 스스로 반납할 때까지 CPU를 빼앗지 않는 방식. 프로세스 종료나 입출력 등의 이벤트가 있기까지 실행을 보장한다.
• 선점형(preemptive): 비선점형과 반대로 운영체제가 CPU의 사용권을 빼앗을 수 있는 방식.

 

Dispatcher

CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘길 수 있도록 하는 운영체제의 코드. 이 과정을 context switch라고 한다. 

* 문맥 교환 시 CPU를 내어주는 프로세스의 상태를 PCB에 저장하고 새롭게 얻은 프로세스의 상태를 PCB에서 읽어온다.

 

CPU 스케줄링의 성능 척도

 

• 이용률: 전체 시간 중 CPU가 일을 한 시간의 비율.
• 처리량: 주어진 시간 동안 CPU 버스트를 끝낸 프로세스의 개수.
• 소요 시간: CPU 요청 시점부터 CPU 버스트가 끝날 때까지 걸린 시간(프로그램 시작부터 종료시간 XXX).
• 대기 시간: CPU 버스트 중 프로세스가 Ready Queue에서 기다린 시간의 합.
• 응답 시간: 프로세스가 Ready Queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간.

 

CPU 스케줄링 알고리즘

❕ FCFS (First-Come-First-Served)

선입선출 스케줄링으로 Ready Queue에 도착한 시간 순서대로 CPU를 할당한다.

단점: CPU 버스트가 긴 프로세스가 짧은 프로세스보다 먼저 들어오면 평균 대기 시간이 길어지고, 이로 인해 I/O 장치의 이용률도 낮아진다(= Convoy Effect)

 

❕ SJF (Shortest-Job-First)

다음 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당한다. 프로세스의 CPU 버스트가 끝날 때까지 CPU를 빼앗지 않는 비선점형 방식, CPU 버스트가 더 짧은 프로세스가 들어오면 CPU를 빼앗기는 선점형 방식으로 나눌 수 있다. 

* 후자의 경우 현재를 기준으로 남은 시간이 제일 짧은 프로세스에 CPU를 할당하기 때문에 Shortest-Remaining-Time-First(SRTF)라고도 한다. 

 

단점: CPU 버스트가 긴 프로세스의 경우 Starvation이 발생하고, CPU 버스트 시간을 정확하게 예측하기 힘들다.

장점: 최소 평균 대기 시간을 보장한다.

* 시간 예측의 경우 과거의 CPU 버스트 시간에 가중치를 매겨 계산한다.

 

 

❕ Priority Scheduling

높은 우선순위를 가진 프로세에게 먼저 CPU를 할당한다. 선점형과 비선점형 방식으로 나눌 수 있다.

단점: 앞서 SJF와 마찬가지로 Starvation이 발생할 수 있다.

해결책: aging 기법을 사용한다. 이는 대기 시간이 길어지면 우선순위를 높여 CPU를 할당받을 수 있도록 하는 기법이다.

* SJF의 경우 우선순위가 다음 CPU 버스트 시간인 Priority Scheduling이다.

 

❕ Round Robin

실제 사용하는 CPU 스케줄링의 근간이 되는 알고리즘으로, Timer를 사용해 연속적으로 CPU를 사용할 수 있는 시간을 제한한다. 이 제한 시간을 time quantum이라고 부른다.

 

단점: time quantum이 너무 길면 FCFS와 같은 결과가 나올 수 있다. 반대로 너무 짧으면 프로세스가 자주 바뀌어 context switch로 인한 오버헤드가 커진다.

* 일반적으로 시간은 10-100 ms로 설정한다.

장점: 프로세스가 n개, time quantum이 q일 때, 어떤 프로세스도 (n-1) q 이상 기다리지 않는다.

 

지금까지 하나의 Ready Queue를 사용하는 경우를 봤다면, 이를 여러 개로 분할해 관리하는 방법도 알아보자!

 

❕ Multilevel Queue

Ready Queue를 여러 개로 분할해 관리하는 스케줄링 기법. 일반적으로 다음과 같이 분할한다.

• Foreground Queue: 대화형 작업. 응답 시간을 짧게 하기 위해 Round Robin 스케줄링을 사용한다.
• Background Queue: 계산 위주의 작업. FCFS 스케줄링을 사용해 context switch로 인한 오버헤드를 줄인다.

 

여러 개의 큐가 있기 때문에, 큐 자체에 대한 스케줄링도 필요하다.

• Fixed priority scheduling: 고정적인 우선순위를 부여하는 방식. Foreground Queue와 Background Queue를 사용하는 경우 Foreground Queue의 프로세스에게 우선적으로 CPU를 할당한다.
• Time slice: 각 큐에 CPU 시간을 적절한 비율로 할당하는 방식. Starvation 문제를 해결할 수 있다.

 

 

❕ Multilevel Feedback Queue

멀티 레벨 큐에서 프로세스가 다른 큐로 이동할 수 있다는 점이 추가된 스케줄링 기법. Starvation 문제를 해결하기 위해 오래 기다린 프로세스를 우선순위가 높은 큐로 올리는 aging 기법을 적용할 수 있다.

 

 

다중 처리기 스케줄링 (Multiple Processor Scheduling)

CPU가 여러 개인 시스템을 다중 처리기 시스템(Multi-Processor System)이라고 부른다. 다중 처리기 스케줄링은 이 시스템 환경에서 사용하는 기법이다. 일부 CPU에 작업이 몰리지 않고 적절히 분산되도록 하는 Load balancing을 필요로 한다.

 

• 대칭형 다중처리: 각 CPU가 알아서 스케줄링을 결정한다.
• 비대칭형 다중처리: 하나의 CPU가 다른 모든 CPU의 스케줄링을 관리한다.

 

실시간 스케줄링 (Real-time Scheduling)

각 작업마다 주어진 데드라인 안에 작업을 처리해야 하는 실시간 시스템(Real-time System)에서 사용하는 기법이다. 

 

• Hard Real-time Scheduling: 정해진 시간 안에 특정 작업이 반드시 완료되도록 스케줄링한다. 예) 미사일 발사, 원자로 제어 등
• Soft Real-time Scheduling: 특정 작업이 다른 작업보다 높은 우선순위를 가지도록 스케줄링한다. 예) 스트리밍 시스템 등

 

스케줄링 알고리즘의 평가

• 큐잉 모델 (Queueing Model): 이론가들의 평가 방식. 프로세스의 arrival rate와 service rate를 입력값으로 해서 CPU의 처리량, 프로세스의 평균 대기 시간과 같은 각종 성능 지표를 구한다. 
• 구현 및 실측 (Implementation & measurement): 구현가들의 평가 방식. 운영체제 커널의 CPU 스케줄링 코드를 수정 후 실행시간을 측정한다.
• 시뮬레이션 (Simulation): 실제 시스템에 구현하는 것이 아닌 모의 프로그램에서 평가하는 방식이다. CPU 스케줄링 프로그램을 작성한 후 CPU 요청을 입력값으로 넣어 결과를 비교한다.

* 시뮬레이션에서 CPU 입력값은 가상으로 생성할 수도 있고, 실제 시스템에서 추출해 사용할 수도 있다(trace). 

 

 

---

운영체제