CPU Scheduling

 

 

반효경 교수님의 강의로 운영체제를 공부하고 있습니다.

 

 

 

프로그램이 실행되면 위와 같은 사진처럼 실행되게 됩니다.

load store, add store는 CPU를 실행시키다가 중간에 오래걸리는 작업(파일 읽기)일 때는 wait을 하고

다시 CPU를 사용하고 ... 결국 CPU를 사용하는 단계와 I/O를 하는 단계를 연속적으로 일어나게 됩니다.

CPU만 사용하는 단계를 CPU burst라 부르고, I/O 를 사용하는 단계를 I/O burst라고 합니다.

프로그램의 종류에 따라 빈도는 달라진다.

보통 애플리케이션들은 이 빈도가 많다. -> 데이터를 읽어와 화면 출력을 반복하기 때문에.

 

 

프로세스의 특성 분류

프로세스는 그 특성에 따라 다음 두 가지로 나눔

• 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의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.

이 과정을 context switch(문맥 교환)이라고 한다.

 

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

1. Running -> Blocked (예: I/O 요청하는 시스템 콜)

2. Running -> Ready ( 예 : 할당시간만료로 timer interrupt)

3. Blocked -> Ready ( 예 : I/O 완료후 인터럽트)

4. Terminate

 

1, 4에서는 스케줄링은 nonpreemptive( 강제로 빼앗지 않고 자진반납)

그외 모든 스케줄링은 preemptive(강제로 빼앗음)

 

 

Schediling Criteria

performane Index( Performance Measure, 성능척도)

성능을 이야기하므로 처리 시간이 빠를 수록 좋다. 밑에 3개를 주로 이야기함.

• CPU utilization(이용률)
  • keep the CPU as busy as possible
  • CPU가 놀지 않고 일하는 시간 -> 높을 수록 좋다
• Throughput(처리량)
  • of processes that complete their execution per time unit
  • 많을수록 좋다
• Turnaround time(소요시간, 반환시간)
  • amount of time to execute a particular process
• Waiting time(대기 시간)
  • amount of time a process has been waiting in the ready queue
• Response time(응답 시간)
  • amount of time it takes from when a request was submiited until the first response is produced, not output

 

Scheduling Algorithms

• FCFS(First-Come First-Served)
•  SJF(Shortest-Job-First)
•  SRTF(Shortest-Remaining-Tgime-First)
• Priority Scheduling
• RR(Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

 

FCFS (First-Come First-Served)

먼저 온 순서대로 처리를 한다.

비선점형이다. nonpreemtive 강제로 빼앗지 않음

좋은 선택은 아니다.

짧은 시간에 프로세스들이 먼저 도착한 롱 프로세스로 인하여 Convoy effect 가 발생한다.

 

SJF(Shortest-Job-First)

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

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

Two schemems:

Nonpreemptive - 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

Preemptive - 현재 수행중인 프로세스의 남은 burst time보다더 짧은 CPU를 빼앗김 이 방법을 shortest-Remaining-time-first이라고도 부른다

 

SJF is optimal

주어진 프로세스들에 대해 minimum average waiting time을 보장

 

문제점 

Starvation : low priority processes may never execute. 굶어죽는다. 너무 효율성만 생각하다보니 짧은 프로세스하테 우선권을 줌으로써 롱 프로세스는 영원히 CPU를 못얻을 수 있다.

 

해결점 

Aging : as time progresses increase the priority of the process. 오래 기다리면 우선순위를 높여주자.

 

Priority Scheduling

우선순위를 나타내는 숫자가 주어진다. 숫자가 낮을수록 우선순위가 높다.highest proirity를 가진 프로세스에게 CPU를 할당SJF는 일종의 priority schduling이다.Problem : starvation(기아 현상) - 극단적으로 CPU사용시간이 짧은 잡을 선호한다.그래서 CPU 사용시간이 긴 잡은 영원히 사용못할 수 도 있다.

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

 

Round Robin(RR)

각 프로세스는 동일한 크기의 할당시간을 가짐(일반적으로 10`100milliseconds)할당 시간이 지나면 프로세스는 신짐당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.n개의 프로세스가 ready quq에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.Performance- q large => FIFO- q small => context switch 오벟헤드가 커진다.

 

라운드로빈은 SJF보다 길어질수있지만 최초의 CPU를 얻는 시간을 짧다.

 

Multilevel Queue

Ready queue를 여러개로 분할

• foreground(interactive)
• background(batch-no human interation)

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

• foreground -RR
• background - FCFS

큐에 대한 스케줄링이 필요

• Fixed priority scheduling
  • serve all from foreground then from background
  • Possibility of starvation
• Time slice 
  • 각 큐에 CPU time 을 적절한 비율로 할당
  • Eg., 80% foreground in RR, 20 % to background in FCFS

 

Multilevel Feedback Queue

프로세스가 다른 큐로 이동가능

에이징을 이와 같은 방식으로 구현할 수 있다.

Multilevel- feedback-queue- scheduler를 정의하는 파라미터들

• Queue의 수
• 각 큐의 scheduling algorithm
• Process를 상위 큐로 보내는 기준
• Process를 하위 큐로 내쫓는 기준
• 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

 

Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄리은 더욱 복잡해짐

Homeogeneos processor인 경우

• Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
• 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐

Load sharing

• 일부 프로세서에 잡이 몰리지 않도록 부하를 적적히 공유하는 메커니즘 필요
• 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법

Symmetirc Multiprocessing(SMP)

• 각 프로세서가 각자 알아서 스케줄링 결정

Asymmetric multiprocessing

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

 

Real-Time Scheduling

Hard real-time systems

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

Soft real-time computing

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

 

Thread Scheduling

Local Scheduling

• User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정

Glovbal Scheduling

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

 

알고리즘 평가 방법

Queueing models

확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각정 performance index 값을 계산

 

Implememtation(구현) & Measurement(성능 측정)

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

 

Simulation(모의 실험)

알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교