Scheduling

Computing Theory:

Computing Theory Scheduling Resource used: OCR Computing Text Book, Hodder Education

Scheduling, Job Queues and Priorities:

Scheduling, Job Queues and Priorities Life requires Schedules, Priorities and Queues. Without them, things would not function.

Slide 3:

What are your priorities? Physical Spiritual Mental Emotional

Scheduling:

Scheduling Take the exampe of a multi operating system….there are a number of jobs that must be in the memory in order of the OS to switch from one job to the other This in turns means the OS must have a set of rules that it can use in order to determine the order in which the jobs should be handled The use of this set of rules is known as job scheduling

So what’s scheduling?:

So what’s scheduling? The use of a set of rules to determine the order that jobs should be handled is called Scheduling

What’s scheduling?????:

What’s scheduling????? Set of rules These set of rules determine the order in which jobs should be handled. Use of these rules is called job scheduling!

More about the rules…:

More about the rules… The rules used will be largely decided by the importance applied to the different jobs to be carried out This concept of “importance” implies that the jobs can be arranged into some sort of order and the OS can then follow this order of jobs HOW IS THE ORDER OF JOBS DECIDED!?!?!??

How do you order jobs in your brain?:

How do you order jobs in your brain? Jobs that require physical strength – (interfacing with physical external objects…?) Jobs that require emotional strength (things that require processing and brain powre)

Two types of jobs! (for a processor!):

Two types of jobs! (for a processor!) Jobs that required printers and peripherals a lot – such as a job that needs you to print gas bills Jobs that might use the processor a lot – such as a program to calculate a prime number or square root of something. TWO JOBS HERE ARE: I/O Bound Jobs Processor Bound Jobs

Which ones are given a higher prioity?:

Which ones are given a higher prioity? I/O bound jobs or Processor bound jobs?? I/O Bound jobs! Why do you think this is?

Exam paper Practice!:

Exam paper Practice! Remember the mark scheme is a good way to memorise answers! (in a concise manner)

From Spec Paper f453 (Q1):

From Spec Paper f453 (Q1)

Answers!:

Answers!

Scheduling/Round Robin Scheduling:

Scheduling/Round Robin Scheduling

Answers!:

Answers!

If you had loads of things to do, you might develop an unconscious algo in your head…:

If you had loads of things to do, you might develop an unconscious algo in your head… First Watch GLEE Then Bully little Brother Then do computing coursework (if time left)

Take your computing coursework:

Take your computing coursework Do first come, first served – as in what you’ve been asked to do – you do Do a bit of everything – equal amounts of time spent on write-up and programming Do the shortest bit first (as in do login screen, then move on to sorting algorithm – leave write-up for last, as its longest!) Devise a system where you spend some time on the write-up but an alarm goes off if you spend too much time on it, and then move on to another job. Multi-level and complex Parts to focus on: Write-up + Coding

Scheduling Algorithims:

Scheduling Algorithims Some examples of Scheduling Algorithims: FCFS RR SJF SRT MFQ – Multilevel feedback queues – a very complex algorithm involving a number of queues set up according to rules and acting like a set of league tables. As jobs are given lots of peripheral time, they drop Down the league table, some getting relegated. When a job is finished it leaves the system another job can then get promoted. In this way JOBS CANNOT SPEND TOO MUCH TIME MONOPOLISING THE PROCESSOR

Scheduling Algorithims:

Scheduling Algorithims Some examples of Scheduling Algorithims: FCFS RR SJF SRT –Shortest Remaining Time – similar to SJF – jobs will obviously get shorter and hence nearer the top of the queue as they are processed. Jobs are returned to the queue when they have to stop for some reason like waiting for some input from a keyboard. The major problem with this scheduling algorithm is…..? MFQ LONGER JOBS MAY NEVER GET STARTED!

Scheduling Algorithims:

Scheduling Algorithims Some examples of Scheduling Algorithims: FCFS RR SJF – Shortest Job first. When new jobs are added it is important to make sure they are placed in the right place in the queue by the OS making an estimate of the length of time required to carry out the task SRT MFQ

Scheduling Algorithims:

Scheduling Algorithims Some examples of Scheduling Algorithims: FCFS RR – Round Robin ! The concept of every user getting a small amount of time with the processor betfore it goes on to the next user. (used in Multi-access OS’s) It uses time slices of various lengths to ensure that all jobs get a share of processor time! SJF SRT MFQ

Scheduling Algorithims:

Scheduling Algorithims Some examples of Scheduling Algorithims: FCFS: First Come, First Served RR SJF SRT MFQ

Take your computing coursework:

Take your computing coursework You do what you’ve been asked to do – in the order you are given it! Do a bit of everything – equal amounts of time spent on write-up and programming Do the shortest bit first (as in do login screen, then move on to sorting algorithm – leave write-up for last, as its longest!) Devise a system where you spend some time on the write-up but an alarm goes off if you spend too much time on it, and then move on to another job. Multi-level and complex Parts to focus on: Write-up + Coding Poor example perhaps – but can you match the types of Scheduling Algorithms to the examples provided above?

So what is the purpose of Scheduling?:

So what is the purpose of Scheduling? It is used in order to try and maximise the use of the computer and all its peripherals. It should do this while being “fair” to all the user and ensuring that there is a reasonable response time for all! It should ensure, above all, that the algorithm is robust so that the system will not fail either through ovberloading or by becoming blocked!!

So Scheduling prevents:

So Scheduling prevents (or should prevent) OVERLOADING of system BLOCKAGE of System

Looking more closely at the processor and the ability of a computer to have a number of jobs in different stages of processing…….:

Looking more closely at the processor and the ability of a computer to have a number of jobs in different stages of processing……. We need to know how a processor treats jobs…!

How does a processor treat jobs!:

How does a processor treat jobs!

Any job can be one of three states::

Any job can be one of three states: Think of your coursework projects!!! Jose’s coursework project is READY!

Any job can be one of three states::

Any job can be one of three states: Think of your coursework projects!!! Napoleons coursework is RUNNING (getting there)

Any job can be one of three states::

Any job can be one of three states: Think of your coursework projects!!! Darwin’s coursework project is – incomplete. His brain is incapable of completing it! BLOCKED!

Jobs can be in three states:

Jobs can be in three states READY RUNNING BLOCKED

Slide 32:

READY RUNNING BLOCKED JOB LEAVES THE SYSTEM JOB ENTERS THE SYSTEM

Three cool things you need to know about:

Three cool things you need to know about There is an important thing in the processor that controls jobs around the processor is is called the: THE SCHEDULER!

The Scheduler is made up of::

The Scheduler is made up of: THE HIGH LEVEL SCHEDULER THE LOW LEVEL SCHEDULER And the Medium Level Scheduler…

The SCHEDULER!:

The SCHEDULER! The part of the OS that controls jobs around the processor is called the SCHEDULER There are a number of tasks that have to be done and they are carried out by different parts of the scheduler. When a job wants to be processed it must enter the system and be placed in a queue of jobs waiting for processing called the READY QUEUE

High Level Scheduler:

High Level Scheduler This is the thing that loads the job into the Ready queue HLS = Loads job into Ready queue 

Low level scheduler:

Low level scheduler When the job that is currently running has had to stop then the job at the top of the ready queue is loaded into the processor and is run. THIS IS DONE BY THE LOW LEVEL SCHEDULER (LLS) Jobs may leave the “running” state for one of three reasons

Three states:

Three states Ready Running Blocked (can you think of three reasons that jobs might leave the running state?)

Reasons (for jobs leaving running state):

Reasons (for jobs leaving running state) Job may have finished running in which case it will leave the system Job may require services of a peripheral (like some printing to be carried out, in which case it will be placed in the blocked queue to await servicing) Job has had long enough and it has to give up its place so that the other jobs get a chance…There have to be rules for this to happen, obvious example multi-access system where each user gets a time slice. When time slice is ended, job is returned to ready queue to wait its next turn! Another reason a job might be stopped from running – is if a higher priority interrupt comes along! 3+1 reasons

Three parts of scheduler:

Three parts of scheduler HLS LLS Now the third part: MEDIUM LEVEL SCHEDULER It controls the movement of jobs between the PRIMARY MEMORY AND SECONDARY STORAGE

Note:

Note What is the difference between primary memory and secondary memory? In: Science , Computer Viruses , Data Storage Devices [ Edit categories ] Crucial Memory Upgrades 100% Compatible Computer Memory Upgrades. Free Lifetime Warranty! www.Crucial.com/Computer_Memory [ Improve ] There are two types of memories: Primary and Secondary. The primary memory or the main memory is part of the main computer system. The processor or the CPU directly stores and retrieves information from it. This memory is accessed by CPU, in random fashion. That means any location of this memory can be accessed by the CPU to either read information from it, or to store information in it. o The primary memory itself is implemented by two types of memory technologies. The first is called Random Access Memory (RAM) and the other is read only memory (ROM). A more appropriate name for RAM is RWM (Read Write Memory), the CPU can write and read information from any primary memory location implemented using RAM. The other part of primary memory is implemented using ROM which stands for Read Only Memory. Primary memory is much faster and also it is more cost effective. But the secondary memory is much slower and also less costly. It stores the data permanently unless it is erased. The secondary memory is usually available in the form of floppy disk storage media, hard disk, CD, DVD, Pen drive (i.e. Mass storage devices), memory chips. A 5 and1/4 inch floppy disk typically stores 1.44 mb of data. The data on the floppy disk is organized in terms of tracks and sectors. Hard disk can have large capacity something like 80-300 GB's or higher. Hard disk itself is made up of, large number of platters. Hard disk is usually much faster compared to floppy disk. CD can store up to 750 mb of data. Information on CD ROM is organized in terms of a spiral track. A DVD is digital Versatile Disk and can store 4.6 Gigabyte of information. All these CD disk are usually write ones and read many times (if the disk is not multisession and re writable). So are the DVDs. Difference between Primary and Secondary Memory

Slide 42:

READY RUNNING BLOCKED JOB LEAVES THE SYSTEM JOB ENTERS THE SYSTEM LLS HLS LLS

Slide 43:

READY RUNNING BLOCKED JOB LEAVES THE SYSTEM JOB ENTERS THE SYSTEM LLS HLS LLS MLS

Slide 44:

READY RUNNING BLOCKED JOB LEAVES THE SYSTEM JOB ENTERS THE SYSTEM LLS HLS LLS MLS MLS – A Pre-emptive scheduler. It is allowed to move jobs out of the running state and Into the ready queue. If the job that is running state can only be moved out of it because it has Finished proicessing or because it needs some I/O then that thin arrow can be removed and the Scheduler is said to be NON-PRE-EMPTIVE!