This week we are going to explore scheduling.  Scheduling is also a core concept with Operating Systems that you must understand.

I can not say how many of you will be directly implementing the scheduler kernel process at Microsoft or some other OS vendor but you will benefit from understanding and will run into situations where you will be implementing some sort of scheduler algorithm.  For example, when I was working on a network box at GE we had a crude exec style OS.  It had minimal functionality and was designed to read network packets, assemble them, make a routing decision, and push them on.  The code to read and process a packet was interrupt driven and we had 3 linked lists with each corresponding to a low level OSI like stack layer.  When an interrupt was not being processed the scheduler ran as a big loop that looked at each of the linked lists and processed a packet if it was in the list and moved to another linked list until it reach the list tied to the network link it was being sent out on.  The code was old and had its origins in GE Computer Company code but it had been heavily modified over the years.  The scheduler priorities was to give more time to the link level queue because if you fell too far behind (the linked list got too big) the interrupt to read the next packet would have no place to add a new message and it would have to drop a packet.  Dropping packets being a bad thing in a network.  Balance this with the fact that you had to move the processed packets to the next queue and out the door on the outbound link the scheduler was a balancing act.  It had to give more time to the incoming packets (higher priority) without starving the outbound queues such that they could not move the data packets out.  This balancing act was tweeked based on traffic loads and traffic evolution (BiSync, SDLC, X.25, etc) and changed over time.... the code also looked like it changed over time.  In any case... the below type of calculation has been done by Operating Systems students for a long time.  General OS schedulers are much more complex and usually have more than one queue for different priority levels and multiple processors being used, etc.  But the fundamentals are the same....

It will definitely help you better understand some of the tuning mechanisms that vendors give you such as the nice command in UNIX and the Windows 
System Properties -> Advanced -> Performance -> Advanced -> Processor Settings options.  They both are interfaces that allow you to give a hint to the scheduler and influence the scheduler's choices.  Sometimes I think they are there as placebos but that is just me.

I would like you to do the following:

1) Given the following process and burst times:

          Process  Burst Time
            P1        25
            P2        50
            P3        20
            P4        15
            p5         5

    Calculate the average wait time for FCFS.  Show the order of scheduling and the times.

2) Given the following process and burst times:

          Process  Burst Time
            P1        25
            P2        50
            P3        20
            P4        15
            p5         5  

    Calculate the average wait time for RR.  Show the
    order of scheduling and the times. The time slice is 10

3) Compare and contrast the Round Robin and First Come First Served Algorithms.