[운영체제] CPU 스케줄링

CPU 스케줄링

• 현재 실행 중인 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리고 있는 여러 프로세스 중에 어떤 프로세스를 결정하는 것

스케줄링의 세가지 시점

• 장기 : 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정.
• 중기 : 보류준비 중인 상태의 프로세스들 중에서 어느 프로세스에 메모리를 할당해 줄 것인가를 결정
• 단기 : 준비 상태의 프로세스들 중에 어느 프로세스들에세 메모리를 할당해줄 것인가를 결정 

스케줄링 평가 기준

• 사용자 관점
  
  • 응답 시간 : 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸리는 시간 ( 프로세스가 들어와서 끝날때까지 걸리는 시간)
  • 반환 시간 : 요청으로 부터 결과를 돌려 받는 데까지 걸린 시간
  • 예측 가능성 : 요청한 일이 얼마 후에 완료될 것이라는 예측이 가능한가
• 시스템 관점
  • CPU가 얼마나 잘 활용됐는가를 나타낼 수 있는 처리량과 활용도
    • 처리량: 단위 시간에 처리되어진 프로세스의 갯수
    • 활용도: 주어진 시간 동안 CPU가 실제로 가동된 시간의 비율

=> cpu 처리량과 활용도는 극대화하고, 응답시간과 반환시간은 낮을 수록 예측 가능성은 높을 수록 좋음

 

스케줄링 기법

스케줄링이 가동 되어야 할 시점

1. 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 ( ex : I/O 요청 )
2. 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : intterupt 발생 )
3. 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : I/O 종료 시 )
4. 종료(Terminated)될 때

스케줄링 기법 분류

• 비선점 스케줄링 : 한 프로세스가 CPU를 할당 받았을 때 CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방법
  • 1, 4번이 해당함
• 선점 스케줄링: CPU를 할당 받아 실행 중인 프로세스로부터 CPU를 선점하여(빼앗아) 다른 프로세스에게 할당하는 방식
  • 2,3번이 해당함

스케줄링 알고리즘

1. FCFS  (First Come First Served) 스케줄링

- 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU 할당

- CPU를 할당 받은 프로세스는 스스로 CPU를 반납할 때까지 독점하는 비선점 방식

- 프로세스가 CPU를 독점하여 사용하기 떄문에 아주 긴 프로세스가 실행될 경우, 뒤에 있는 프로세스는 오래 기다려야함                            즉, 응답시간이 길어질 수 있음

- 프로세스들의 갯수와 크기를 짐작할 수 있다면 각각 프로세스들이 언제 실행될지 예측 가능

- 도착 순서만이 실행순서를 결정짓기에 공평하다 할 수 있음

 

2. SPN (Shortest Process Next) 스케줄링 

- SJF(Shortest Job First)라고도 불림

- 준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 것을 먼저 실행시켜 주는 비선점 방식
- 평균 응답 시간 최소화 가능
- 예측 가능성은 떨어짐
- 실행 시간이 긴 프로세스가 CPU를 할당 받지 못하고 계속해서 대기 하는 무한 대기 현상이 발생 가능 에이징(aging) 기법으로 해결
      - 에이징 : 기다린 시간만큼 우선순위를 높여 실행 가능성을 높여주는 것

- 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 불구하 고 그 크기를 가지고 스케줄을 해야 한다는 것

3.SRT (Shortest Remaining TIme) 스케줄링

- SPN을 선점 방식으로 운영

- 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것부터 실행

- 실행 도중 남은 시간이 더 적은 프로세스가 준비큐에 들어오면 현재 실행 중인 것을 중단하고 새 프로세스에 CPU를 할당함

4. 라운드 로빈 스케줄링

- FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한번에 쓸 수 있는 CPU 시간의 크기 (TIme Quantum)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 선점 방식

- TIme Quantum이 너무 크면 FCFS와 같아 지고, TIme Quantum이 너무 작다면 잦은 문맥교환으로 오버헤드 발생 가능

 

5. 우선순위 스케줄링

- 프로세스에 주어진 우선순위를 보고 가장 높은 프로세스부터 실행하는 알고리즘

- 실행시간이 짧은 프로세스가 계속 실행되는 경우, 실행시간이 긴 프로세스가 계속 실행되지 못하는 기아 현상 발생 가능

 

6. Multi-level Queue

- 정적 우선 순위를 사용하는 스케줄링을 구현할 때 가장 적합함

- 같은 우선순위 값을 가지는 프로세스들을 위해 큐가 필요함과 동시에 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 갯수만큼 큐가 필요함

- 프로세스들은 자신의 우선순위 값에 맞는 큐에 들어가며, 우선순위가 낮은 하위 단계 큐의 작업은 실행중이라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗기는 선점 방식

- 정적 우선순위라서 큐들간에 프로세스 이동이 불가능함

 

7. Multi-level-feedback Queue

- 동적 우선 순위를 기반으로 한 선점 방식

- 우선순위의 갯수 만큼 큐가 있으며, 각 단계마다 서로 다른 CPU 시간 할당량을 가짐

- 우선순위가 높을 수록 시간할당량은 작도록 함

   1.  새로운 프로세스는 최상위 단계의 준비 큐에 들어간후 FCFS의 순서로 CPU를 할당 받아 실행됨

   2. 큐의 시간 할당량이 끝나면 한단계 아래의 준비 큐에 들어감 ( 우선순위가 한단계 낮아짐)

   3. 각 단계에서 그 큐의 시간 할댱을 다 사용할때까지 실행 된가면 한단계씩 아래 큐에 들어가게 됨

   4. 마지막 단계의 큐에서는 라운드 로빈식으로 진행 됨

   * 어느 단계든 시간 할당량이 끝나기 전에 입출력등으로 CPU를 내놓게 되면 다시 준비 상태가 되었을때 한 단계위의 큐에 들어가도록 우선순위를 높혀줌

- 즉, CPU를 오래 사용해야 되는 CPU집중 프로세스는 점차 우선순위가 낮아지고, 입출력 집중 프로세스는 높은 우선순위를 받아 빠르게 실행 할 수 있다