Scheduling Algorithms

vkungeLeave a comment

First Come First Serve or Non-pre-emptive Scheduling.

The CPU can run processes in the process queue (in  ready state) one at a time for a  “burst” at a time in a first come first serve fashion.  This is known as non pre-emptive scheduling, since no determination is made into the most efficient order to run processes on the CPU.

It should be noted that the amount of time that a process might stay on the CPU could be very long when compared to others in the queue. This is because a “burst” might  a sequence of CPU and IO instructions the process executes without interruption form the CPU scheduling algorithm .  The process is only moved from execution on the CPU when a I/O operation occurs that causes the process to be put in wait mode, or, it terminates.

Having other processes wait exceedingly long is not desirable, and todays modern operating systems do not implement FCFS. 

FCFS scheduling does have the advantage of being easier to program and implement; but this advantage does not outweigh the performance of an efficient process scheduler.

FCFS scheduling is also prone to race conditions, where 2 processes need to read from the same section in memory and end up producing inconsistent data.  See here for a good explanation:

https://stackoverflow.com/questions/3130079/difference-between-racearound-condition-and-deadlock

Shortest Job First or Pre-Emptive scheduling

This scheduling algorithm examines each process to determine the length of time that is needed for on the CPU.  The algorithm then places processes with the shortest estimated time to be executed as priority.

Round Robin Scheduling

This is very similar to FCFS scheduling , only this time each process is given a fixed maximum time to be executed on the CPU.  If the process exceeds the time, it is put in wait mode and added to the end of the queue.

© 2021  Vedesh Kungebeharry. All rights reserved. 

Algorithms

vkungeLeave a comment

Definition: An algorithm is a set of finite, well defined steps which outlines the solution to a specific problem.

Alternative Definition : WHAT IS AN ALGORITHM? – DEFINITION

We use algorithms every day to solve problems, weather we’re conscious of it or not.

When we cook a new dish we follow a recipe, when we solve a math problem we follow a procedure.

In our case, we’d like to document the solution to a specific problem using an algorithm so that we can communicate it to a programmer , or create the tool  as a program itself.

We use algorithms, but what are the properties of a good algorithm?

I’m sure you’ve come across bad algorithms already –

  • Vague recipe instructions, what exactly is 2 cups of flour?
  • A videogame walkthrough that isn’t descriptive enough
  • A video tutorial that talks  a lot about becoming a youtuber , but the steps aren’t outlined in order.

What are the properties of good instructions, good algorithms?

Properties of good algorithms

  • Has a  finite number of steps ( a definite beginning and an end)
  • Is precise,
  • Is unambiguous (not subject to interpretation)
  • Shows the flow of control from one sub-process to another
  • Must output results
  • It must terminate.

© 2021  Vedesh Kungebeharry. All rights reserved. 

Debugging

vkunge1 Comment

Definition: Finding and removing errors in your program is called debugging. 

While developing the solution to a program , it’s always a good practice to test your program by running it to ensure that the code runs as you intended. If it does not, you try to determine what caused the error and modify your code so that it’s fixed.

In class Demonstration

In the example below, we consider the task to be solved as part of a bigger program, however now, you would be working on the sprite movement:

https://scratch.mit.edu/projects/518447917/

(Credit: https://scratch.mit.edu/users/rickettr , https://scratch.mit.edu/users/CyberParra )

Teacher discusses and demonstrates how  the program can be fixed.

Discussion

Even if you are confident that you have completed your program, you should test it to see that it works correctly , before releasing your programming project for use by it’s intended audience.

 

In class exercise and homework

Open the following scratch studio and try debugging the projects listed after the studio:

https://scratch.mit.edu/studios/219583/

(Credit: https://scratch.mit.edu/studios/219583/curators/ , https://scratch.mit.edu/users/rickettr)

List of Projects to debug:

Debug-It 1.1

Debug-It 1.2

Debug-It 1.3

Debug-It 1.4

Debug-It 1.5

Contingency Class

See the pdf for notes that were given when the internet was not available for class:

https://drive.google.com/drive/folders/103wrSFX2SRvkDy3yvOrszRh2xONpR0l5?usp=sharing

“HOMEWORK – Perform the in class exercise and homework found on the post from our google classroom”

Debugging in Context – Finding the average of an unknown amount of numbers

See video Below:

UPDATES

2022 April 22nd – Added contingency class

2023 January 11th – Added Debugging in Context – Finding the average of an unknown amount of numbers video only.

© 2021  Vedesh Kungebeharry. All rights reserved.