Operating Systems Scheduling (PPT 3)

Question 1

What is scheduling?

Answer 1

It is the process of deciding when a process gets CPU time and how long does it have it for.

Question 2

What are the three types of scheduling?

Answer 2

Long term
-When a process is added to the pool of processes waiting to be executed

Medium Term
-When a process is moved into main memory

Short Term

• When a process is moved from Ready to Running
• When a process is taken of the CPU, e.g. Running to blocked or Ready

Question 3

What is user-oriented criteria?

Answer 3

When a good user experience is put at the forefront of scheduling decisions

Question 4

What is system-oriented criteria?

Answer 4

When the efficiency and utilisation of the machine is at the forefront of scheduling decisions, rather than the user.

Question 5

What is important to accommodate for in user-oriented criteria?

Answer 5

• Low response times meaning things happen immediately

- Event deadlines are met so things happen at the right time.

Question 6

What does the scheduling algorithm have an influence over?

Answer 6

• Priority of processes
• Order in which processes are executed
• How much CPU time is given to each process

Question 7

What should a scheduling mechanism generally do?

Answer 7

• Favour short jobs
• Favour I/O bound jobs to get good I/O device utilisation and better interactive performance
• Determine the nature of a job and schedule accordingly
• Be cheap (efficient) to implement

Question 8

Name four types of scheduling algorithm

Answer 8

• First Come First Serve
• Round Robin
• Shortest Job First
• Shorts Remaining Time

Question 9

How does First Come First Serve work?

Answer 9

When the current process finishes, the process at the head of the ready queue is selected next. It is then allowed to run to completion. Any process becoming ready joins the ready queue

Question 10

What are some characteristics of First Come First Serve?

Answer 10

• Simple to implement
• Favours long processes over short ones because a Running process is allowed to stay running until it completes and Exits
• Favours CPU-bounded processes, i.e. ones that are limited by the power of the computer
• FCFS is a non-pre-emptive algorithm

Question 11

What is CPU-Bounded?

Answer 11

It is when a process is limited by the CPU processing power.

Question 12

What is I/O Bounded?

Answer 12

It is when a process is limited by external events (I/O), such as waiting for a keystroke.

Question 13

How does Round Robin work?

Answer 13

Processes are dispatched by FIFO but are given a fixed time on the CPU. A timer interrupt is used to provide the time slice. It may require many visits to the CPU to complete a task but time is shared equally

Question 14

What is Time Slicing?

Answer 14

This is when the OS sets an interrupting clock to generate an interrupt at some point in the future. This interrupt is the processes’ quantum (time slot or time slice)

Question 15

What are benefits of Time Slicing?

Answer 15

• It allows the OS to regain control of the processor and then pre-empt any process
• Provides reasonable response times and prevents the system being held up by processes in an infinite loop

Question 16

What are some characteristics of Round Robin?

Answer 16

• Effective in time-sharing environments
• Penalises I/O bound processes because they often block quickly. Means they make less use of their time slice that CPU bound processes.
• Is a pre-emptive algorithm

Question 17

What does pre-emption mean?

Answer 17

This is “butting-in” or interrupting the execution of the program code. If the OS is able to stop the process executing and take the CPU away, then this is pre-emption. A scheduling algorithm is pre-emptive if the OS can take the CPU away from a process

Question 18

How is pre-emption useful?

Answer 18

It helps in a situation where there is a high number of high priority processes. It can prevent one process from starving other processes by pre-empting it and returning it to its ready state

Question 19

How does Shortest Job First work?

Answer 19

This is when the process with the shortest expected execution time is dispatched to the processor next.

Question 20

What are some characteristics of Shortest Job First?

Answer 20

• Non-Pre-emptive
• Reduces average waiting time compared to FCFS
• Must know in advance how long process will take
• Possible user abuse (e.g. underestimating the run time)
• Long processes may get starved by short ones

Question 21

How does Shortest Remaining Time work?

Answer 21

Process with the shortest estimated run time to completion is run next. Can be pre-empted by another process if it is estimated to run faster

Question 22

What are some characteristics of Shortest Remaining Time?

Answer 22

• Still requires estimates on the future run time
• Higher overhead than SJF
• No additional interrupts generated as in RR
• Elapsed service time must be recorded

Question 23

The following processes (Pn) exist at time 0, each with a total run-time requirement of T units:
P0 (T=7), P1 (T=13), P2 (T=5), P3 (T=3), P4 (T=2)
Draw a Gantt chart that illustrates when each process runs when using the following types of scheduling: (i) SJF(SPN); (ii) RR.

Answer 23

Example Gantt chart

         Process				      Waiting time
	P0:*******					         0
	P1:          *************			         7
	P2:                            *****			20
	P3:                                   ***		25
	P4:                                       **		28
	Time:        7                   20     25  28 30
Average waiting time = (0+7+20+25+28)/5 = 16

Question 24

What are the three different types of priority a process can have?

Answer 24

-High priority
I/O, User interface and urgent or important processes

-Medium priority
Disk access for periodic saving or less urgent or important that UI processes

-Low priority
Background processes or processes that run slowly and do not affect UI

Question 25

What possible priority policies can a scheduling algorithm have?

Answer 25

It can decide which queue to access next by one of three ways:

• Empty High queue, then empty Medium and finally Low
• Take 3 processes from High, 2 from Medium and 1 from Low
• Take 10 from High, 4 from Medium and 2 from Low

Question 26

What is a benefit of having multiple Ready queues?

Answer 26

Having more than one queue relating to priority means that once a process has been pre-empted and is returning to the ready state, it can change its priority to a new one if it needs to

Question 27

How does the Microsoft Windows Thread Dispatching Priorities System work?

Answer 27

It has 32 Ready queues : 16 Real time and 16 variable. Threads cannot move between real time and variable classes. Threads can migrate up and down the variable priority queues but not the real time ones. Pre-emption works by making threads with real time precedence have priority over others. If a thread becomes ready with a higher priority than the one running, it is pre-empted

Question 28

How does the MS priority relationships work?

Answer 28

Processes have a base priority level. A thread starts off with the base priority plus or minus 2. Threads can migrate up and down the Dynamic Priority but cannot go lower than the base priority. Threads can be boosted and fall in many ways:

• If a thread blocks due to I/O it is boosted
• If interactive, it is boosted
• If CPU bounded, it falls

Question 29

How has MS thread scheduling been designed?

Answer 29

It has been designed to help Interactive threads the most, I/O threads next and CPU bounded threads the least