[운영체제] CPU 스케줄링

목차

1. CPU 스케줄링 개요

2. 디스패처

3. 스케줄링 알고리즘

 

1. CPU 스케줄링 개요

1) 개념

어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다. 이 때 CPU 스케줄러는 어떤 프로세스에 CPU를 배정할지 결정한다

 

2) 선점형 스케줄링과 비선점형 스케줄링

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

 

선점형 스케줄링(2번, 3번)

프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗는 방식이다. 시분할 시스템에서 타임이 만료되었거나, 인터럽트나 시스템 호출 종료 시 더 높은 우선 순위 프로세스가 발생 되었음을 알았을 때, 현 실행 프로세스로부터 강제로 CPU를 회수하는 것이다.

 

비선점형 스케줄링(1번, 4번)

CPU가 한 프로세스에 할당되면 그 프로세스가 종료하든지, 스스로 대기 상태로 전환해 CPU를 놔줄 때까지 기다렸다가 돌려받는 방식이다.

 

3) 스케줄링 기준

스케줄링 기준에는 5가지가 있다.

 

1. 이용률: CPU가 얼마만큼 사용되고 있는지를 의미한다.

2. 처리량: 단위 시간 당 완료된 프로세스의 개수로 나타낼 수 있다.

3. 소요 시간: 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 한다.

4. 대기 시간: 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.

5. 응답 시간: 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간이다.

 

CPU 이용률과 처리량은 최대로, 소요시간, 대기시간, 응답시간은 최소로하는 것이 가장 효율적이다.

 

2. 디스패처

1) 개념

CPU 스케줄러는 어떤 프로세스가 CPU를 할당받는지를 결정한다. 디스패처는 그 결정에 따라 선택된 프로세스에 CPU를 전달해주는 모듈이다.

 

 

3. 스케줄링 알고리즘

1) FCFS(First-Come First-Served)

개념

빨리 도착하는 순서대로 프로세스를 처리하는 방식

 

장점

1. 개발이 용이하다.

2. 공평성을 유지할 수 있다.

3. Starvation 이슈가 발생하지 않는다.

 

단점

1. 소요 시간이 긴 프로세스가 도착할 경우 짧은 프로세스들은 비효율적으로 계속 기다려야 한다.

 

 

2) SJF(Shortest-Job-First)

각 프로세스의 CPU burst time이 가장 짧은 프로세스를 먼저 스케줄하는 방식. 평균 대기 시간이 가장 짧지만, 사용 시간이 긴 프로세스는 영원히 CPU를 할당받지 못할 수도 있다.(Starvation 문제)

 

 

3) Priority Scheduling

우선 순위를 가진 프로세스에게 CPU를 할당하는 방식. 이 방식 또한 우선순위가 낮은 프로세스는 영원히 CPU를 할당받지 못할 수도 있다. (Starvation 문제)

한편, 이 Starvation문제는 시간이 지난 프로세스에 우선순위를 부여해주는 방식으로 해결할 수 있다.

 

 

4) Round Robin

각 프로세스는 동일한 크기의 할당 시간을 가진다. 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 서게 되는 방식이다.

 

 

6) MultiLevel Queue

작업을 여러 종류로 나누어 여러 개의 Queue를 사용하는 방식이다. 우선 순위가 낮은 큐가 실행되지 못하는 것을 방지하지 위해 큐마다 각각의 Time Quantum을 설정한다. 우선 순위가 높은 큐에는 작은 Time Quantum을, 낮은 큐에는 큰 Time Quantum을 설정한다. 하지만 이러한 방식은 한 번 큐에 들어가면 다른 큐로 이동하는 것이 불가능하다. 즉 유연하지 못하다는 단점이 있다.

 

 

7) MultiLevel Feedback Queue

예시

프로세스는 일단 가장 우선순위인 Queue에 들어가고 어떠한 결정에 의해 우선순위가 오르기도 하고 내리기도 하는 방식이다. 이 방식은 각각의 Queue 마다 어떤 스케줄링 알고리즘을 선택할지 결정할 수 있으며, 프로세스의 우선순위를 올릴지 내릴지에 대한 기준도 정할 수 있다.

위의 예시의 경우 8ms가 지나면 다음 Queue로 우선순위가 내려가는 식의 알고리즘이 적용되어 있는 것이다.

 

 

 

4.멀티 프로세서 스케줄링

1) Homogeneous processor

1. Queue를 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다. 

2. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 더 복잡해진다.

2) Load sharing

1. 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유한다.

3) Symmetric Multiprocessing

1. 각 프로세서가 알아서 각자 스케줄링 결정

4) Asymmetric Multiprocessing

1. 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세스는 거기에 따른다.

 

5. Real-Time 스케줄링

1) Hard real-time systems

1. 정해진 시간 안에 반드시 끝내도록 스케줄링

2) Soft real-time computing

1. 일반 프로세스에 비해 높은 priority를 가진다.

 

 

6. Thread 스케줄링

1) Local Scheduling

1. User level Thread의 경우, OS가 모르고, 프로세스 내에서 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다.

2) Global Scheduling

2. OS thread 경우, 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할 지 결정한다.

 

7. Algorithm Evaluation

1) Queueing models

1. 확률 분포로 주어지는 arrival rate와 service rate을 통해 각종 performance index 계산

2) 구현과 성능 측정

1. 실제 시스템에 알고리즘을 구현하여, 실제 작업을 성능 측정한다.

3) 모의 실험

알고리즘 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과를 비교한다.

 

 

본 포스팅은 kowc 이화여대 반효경 교수님 운영체제 강의를 바탕으로 작성하였습니다.