程序代写代做代考 algorithm Scheduling – cscodehelp代写 – INTERVIEW&CODEHELP

Scheduling
CSci4061: Introduction to Operating Systems

September 28, 2021
Computer Science & Engineering, University of Minnesota
1

Last lecture: Threads
• Processes vs. Threads
• Thread benefits and problems • Kernel vs. User threads
• Pthreads
2

Scheduling

State transition diagram
How does OS decide who runs next?
Figure from [4].
3

Scheduling definition
• When contexts are switching among execution units (jobs/processes/threads), OS picks who runs next
• Does it matter?
• Under what situation does this occur? • What should it do?
• Making this decision is called scheduling
4

Scheduler
• The scheduler is the OS module that manipulates the process (ready and waiting/blocked) queues, moving jobs to and from them
• The scheduling algorithm determines which jobs are chosen to run next, for how long, and what queues they wait on
• In general, the scheduler runs:
• When a job switches from running to waiting • When an interrupt occurs
• Why?
• When a job is created or terminated
5

Scheduling levels
Scheduling works at two levels in an operating system
1. Control multiprogramming level – number of jobs loaded into memory
• Which jobs are admitted into memory
• Moving jobs to/from memory is often called swapping • Known as “long-term scheduler”: infrequent
2. To decide what (in-memory) job to run next
• Does it matter? What criteria?
• Known as “short-term scheduler”: frequent
• We are concerned with this level of scheduling
6

Scheduling styles
Scheduler works differently in different systems; in general:
1. Preemptive Scheduling
• The scheduler can interrupt a running job (involuntary context switch) 2. Non-Preemptive (cooperative) Scheduling
• The scheduler waits for a running job to explicitly block (voluntary context switch)
Not confused by preemptive kernel (whether it can be interrupted)
• Non-preemptive kernel disables maskable interrupts during event handling • Preemptive kernel allows interrupts to be delivered during event handling
Is Linux preemptive or non-preemptive? Can non-preemptive scheduling and preemptive kernel co-exist?
7

Scheduling goals
What are some reasonable goals for a scheduler?
8

Scheduling goals
What are some reasonable goals for a scheduler?
Generally speaking, maximizing resource usage and avoiding resource starvation Scheduling algorithms can have many different goals (some important terms):
• CPU, I/O utilization – CPU-intensive and I/O-intensive (interactive) processes • Job throughput
• How many tasks can be done in per unit of time. (# jobs/unit time)
• Response time
• The delay between submitting a process and it being scheduled to run
• Time in ready queue (NOT waiting queue)
• Turnaround time
• Total time taken to complete the whole task: Tfinish – Tstart
8

Scheduling goals – Continued
• Avg. Waiting time
• Avg(Twait): average time spent on wait queues
• Avg. Response time
• Avg(Tready): average time spent on ready queue
In general
• Batch systems
• Strive for job throughput, turnaround time (supercomputers)
• Interactive systems
• Strive to minimize response time for interactive jobs (PC)
9

Job characteristics
Achieving the goals requires knowing the job
• Past: When it arrived, how much progress has it made, how long has it run, has it been behaving nicely, . . .
• Current: How many resources it uses, how many are left,. . .
• Future: How much work is left?. . . Important for some scheduling algorithm,
but can we really know?
• Type: GUI, I/O, realtime,. . .
• Priority
• etc.
10

Starvation
Starvation is a scheduling “non-goal”:
• Starvation: a job is prevented from making progress because other jobs have the resource it requires
• Resource could be the CPU, or a lock (later in synchronization)
• Starvation is usually a side effect of the scheduling
• E.g., a high priority process always prevents a low priority process from running on the CPU
• Starvation can be a side effect of synchronization
• E.g., one thread always beats another when acquiring a lock • E.g., constant supply of readers always blocks out writers
11

Basic scheduling algorithms

What constitutes a good scheduler?
12

What constitutes a good scheduler?
• Be fair
• Give each process a fair share of the CPU
• Be efficient
• Keep the CPU busy all the time
• Maximize throughput
• Service the largest possible number of jobs in a given amount of time
• Minimize response time
• Interactive users should see good performance
• Be predictable
• Same amount of time in each run for the same program
• Minimize overhead
• Don’t waste too many resources in scheduling and context switching
12

What constitutes a good scheduler?
• Maximize resource use
• Favor processes that will use underutilized resources.
• Avoid indefinite postponement
• Every process should get a chance to run eventually.
• Enforce priorities
• If the scheduler allows a process to be assigned a priority, it should be meaningful and enforced.
• Degrade gracefully
• As the system becomes more heavily loaded, performance should deteriorate gradually, not abruptly.
Which ones are contradicting to each other?
13

First In First Out (FIFO)
Schedule tasks in the order they arrive
• Continue running them until they complete or give up the processor • Example: queues
• Supermarket, banks, drive-through, . . .
On what workloads is FIFO particularly bad?
• Imagine being at supermarket to buy a drink of water, but get stuck behind someone with a huge cart (or two!)
• and who pays in pennies!
• It is called Convoy Effect
• Lots of small jobs getting stuck behind a few big jobs that almost never ends
14

Shortest Job First (SJF)
• Always do the task that has the shortest remaining amount of work to do
• Can be either preemptive or non-preemptive
• Preemptive SJF is called shortest remaining time first (SRTF)
• Suppose we have five tasks arrive one right after each other, but the first one is much longer than the others
• Which completes first in FIFO? • Which completes last in SJF?
15

FIFO vs SJF
• What is the big deal? Don’t they finish at the same time?
16

FIFO vs SJF
• Assuming three jobs A, B, C with execution time 8, 4, 2; jobs arrives almost at the same time
• What is the average turnaround time (ATT) for SJF? • What is the ATT for FIFO?
17

FIFO vs SJF
18

FIFO vs SJF
• Claim: SJF is optimal for average response time
• Why? Easy to prove by contradiction
• For what workloads is FIFO optimal?
• For what is it pessimal (i.e., worst)?
• Does SJF have any downsides?
19

Problems with SJF
• Long-burst (CPU-intensive) processes are hurt with a long mean waiting time • Starvation (Particularly for STRF:preemptive)
• Wide variations in response time
• Impossible to know size of CPU burst
• Like choosing person in line without looking inside basket/cart • How can you make a reasonable guess?
20

Discussion about FIFO
• Is FIFO ever optimal?
• Yes, when all requests are of equal length
• Why is FIFO generally good?
• No context switches—non-preemptive • Simple
• Seems fair
21

Round Robin
Round Robin is a preemptive version of the FIFO scheduling
Each task gets resource for a fixed period of time (time quantum)
• If task doesn’t complete or gets blocked because of I/O, it goes back in line • No starvation, No favoritism
22

Round Robin
23

Advantages of Round Robin
• Round robin scheduling is fair: every process gets an equal share of the CPU • It is easy to implement
• If we know the number of processes on the run queue, we can know the
worst-case response time for a process
24

Problems with Round Robin
• Highly interactive processes may get hurt • Need to pick a time quantum
• What if time quantum is too long?
• Waste for highly interactive processes
• What if time quantum is too short? • Context switch overhead
• Average turnaround time often increases!
25

Round Robin vs FIFO/SJF
• What about average response time?
26

Round robin = Fairness?
• Is round robin always fair?
• Sort of but short jobs finish first!
• What is fair?
• FIFO?
• Equal share of CPU?
• What if some tasks don’t need their full share? • Minimize work case divergence?
• time task would take if no one else was running vs.
• time task takes under scheduling algorithm with other jobs
27

Comparing basic algorithms
• FIFO
• Good: fairness
• Bad: turnaround time, response time
• SJF
• Good: turnaround time
• Bad: fairness, hard to estimate run-time
• Round Robin
• Good: fairness, response time • Bad: turnaround time
Q: Is there a scheduler that balances these issues better?
• Challenge: limited information about a process in the beginning
• Challenge: how to prevent gaming the scheduler to get more run-time
28

Complex/Hybrid scheduling algorithms

Priority Scheduling
• Basic algorithms assume that all processes are equally important, true? • Priority Scheduling
• Choose next job based on priority • Example: Delta Sky Priority
• Can implement SJF: priority = 1/(expected CPU burst)
• Also can be either preemptive or non-preemptive
• Problem?
• Starvation – low priority jobs can wait indefinitely
• Solution?
29

Multilevel Queues (MLQ): combining algorithms
• Scheduling algorithms can be combined
• Have multiple queues
• Use a different algorithm for each queue • Move jobs among queues
• Example: Multiple-level feedback queues (MLFQ)
• Multiple queues representing different job types • Interactive, CPU-bound, batch, system, etc.
• Queues have priorities, jobs on same queue scheduled RR
• Jobs can move among queues based upon execution history • Feedback: Switch from interactive to CPU-bound behavior
30

Multi-level Feedback Queue
Goals:
• Responsiveness
• Low overhead
• Starvation freedom
• Some tasks are high/low priority
• Fairness (among equal priority tasks)
Not perfect at any of them – Used in Linux (and probably Windows, MacOS) More details: Arpaci-Dusseau Ch. 18
31

Quiz 1
Which scheduling algorithm allocates the CPU first to the process that requests the CPU first?
a) FIFO scheduling
b) shortest job scheduling c) priority scheduling
d) none of the mentioned
32

Quiz 1
Which scheduling algorithm allocates the CPU first to the process that requests the CPU first?
a) FIFO scheduling
b) shortest job scheduling c) priority scheduling
d) none of the mentioned
Ans a)
32

Quiz 2
Round robin scheduling falls under the category of :
a) Non preemptive scheduling b) Preemptive scheduling
c) All of the mentioned
d) None of the mentioned
33

Quiz 2
Round robin scheduling falls under the category of :
a) Non preemptive scheduling b) Preemptive scheduling
c) All of the mentioned
d) None of the mentioned
Ans b)
33

Quiz 3
The real difficulty with SJF in short term scheduling is :
a) it is too good an algorithm
b) knowing the length of the next CPU request c) it is too complex to understand
d) none of the mentioned
34

Quiz 4
One of the disadvantages of the priority scheduling algorithm is that :
a) it schedules in a very complex manner
b) its scheduling takes up a lot of time
c) it can lead to some low priority process waiting indefinitely for the CPU d) none of the mentioned
35

Quiz 5
What is
• turnaround time? • response time? • and throughput?
36

Summary
• Scheduling
• Goals
• Styles
• Algorithms: pros and cons
37

Next lecture
• Address space and dynamic memory management • Reading: Arpaci-Dusseau Ch. 13
38

Backup slides
39

MLFQ: Multi-level Feedback Queue
• Set of Round Robin queues
• Each queue has a separate priority
• High priority queues have short time slices
• Low priority queues have long time slices
• Why?
• Scheduler picks first thread in highest priority queue • Jobs start in highest priority queue
• Assumes good behavior
• If a job used up the entire time slice, its priority drops one level
• Otherwise it retains its priority
40

MLFQ: Starvation freedom and Gaming
• Wait . . . this design still allows starvation
• Lots of arriving I/O bound jobs
• How to solve this issue?
• After some period S, reset the priority by moving every job to the highest priority
• Can a job abuse the scheduler to increase its running time?
• Jobs can deliberately relinquish the CPU before slice expires • Solution: using allotment time instead of one slice
41

References
[1] https://www.cs.ucr.edu/~csong/cs153/l/sched1.pdf
[2] https://www.cs.ucr.edu/~csong/cs153/l/sched2.pdf
[3] http://www-users.cselabs.umn.edu/classes/Fall- 2017/csci5103/notes/week6_7.1_scheduling_post.pdf [4] http://www-users.cselabs.umn.edu/classes/Spring- 2018/csci4061/notes/processes.pdf [5] https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html
42

程序代写代做代考 algorithm Scheduling – cscodehelp代写

Published by admin

Leave a Reply Cancel reply