[OS] 6장 CPU 스케줄링

6장, CPU 스케줄링

 

CPU?

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

 

프로그램 카운터(Program Counter : PC)?

현재 수행할 코드의 메모리 주소 값을 가지고 있는 레지스터

---

기계어 명령의 종류

• CPU 내에서 수행되는 명령
  - 수행 속도가 매우 빠름
  - 일반명령
  - ex) Add
• 메모리 접근을 필요로 하는 명령
  - CPU 내에서 수행되는 명령보다는 느리지만 비교적 빠른 속도
  - 일반명령
  - ex) Load, Store
• 입출력을 동반하는 명령
  - 매우 긴 수행 시간
  - 특권 명령

 

프로그램의 수행 단계

• CPU 버스트(burst)
  사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
• I/O 버스트(burst)
  I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

• CPU 바운드 프로세스
  CPU 버스트가 길게 나타나는 프로세스 (I/O 작업이 거의 없음)
  입출력 작업 없이 상당 시간을 CPU 작업에 소모하는 계산 위주의 프로그램
• I/O 바운드 프로세스
  CPU 버스트가 짧게 나타나는 프로세스 (I/O 요청이 빈번함)
  사용자로부터 인터랙션을 받아 프로그램을 수행시키는 대화형 프로그램(interactive program)
  
  

 

CPU 스케줄링 시, CPU 버스트를 분석하는 것이 중요하다. CPU 버스트가 짧은 프로세스는 대부분 대화형 작업인데, 대화형 작업의 경우 사용자에 대한 빠른 응답이 중요하다. 따라서 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다. 즉 I/O 버스트 프로세스에 높은 우선순위를 주어야 한다는 것이다.

 

 

CPU 스케줄러

준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드

 

 

 

CPU 스케줄링 방식

• 선점형(preemptive)
  프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법
  - 할당 시간(time quantum)을 부여한 후, 타이머 인터럽트를 발생시키는 방법
  - ex) 실행상태에 있던 프로세스가 타이머 인터럽트에 의해 준비상태로 바뀌는 경우, I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고, 프로세스의 상태가 준비상태로 바뀌는 경우(I/O가 완료된 프로세스에게 CPU를 할당)
• 비선점형(nonpreemptive)
  CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
  - ex) 실행상태에 있던 프로세스가 I/O요청 등에 의해 봉쇄 상태로 바뀌는 경우, CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

 

디스패처(dispatcher)

- 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드 

- 현재 수행 중이던 프로세스의 문맥(context)을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정 수행

- 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간 : 디스패처 지연시간(dispatch latency) -> 문맥 교환 오버헤드

 

 

스케줄링 성능 평가 지표

시스템 관점

• CPU 이용률(CPU utilization) : 전체 시간 중에서 CPU가 일을 한 시간의 비율.
  휴면(idle) 상태의 시간을 최대한 줄이는 것이 목표
• 처리량(throughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지
  주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리 

사용자 관점

• 소요시간(turnaround time) : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU버스트가 끝날 때까지 걸린 시간
  준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간의 합
• 대기시간(waiting time) : CPU버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
• 응답 시간(response time) : 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
  타이머 인터럽트가 빈번할수록 응답 시간은 짧아진다

 

스케줄링 알고리즘

• 선입선출 First-Come First-Served : FCFS) 스케줄링
  프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
  CPU를 할당받은 프로세스가 자진해서 CPU를 반납할 때까지 빼앗지 않음
  - 한계 : 대기시간 증가(콘보이 현상-Convoy effect), I/O 장치들의 이용률 하락
  ※ 콘보이 현상 : CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착하여 오랜 시간을 기다리는 것
  
  
• 최단 작업 우선(Shortest-Job First : SJF) 스케줄링
  CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  평균 대기시간이 가장 짧은 최적 알고리즘(optimal algorithm)
  - 선점형(preemptive) : CPU버스트가 더 짧은 프로세스가 도착하면, CPU를 빼앗아 그 프로세스에게 할당하는 것
    => SRTF(Shortest Remaining Time First) 일반적인 시분할 환경에서 평균 대기시간을 가장 많이 줄일 수 있는 방식
  - 비선점형(non-preemptive) : 일단 CPU를 획득하면, 자진 반납 전까지 CPU를 빼앗지 않는 것
  CPU 버스트 시간 예측
  
  - 한계 : 기아 현상(starvation) - 해당 프로세스보다 CPU버스트가 짧은 프로세스가 계속 도착하여, 영원히 CPU를 할당받지 못하는 현상
  
  
• 우선순위(priority) 스케줄링
  준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  우선순위 값(priority number)을 통해 표시
  여러 가지 방식으로 우선순위 결정 가능
  - 한계 : 기아 현상
  => 기아 현상 해결을 위해 노화(aging) 기법을 사용하여 대기시간이 길어지면 우선순위를 조금씩 높여준다
  
  
• 라운드 로빈(Round Robin) 스케줄링
  각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 CPU를 회수하여 준비 큐에 있는 프로세스에게 CPU를 할당하는 방식
  할당 시간(time quantum) : 연속적으로 사용할 수 있는 최대 시간, 너무 길면 FCFS와 같아지고, 너무 짧으면 오버헤드가 커진다
  여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적
  동일한 CPU 버스트 시간을 가진 프로세스가 동시에 들어올 경우, 비효율적일 수 있음
  
  
• 멀티 레벨 큐(multi-level queue)
  준비 큐를 여러 개로 분할해 관리하는 스케줄링 방식
  별도의 준비 큐를 두어 성격이 다른 프로세스를 관리하고, 성격에 맞는 스케줄링을 적용한다
  - 전위 큐(foreground queue) : 대화형 작업을 담기 위한 큐 - 라운드 로빈 스케줄링
  - 후위 큐(background queue) : 계산 위주의 작업을 담기 위한 큐 - FCFS 스케줄링
  큐 자체에 대한 스케줄링이 필요 - 고정 우선순위 방식 / 타임 슬라이스(time slice) 방식
  ※ 타임 슬라이스 방식 : 각 큐에 CPU 시간을 적절한 비율로 할당하는 방식
  
  
• 멀티 레벨 피드백 큐(Multilevel Feedback Queue)
  여러 큐를 사용하여 프로세스를 줄 세우면서, 프로세스가 다른 큐로 이동할 수 있는 방식
  멀티 레벨 큐 + 큐 간 이동
  
  
• 다중 처리기(multiple-processor) 스케줄링
  다중 처리기 환경에서의 스케줄링 방식
  프로세스를 한 줄로 줄 세우고 CPU가 알아서 다음 프로세스를 꺼내가게 할 수 있지만, 특정 CPU에서 작업되어야 하는 프로세스가 있을 수 있다. 때문에 각 CPU 별로 줄 세우기를 할 수 있는데, 이때 특정 CPU에 작업이 편중되는 현상이 발생할 수 있다. 이를 해결하기 위해 다중 처리기 스케줄링은 부하 균형(load balancing) 메커니즘을 필요로 한다.
  - 대칭형 다중처리(symmetric multi-processing) : 각 CPU가 알아서 스케줄링 결정
  - 비대칭형 다중처리(asymmetric multi-processing) : 하나의 CPU가 모든 CPU의 스케줄링 및 데이터 접근을 책임 짐
  
  
• 실시간(real-time) 스케줄링
  각 작업마다 주어진 데드라인이 있는 실시간 시스템에서 사용하는 스케줄링 방식
  - 경성 실시간 시스템(hard real-time system) : 시간을 정확히 지켜야 하는 시스템. ex) 미사일 발사, 원자로 제어 등
  - 연성 실시간 시스템(soft real-time system) : 데드라인을 지키지 못해도 위험하지는 않은 것. ex) 스트리밍
  실시간 환경에서는 빠른 서비스도 중요하지만, 데드라인을 지키는 것이 더 중요하다
  EDF(Earlist Deadline First) 스케줄링 : 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 방식

 

 

스케줄링 알고리즘 평가방법

- 큐잉 모델(queueing model)

- 시뮬레이션(simulation)

- 구현 및 실측(implementation & measurement)

 

 

 

 

 

---

참고 자료

반효경, 『운영체제와 정보기술의 원리』, 이화여자대학교출판문화원(2020), p145-p175