[OSTEP] Scheduling : Introduction

Soeng_dev·2020년 12월 31일
0

Scheduling Policy (discipline)

• Workload Assumption

  1. 모든 작업시간은 동일
  2. 모든 작업은 동시에 도착
  3. 각 작업은 시작되면 완료될 때까지 실행됨
  4. 모든 작업은 CPU만 사용 (입출력 수행 X)
  5. 각 작업의 실행시간을 알고 있음

• Scheduling Metrics

» Turnaround time (반환시간)

반환시간은 성능 측면에서의 평가기준

Tturnaround = Tcompletion - Tarrival

이때, 모든 작업은 동시에 도착한다고 가정했으므로
Tturnaround = 0

∴ Tturnaround = Tcompletion (추후 가정을 수정)

» Fairness (공정성)

Scheduling에 있어서 성능과 공정성은 서로 상충되는 목표
Jain's Fairness Index등에 의해 평가가능
(서적 The Art of Computer Systems Performance Analysis, Raj Jain 참고)

» Response time (응답시간)

시스템이 상호작용을 원활히 하기 위한 성능
작업이 도착할 때부터 처음 스케줄 될 때까지 걸리는 시간

Tresponse = Tfirstrun - Tarrival

아래의 STCF류의 정책들은 반환시간은 훌륭하지만, 응답 시간과 상호작용 측면은 안좋은 방법이다.

• FIFO (First in, First out)

FIFO(First in, First out), FCFS(First come, First served)

» Covey effect

위 그림과 같이 실행시간이 짧은 프로세스들이 긴 실행시간의 프로세스 종료를 기다리는 현상
평균 반환 시간을 악화시킨다.

• SJF (Shortest Job First)

가정 2 '모든 작업은 동시에 도착' 이 없다면 아래와 같은 문제가 발생

• STCF (Shortest Time-to-Completion First)

STCF (Shortest Time-to-Completion First), PSJF(Preemtive Shortest Job First)

SJF의 문제를 해결하기 위해 가정 3 '각 작업은 시작되면 완료될 때까지 실행됨'을 완화

시스템에 새로운 프로세스가 들어오면 스케줄러는 남은 작업과 새로운 작업 중 남은 실행시간이 제일 적은 프로세스를 스케줄한다.

반환 시간은 훌륭하지만 응답시간은 안좋다.

» Preemptive Scheduler

Preemtive Scheduler
각 작업이 종료될 때까지 계속 실행

Non-preemptive Scheduler
다른 프로세스 실행을 위해 필요하면 문맥교환을 수행하며, 현재 프로세스를 중단, 다른 프로세스를 재개 또는 시작함

• RR(Round-Robin) Scheduling

RR(Round-Robin) Scheduling, Time slicing

일정시간 동안 실행 후 실행 큐의 다음 작업으로 전환

작업이 실행되는 시간을 time slice 또는 scheduling quantum이라고 함

RR과 같이 공정한 policy, 작은 시간단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환시간 같은 평가기준에선 성능이 나쁘다.

» Time slice

time slice는 타이머 인터럽트 주기의 배수여야 함
time slice가 짧아지면 RR의 응답시간은 좋아지지만, 너무 짧아지면 문맥 교환 비용이 전체 성능에 미치는 영향이 커짐
문맥교환 비용을 상쇄할 수 있을만큼 길어야하지만, 너무 길면 안 된다.

• I/O 작업을 고려

시스템 활용도 즉, 전반적인 사용성과 효율성을 향상 하기위해선 연산을 중첩되게 실행해야 함

» 효율성

입출력 작업을 요청 시, 실행중인 프로세스는 입출력 완료까지 CPU를 사용하지 않음
효율성을 위해 스케줄러는 다음에 할 작업을 결정해야함

» 사용성

또한, 각각의 cpu burst를 독립된 하나의 작업으로 간주하면 스케줄러는 대화형 프로세스 (interactive process)가 더 자주, 유리하게 실행되는것을 보장함

Related Knowledge

• Workload

시스템에서 작동중인 프로세스들, 프로세스들이 하는 작업들의 특징(소요시간, I/O호출)등을 총칭

profile
Software Engineer

0개의 댓글