CPU Scheduling

기본 컨쌥!

- 다중 프로그래밍의 목적은 CPU이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는데 있다.

- CPU-I/O 불태우는 싸이클! : CPU 실행과 I/O의 적절한 고려!

CPU Scheduler

- 실행될 준비가된 프로세스가운데에서 골라 CPU에 배치하는 과정

- CPU 스케쥴링 결정이 나타나는 상황

  1. running에서 waiting으로 전환될때(I/O 또는 자식의 종료를 기다림)

  2. running에서 ready로 전활될때(인터럽트)

  3. waiting에서 ready로 전활될때(I/O 종료)

  4. 프로세스가 종료

- 1 과 4는 비선점(nonpreemptive)이다.

- 2 와 3은 선점(preemptive)이다.

Dispatcher

- dispatcher의 기능

  ㅁ 문맥교환

  ㅁ 사용자 모드로 전활

  ㅁ 프로그램을 다시 시자하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

- Dishpatch latency(디스패치 지연)

  : 한 프로세스를 정지 시키고 다른것을 실행시키는대 걸리는 시간

Scheduling Criteria(스케쥴링 기준)

- CPU utilization(CPU 이용률) : keep the CPU as busy as possible

                                          : OS안끼아듬, switching, 스케쥴링 잘안함

- Throughput(처리량) : 단위시간당 완료되는 프로세스의 갯수

- Turnaround time(총처리 시간) : 특정 프로세스를 실행하는데 걸린시간(waiting 포함)

- waiting time(대기 시간) : 프로세스가 ready 큐에서 기다린 시간

- Response time(응답 시간) : 응답이 시작 되는 시간, 응답출력X

Optimization Crteria(최적화된 기준)

- 최대의 CPU 활용

- 최대의 처리량

- 최소의 총처리시간

- 최소의 대기시간

- 최소의 응답시간

Scheduling Algorithms

FCFS

SJF

Priority Scheduling

Round Robin

Multilevel Queue Scheduling

Multilevel Feedback Queue Scheduling

FCFS(first come first served)

걍 순서대로!!!!

Convoy effect(호위 효과) : 모든 다른 프로세스들이 하나의 큰 프로세스가 CPU를 줄때까지 기다리는것[긴프로세스가 짧은 프로세스보다 앞에 있는 상태]

SJF(Shortest job first)

짧은거 순서대로!!!!!

2가지 방법있삼!(preemtive, nonpreemtive)

- nonpreemtive : 그냥 짧은거 다 실행하고 다은 짧은놈 실행

- preemtive : 실행하다가 남은시간보다 더 짧은놈 들어오면 그놈 실행함(SRTF[shortest reemaining time first])

- SJF는 최적화 되었다!(평균 대기 시간이 가장 짧음)

문제점 : burst time을 모름-_-;;;;

Prioritty Scheduling

- 우선순위가 프로세스각각에 매겨진다.

- 우선순위가 높은 프로세스를 CPU가 배치시킨다.

  ㅁ 선점형

  ㅁ 비선점형

- SJF는 CPU burst time이 예측되어지는 Priority Scheduling이다.

- 문제점 : Starvation(기아[KIA]...?;)

  해결방법 : Aging 시간이 지날수록 우선순의를 상승시킨다.

Round Robin(RR)

- 알자나~

- 일정시간동안 돌아가면서 실행!

- 실행중...

  ㅁ quantum 이 너무길면 FCFS

  ㅁ quantum 이 너무 짤으면 context switching 시간이 너무 많아 완죤 새됨

- SJF보다 높은 평균 총처리시간이 걸리지면 좋은 반응시간을 가진다.

- 하지만 알고보면 라운드 로빈은 context switching이라는 것때문에 성능이 아주 구리다.

Multilevel Queue

- Ready queue가 많다.(foreground, background)

- 각각의 큐는 각각의 scheduling 알고리즘을 가진다.

  ㅁ foreground - RR
  ㅁ background - FCFS

- 각각의 큐마다의 스케쥴링이 필요하다.

  ㅁ 고정된 우선순위 스케쥴링 : Starbation가능

  ㅁ Time slice - 각각의 큐는 %로 CPU의 사용시간을 가진다.(fore = 80%, back = 20%)

Multilevel Feedback Queue

- 프로세스는 큐를 왓다리 갓다리함.(aging 기법이 사용됨)

- 다단계 피드백 큐 스케쥴러는 다음의 매개변수에 의해 정의된다.

  ㅁ 큐의 수

  ㅁ 각 큐를 위한 스케쥴링 알고리즘

  ㅁ 한 프로세스를 높은 우선순위 큐로 올려주는 시기 결정 방법

  ㅁ 한 프로세스를 낮은 우선순위 큐로 내려주는 시기 결정 방법

  ㅁ 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

Multiple-Processor Scheduling

- 다중 처리기를 사용할때 CPU 스케쥴링이 더복잡하다.

- 동일한 처리기일때의 상황만 설명한덴다..쩝...-_-ㅋ 그냥 다해주지...

- 부하공유 : I/O장치를 여러명이서 쓸라할때! 싸운다.......

- 비대칭 다중처리 : 하나의 처리기만이 시스템자료에 접근하기에 정보공유의 문제를 배제.

Real-Time Scheduling

- 경성

- 연성

Algorithm Evaluation

- 결정론적 모델링(Deterministic Modeling) : 사전에 정의된 특정한 작업 부하를 받아들여 그 작업 부하에 대한 각 알고리즘의 성능을 정의한다.

- 큐잉 모델(Queueing Model)

- 모의 실헝(Simulation)

- 구현(Implementation)

P(i) = Base + CPU(i-1)/2 + nice

CPU(i) = U(i)/2 + CPU(i-1)/2

U(i) ... ...??

P(10) = U(9)/4 + U(8)/8 + U(7)/16 .......... + Base + nice