Operating Systems Scheduling (PPT 3) Flashcards
What is scheduling?
It is the process of deciding when a process gets CPU time and how long does it have it for.
What are the three types of scheduling?
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
What is user-oriented criteria?
When a good user experience is put at the forefront of scheduling decisions
What is system-oriented criteria?
When the efficiency and utilisation of the machine is at the forefront of scheduling decisions, rather than the user.
What is important to accommodate for in user-oriented criteria?
- Low response times meaning things happen immediately
- Event deadlines are met so things happen at the right time.
What does the scheduling algorithm have an influence over?
- Priority of processes
- Order in which processes are executed
- How much CPU time is given to each process
What should a scheduling mechanism generally do?
- 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
Name four types of scheduling algorithm
- First Come First Serve
- Round Robin
- Shortest Job First
- Shorts Remaining Time
How does First Come First Serve work?
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
What are some characteristics of First Come First Serve?
- 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
What is CPU-Bounded?
It is when a process is limited by the CPU processing power.
What is I/O Bounded?
It is when a process is limited by external events (I/O), such as waiting for a keystroke.
How does Round Robin work?
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
What is Time Slicing?
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)
What are benefits of Time Slicing?
- 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
What are some characteristics of Round Robin?
- 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
What does pre-emption mean?
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
How is pre-emption useful?
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
How does Shortest Job First work?
This is when the process with the shortest expected execution time is dispatched to the processor next.
What are some characteristics of Shortest Job First?
- 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
How does Shortest Remaining Time work?
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
What are some characteristics of Shortest Remaining Time?
- 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
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.
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
What are the three different types of priority a process can have?
-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
