Uniprocessor Scheduling

Slides:



Advertisements
Similar presentations
Lee Hoon Copyright(c) 2008 LeeHoon All rights reserved. 제7강제7강.
Advertisements

OS 소개 Introduction 설계목표 기본 용어 Resource Management History.
Chapter 1. 운영체제의 개요 이태호.
Mar OSEK/VDK Woo Dong Kyun.
Project #2-2. Pintos User Program
제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링
Chapter 3 데이터와 신호 (Data and Signals).
제 2장 컴퓨터 구조.
정보통신실습 및 특강(5)
Operating Systems Overview
AWR DB 보고서 분석.
7장 : 캐시와 메모리.
임베디드 하드웨어 Lecture #6.
운영체제 레프토 (4장 CPU 스케줄링) b반 박상수.
제 2 장 프로세스 관리 2.1 개요 프로세스 스케줄링은 준비완료(ready) 상태에 있는 프로세스들 중 어느 것을 중앙처리장치에 할당시킬 것인가를 결정 중앙처리장치 처리율(throughput)의 최대화와 반환 시간(turnaround time)의 최소화 2.2 프로세스.
5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle)
운영체제 (Operating Systems)
프로세스 관리.
6장 단일 프로세서 스케줄링.
컴퓨터 과학 개론 √ 원리를 알면 IT가 맛있다 컴퓨터 과학도를 위한 첫 전공서 ehanbit.net.
1. 스케줄링 개요 [그림 6-16] 프로세스의 반환, 대기, 반응 시간
임베디드 운영체제 (리눅스 중심) Lecture #2.
운영체제 (Operating System) (하드웨어와 응용 프로그램 사이의 인터페이스 역할을 담당하는 시스템 소프트웨어)
2.2 CPU 스케줄링의 목적과 유형 스케줄링의 목적
DSP와 TMS320F28x의 이해.
운영체제와 Windows XP 초등 ICT 교육 방법론 2013년 1학기.
MicroC/OS-II 1. Miscellaneous
운영체제 (OS: Operating System)
CPU스케줄링(CPU Scheduling) ~
Chapter 5. CPU 스케줄링 (CPU Scheduling)
Chapter 10. Interrupt.
2장 운영 체제의 개요 운영체제의 개념 운영체제의 유형 운영체제의 발전 과정 운영체제의 구성 운영체제 서비스 시스템 구조
Multiprocessor and Real-time Scheduling
Multiprocessor and Real-time Scheduling
Chapter 5. CPU 스케줄링 (CPU Scheduling)
Lecture #3 프로세스(Process).
Geek-OS Project 정영진
운영체제 (Operating Systems)
Xen and the Art of Virtualization
제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링.
Operating system #5 Disk Scheduling
Chapter 10. 파일 시스템 인터페이스(File System Interface)
5.1.1 CPU-I/O 버스트 주기(CPU-I/O Burst Cycle)
6 단일 프로세서 스케줄링.
제2장 프로세스 이나현.
제5장 CPU스케줄링(CPU Scheduling)
제10,11,12장 파일시스템 디스크 스케줄링.
운영체제(Operating System)
운영체제 (Operating Systems) (Memory Management Strategies)
7장 메모리 관리 메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다.
Computer System Overview
제7강 PC정비사 1급(필기) Lee Hoon Copyright(c) 2008 LeeHoon All rights reserved.
Chapter 12 Memory Organization
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
23. Unix 시스템 커널. 개요 커널의 기본 서비스 커널의 특징 참고서적 프로세스 관리 장치 관리 파일 관리 가상 메모리
제 2장 프로세스 관리와 CPU 스케줄링 2.1 프로세스의 개념 2.2 CPU 스케줄링의 목적과 유형
운영체제 (Operating System) (하드웨어와 응용 프로그램 사이의 인터페이스 역할을 담당하는 시스템 소프트웨어)
제4장 CPU 스케줄링 이나현.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
제4장 CPU 스케쥴링 운영체제 1-C반 박소라.
I/O Management and Disk Scheduling
운영체제 (Operating Systems)
Lecture #7 CPU Scheduling.
임베디드 하드웨어 Lecture #6.
5.1 개요 고정 헤드 디스크 유동 헤드 디스크 드럼 플로피디스크
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
Lecture 7 7-Segment LED controller using u-controller
CPU 스케줄링 장우영.
Chapter 7: Deadlocks.
가상 기억장치 (Virtual Memory)
Presentation transcript:

Uniprocessor Scheduling Lecture #7 Uniprocessor Scheduling

CPU Scheduling 다중 프로그래밍 시스템에서 실행준비 상태인 프로세스 중에서 다음에 실행될 프로세스를 결정하여 CPU를 할당하는 동작 목 적: High processor utilization High throughput number of processes completed per unit time Low response time elapsed time from the submission of a request to the beginning of the response Operating System

Operating System

스케줄링 동작의 분류 Long-term : which process to admit Medium-term: which process to swap in or out Short-term: which ready process to execute next Operating System

Queuing Diagram for Scheduling Operating System

Long-Term Scheduling 어떤 프로그램을 시스템에서 실행할 수 있도록 허용할 것인가를 결정하는 작업 다중 프로그래밍 정도(the degree of multi-programming)를 결정한다 많은 프로세스를 허용하는 경우: 모든 프로세스가 대기상태(blocked)가 될 가능성이 적어진다 CPU 이용률을 높일 수 있다 각 프로세스에 대한 CPU 할당 시간이 적어진다 각 프로세스의 반응 시간이 길어진다 Processor-bound 프로세스와 I/O-bound 프로세스를 적절하게 혼합될 수 있도록 허용하는 것이 효율적 Operating System

Medium-Term Scheduling Swapping decisions based on the need to manage multiprogramming 어떤 프로세스를 swapping 할 것인지를 결정 메모리 관리 소프트웨어에 의해 수행 Operating System

Short-Term Scheduling 어떤 프로세스를 다음에 실행할 것인지를 결정 CPU scheduling Dispatcher 준비 상태의 프로세스 중에서 다음에 실행할 프로세스를 선택 선택된 프로세스에게 CPU를 할당 문맥을 교환 사용자 모드로 전환 프로그램 실행을 위해 사용자 프로그램의 적절한 위치로 이동 – PC(program count) 설정 CPU 스케줄링이 수행되는 시점(events): clock interrupts I/O interrupts operating system calls and traps signals Operating System

CPU-I/O Burst Cycle 하나의 프로세스는 CPU 작업과 I/O 작업을 교대로 요구하는 동작을 반복적으로 수행  load store add store read from file store increment index write to file 하나의 프로세스는 CPU 작업과 I/O 작업을 교대로 요구하는 동작을 반복적으로 수행 각 사이클은 CPU burst (typically of 5 ms)와 I/O burst(usually longer)로 구성 프로세스는 CPU burst로 시작하여 CPU burst로 종료 CPU-bound process는 I/O-bound process보다 더 긴 CPU bursts을 갖는다 CPU Burst Wait for I/O I/O Burst CPU Burst Wait for I/O I/O Burst CPU Burst Wait for I/O I/O Burst Operating System

CPU 스케줄링 기준(Criteria) 사용자 관점 기준 시스템 관점 기준 Response Time(응답 시간): 프로그램이 제출된 때부터 반응을 시작하는데 걸리는 시간 Turnaround Time(작업 반환 시간): 프로그램이 제출된 때부터 완료될 까지 걸리는 시간 시스템 관점 기준 processor utilization(CPU 이용률) Fairness(공평성) Throughput(처리율): 단위 시간당 수행 완료하는 프로세스 수 Operating System

Operating System

Operating System

CPU 스케줄링 알고리즘의 특성 선택함수(selection function) 결정모드(decision mode) ready queue에 있는 프로세스들 중에서 다음에 실행한 프로세스를 결정하는 방법(기준) 결정모드(decision mode) 선택함수를 실행할 시점을 정의 Non-preemptive(비선점) 일단 프로세스가 실행상태가 되면 실행을 종료하거나 I/O로 인해 대기상태가 될 때까지 실행을 계속하는 모드 Preemptive(선점) 현재 실행중인 프로세스를 중지하여 ready queue에 보내고 새로 선택된 프로세스를 실행하는 모드 하나의 프로세스가 오랜 시간동안 CPU를 독점하지 못하도록 함으로써 더 나은 서비스를 허용한다 Operating System

CPU 스케줄링 알고리즘 선입 선처리(First Come First Served) 스케줄링 라운드 로빈(Round-Robin) 스케줄링 짧은 프로세스 우선(Shortest Process Next:SPN) 스케줄링 최단 잔여 시간(Shortest Remaining Time:SRT) 스케줄링 최고 응답률 우선(Highest Response Ratio Next:HRRN) 스케줄링 우선순위(Priority) 스케줄링 다단계 피드백 큐(Multi-level Feedback Queue) 스케줄링 Multiprocessor 스케줄링 실시간 스케줄링(Real-Time Scheduling) Operating System

CPU 스케줄링 알고리즘의 비교 Process Arrival Time Service 1 2 3 4 5 6 8 - Service time = total processor time needed in one (CPU-I/O) cycle - Jobs with long service time are CPU-bound jobs and are referred to as “long jobs” Operating System

선입 선처리 스케줄링 : First Come First Served (FCFS) 선택함수 ready queue 에서 가장 오랫동안 대기하고 있는 프로세스를 선택 First Come First Served(FCFS) 결정모드 Non-preemptive(비선점) 프로세스는 종료하거나 대기상태가 될 때까지 실행한다 Operating System

FCFS 스케줄링의 단점 어떤 I/O도 요구하지 않는 프로세스가 CPU를 독점할 수 있다 CPU-bound process를 선호한다 I/O-bound process는 CPU-bound process가 종료할 때까지 기다려야 한다 I/O-bound process는 I/O가 완료되더라도 기다리는 상태이므로 다음 I/O을 실행하지 못한다(poor device utilization) I/O bound process에 한 레벨 높은 우선순위를 부여함으로써 I/O device의 이용률을 높일 수 있다 Operating System

라운드-로빈(Round-Robin) 스케줄링 선택함수: FCFS와 같다 결정모드: preemptive(선점) 프로세스는 하나의 time slice (quantum, typically from 10 to 100 ms) 동안에 실행된다 clock interrupt가 발생하면 현재 실행중인 프로세스를 ready queue로 보내고 FCFS 방식으로 새로운 프로세스를 실행한다 Operating System

Time Quantum for Round Robin (1) Clock interrupt과 dispatching 처리를 위한 시간보다 더 크게 결정되어야 한다 should be larger than the typical interaction 작업 반환 시간이 커질 수 있다 Operating System

Time Quantum for Round Robin (2) Operating System

Round Robin 스케줄링 분석 여전히 CPU-bound process를 선호한다 I/O bound process는 time slice보다 적은 시간동안 CPU를 사용하고 I/O 요구에 대해 대기상태가 된다 CPU-bound process는 모든 time slice 동안 실행되고 ready queue로 되돌아간다. 이때, 대기 상태의 프로세스 앞에 놓이게 된다 해결책: 가상 라운드 로빈(virtual round robin) I/O가 완료되었을 때에 대기 상태의 프로세스를 ready queue보다 높은 우선순위를 가지는 보조 큐(auxiliary queue)에 보낸다 Operating System

Queuing for Virtual Round Robin Operating System

Shortest Process Next (SPN) 스케줄링 선택함수: 가장 짧은 CPU burst time을 가진 프로세스를 선택한다 최소 작업 우선(Shortest Job First) 스케줄링 결정모드: non-preemptive(비선점) I/O bound process가 먼저 선택된다 각 프로세스의 CPU burst time을 미리 예측하여야 한다 Operating System

CPU burst time 예측(1) Let T[i] be the execution time for the i-th instance of the process the actual duration of the i-th CPU burst of this process Let S[i] be the predicted value for the i-th CPU burst of this process. The simplest choice is: S[n+1] = (1/n) S_{i=1 to n} T[i] To avoid recalculating the entire sum we can rewrite this as: S[n+1] = (1/n) T[n] + ((n-1)/n) S[n] But this convex combination gives equal weight to each instance Operating System

CPU burst time 예측(2) But recent instances are more likely to reflect future behavior A common technique for that is to use exponential averaging S[n+1] = a T[n] + (1-a) S[n] ; 0 < a < 1 more weight is put on recent instances whenever a > 1/n Operating System

SPN 스케줄링 분석 짧은 프로세스가 계속적으로 생성될 때에는 긴 프로세스가 starvation 될 가능성이 있다 비선점 방식이므로 시분할 환경(대화형 환경)에는 부적합하다 CPU bound process가 낮은 우선순위를 가지지만 여전히 I/O을 요구하지 않는 프로세스가 CPU를 독점할 수 있다 대화형 응용 프로그램 실행에는 부적합 SPN 스케줄링은 함축적으로 우선순위 기법을 수용한다 shortest jobs are given preferences Operating System

Shortest Remaining Time (SRT) 스케줄링 선택함수: 예측된 잔여 처리 시간이 가장 짧은 프로세스를 선택 SPN 스케줄링의 선점형 결정모드: preemptive(선점) 새로운 프로세스의 처리 요구 시간이 현재 수행중인 프로세스의 잔여 처리 시간보다 짧은 경우 선점된다 Operating System

Shortest Remaining Time (SRT) 스케줄링 분 석: FCFS 스케줄링보다는 공평한 스케줄링을 수행 실행 시간이 긴 프로세스들이 기아 상태에 빠질 가능성이 존재 라운드-로빈과 달리 인터럽트가 추가로 발생하지 않음 선점형이기 때문에 SPN보다 작업처리 시간이 훨씬 짧다 프로세스의 처리 시간 예측 및 프로세스 서비스 시간 계산에 대한 오버헤드가 존재 Operating System

Highest Response Ratio Next (HRRN) 스케줄링 선택함수: 응답 비율(RR: Response Ratio)이 가장 큰 프로세스를 선택 RR = (CPU 대기 시간 + 예측된 서비스 시간)/예측된 서비스 시간 모든 프로세스들에 대한 응답 비율의 평균값을 최소화 결정모드: nonpreemptive(비선점) Operating System

Highest Response Ratio Next (HRRN) 스케줄링 분 석: 프로세스의 대기 시간을 고려하기 때문에 효과적 일반적으로 짧은 실행시간을 가진 프로세스가 유리 실행 시간이 긴 프로세스의 경우 대기 시간이 증가함에 따라 응답비율이 증가하여 짧은 실행 시간의 프로세스보다 먼저 실행 Operating System

우선순위 스케줄링 : Priority Scheduling 선택함수 : 우선 순위 기반의 스케줄링 프로세스의 우선순위를 비교 높은 우선순위의 프로세스를 먼저, 같은 수준의 우선순위를 가진 프로세스에 대해서는 FCFS 방식으로 선택 결정모드: preemptive(선점) 각 우선순위 레벨을 나타내는 다수의 ready queue을 사용하여 구현할 수 있다 Multi-level queue 낮은 우선순위 프로세스가 starvation 될 수 있다 동적 우선순위(dynamic priority) 사용 실행 시간 경과에 따라 프로세스의 우선순위를 바꾼다 Operating System

Operating System

다단계 피드백 큐 스케줄링 : Multilevel Feedback Queue Scheduling Preemptive scheduling with dynamic priorities Several ready queues with decreasing priorities: P(RQ0) > P(RQ1) > ... > P(RQn) 새로운 프로세스는 RQ0에 보낸다 Time slice가 완료되면 프로세스를 RQ1으로 보낸다. 그리고 그 다음 단계에서는 RQ2로, 계속하여 RQn까지 보내도록 한다 Operating System

다단계 피드백 큐 스케줄링 : Multilevel Feedback Queue Scheduling I/O-bound process는 높은 우선순위 큐에서 유지되는 반면에 CPU-bound process는 낮은 우선순위 큐로 옮겨간다 Dispatcher는 RQi-1에서 RQ0 까지의 큐가 비어있을 때에 RQi 에서 실행할 프로세스를 선택한다 긴 프로세스는 starvation 될 가능성이 있다 낮은 우선순위 큐에서 오래 대기한 프로세스를 높은 우선순위 큐로 이동시킴(aging)으로써 해결 Operating System

Multiple Feedback Queues 각 큐에서는 FCFS 스케줄링 가장 낮은 우선순위 큐에서는 Round-Robin 스케줄링 Operating System

Time Quantum for MFQ Scheduling 고정 크기의 time slice를 가지는 경우, 긴 프로세스의 작업 반환 시간이 대단히 길어질 수 있다 큐의 레벨에 따라 time slice를 증가시킴으로써 평균 작업 반환 시간을 줄일 수 있다 예: time slice of RQi = 2^{i-1} Operating System

스케줄링 알고리즘의 특성 비교 Operating System

Operating System

Fair-Share Scheduling(FSS) User’s application runs as a collection of processes (threads) User is concerned about the performance of the application Need to make scheduling decisions based on process sets Operating System

Operating System

Traditional UNIX Scheduling Multilevel feedback using round robin within each of the priority queues If a running process does not block or complete within 1 second, it is preempted Priorities are recomputed once per second Base priority divides all processes into fixed bands of priority levels Operating System

Bands Decreasing order of priority Swapper Block I/O device control File manipulation Character I/O device control User processes Operating System

Bands of process priorities Kernel and user priorities Operating System

Operating System