운영체제(OS) - 5. CPU 스케줄링

 # 기계어 명령의 종류

   1. CPU 내부 수행 명령 (수행속도 가장 빠름)

     (일반명령) (CPU burst) (사용자모드)

     - Add 명령 : CPU내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령

 

   2. 메모리 접근 수반 명령 (수행속도 비교적 빠름)

     (일반명령) (CPU burst) (사용자모드)

     - Load 명령 : 메모리에 있는 데이터를 CPU로 읽어들이는 명령

     - Store 명령 : CPU 계산 결과값을 메모리에 저장하는 명령

 

   3. 입출력 동반 명령 (수행속도 느림)

     (특권명령) (I/O burst) (커널모드)

---

 # CPU Burst time

   Ready Queue 대기시간 + 프로그램이 직접 CPU를 가지고 명령을 수행한 시간 

   => 순수 CPU 사용시간

 

 # CPU Burst

   I/O 작업완료 후 ~ I/O 요청까지의 기간

   => I/O Burst 시작 전까지

  (= Ready Queue 대기시간 + 프로그램이 직접 CPU를 가지고 명령을 수행한 시간)

  (= turn-around time : 소요시간) 

 

---

 # I/O Burst time

   I/O 요청 ~ 요청 완료 후 다시 CPU 버스트로 돌아가기전까지의 시간

   (I/O 요청 후 기다리는 시간)

 

 # CPU Bound Process

  CPU Burst time이 대부분인 프로세스 (긴 CPU버스트 소수로 구성)

   

 # I/O Bound Process 

  I/O Burst time이 대부분인 프로세스 (짧은 CPU버스트 다수로 구성)

---

 # 스케줄링 우선순위

  CPU 버스트가 짧은 프로세스에게 우선적으로 CPU할당

    - 대화형 프로그램이므로 사용자에 대한 빠른응답을 위해서

    - I/O 장치의 이용률/효율성을 높이기 위해서

      (CPU 바운드 프로세스에게 먼저 할당할 경우 I/O 장치의 휴면상태가 길어짐) 

 

  # 스케줄링의 목표

   

    고비용의 자원인 CPU의 휴면(idle) 상태를 최대한 줄이는 것

 

---

 

 1. CPU 스케줄러

 

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

 

---

 

   # CPU 스케줄러 호출 케이스

    1 . 프로세스의 상태가 Running -> Blocked  (by I/O 호출등) (비선점형 스케줄링 방식)

    2. 프로세스의 상태가 Running -> Ready  (by 타이머 인터럽트) (선점형 스케줄링 방식)

    3. 프로세스의 상태가 Blocked -> Ready (by I/O 하드웨어 인터럽트)  (선점형 스케줄링 방식)

                     (문맥교환을 통해 인터럽트 당한 프로세스가 CPU를 반납 하고 I/O 완료 프로세스가 CPU를 획득하는 경우에 해당)

   

    4. 프로세스의 상태가 Running -> Terminated (by 프로세스 종료) (비선점형 스케줄링 방식)

 

   # CPU 스케줄링 방식

     1. 비선점형(nonpreemptive) 방식

       - CPU 획득 프로세스가 스스로 CPU 반납 전까지 CPU를 빼앗기지 않는 방식

     2. 선점형(preemptive) 방식 

       - CPU 획득 프로세스가 계속 CPU를 사용하기를 원하더라도 강제로 빼앗을 수 있는 방식

       - 할당시간(time quantum) 부여후 타이머 인터럽트를 발생시키는 것이 대표적인 예시

---

2. Dispatcher

 

CPU 스케줄러의 결정을 받고, 새롭게 선택된 프로세스에게 실제로 CPU를 이양하는 작업을 하는 운영체제의 코드부분

 

 

# 디스패쳐의 업무

 

수행중인 프로세스의 context 를 그 프로세스의 PCB에 저장

↓

새롭게 선택된 프로세스의 문맥 PCB로부터 호출 후 CPU 이양 

---

# 디스패치 지연시간(Dispatch latency)

  하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 이양하기 까지 걸리는 시간

  이 시간의 대부분은 문맥교환 오버헤드에 해당된다

 

---

3. 스케줄링 성능평가

 

# 시스템 관점 지표

  - CPU 이용률 & 처리량

# 사용자 관점 지표

  - 소요시간, 대기시간, 응답시간

---

# CPU 이용률 (CPU utilization)

 전체 시간 중 CPU가 일한 시간의 비율

 

# CPU 처리량 (CPU throughput)

 주어진 시간 동안 ready queue의 프로세스 중 CPU 버스트를 완료한 프로세스의 개수

(= CPU 버스트를 끝내고 ready queue를 떠난 프로세스의 개수)

 처리량을 늘리기 위해선 CPU 버스트가 짧은 프로세스에게 우선적으로 할당하는 것이 유리

---

# 소요시간 (turn-around time)

 Ready queue 대기시간 & CPU 사용시간의 합 

(= 단일 CPU 버스트 시간) 

 

# 대기시간 (waiting time) 

  단일 CPU 버스트 기간 중 프로세스가 Ready Queue 에서 기다린 시간

  타이머 인터럽트로 인해 한번의 CPU 버스트 중에도 Ready queue 대기사건이 여러번 발생할 수 있다.

 

# 응답시간 (response time)

  단일 CPU 버스트 기간 중, Ready Queue 에 들어온 후, 최초 CPU획득시 까지 기다린 시간

  사용자 입장에서 가장 중요한 성능척도

 

  타이머 인터럽트가 빈번할 수록, 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로

 최초 CPU 획득시간(응답시간)이 줄어든다.

  

---

4. 스케줄링 알고리즘

 

1. 선입선출 스케줄링 (FCFS : First-Come, First-Served)

 Ready queue 에 도착한 순서대로 CPU 할당

 자발적으로 CPU를 반납할 때까지 CPU를 빼앗지 않음

 평균대기시간 증가, I/O 장치 이용률 하락

 

 # 콘보이 현상(Convoy effect)

   CPU 버스트가 긴 프로세스가 먼저 도착해, 짧은 프로세스들이 오랜시간 기다려야하는 현상

---

 2. 최단작업 우선 스케줄링 (SJF : Shortest-Job First)

  CPU 버스트가 가장 짧은 프로세스에게 먼저 CPU를 할당하는 방식

  평균 대기시간을 가장 짧게하는 최적 알고리즘

 

---

  # 비선점형 SJF

• 일단 CPU 획득을 하면, CPU 자진반납전까지 뺏지않음

  # 선점형 SJF (SRTF : Shortest Remaining Time First)

• CPU 버스트가 더 짧은 프로세스 Ready Queue에 도착시, CPU 빼앗아 그 프로세스에게 이양
• 하지만, CPU 버스트가 긴 프로세스는 무작정 기다려야 하는 상황이 나올 수 있다.

  시분할 환경에서는 중간중간 새로운 프로세스가 Ready Queue 에 도착하므로 선점형 방식이 평균대기시간을 가장 많이 줄일 수 있다.

---

   # 기아 현상(starvation)

     선점형 SJF에서 CPU 버스트 시간이 짧은 프로세스가 계속 도착하여, 긴 프로세스는 영원히 할당 받지 못하는 경우

---

 # CPU 버스트 타임 예측

   현실적으로 프로세스의 CPU 버스트 시간을 미리 알 수 없기에 예측치가 가장 짧은 프로세스에게 CPU를 할당한다

   CPU 버스트 타임의 예측은 과거 CPU 버스트 시간을 통해 이루어진다.

   

   # (n+1)번째 CPU 버스트의 예측시간 T(n+1) 

   

      t(n) : n번째 실제 CPU 버스트시간

      T(n) : n번째 예측 CPU 버스트시간

      a : t(n)과 T(n), 두 상수의 반영비율을 정하기 위한 매개변수

 

      T(n+1) = a*t(n) + (1-a)*T(n)            // (0<a<1) 

                  = a*t(n) + (1-a) * ( a*t(n-1) + (1-a)*T(n-1) ) 

                  = a*t(n) + (1-a)*a * t(n-1) + ....                    

 

      => a는 0과 1사이의 값이기에, a*t(n) 부분 뒤쪽의 값은 식을 풀어낼수록 작아져 영향을 적게 미친다

      => 그러므로, 가장 최근의 실제 CPU 버스트 시간인 t(n)의 영향의 비중을 크게 주는 식이다

                           (오래된 과거일수록 영향력이 적어지도록 반영하는 방식)

---

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

Ready Queue에 있는 프로세스에서 우선순위가 가장 높은 프로세스에게 CPU 먼저 할당하는 방식

우선순위 값(priority number)이 작을수록 높은 우선순위를 가지는것으로 가정

 

CPU 버스트 시간을 우선순위값으로 정의하면, SJF 알고리즘과 동일한 의미

 

# 비선점형 우선순위 스케줄링

 우선순위 높은 프로세스 도착하더라도, CPU 제어권 뻇지않음

# 선점형 우선순위 스케줄링  

 우선순위 높은 프로세스 도착시, CPU 제어권 이양

 

# 노화(aging) 기법

기아 현상(starvation) 방지책

프로세스의 대기시간이 길어질수록 우선순위를 높이는 방식

---

4. 라운드로빈 스케줄링 (Round Robin Scheduling)

 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식

 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한

 일반적으로, SJF 방식보다 평균대기시간(average waiting time)은 길지만 응답시간(response time)이 짧다.

 

 CPU 버스트 시간에 비례해 대기시간(waiting time)과 소요시간(turn around time)이 증가한다.

 

 이 스케줄링의 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻게함과 동시에, CPU 버스트가 긴 프로세스가 불이익을 당하지 않도록 함

 즉, 대화형프로그램이 대부분 이거나, 여러 이질적인 프로세스들이 같이 실행되는 환경에서 효과적이다.

# 소요시간 (turn-around time)

 Ready queue 대기시간 & CPU 사용시간의 합 

(= 단일 CPU 버스트 완료까지 걸린 시간) 

 

# 대기시간 (waiting time) 

  단일 CPU 버스트 기간 중 프로세스가 Ready Queue 에서 기다린 시간

  타이머 인터럽트로 인해 한번의 CPU 버스트 중에도 Ready queue 대기사건이 여러번 발생할 수 있다.

 

# 응답시간 (response time)

  단일 CPU 버스트 기간 중, Ready Queue 에 들어온 후, 최초 CPU획득시 까지 기다린 시간

  사용자 입장에서 가장 중요한 성능척도

 

 평균대기시간보다 응답시간에 중점을 둔 스케줄링

 (n개의 프로세스가 Ready Queue 에 있고, 할당시간이 q라 할 때,

  모든 프로세스는 (n-1)q 시간 내에 적어도 한번은 CPU 할당이 가능하기 때문)

 

 # 할당시간(time quantum)

• 각 프로세스마다 CPU를 한번에 연속적으로 사용할 수 있는 최대시간
• 할당시간이 너무 길면, FCFS와 같은 결과
• 할당시간이 너무 짧으면, Context Switch 오버헤드 발생
• 인간이 느리지 않다고 체감할 정도의 시간규모로 설정
• 타이머 인터럽트로 제어한다.

---

5. 멀티레벨 큐(multi-level queue)

 

 Ready Queue를 여러개로 분할해 관리하는 스케줄링 기법

 성격이 다른 프로세스들을 별도로 관리하고, 프로세스 성격에 맞는 스케줄링을 위해 사용한다

 

 일반적으로 전위 큐(foreground queue)에 대화형작업을, 후위 큐(background queue)에 계산위주의 작업을 담으며,

 전위 큐 에서는 라운드 로빈 스케줄링을, 후위 큐 에서는 FCFS 스케줄링을 적용하여 context switch overhead를 감소시킨다

 

 보통 우선순위가 높은 큐가 비어 있을때만, 하위 큐가 서비스된다.

---

 # 고정 우선순위 방식(fixed priority scheduling)

  각 큐들에 고정적인 순위를 부여하여, 순위가 높은 큐를 먼저 서비스하는 방식

  우선순위가 높은 큐가 비어 있어야 낮은 큐가 서비스 가능하기에 기아현상이 발생할 수 있다

 

  # 타임 슬라이스 방식(time slice scheduling)

   기아현상(starvation)을 해소할 수 있게, 각 큐에 CPU 시간을 적절한 비율로 할당한다.

   예를 들자면, 전위 큐에는 80%, 후위 큐에는 20%를 할당하여 사용할 수 있다.

---

6. 멀티레벨 피드백 큐(multi-level feedback queue)

 

멀티레벨 큐 개념 + 프로세스가 다른레벨의 큐로 이동가능

노화(aging)기법을 적용하여, 우선순위가 낮은 큐에서 오래기다릴 수록 상위 큐로 승격시키는 방식을 사용할 수도 있다

 

FCFS 방식은 문맥교환 없이 CPU를 사용할 수 있기에 보통 후위큐로 사용한다.

 

상위 큐 2개는 라운로빈, 최하단 큐는 FCFS로 구성

 

# 멀티레벨 피드백 큐 구성요소

• 큐의 갯수
• 각 큐의 스케줄링 알고리즘
• 상위 큐 승격기준
• 하위 큐 강등기준
• 프로세스 도착시, 각 큐 진입기준

---

7. 다중처리기 스케줄링 & 실시간 스케줄링

 

# 다중처리기 스케줄링 (multi-processor system scheduling)

  각 CPU별 부하가 적절히 분산되도록 부하균형(load balancing) 메커니즘을 필요로 함

---

   # 대칭형 다중처리(symmetric multi-processing)

     각 CPU가 각자 알아서 스케줄링을 결정

   # 비대칭형 다중처리(asymmetric multiprogramming)

     하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 결정

---

# 실시간 스케줄링 (real-time system scheduling)

  시분할 시스템과 달리 데드라인이 존재하는 시스템에서의 스케줄링이 필요

  일반작업과 VOD 작업(연성 실시간시스템이 필요)이 혼재된 환경에서 VOD작업에게 더 높은 우선순위를 할당하는 방법도 있음

 

    # EDF(Earlist Deadline First) 스케줄링

      데드라인이 얼마남지 않은 요청을 먼저 처리

---

8. 스케줄링 성능 평가

 

 

 # Queueing Model

  프로세스들의 도착률과 CPU의 처리율을 INPUT 으로 사용하여,

  확률분포를 통해 복잡한 수학적 계산을 통해 CPU 처리량, 프로세스 평균 대기시간 등

각종 성능지표(performan Index)를 구하는 성능평가 방법

 

 

---

 

 # Implementation & Measurement

  기존 커널과 업그레이드(수정)한 커널을 실제 수행시킨 후

실행시간을 측정하여 알고리즘의 성능을 평가

 

실제 시스템에 컴파일후 설치한다.

 

 

---

 

# Simulation

가상으로 Implementation & Measurement 를 수행

INPUT으로 실제 시스템에서 추출한 입력값(=trace)을 사용할 수도 있고, 

가상으로 생성해 사용할 수도 있다.