Smarter Scheduling (Priorities, Preemptive Priority Scheduling, Lottery and Stride Scheduling)

80 %
20 %
Information about Smarter Scheduling (Priorities, Preemptive Priority Scheduling, Lottery...
Technology

Published on March 1, 2014

Author: DavidEvansUVa

Source: slideshare.net

Description

University of Virginia
cs4414: Operating Systems
http://rust-class.org

Scheduling Recap
Real-Time Scheduling
On-Demand vs. Planned Scheduling
First Come, First Served
Round-Robin
Priorities
Priority Preemptive
Priority Inversion
Lottery Scheduling
Stride Scheduling

For embedded notes, see: http://rust-class.org/class-11-smarter-scheduling.html

Smarter Scheduling (Priorities)

Plan for Today Recap: Scheduling First Come, First Served / Round-Robin Priorities Lottery and Stride Scheduling Scheduling in Linux 1

Wil Thomason 2

Recap Main Goals of Scheduling Maximize Resource Use Fairness Switching is Expensive Fundamental tradeoff between maximizing usage and fairness 3

Planned vs. On-Demand Planned: schedule in advance Supervisor/developer plans schedule given a priori knowledge about all tasks and deadlines On-Demand: schedule on-the-fly Supervisor runs periodically and makes decision based on current information Where is planned used? 4

Real-Time Systems Hard Real-Time Missing a deadline is a total system failure. Soft Real-Time Undesirable to miss too many deadlines too badly. 5

Hard Real-Time Missing a deadline is a total system failure. Soft Real-Time Undesirable to miss too many deadlines too badly. 6

What must programs be able to do to have guaranteed schedules? 7

Planned vs. On-Demand Planned: schedule in advance Necessary (at least in part) for hard real time On-Demand: schedule on-the-fly Most normal systems have unpredictable tasks with unknown deadlines 8

What should your courses be? 9

What should your courses be? Exam 2 will be scheduled later (not next week) Problem Set 3 is due 11:59pm Wednesday, March 5 Demos on Wednesday, Thursday, Friday No demos after Spring Break barring snow-out (firm real-time deadline) But…if you planned a schedule around the previously posted deadlines, you can stick to them (see me after class) 10

Scheduling Strategies First Come, First Served (FIFO) P1 P2 P3 (effectively: non-preemptive multi-processing) 11

First Come, First Served (FIFO) P2 P1 P3 (effectively: non-preemptive multi-processing) Round-Robin P1 P2 Time Slice P3 P1 P2 P3 P1 P3 P1 P3 Blocked Each process gets to run for a set time slice, or until it finished or gets blocked. 12

Comparison First Come, First Served Round Robin 13

Which one is my laptop using? 14

Priorities More important processes: “higher priority” (except Linux inverts priority values!) Highest priority = 0 gets most preferential treatment Lowest priority = 99 highest number varies by Linux flavor 15

High Priority Processes ps -w -e -o pri,pid,pcpu,vsz,cputime,command | sort -n -r --key=5 | sort --stable -n --key=1 16

Pre-emptive Priority Scheduling Always run the highest priority process that is ready to run Round-robin schedule among equally high, ready to run, highest-priority processes Priority 0: P 629 Priority 1: P 44 Memory Read P 815 P 516 P 131 Network Data P 528 Priority 2: Waiting: P 124 P 221 Shared Bus P 1209 17

Mars Curiosity (2012) 18

Mars Pathfinder (1997) 19

Pathfinder OS: Pre-emptive Priority Always run the highest priority process that is ready to run Round-robin schedule among equally high, ready to run, highest-priority processes Actuators Shared Bus CPU Radio Camera Flash Memory 20

Priority Inversion Task 1 (scheduler) – highest priority (Priority = 1) Task 2 (send data) – (Priority = 4) Task 3 (science analysis) – lowest priority (Priority = 97) Actuators Shared Bus CPU Radio Camera Flash Memory 21

How should we solve priority inversion? 22

Waiting: Priority 0: Priority 1: P 44 Holds Bus Lock P 815 P 516 P 131 Network Data P 528 Priority 2: Memory Read P 221 Shared Bus P 1209 PRI: 0 23

Should my MacBook use a priority pre-emptive scheduler with priority inheritance? 24

Should my MacBook use a priority pre-emptive scheduler with priority inheritance? 25

Kinds of Processes “Compute-Bound” P1 “I/O-Bound” P2 wait for disk… P2 wait for network… P2 wait for user… “Real Time” P3 need frame ^ P3 need frame ^ P3 need frame ^ P3 need frame ^ 26

Carl Waldspurger 27

Lottery Scheduling 28

Lottery Scheduling • Each user (process) gets a share of the “tickets” – e.g., 1000 total tickets, 20 processes each get 50 tickets (or more/less weighted by priority) • User/process can distribute tickets however it wants – Among its own threads, can “loan” to other processes’ threads • Scheduler: randomly picks a ticket – Associated thread gets to run for that time slice 29

Priority Pre-Emptive Lottery Scheduling 30

31

32

What is the running time? 33

> uname -a Linux power2 3.2.0-49-generic #75-Ubuntu SMP Tue Jun 18 17:39:32 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux > sysctl kernel.pid_max kernel.pid_max = 32768 What is the running time? 34

Charge Stride scheduling works (in real life also)! Much smarter than priority pre-emptive (never finish anything) or first-come first-served or earliest-deadlinefirst. (Unless you like to live serendipitously: then you should use lottery scheduling) Problem Set 3 should have high (but not quite hard real-time) priority! (and try to turn off interrupts when you work on it!) 35

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Class 11: Smarter Scheduling

Class 11: Smarter Scheduling Posted: Thu 27 February 2014 ... Preemptive Priority Scheduling. ... Lottery and Stride Scheduling: ...
Read more

Scheduling (computing) - Wikipedia, the free encyclopedia

Scheduling (computing) ... A preemptive scheduler relies upon a programmable interval timer ... Least slack time scheduling; Lottery scheduling; Priority ...
Read more

Smarter Scheduling - YouTube

Priority Preemptive Scheduling ... Smarter Scheduling Embedded notes are available at: ... Lottery and Stride Scheduling by David Evans.
Read more

Priority Preemptive Scheduling - YouTube

... Smarter Scheduling Embedded notes are available at: ... Priority Preemptive Scheduling ... Lottery and Stride Scheduling - Duration: ...
Read more

Fixed-priority pre-emptive scheduling - Wikipedia, the ...

Fixed-priority pre-emptive scheduling ... Fixed-priority preemptive scheduling is a ... With fixed priority preemptive scheduling, the scheduler ...
Read more

Premptive Priority Scheduling - Class 11: Smarter Scheduling

Premptive Priority Scheduling. ... What are the advantages and disadvantages of preemptive priority scheduling? ... Lottery and Stride Scheduling: ...
Read more

Scheduling Priorities (Windows)

Scheduling Scheduling Priorities. ... Multimedia Class Scheduler Service. ... Threads are scheduled to run based on their scheduling priority.
Read more

Scheduling Algorithms - OSDev Wiki - Expanded Main Page ...

if using priorities, a low-priority task must not hold up a high-priority task; ... Interactive Scheduling Algorithms ... Lottery Scheduling .
Read more