[OS] CPU 스케줄링 기본 개념과 기준 정리

CPU 스케줄링 기본 개념

• 기본 가정
  • 일반적인 스케줄링 개념을 논의하는 경우 → 프로세스 스케줄링
  • 스레드에 국한된 개념을 가리키는 경우 → 스레드 스케줄링
  • “CPU에서 실행”이라는 용어를 사용하는 경우
    → 프로세스가 CPU 코어에서 실행되고 있음을 의미

 

다중 프로그래밍

• 다중 프로그래밍의 목적
  • CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데에 있음
  • 대기 시간으로 인한 낭비를 줄여 시간을 생산적으로 활용하려고 시도한다.
    
    • 대기 시간이 발생하는 이유 → 프로세스는 I/O 요청이 완료되기를 기다려야 함
      
      
• 다중 프로그래밍 개념 → 해당 개념은 모든 처리 코어로 확장됨
  • CPU를 항상 바쁘게 유지한다. → 다수의 프로세스를 메모리 내에 유지한다.
    • 어떤 프로세스가 대기해야 하면, 운영체제는 CPU를 회수해서 다른 프로세스에 할당
    • 하나의 프로세스가 대기할 때마다 다른 프로세스가 CPU 사용을 양도받을 수 있다.
    • 일종의 스케줄링의 해당된다.

 

스케줄링

• 위와 같은 종류의 스케줄링은 운영체제의 기본적인 기능
  • 모든 컴퓨터 자원들은 사용되기 전에 스케줄 됨
    • CPU 또한 중요한 컴퓨터 자원 중 하나
      
      
• CPU의 스케줄링은 운영체제 설계의 핵심

 

---

CPU-I/O 버스트 사이클

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

CPU 버스트와 I/O 버스트

• 프로세스들은 이들 두 상태를 교대로 왔다 갔다 함
  1. 프로세스 실행은 CPU 버스트(Burst)로 시작
  2. 뒤이어 I/O 버스트 발생
  3. 다시 CPU 버스트 … (반복)
  4. 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신,
     실행을 종료하기 위한 시스템 요청과 함께

 

버스트 지속 시간 측정

CPU 버스트의 지속시간의 히스토그램

• 해당 곡선은 지수형 또는 초지수형으로 특성화됨
• 짧은 CPU 버스트가 많이 있으면 , 긴 CPU 버스트가 적다.
• I/O 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가진다.
• CPU 지향 프로그램은 다수의 긴 CPU 가질 수 있다.
• 이러한 분포는 CPU 스케줄링 알고리즘 구현시 매우 중요

 

---

CPU 스케줄러

• CPU 스케줄러 : 운영체제가 준비 큐에 있는 프로세스를 하나 고를 때의 선택 절차를 실행하는 곳
  • CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 실행
    • 유휴 상태 : 컴퓨터 시스템이 사용 가능한 상태이나 실제적인 작업이 없는 시간.
      
      
• 스케줄러는 실행 준비가 되어있는 메모리 내 프로세스 중 하나를 선택해서 CPU 할당
• 준비 큐는 반드시 선입선출(FIFO) 방식의 큐가 아니어도 된다.
  • 준비 큐는 선입선출 큐, 우선순위 큐, 트리, 순서 없는 연결 리스트로 구현할 수 있음
  • 개념적으로 준비 큐에 있는 모든 프로세스는 CPU에서 실행될 기회를 기다리며 대기
    
    
• 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB) 임

 

---

선점 및 비선점 스케줄링

CPU 스케줄링 결정에서 발생할 수 있는 4가지 상황

1. 한 프로세스가 실행 상태 → 대기 상태로 전환될 때
   • 예 : I/O 요청이나 자식 프로세스 종료를 기다리기 위해 wait()를 호출할 때
     
     
2. 프로세스가 실행 상태 → 준비 완료 상태로 전환될 때
   • 예 : 인터럽트 발생
     
     
3. 프로세스가 대기 상태 → 준비 완료 상태로 전환될 때
4. 예 : I/O 종료 시
5. 프로세스가 종료할 때

• 1번과 4번의 경우, 스케줄링 면에서 선택의 여지가 없다.
  → 실행을 위해 새로운 프로세스(준비 큐에 하나라도 존재한다면)가 반드시 선택되어야 함
  • 이러한 스케줄링 방식을 비선점(nonpreemptive)또는 협조적(cooperative)라고 부름
    
    
• 2번과 3번의 경우, 스케줄링 면에서 선택의 여지가 있음
  • 이러한 스케줄링을 선점(preemptive)라고 함

 

비선점형과 선점형

• 비선점 스케줄링
  • CPU가 한 프로세스에 할당되면 CPU를 방출할 때까지 점유한다.
    • CPU 방출 → 프로세스가 종료하거나, 대기 상태로 전환되는 것
      
      
• 선점 스케줄링
  • 다른 프로세스를 중지시키고 사용하고 있던 CPU를 가로채서 사용하는 것
  • 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있음
    • 예 : 두 프로세스가 자료를 공유하고 있는 경우 → 데이터의 일관성이 깨질 수 있음
      
      
  • 대부분의 최신 운영체제들은 선점 스케줄링 알고리즘을 사용

 

운영체제 커널 설계

• 운영체제 커널은 선점 또는 비선점 방식으로 설계될 수 있다.
• 선점은 운영체제 커널 설계에 영향을 준다.
  • 시스템 콜을 처리할 동안, 커널은 프로세스를 위한 활동으로 바쁠 수 있음
    • 이러한 활동에는 중요한 커널 자료 변경이 포함
      → 변경 도중 프로세스 선점이 발생하여 변경이 일어나면 혼란 발생
      
      
• 비선점형 커널
  • 문맥 교환 시작 전, 시스템 콜이 완료되거나 입출력 완료를 기다리며 프로세스 봉쇄를 기다림
    → 커널 자료구조가 비일관적인 상태에 있을 때 커널이 해당 프로세스를 선점하지 않음
    → 커널 구조를 단순하게 만듦
    
    
  • 이런 커널 실행 모델은 실시간 컴퓨팅을 지원하기 적절한 모델은 아님
    
    
• 선점형 커널
  • 공유 커널 데이터 구조에 액세스 할 때 경쟁 조건을 방지하기 위해 mutex락과 같은 기법 필요
  • 대부분의 최신 운영체제는 커널 모드에서 실행될 때 완전히 선점될 수 있다.

 

인터럽트

• 인터럽트는 어느 시점에서건 발생할 수 있다.
• 항상 커널에 의해서 무시될 수 없다.
  → 인터럽트에 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 함
  
  
  • 운영체제는 항상 인터럽트를 받아들일 필요가 있음
    • 그렇지 않으면 입력을 잃어버리거나 출력이 겹쳐서 쓰일 수 있다.
      
      
• 인터럽트에 영향받는 코드 보호하는 법
  • 다수 프로세스가 병행으로 접근할 수 없도록 진입점에서 인터럽트를 불능하고,
    출구에서 인터럽트를 다시 가능하게 함
    
    
    • 인터럽트 불능화는 자주 발생해서는 안되고 아주 적은 수의 명령어만 포함해야 함
      
      

 

---

디스패처(Dispatcher)

• 디스패처(Dispatcher) : CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈
• 다음의 3가지 작업 포함
  1. 한 프로세스에서 다른 프로세스로 문맥 교환하는 일
  2. 사용자 모드로 전환하는 일
  3. 프로그램을 다시 시가학 ㅣ위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

 

디스패치 지연(Dispatch latency)

• 디스패치 지연 : 디스패처가 하나의 프로세스를 정지하고 다른 프로세스를 시작하는데 걸리는 소요시간
  • 디스패처는 모든 프로세스의 문맥 교환 시 호출
    → 가능한 최고로 빨리 수행되어야 함

디스패치 역할

 

자발적 문맥 교환 vs 비자발적 문맥교환

• 자발적 문맥 교환 : 현재 사용 불가능한 자원을 요청해서 프로세스가 CPU 제어를 포기한 경우 발생
  • 예 : I/O를 기다리며 봉쇄됨
    
    
• 비자발적 문맥 교환 : CPU를 빼앗겼을 때 발생
  • CPU를 빼앗기는 상황 → 타임 슬라이스 만료, 우선순위가 더 높은 프로세스의 선점

 

---

스케줄링 기준

• CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 제시되어 있다.
  • 비교하는 데 사용되는 특성에 따라 최선의 알고리즘 결정에 큰 차이가 발생

 

---

사용되는 기준

• CPU 이용률(utilization) : 가능한 CPU를 최대한 바쁘게 유지하기를 원한다.
  • 실제 시스템에서는 40% ~ 90%까지의 범위를 가져야 함
    
    
• 처리량(throughput) : 작업량 측정의 한 방법으로, 단위 시간당 완료된 프로세스의 개수
  • CPU가 프로세스를 수행하느라고 바쁘다면 작업이 진행되고 있는 것
  • 긴 프로세스인 경우에는 이 비율은 몇 초 동안 한 프로세스가 될 수 있음
  • 짧은 트랜잭션인 경우 처리량은 초당 몇십 개의 프로세스가 될 수 있음
    
    
• 총 처리 시간(turnaround time) : 프로세스의 제출 시간과 완료 시간의 간격
  • 총 처리 시간은 준비큐에서 대기한 시간, CPU에서 실행한 시간, 그리고 I/O 시간을 합한 시간
    
    
• 대기 시간(waiting time) : 준비 큐에서 대기큐에서 대기하면서 보낸 시간의 합
  • CPU 스케줄링 알고리즘은 프로세스가 실행하거나 I/O을 하는 시간의 양에 영향 X
  • 스케줄링 알고리즘은 단지 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 줌
    
    
• 응답 시간(response time) : 응답이 시작되는 데까지 걸리는 시간
  • 응답을 출력하는 데 걸리는 시간이 아님
  • 대화식 시스템(interactive system)에서 총 처리 시간은 최선의 기준이 아닐 수 있음
    • 또 다른 기준인 요구 제출 후 첫 번째 응답이 나올 때까지의 시간일 수도 있음

 

---

스케줄링 최적화

• CPU 이용률과 처리량을 최대화하고,
  총 처리 시간, 대기시간, 응답 시간을 최소화하는 것이 이상적
• 대부분의 경우, 평균 시간을 최적화하려고 함
• 어떤 경우에는 평균보다는 최솟값/최댓값을 최적화하는 것이 바람직할 수 있음
  • 예
    • 모든 사용자가 좋은 서비스를 보장받기 우해, 최대 응답 시간을 최소화하는 경우
      
      
• 대화식 시스템(PC 데스크톱 혹은 랩톱 시스템)의 경우
  • 평균 응답시간 최소화보단, 응답 시간의 편차를 최소화하는 것이 중요하다고 제시