CPU 스케쥴링 알고리즘 한줄 정리

CPU Scheduling

• Preemptive(선점) vs Non-Preemptive(비선점)
  - Preemptive : CPU가 현재 실행중인 Process의 작업은 강제로 중단하고, Scheduling하는 것을 말한다.
  ex) 응급실
  • Non Preemptive : 현재 실행중인 Process가 종료되거나 I/O작업을 하기 전까지는 Scheduling을 하지 않는다.
    ex) 은행
• Scheduling Criteria
  여러가지의 scheduling방식이 존재하고 이 방식들을 비교하기 위한 척도이다.
  - CPU Utilization (CPU이용률) : CPU를 얼마나 이용하고 있는가.
  - Throughput (처리율) : 단위시간당 몇 개의 작업을 끝내는가.
  - Turnaround Time (반환시간) : 어떤 작업이 Ready Queue에 처음 들어갔을 때부터 Terminated 되기 까지의 시간.
  - Waiting Time (대기시간) : Ready Queue에서 CPU의 service를 받기까지 기다린 시간.
  - Response Time (응답시간) : 사용자가 컴퓨터에 명령을 내린 후 처음 응답을 받을 때까지 기다린 시간. 응답시간은 Interactive System에서 중요하다. ->CPU Utilization, Throughput은 클수록 Turnaround Time, Waiting Time, Response Time은 작을수록 좋다.
• CPI Scheduling Algorithms : FCFS, SJF, Priority, RR, Multilevel Queue, Multilevle Feedback Queue 등의 알고리즘이 존재한다.
  

First-Come, First-Served

• FCFS(First-Come Fisrt-Served)
  - Queue에 먼저 도착한 Process를 먼저 Service 해주는 Non-Preemptive 알고리즘이다.
  • 장점
    • 가장 간단하고 일반적으로 공평한 방법이다.
  • 단점
    • Convery Effect (호위 효과) : burst time이 긴 Process가 먼저 도착한 경우, 그 Process가 실행할 동안 다른 Process들은 기다려야 한다.

Shortest Job First

• SJF(Shortest Job First)
  • 실행 시간(Burst Time)이 가장 짧은 작업을 먼저 서비스 해준다.
  • 장점
    • 평균대기시간(AWT)를 줄이는 최적의 방법이다.
      - 단점
    • 실제로 실행 전에는 Process들의 CPU Time을 알 수 없기 때문에 비현실적이다.
      • 이 방법을 실제로 사용하기 위해서는 각 프로세스의 CPU Time에 대한 예측이 필요한데 예측을 하기 위한 Overhead(과거 기록, context switching마다 CPU Time 확인...)가 크다.
• Preemptvie vs Non-preemptive
  - Non-preemptive SJT : 새로운 Process가 도착하더라도, 지금 진행 중인 Process의 작업이 다 끝난 다음에 Scheduling한다.
  • Preemptive SJT (= Shortest Remaining Time First) : 새로운 Process가 도착하면, 현재 진행중이던 Process의 작업을 멈추고 Process들의 잔여작업시간을 비교하여 scheduling한다. 즉, 현재 진행중인 Process의 잔여 작업시간보다 더 짧은 작업시간을 갖는 Process가 들어오면, Process의 작업을 중단하고 새로운 Process를 실행한다.

Priority Scheduling

• Priority Scheduling
  - 우선순위가 높은 것을 먼저 서비스 해준다. (대부분의 운영체제에 일반적으로 숫자가 작은 게 우선순위가 높다.)
  • 우선순위를 부여하는 방법?
    • 내부적인 요소 : Time Limit이 짧고, Memory를 작게 차지하고, CPU Time이 짧은 프로세스의 우선순위를 높여준다.
      • 외부적인 요소 : 서버 컴퓨터의 경우 돈을 많이 낸 프로세스에 우선순위를 높여준다.
  • 단점
    • Starvation : 우선순위가 낮은 프로세스는 외부에서 더 높은 우선순위를 갖는 새로운 프로세스가 계속해서 들어온다면 계속 기다려야 한다.
    • 해결방법 : Aging - O/S가 Ready Queue를 주기적으로 확인하여 Ready Queue에 오래 머무는 프로세스의 우선순위를 점진적으로 높여준다.

Round-Robin

• Round-Robin
  - Time Quantum(=Time Slice)을 최대 수행시간으로 하여 CPU가 실행하는 Process를 Switching한다. 이는 시분할 시스템(Time Sharing System)에서 많이 사용되는 방법이다.
  • 단점
    • Performance가 Time Quantum에 크기에 의존적이기 때문에 적절한 Time Quantum을 잡는게 중요하다. 만약 Time quantum이 너무 크다면 FCFS 알고리즘과 같아지고, Time quantum이 너무 작아지면 Context Switching이 빈번하게 일어나서 Context Switching Overhead(Dispatcher가 현재 실행 중인 Process의 PCB에 저장하고 새로 실행할 Process의 정보를 load 해주어야 한다.)가 커진다.
• Preemptive
  - Time Quantum이 지나면, 자동으로 다른 Process로 넘어간다.

Multilevel Queue Scheduling

• Process Groups
  프로세스는 System Process, Interactive Process, Batch Process등과 같이 성격에 따라 Grouping할 수 있다. 이 중 Systme Process > Interactive Process > Batch Process 순으로 작업의 중요도가 크다..
  - System Process : O/S의 작업(가상 메모리 매핑, 파일 읽기, 통신...)
  - User Process
  - Interactive Process : 사용자와 대화하느 프로그램 (워드와 같은 Editing Process가 여기서 속한다.)
  - Batch Process : 일괄처리
• Single Ready Queue -> Several Seperate Queues
  프로세스의 그룹별로 다른 Queue에 줄을 세운다. 각 Queue는 절대적인 우선순위가 존재하거나 차등적으로 CPU시간을 부여받고 또는 다른 Scheduling방식을 채택할 수 있다.

Multilevel Feedback Queue Scheduling

• 복수 개의 Queue를 두어 각 Process들은 Queue의 정책에 따라 작업하다가 기아 상태 우려, 너무 많은 CPU Time이 필요함과 같은 상황들로 인해 점진적으로 다른 Queue로 이동을 한다.

참고 영상

본 글은 다음 링크의 강의 영상을 정리한 것입니다.
운영체제:(7)CPU스케쥴링 알고리즘1-Youtube
운영체제:(8)CPU스케쥴링 알고리즘2-Youtube
운영체제:(9)CPU스케쥴링 알고리즘3-Youtube