[week08] KOCW 운영체제(반효경교수님) - CPU Scheduling 1

CPU Scheduling 1

CPU and I/O Bursts in Program Execution

CPU burst : CPU를 연속적으로 쓰는 단계

I/O burst : I/O를 실행하는 단계

CPU-burst Time의 분포

CPU는 실제로는 CPU bound job이 많이 사용하는데 그 빈도수가 적은 것이고, I/O bound job은 CPU를 짧게 쓰는데 빈도가 잦은 것이다.

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.

• 사람과 소통하는 I/O bound job에 CPU를 우선적으로 준다.

프로세스의 특성 분류

프로세스는 그 특성에 따라 2가지로 나눈다.

I/O bound process

• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
• many short CPU bursts

CPU-bound process

• 계산 위주의 job
• few very long CPU bursts

CPU scheduler & dispatcher

CPU scheduler

• 하드웨어가 아니라 운영체제에 있는 어떤 기능
• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름

Dispatcher

• CPU의 제어권을 선택된 프로세스에게 넘김
• 이 과정을 context switch(문맥 교환)이라고 한다.

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

1. Running → Blocked(ex: I/O 요청하는 system call)
2. Running → Ready(ex: 할당시간 만료해서 time interrupt)
3. Blocked → Ready(ex: I/O 완료 후 인터럽트)
4. Terminate

• 1,4에서의 스케줄링은 nonpreemptive(자진반납) - 비선점형
• 나머지 scheduling : preemptive(강제로 빼앗음) - 선점형

Scheduling Criteria(Performance Index - 성능 척도)

System입장에서의 성능 척도(중국집 사장 입장)

CPU utilization(이용률)

• CPU일한시간 / 전체시간

Throughput(처리량)

• 주어진 시간동안 몇 개의 일을 처리했는지

Process입장에서의 성능 척도(중국집 손님 입장)

Turnaround time(소요시간, 반환시간)

• CPU를 쓰러 들어와서 다 쓰고 나갈 때까지 걸린 시간(CPU burst 시간)
• 이 프로세스가 CPU를 쓰러 들어와서 I/O하러 나가기 전까지 걸린 시간

waiting time(대기시간)

• ready queue에 줄 서서 기다리는 시간

Response time(응답시간)

• ready queue에서 기다리다가 최초의 CPU를 얻기 까지 기다린 시간
• 사용자 입장에서는 체감이 강하게 되기 때문에 중요

헷갈림주의

• 여기서의 ‘시간’은 프로세스가 시작해서 종료될때까지의 시간을 말하는 것이 아니다.
• CPU관점만 따지고 있기 때문에 매 CPU burst 건마다 따지는 것이다.
• ready queue에 들어온 것에 한해서 스케줄링 대상이 되기 때문

FCFS(First-Come First-Served)

먼저 온 순서대로 처리

• 그다지 효율적이지 않다.
• 비선점형

만약 도착순서가 변경되면 어떻게 될까?

순서가 바뀌면 걸리는 시간에 상당한 영향을 미침

SJF(Shortest-Job-First)

각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

Two schemes:

Nonpreemptive

• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption)당하지 않음

Preemptive

• 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도작하면 CPU를 빼앗김
• 이 방법을 SRTF(Shortest-Remaining-Time-First)이라고도 부름
  • 남은 시간이 짧은 프로세스에게 CPU를 주기 때문

SJF is optimal(최소)

• 주어진 프로세스들에 대해 minimum average waiting time을 보장
• preemptive방식 사용시 최소가 됨

Example of Non-Preemptive SJF

CPU를 다 쓰고 나가는 시점에 스케줄링을 결정

Example of Preemptive SJF

새로운 프로세스 도착하면 스케줄링 결정(우선순위 비교해서 높은놈으로 갈아껴야함)

SJF사용시 문제점

첫 번째 문제

SJF를 사용하면 CPU burst 시간이 긴 process는 영영 실행을 못 할수도 있다(Starvation).

두 번째 문제

다음번 CPU burst time을 예측할 수 없다.

• 내가 지금 CPU를 얼마나 쓰고 나갈지 예측할 수 없다.

추정(estimate)는 가능하다.

• 과거의 CPU burst time을 이용해서 추정
• 현재를 기준으로 최근의 과거는 가중치를 높게 반영하고 오래된 과거일수록 가중치를 낮게 반영

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

각 프로세스마다 Priority number가 주어지게 된다(정수값).

보통 우선순위가 가장 높으면 가장 작은 정수를 준다(PintOS에서는 우선순위 높으면 큰 정수).

두 가지 방식이 있다.

• preemptive
• nonpreemptive

SJF는 일종의 priority scheduling이다.

• priority = predicted next CPU burst time (SJF에서는 CPU burst time이 우선순위가 됨)

Problem:

Starvation(기아): low priority processes may never execute

Solution:

Aging(노화): 오래 기다리게 되면 우선순위를 높여준다.

Round Robin(RR)

현대적인 컴퓨터에서 사용하는 컴퓨터 스케줄링은 Round Robin에 기반한다.

각 프로세스는 동일한 크기의 할당시간(time quantum)을 가짐

• 일반적으로 10~100ms
• PintOS에서는 4tick(40ms)

할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.

n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.

• 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.(강점: 응답시간이 빨라진다)

q 크기에 따른 극단적 상황

• q too large → FCFS(First-Come First-Served)
• q too small → context switch 오버헤드가 커짐

특징

대기시간이 본인이 CPU를 사용하려는 시간에 비례

• CPU를 짧게 쓰는 프로세스는 기다리는 시간이 짧아진다.
• CPU를 길게 쓰는 프로세스는 기다리는 시간이 길어진다.

일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

CPU 사용시간이 모두 동일한 프로그램을 사용할 때는 효율이 안나올 수 있다

• 그러나 우리는 모두 섞여있다고(CPU를 길게 사용, 짧게 사용) 가정하기 때문에 RR은 효율적이다.

효율성 + 공정성을 챙기는 방법이다.

문맥이 저장이 되기 때문에 이런 scheduling이 가능하다는걸 잊지 말자.