Chapter Objectives o To introduce CPU scheduling. o To describe various CPU-scheduling algorithms. o To discuss evaluation crieria for selecting a CPU-scheduling algorithm for a particular system. 口1⊙生年12月00 东香兰xanchen@ustc.edu.cn http:/staff..u011740i:Operating System操作系统原理斐 March27,20193/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter Objectives To introduce CPU scheduling. To describe various CPU-scheduling algorithms. To discuss evaluation crieria for selecting a CPU-scheduling algorithm for a particular system. 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 3 / 68
提纲一CPU scheduling Basic Concepts Scheduling Criteria 3 Scheduling Algorithms Multiple-Processor Scheduling 5 Real-Time Scheduling OS examples Algorithm Evaluation 8 小结 口18，走卡11月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March27,20194/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 提纲——CPU scheduling 1 Basic Concepts 2 Scheduling Criteria 3 Scheduling Algorithms 4 Multiple-Processor Scheduling 5 Real-Time Scheduling 6 OS examples 7 Algorithm Evaluation 8 小结 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 4 / 68
Outline Basic Concepts CPU-1/O Burst Cycle CPU Scheduler o Preemptive Scheduling ●Dispatcher 口1⊙生年12月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March27,20195/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Basic Concepts CPU-I/O Burst Cycle CPU Scheduler Preemptive Scheduling Dispatcher 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 5 / 68
Basic Concepts o Scheduling is a fundamental OS function. Almost all computer resources are scheduled before use. CPU scheduling is the basis of multiprogrammed OSes. Objective of multiprogramming o Maximum CPU utilization 口G￥4老年年色走QG 东香兰xlanchen@ustc,edu.cn http:/staff..u011740i:Operating System操作系统原理 March27,20196/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basic Concepts Scheduling is a fundamental OS function. ▶ Almost all computer resources are scheduled before use. ▶ CPU scheduling is the basis of multiprogrammed OSes. Objective of multiprogramming Maximum CPU utilization 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 6 / 68
Outline Basic Concepts CPU-1/O Burst Cycle o CPU Scheduler o Preemptive Scheduling o Dispatcher 口1⊙生年12月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March27,20197/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Basic Concepts CPU-I/O Burst Cycle CPU Scheduler Preemptive Scheduling Dispatcher 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 7 / 68
Basic Concepts:CPU-I/O Burst Cycle oA property of process: CPU-1/O Burst Cycle Process execution consists of a load store cycle of CPU execution and I/O add store CPU burst read from file wait Alternating Sequence of CPU And wait for I/O I/O burst 1/O Bursts store increment index CPU burst o Begin and end with a CPU burst write to file ●Process execution wait for l/O l/O burst n(CPU execution l/O wait) load store +CPU execution add store CPU burst read from file wait for I/O 1/O burst EDao 陈话兰xlanchen@ustc.edu:cn http/staff.uO1174O1 Operating System操作系统原理 March27,20198/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Basic Concepts: CPU-I/O Burst Cycle A property of process : CPU-I/O Burst Cycle Process execution consists of a cycle of CPU execution and I/O wait Alternating Sequence of CPU And I/O Bursts Begin and end with a CPU burst Process execution = n (CPU execution + I/O wait) + CPU execution ... load store add store read from file wait for I/O store increment index write to file wait for I/O load store add store read from file wait for I/O ... CPU burst I/O burst CPU burst I/O burst CPU burst I/O burst 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 8 / 68
CPU burst distribution 160 140 12 100 80 50 40 20 16 24 32 40 burst duration (milliseconds) Histogram of CPU-burst Times 东香兰xlanchen@ustc,edu.cn http:/staff..u0117401 Operating System操作系统原理 March27,20199/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CPU burst distribution 0 8 16 24 32 40 20 40 60 80 100 120 140 160 frequency burst duration (milliseconds) Histogram of CPU-burst Times 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 9 / 68
Outline Basic Concepts o CPU-1/O Burst Cycle o CPU Scheduler o Preemptive Scheduling o Dispatcher 口1⊙生年12月00 陈香兰xlanchen@ustc.edu:cn http:/staf.u01174oi:Operating System操作系统原理斐 March27.201910/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Basic Concepts CPU-I/O Burst Cycle CPU Scheduler Preemptive Scheduling Dispatcher 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 10 / 68
CPU Scheduler CPU scheduler(Short-term Scheduler) selects a process from the processes in memory that are ready to execute and allocates the CPU to the process o Ready Queue could be: a FIFO Queue? a priority queue? a tree? an unordered linked list? 口5，注，”12月0C 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March27.201911/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CPU Scheduler CPU scheduler (Short-term Scheduler) selects a process from the processes in memory that are ready to execute and allocates the CPU to the process Ready Queue could be: ▶ a FIFO Queue? ▶ a priority queue? ▶ a tree? ▶ an unordered linked list? 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 11 / 68
Outline Basic Concepts 0 CPU-1/O Burst Cycle CPU Scheduler o Preemptive Scheduling o Dispatcher 口1⊙生年12月00 陈话兰xlanchen@ustc.edu:cn http/staff.u0117401 Operating System操作系统原理斐 March27,201912/68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Outline 1 Basic Concepts CPU-I/O Burst Cycle CPU Scheduler Preemptive Scheduling Dispatcher 陈香兰 xlanchen@ustc.edu.cn http://staff.ustc.edu.cn/~xlanchen (Computer Application Laboratory, CS, USTC @ Hefei Embedded System Laboratory, CS, USTC @ Suzhou) 0117401: Operating System 操作系统原理与设计 March 27, 2019 12 / 68