[운영체제] CPU 스케줄링

CPU 스케줄링의 핵심은 두 가지다.

1. 여러 작업이 들어올 때 누구를 먼저 할 것인가

2. 사용하고 있는 CPU를 언제 가져올것인가

 

스케줄링 알고리즘

스케줄링에는 CPU를 다 사용할때까지 기다리는 비선점형과 중간에 뺏을 수 있는 선점형이 있다.

 

1. FCFS(First Come First Served): 먼저 오면 먼저 사용

  - 비선점형

  - 나머지 작업들 CPU를 다 사용할 때까지 기다려야한다

  - 비효율적

※ convoy effect:  CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상 이로 인해 평균 대기시간이 길어지게 된다.

 

2. SJF(Shortest job first): CPU를 사용하는 시간이 짧은 작업에 먼저 이용권을 준다

  - average wait time 최적

  - 비선점의 경우 한 번 CPU를 얻으면 사용을 보장한다

  - 선점형의 경우 CPU를 사용하다가 사용시간 더 짧은 작업이 오면 바로 넘겨준다(SRTF)

  - 문제점: 프로세스 긴 시간 영원히 못 받을 수도 있다(starvation ), cpu 사용시간을 미리 알 수 없다

 

3. RR(Round Robin)

  - 선점형

  - 현재 컴퓨터 시스템

  - 작업마다 time을 할당해서 CPU를 주고 time이 끝나면 CPU가 넘어간다

  - 응답시간이 빠르다

  - 사용시간과 대기시간이 비례한다

 

4. Priority Scheduling(우선순위 스케줄링): 우선순위가 높은 프로세스에게 CPU를 할당

  - 작업마다 우선순위를 나타내는 숫자가 있다

  - aging: 대기시간이 길어질수록 우선순위를 높인다

 

5. Multilevel Queue

  - ready queue를 여러 개로 분할한다

  - 각 큐는 독립적인 스케줄링 알고리즘을 가진다

  - 우선순위별로 기다린다

  - starvation문제를 해결하기 위해서는 큐에 대한 스케줄링이 필요한데 cpu time을 적절한 비율로 할당해 해결 가능

 

6. Multilevel Feed back Queue: 

  - 여러 줄로 기다리면서 줄 간의 이동이 가능하다

  - 처음 들어오면 우선순위 높은 큐에 들어가고 그 다음부터 라운드 로빈 알고리즘으로 동작한다.

  - 낮은 우선순위의 큐는 FCFS 알고리즘으로 동작, 이때 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동

 

cpu가 여러개일때 

Multiple Processor Scheduling

  - 일부 프로세스에 job이 몰리지 않도록 부하를 적절히 공유해야함

  - 하나의 프로세스가 시스템 데이터의 접근과 공유를 책임지고 나머지는 프로세서는 거기에 따름

 

데드라인이 있을때

Real Time Scheduling

  - 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함

  - soft real time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 해야함

 

스레드가 여러개일때

Local Scheduling: user level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정

Global Scheduling: kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

 

그렇다면 스케줄링을 평가할 수 있는 기준은 무엇이 있을까?

스케줄링 성능척도

1. 시스템 입장

  - CPU 이용률: cpu가 놀지않고 일한 시간의 비율, 최대한 일을 많이 하는게 좋다

  - 처리량: 주어진 시간동안 몇 개의 일을 처리했는가

 

2. 프로그램 입장

  - Turnaround time(소요시간, 반환시간): 들어와서 기다리고 다 쓰고 빠져나갈 때까지 ex) 음식을 주문하고 다 먹고 나가는 시간

  - 대기 시간: ex) 음식을 기다린 시간

  - 응갑 시간: ex) 첫번째 음식 나오는 시간

※ 총시간: cpu 들어와서 입출력으로 나가는 시간

 

스케줄링 평가

1. Queue models

  - 큐에 도착시간과 작업을 하고 나가는 비율을 계산해 평가

2. 구현과 성능 측정

  - 실제 시스템에 알고리즘을 수현하여 실제 작업에 대해서 성능을 측정 비교

3. 모의 실험

  - 간단한 예시를 들어 계산해본다