[OS] CPU Scheduling 1 : FCFS, SJF, Priority Scheduling, RR

Doodung·2022년 5월 5일

OS - 운영체제

목록 보기

10/15

CPU and I/O Bursts in Program Execution

프로그램이 수행이 되면 어떤 프로그램이든 간에 위의 과정이 실행된다. CPU 러닝(load, add..), 오래 걸리는 작업(read) 등..

프로그램에 따라 약간의 차이가 있겠지만, 어쨌든 CPU만 연속적으로 쓰는 단계(CPU Burst)와 I/O를 하는 단계(I/O Burst)가 번갈아가며 실행된다.

단, 프로그램 종류에 따라서 이가 빈번하게 일어날수도 있고, 아닐수도 있다.
주로 사람이 인터랙션을 하는 프로그램이 중간 중간에 CPU, I/O가 많이 끼어든다. 사람이 키보드 입력하고 → CPU실행하고 → I/O또하고 이런식으로..

반면, 1000*1000 행렬 곱셈이라 하면 디스크에서 읽어온 후 메모리에서 계속 CPU만 오래쓴다.

CPU-Burst Time의 분포

그래프를 보면 CPU burst가 짧은, 중간에 I/O 작업이 긴 경우가 많았다. 또 CPU burst가 아주 긴 경우는 굉장히 빈도가 낮았다.

CPU를 짧게 쓰고 중간에 I/O가 끼어드는 작업을 I/O bound job이라고 하고 , CPU만 굉장히 오래쓰는 작업을 CPU bound job이라고 한다.

대부분의 CPU 시간은 I/O bound job이 다 쓰는 것일까?
→ no!
→ I/O bound job은 CPU 시간이 난도질 당해서 빈도가 높은 것이고, CPU bound job은 오랫동안 쓰기 때문에 빈도수가 낮은것이다. 실제로는 CPU bound job이 더 많이 쓴다.

컴퓨터에는 이렇게 job들이 섞여있다. 그래서 CPU 스케줄링이 필요한 것이다.

CPU bound job은 별로 문제가 되지 않는데, I/O bound job이 문제가 된다. 이는 인터렉티브한 잡이라서 (사람과 끊임없이 인터랙션) CPU를 CPU bound job이 한번 잡고 놓지 않으면 I/O는 CPU를 잡지 못해 사람은 답답함을 느낀다.

그래서 가능하면 사람과 인터랙션하는 I/O bound job에게 CPU를 더 우선적으로 주는것이 필요하다.

이것이 CPU 스케줄링의 중요한 필요성이다. 공평함 보다는 효율성이 중요하다.
누구에게 우선으로 줄 것인가?, 언제 뺏을 것인가? 하는 이슈들이 있다.

지금까지 계속 배워왔던 'CPU는 짧은 시간 단위로 계속 번갈아가면서 쓴다'는 그것이 바로 특정 스케줄링을 말한다. CPU를 빼앗기지 않게 작업할 수도 있다.

프로세스의 특성 분류

프로세스는 그 특성에 따라 다음 두 가지로 나눔
- I/O-bound process
  : cpu를 잡고 계산하는 시간보다 i/o에 많은 시간이 필요한 job
  (many short CPU bursts)
- CPU-bound process
  : 계산 위주의 job, CPU를 연속적으로 쓰는 시간이 길어진다.
  (few very long CPU bursts)

CPU Scheduler & Dispatcher

CPU Scheduler

누구한테 CPU 줄지 고르는 것.
운영체제에서 이 역할을 하는 코드가 있고, 그 것을 CPU 스케줄러라 하는 것
Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher

정한 친구에게 CPU를 주는 것.
CPU 줄려면 지금 방금 전에 CPU에서 돌아가던 context SAVE, 그리고 새로 줄려고 하는 애의 context 알아야 한다. register 세팅 해놓고.
CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
이 과정을 context switch(문맥 교환)라고 한다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

1. Running → Blocked (예 : I/O 요청하는 시스템 콜)
: CPU를 어떤 프로세스가 잡고 있다가 그 프로세스가 I/O 작업처럼 오래 걸리는 작업을 하러 간 경우, 자진해서 CPU를 내어놓는 것.
‘더이상 CPU 가지고 있어봐야 일 못한다’ 하고 다른 프로세스에게 CPU 넘어가야 하는 경우

2. Running → Ready (예 : 할당 시간 만료로 tiner interrupt)
: 나는 CPU를 계속 쓰고 싶은데, 이 친구한테 무한정 CPU를 줄 수 없기 때문에 강제로 CPU를 빼앗아서 다시 줄서게 함.
(타이머 인터럽트 발생) 그리고 다른 CPU를 필요로 하는 프로세스에게 넘김

3. Blocked → Ready (예 : I/O 완료 후 인터럽트)
: I/O를 요청했던 프로세스가 오래 걸리는 작업을 끝내고 난 후, 디바이스 컨트롤러가 인터럽트를 걸어서 이 친구의 상태를 READY로 바꿔 CPU를 얻을 수 있는 상태로 만들어줌.
근데 이 작업에서 I/O가 끝난 애에게 바로 CPU를 주지 않는다. 이 친구에게 주기 전에 CPU를 지니고 있는 프로그램이 있을 수 있기 때문.

그런데, 이 상황에서 I/O가 끝난 이 친구에게 CPU를 바로 넘겨야 할 때가 있다.
어떤 경우냐면 스케줄링이 여러 경우가 있는데, 그중 우선순위기반 스케줄링이고, 이 프로세스가 시스템 안에서 우선순위가 높다면, 앞의 인터럽트 당했던 프로세스의 시간이 남아있다 하더라도 절대적으로 우선순위로 스케줄링하기 때문에 바로 CPU를 넘겨줘야 하는 경우가 된다.
그래서 이때 스케줄링이 필요할 수도 있다고 설명하는 것이다.

4. Terminate
: 어떤 프로세스가 종료돼서 할 일이 없으니까 새로운 프로세스에게 CPU를 넘겨주는 것.

1,4 에서의 스케줄링은 nonpreemptive(=강제로 빼앗지 않고 자진 반납) → CPU를 가지고 있어도 더이상 인스트럭션 실행 안된다.
2,3 All other scheduling is preemptive(=강제로 빼앗음) → 나는 CPU를 계속 쓰고 싶은데 타이머가 있기 때문에.. 아니면 내가 우선순위가 떨어져서 CPU를 넘겨주고.

CPU Scheduling Algorithm

강제로 cpu를 빼앗지 않는 방법 → 비선점형
강제로 cpu를 뺏는 방법 → 선점형 : 현대적인 cpu 스케줄링은 거의 이 방법 사용함.

Scheduling Criteria : 스케줄링 성능 척도

(Performance Index, Performance Measure)

- 시스템 입장에서의 성능 척도
: CPU 하나를 가지고 최대한 일을 많이 시키면 좋은 것
1. CPU Utilization : 이용률
→ 전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율
→ cpu는 가능한 바쁘게 일을 시켜라.
2. Throughput : 처리량
→ 주어진 시간 동안에 몇개의 작업, 일을 처리했느냐

- 프로그램, 프로세스 입장에서의 성능 척도
: 가능하면 내가 cpu를 빨리 얻어서 빨리 끝내면 좋은 것
1. Turnaround time : 소요시간, 반환시간
→ cpu를 쓰러 들어와서 다 쓰고 나갈때까지 걸린 시간
2. Waiting time : 대기시간
→ 기다린 시간, cpu를 쓰고자 할 때 레디 큐에서 기다리는 시간
3. Response time : 응답시간
→ 레디 큐에 들어와서 처음으로 cpu를 얻기까지 걸린 시간

Scheduling Algorithms

FCFS (First-Come First-Served)
SJF (Shortest-Job-First)
Priority Scheduling
RR (Round Robin)
Multilevel Queue
Mulitilevel Feedback Queue

1. FCFS (First-Come First-Served) | 비선점

: 먼저 온 순서대로 처리

CPU를 오래 사용하는 프로그램이 먼저 CPU를 얻게 되면 나머지 cpu를 짧게 쓰는 프로그램들이 오래 기다려야 한다.

간트차트 x : 시간축
P1이 제일 먼저 도착했기 때문에 도착하자마자 CPU 장악해서 24초동안 실행한다. 두번째, 세번째도 순서대로.
P1이 만약 100만초 정도로 아주 길었으면, P2,P3가 굉장히 오래 기다려야 하는 것이다. 이러한 현상을 convoy effect라고 한다. (큐에서 오래 기다리는 현상) 그래서 좋은 스케줄링 방법은 아니다.

FCFS는 앞의 프로세스에 따라 기다리는 시간에 상당한 영향을 미치게 된다.

2. SJF (Shortest-Job-First) | 비선점, 선점

: cpu를 짧게 쓰는 프로그램에게 cpu를 먼저 주는 것.

각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 활용
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
Two schemes
- Nonpreemptive
  - 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음
    
    0초 시점에 도착한 프로세스가 p1밖에 없음, p1은 본인이 원하는 만큼 cpu 쓰고 반납한다. 7초 시점에 나머지는 다 도착해 있는데, p3가 burst time 가장 짧기 때문에 p3가 그 다음 cpu를 얻게 된다.
    
    → cpu 스케줄링 언제? cpu를 다 쓰고 나가는 시점에 스케줄링을 할 지 안할지 결정
- Preemptive
  - 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  - 이 방법을 Shortest-Remaining-Time-First(SRTF) 라고도 부른다
    
    p1이 cpu를 얻었지만, 더 짧은 프로세스가 도착하면 빼앗긴다. p2가 cpu를 쓰는 시간은 4초이고, p1은 7초를 쓰고자했는데 2초 썼으므로 5초가 남는다. p2가 더 작으므로 p2에게 넘겨준다.
    
    4초에 p3가 도착하는데, p3는 1초만 사용하므로 cpu를 얻게 된다. 그 후 5초 시점에 4개의 프로세스가 모두 도착한 시점이다. p1,p2,p4 중 현재 추가로 써야하는 cpu 시간이 가장 짧은 p2가 cpu를 얻게 된다.
    
    앞의 비선점 방식보다 평균시간이 더 짧다. (minimum이다. 어떤 스케줄링을 쓰더라도 3초보다 짧을 순 없다.)
    
    → cpu 스케줄링 언제? 새로운 프로세스가 도착하면 언제든지 스케줄링이 이루어질 수 있다.
SJF is optimal
- 주어진 프로세스들에 대해 minimun average wating time을 보장 → Preemptive버전
문제점
1. long process의 Starvation 문제, 기아현상 : sjf는 극단적으로 cpu 시간이 짧은 job을 선호한다. 그렇기 때문에 cpu 사용 시간이 긴 프로세스는 영원히 서비스를 못 받을 수도 있다.
2. cpu 사용 시간을 미리 알 수 없다.
  그러나 추정은 가능 하다.
  프로그램의 종류에 따라서 사람과 인터랙션을 하는 것들은 버스트가 짧고, 과학 계산등은 cpu 사용이 길다.
  과거에 cpu를 얼마나 썼는지 보고 이번에 얼마나 쓸지 예측을 할 수 있긴하다.
  
  tn → n번째 실제 cpu 사용 시간
  타우n+1 → n+1 번째 cpu 사용을 예측한 시간
  알파 상수 : 0과 1 사이의 값
  두가지를 일정 비율식 반영하면서 더해서 타우 값 구한다.
  
  최근 것은 가중치를 높게 반영하고 오래전 거는 가중치를 낮게 하여 더함.

3. Priority Scheduling | 비선점, 선점

우선순위 스케줄링, 우선순위가 높은 프로세스에게 cpu 주겠다

A priority number(integer) is associated with each process
highest priority를 가진 프로세스에게 CPU 할당
(smallest integer - highest priority)
- Preemptive
- Nonpreemptive
SJF는 일종의 priority scheduling 이다.
- priority = predicted next CPU burst time
  우선순위가 cpu 사용 시간으로 정의하면 되는 것.
문제점
- Starvation (기아현상) : low priority processes may never execute
  우선순위가 낮은 프로세스가 영원히 cpu를 얻지 못할수도 있음
해결 방법
- Aging : as time progresses increase the priority of the process
  아무리 우선순위가 낮은 프로세스라 하더라도 오래 기다리면 우선순위를 조금씩 높여주자. 그럼 언젠가는 cpu를 얻게 되니까 기아현상을 막을 수 있다.

4. RR (Round Robin) | 선점

현대적인 cpu 스케줄링은 rr을 사용한다. 맨 처음 부터 설명하던 timer 인터럽트 걸리고, 등등.. 이런게 다 rr 기반 스케줄링이었다.

효율적이고 공정한 방법으로. CPU를 주고 나서 쓰고싶은 만큼 무작정 쓰게하는게 아니라 할당된 시간만큼만 CPU를 쓰고 다음 프로세스에게 넘겨주는 스케줄링.

i/o 바운드일 경우에 주어진 타임 퀀텀 내에서 본인이 원하는 만큼 쓰고 빠져나갈 수있다.

cpu를 오래쓰는 경우 썼다 뺏겼다의 상황을 반복하게 된다.

rr은 CPU를 기다리는 시간이 본인이 cpu를 사용하려는 시간과 비례하는 측면에서 공정한 스케줄링이 된다.

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10~100milliseconds)
할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. 그 후 그 다음 프로세스가 같은 과정을 반복한다.
따라서 응답 시간이 빨라진다.
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

→ 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
대기 시간이 본인이 cpu를 사용하려는 시간에 비례한다. cpu를 짧게 쓰는 프로세스는 한번만에 나가고, 길게 쓰는 프로세스는 오랫동안 반복해서 기다리기 때문이다.
Performance | 극단적인 상황에서의 성능
- q large (q의 값이 엄청 크다면) → FCFS
- q small (q의 값이 엄청 작으면 : 할당 시간을 지나치게 잘게 쪼개놓으면) → context switch 오버헤드가 커진다.
- 그래서 적당한 규모의 time 퀀텀이 중요하고, 10~100ms 정도다.
  p2는 할당시간보다 버스트 타임이 작기 때문에 그 시간만 쓰고 나간 것.
일반적으로 SJF보다 average turnaround time, rating time이 길어질 수 있지만 response time(최초로 cpu얻게되는 시간)은 더 짧아진다.
특이한 경우 : cpu 사용 시간이 100초인 프로그램이 10개 있는데 fcfs로 처리하면 p1 100초 → p2 100초 → ,,, 그럼 기다리는 시간이 0,100,200, 이렇게 될것임.

그러나 rr은 모두가 1000초가 되는 지점에 빠져나가는 스케줄링이 되는 것. 이처럼 rr은 마구잡이로 cpu 사용시간이 다른 프로세스를 처리할때 유용하게 사용되는데, 모두가 같은 사용시간을 가지고 있다면 효율적이지 못하게 되는 것이다. waiting time이 굉장히 길어진다.