운영체제

4. CPU 스케줄링 알고리즘

ggomjiu 2025. 1. 16. 17:13

CPU Scheduling

: 언제 어떤 프로세스에 CPU를 할당할지 결정한는 작업

- CPU 이용률을 극대화하기 위해서는 멀티 프로그래밍이 필요함

 

1. CPU - I/O Burst Cycle

- 프로세스 실행은 CPU 실행과 I/O 대기 사이클로 구성

- CPU Burst : 프로그램 실행 중 CPU 연산이 연속적으로 실행되는 상황

- I/O Burst : 프로그램 실행 중 I/O 장치의 입출력이 이루어지는 상황

- 모든 프로그램은 CPU, I/O Burst의 연속이지만, 프로그램의 종류에 따라서 각 Burst의 빈도나 길이가 다름

- I / O Bound Job : CPU를 짧게 쓰고 중간에 I/O가 끼어드는 job

  • CPU Burst가 짧은 경우
  • interactive함
  • 빈도 잦음

- CPU Bound job : CPU만 오랫동안 쓰는 job

  • CPU Burst가 긴 경우
  • 빈도 낮음(한 번에 길게)

- CPU Bound job는 CPU를 많이 쓰고, I/O Bound job은 CPU를 짧게, 잦게 씀

-> 가능하면 사람과 interactive하는 I/O Bound job에 CPU를 우선적으로 주는 것이 필요

 

2. CPU Scheduler

- CPU가 유후 상태가 될 때 마다, OS는 Ready queue에 있는 프로세스들 중에 누구에게 CPU를 줄 것인지, 얼마나 쓰게 할 것이지 결정해야 함 -> 이를 수행하는 커널 코드

- CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당

- Ready Queue는 반드시 FIFO방식의 Queue가 아니어도 되고, 우선순위 큐, 트리 등으로 구현될 수 있음

- 일반적으로 Queue에 있는 레코드들은 프로세스의 프로세스 제어블록들(PCB)임

 

1) CPU Scheduler가 필요한 경우

  1. 실행 상태에서 대기 상태로 전환될 때
  2. 실행 상태에서 준비 상태로 전환될 때
  3. 대기 상태에서 준비 상태로 전환될 때
  4. 종료 될 때

- 선점 스케줄링 : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit

- 비선점 스케줄링 : I/O or Event Wait, Exit

 

2) 비선점 스케줄링

- 1, 4번의 경우

- CPU가 한 프로세스에 할당되면 프로세스가 종료되거나 입출력 등의 이벤트가 있을 때까지 실행을 보장 -> 뺏을 수 없음

- 필요한 문맥 교환만 일어나기 때문에 Overhead가 상대적으로 적음

- 프로세스의 배치에 따라 효율성 차이가 많이 남

- 응답 시간 예측 가능

- 짧은 작업을 수행하는 프로세스라도 긴 작업이 종료될 때까지 기다려야 함

문맥 교환
- CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때, 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(Context)를 교체하는 작업
- 자발적 문맥 교환 : 현재 사용 불가능한 자원을 요청했을 때 프로세스가 CPU 제어를 포기한 경우 발생
- 비자발적 문맥 교환 : 타임 슬라이스가 만료되었거나 우선 순위가 더 높은 프로세스에 의해 선점되는 경우와 같이 CPU를 빼앗겼을 때 발생

 

 3) 선점 스케줄링

- 비선점을 제외한 모든 경우

- 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료 시에 더 높은 우선 순위 프로세스가 발생되었음을 알았을 때, 현 실행 프로세스로부터 강제로 CPU를 회수하는 것

높은 우선 순위를 가진 프로세스를 빠르게 처리하려는 시스템에 유용

- 빠른 응답을 요구하는 시분할 시스템에 유용

- CPU 처리 시간이 매우 긴 프로세스의 사용 독점을 막을 수 있어 효율적임

- 높은 우선 순위를 가진 프로세스들만 들어오는 경우 Overhead 발생

인터럽트(Interrupt)
- CPU가 특정 기능을 수행하는 도중에 급하게 다른 일을 처리하고자 할 때 사용할 수 있는 기능
- 어느 시점에서건 일어날 수 있고, 커널에 의해서 항상 무시될 수는 없기 때문에, 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 함

오버헤드(Overhead)
- 어떤 일을 처리할 때 추가적으로 소모된 자원
- EX) 프로그램의 실행 흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때, 추가적으로 시간, 메모리, 자원이 사용되는 현상

 

4) 디스패처(Dispatcher)

: CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈

- 한 프로세스에서 다른 프로세스로 문맥을 교환

- 사용자 모드로 전환

- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동

- 디스패치 지연 : 디스패치가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간

 

3. 스케줄링 성능 척도, 기준(Scheduling Criteria)

: 스케줄링 알고리즘을 평가할 수 있는 기준

- CPU 관점에서 따지고 있으므로, 한 프로세스가 시작해서 종료할 때까지가 아닌 매 CPU Burst 건 1개에 대한 것에 한해서만 따진다고 이해 해야 함

1) 시스템 입장에서의 성능 척도

- CPU 이용률(CPU Utilization)

  • 시간당 CPU를 사용한 시간의 비율
  • 프로세스를 실행 상태로 항상 유지하려고 해야 함

- 처리량(Throughput)

  • 단위 시간 당 완료된 프로세스의 개수

 

2) 프로그램 입장에서의 성능 척도

- 총 처리 시간, 반환 시간(Turnaround Time)

  • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
  • 작업이 준비 큐에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합

- 대기 시간(Waiting Time)

  • 대기열에 들어와 CPU를 할당 받기까지 기다린 시간
  • 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합

- 응답 시간, 반응 시간(Response Time)

  • 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
  • 대기 시간과 비슷하지만 다른 점은, 대기 시간은 분지 큐에서 기다린 모든 시간을 합친 것이지만 
  • 반응 시간은 CPU를 할당받은 최초의 순간까지 기다린 시간 한 번만을 측정

-> CPU Utilization, Throughput을 최대화하고, Turnaround Time, Waiting Time, Response Time을 최소화하는 알고리즘의선택이 바람직한 선택

 

4. 시스템 별 목표

1) Batch System

: 한 번에 하나의 프로그램만 수행하는 것

- 가능한 많은 일을 수행하기 위해 Throughout과 CPU Utilization이 중요

 

2) Interactive System

: 사용자가 컴퓨터 앞에서 대화형으로 동작하는 시스템

- Time Sharing 기법을 이용해야 함

- Response Time -> 프로세스가 Ready Queue에서 대기하는 시간을 최소화함

- Waiting Time -> 프로세스가 Wait Queue에서 대기하는 시간을 최소화함

- Proportionality -> 사용자가 요구하는 바를 이루어야 함

 

3) Real - Time System

: 시간 제약 조건이 걸려있는 시스템

- Meeting DeadLines

- Predictability

 

5. CPU Scheduling Algorithm

1. 선입 선처리 알고리즘 (FCFS)

: CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 방식

- 비선점형

작성이 간단하고 이해하기 쉬움

- 평균 대기 시간이 길어질 수 있음

- 응답 시간이 길어질 수 있음

- 반환 시간 면에서는 좋을 수 있음

- 호위 효과(Convoy Effect)가 발생할 수 있음

호위 효과(Convoy Effect)
: CPU 사용 시간이 긴 프로세스에 의해 사용 시간이 짧은 프로세스들이 오래 기다리는 현상
- 호위 효과가 발생할 경우 CPU와 장치 이용률이 낮아짐

 

2. 최단 작업 우선 스케줄링(SJF)

: CPU Burst 길이가 가장 작은 프로세스부터 순서적으로 CPU 코어를 할당하는 방식

- 비선점형 + 선점형

- 평균 대기 시간을 줄일 수 있음

 

3. 라운드 로빈 스케줄링(RR)

: 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간으로 제한하여 이 시간이 경과하면 프로세스로부터 CPU를 회수해 준비 큐에 있는 다른 프로세스에게 CPU를 할당

- 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효율적

  • n개의 프로세스가 있을 때, 할당 시간을 q로 설정하면 어떤 프로세스도 (n-1)q 시간 이상을 기다리지 않아도 됨
  • 성능이 q의 크기에 많은 영향을 받음
  • q가 커진다면 -> FCFS처럼 작동
  • q가 매우 작아지면 -> process sharing이라고 부름, 이것은 n개의 프로세스가 프로세서 속도의 1/n씩으로 작동함, 문맥 교환의 오버헤드가 커짐

4. 우선 순위 스케줄링(Priority Scheduling)

: 준비 큐에서 기다리는 프로세스들 중에서 우선 순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식

- 비선점형 + 선점형

- 정적 / 동적으로 우선 순위를 부여해 높은 순으로 CPU에 할당하는 방식

  • 내부 : 제한 시간, 기억 장소 요청량, 사용 파일 수, 평균 프로세서 Burst에 대한 평균 입출력 Burst의 비율
  • 외부 : 프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적 요인

 

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

: 우선 순위 스케줄링이 라운드 로빈과 결합한 스케줄링 알고리즘

- 선점형

- 성격이 다른 프로세스들을 별도로 관리하고 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 여러 개로 분할하여 관리

- 각 큐는 각자의 스케줄링 알고리즘을 가지고 있음

- 각 큐 사이에서 프로세스들이 이동할 수 없음

- 우선 순위가 낮은 큐들이 실행 못하는 것을 방지하고자 큐마다 다른 Time Quantum을 설정

  • 우선 순위가 높은 큐 : 작은 Time Quantum
  • 우선 순위가 낮은 큐 : 큰 Time Quantum

 

6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

: 다단계 큐 스케줄링과 비슷하지만, MFQ는 각 큐 간에 프로세스들이 이동할 수 있음

- 선점형

- 다단계 큐에서 자신에게 할당된 Time Quantum을 다 사용한 프로세스는 밑으로 내려가고 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 위치 그대로 둠

- 짧은 작업에 유리하며 입출력 위주의 작업에 우선권을 줌

- 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

 

7. HRN(Highest Response-ratio Next)

: 점유 불평등 현상이 발생하는 SJF 알고리즘을 보완하기 위해 만들어짐

- 우선 순위를 계산하여 동작함

- 비선점형

- 준비 큐에서 우선 순위에 밀려서 오랫동안 CPU를 받지 못하는 프로세스의 우선 순위를 높이는 방식 -> 기아 현상 보완

- 우선 순위 = (대기 시간 + 실행 시간) / (실행 시간)