TYPE OF SCHEDULING PROCESS :

In mono-tasking operating systems the issue of scheduling is trivial: after the system has set up the execution environment of a process, CPU control is given to it until the process itself exits. In a pun, the system is not operating at all during the program's execution, save for providing services through subroutine calls. It's only with multi-tasking operating systems that scheduling becomes a top entry in a designer's agenda.

In many multitasking systems the processor scheduling subsystem operates on three levels, differentiated by the time scale at which they perform their operations. In this sense we differentiate among:

• Long term scheduling: which determines which programs are admitted to the system for execution and when, and which ones should be exited.
• Medium term scheduling: which determines when processes are to be suspended and resumed;
• Short term scheduling (or dispatching): which determines which of the ready processes can have CPU resources, and for how long.

Taking into account the states of a process, and the time scale at which state transition occur, we can immediately recognise that

• dispatching affects processes
• running;
• ready;
• blocked;
• the medium term scheduling affects processes
• ready-suspended;
• blocked-suspended;
• the long term scheduling affects processes
• new;
• exited

Long term scheduling obviously controls the degree of multiprogramming in multitasking systems, following certain policies to decide whether the system can honour a new job submission or, if more than one job is submitted, which of them should be selected. The need for some form of compromise between degree of multiprogramming and throughput seems evident, especially when one considers interactive systems. The higher the number of processes, in fact, the smaller the time each of them may control CPU for, if a fair share of responsiveness is to be given to all processes. Moreover we have already seen that a too high number of processes causes waste of CPU time for system housekeeping chores (trashing in virtual memory systems is a particularly nasty example of this). However, the number of active processes should be high enough to keep the CPU busy servicing the payload (i.e. the user processes) as much as possible, by ensuring that - on average - there always be a sufficient number of processes not waiting for I/O.

Simple policies for long term scheduling are

• Simple First Come First Served (FCFS): it's essentially a FIFO scheme. All job requests (e.g. a submission of a batch program, or an user trying to log in in a time shared system) are honoured up to a fixed system load limit, further requests being refused tout court, or enqueued for later processing.
• Priority schemes. Note that in the context of long term scheduling ``priority'' has a different meaning than in dispatching: here it affects the choice of a program to be entered the system as a process, there the choice of which ready process process should be executed.

Medium term scheduling is essentially concerned with memory management, hence it's very often designed as a part of the memory management subsystem of an OS. Its efficient interaction with the short term scheduler is essential for system performances, especially in virtual memory systems. This is the reason why in paged system the pager process is usually run at a very high (dispatching) priority level.

FIRST IN FIRST OUT (FIFO) :

First In First Out (FIFO)

This is a Non-Premptive scheduling algorithm. FIFO strategy assigns priority to processes in the order in which they request the processor.The process that requests the CPU first is allocated the CPU first.When a process comes in, add its PCB to the tail of ready queue. When running process terminates, dequeue the process (PCB) at head of ready queue and run it.

Consider the example with P1=24, P2=3, P3=3

  Gantt Chart for FCFS :  0 - 24 P1 , 25 - 27 P2 , 28 - 30 P3

  Turnaround time for P1 = 24

  Turnaround time for P1 = 24 + 3

  Turnaround time for P1 = 24 + 3 + 3

  Average Turnaround time = (24*3 + 3*2 + 3*1) / 3

  In general we have (n*a + (n-1)*b + ....) / n

  If we want to minimize this, a should be the smallest, followed by b and

  so on.

Comments: While the FIFO algorithm is easy to implement, it ignores the service time request and all other criteria that may influence the performance with respect to turnaround or waiting time.
Problem: One Process can monopolize CPU
Solution: Limit the amount of time a process can run without a context switch. This time is called a time slice.

ROUND ROBIN SCHEDULING :

Round-robin job scheduling may not be desirable if the sizes of the jobs or tasks are highly variable. A process that produces large jobs would be favoured over other processes. This problem may be solved by time-sharing, i.e. by giving each job a time slot or quantum^[1] (its allowance of CPU time), and interrupt the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process.

Example: The time slot could be 100 milliseconds. If job1 takes a total time of 250ms to complete, the round-robin scheduler will suspend the job after 100ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100ms each), job1 will get another allocation of CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.

• Job1 = Total time to complete 250ms (quantum 100ms).

1. First allocation = 100ms.
2. Second allocation = 100ms.
3. Third allocation = 100ms but job1 self-terminates after 50ms.
4. Total CPU time of job1 = 250ms.

or one more method to avoid the failure is by dividing the process timing quanta according to their size and time taken such that the ratio becomes equal and all processes ends at same time.

[edit]

SHORTEST JOB FIRST (SJF) :

Maintain the Ready queue in order of increasing job lengths. When a job comes in, insert it in the ready queue based on its length. When current process is done, pick the one at the head of the queue and run it.
This is provably the most optimal in terms of turnaround/response time.
But, how do we find the length of a job?
Make an estimate based on the past behavior.

  Say the estimated time (burst) for a process is E0, suppose the actual 

  time is measured to be T0.

  Update the estimate by taking a weighted sum of these two

  ie. E1 = aT0 + (1-a)E0

  in general, E(n+1) = aTn + (1-a)En    (Exponential average)

  if a=0, recent history no weightage

  if a=1, past history no weightage.

  typically a=1/2.

               E(n+1) = aTn + (1-a)aTn-1  +  (1-a)^jatn-j + ...

  Older information has less weightage

Comments: SJF is proven optimal only when all jobs are available simultaneously.
Problem: SJF minimizes the average wait time because it services small processes before it services large ones. While it minimizes average wiat time, it may penalize processes with high service time requests. If the ready list is saturated, then processes with large service times tend to be left in the ready list while small processes receive service. In extreme case, where the system has little idle time, processes with large service times will never be served. This total starvation of large processes may be a serious liability of this algorithm.

Solution: Multi-Level Feedback Queques

SHORTEST REMINING TIME(SRT) :

Similar to Shortest­ Job­ First (SJF). With this strategy the scheduler arranges processes with the least estimated processing time remaining to be next in the queue. This requires advance knowledge or estimations about the time required for a process to complete.

• If a shorter process arrives during another process' execution, the currently running process may be interrupted (known as preemption), dividing that process into two separate computing blocks. This creates excess overhead through additional context switching. The scheduler must also place each incoming process into a specific place in the queue, creating additional overhead.
• This algorithm is designed for maximum throughput in most scenarios.
• Waiting time and response time increase as the process' computational requirements increase. Since turnaround time is based on waiting time plus processing time, longer processes are significantly affected by this. Overall waiting time is smaller than FIFO, however since no process has to wait for the termination of the longest process.
• No particular attention is given to deadlines, the programmer can only attempt to make processes with deadlines as short as possible.
• Starvation is possible, especially in a busy system with many small processes being run.

[edit]

PRIORITY BASED SCHEDULING :

Run highest-priority processes first, use round-robin among processes of equal priority. Re-insert process in run queue behind all processes of greater or equal priority.

• Allows CPU to be given preferentially to important processes.
• Scheduler adjusts dispatcher priorities to achieve the desired overall priorities for the processes, e.g. one process gets 90% of the CPU.

Comments: In priority scheduling, processes are allocated to the CPU on the basis of an externally assigned priority. The key to the performance of priority scheduling is in choosing priorities for the processes.
Problem: Priority scheduling may cause low-priority processes to starve

Solution: (AGING) This starvation can be compensated for if the priorities are internally computed. Suppose one parameter in the priority assignment function is the amount of time the process has been waiting. The longer a process waits, the higher its priority becomes. This strategy tends to eliminate the starvation problem.

MULTILEVEL QUEVE :

Several queues arranged in some priority order.
Each queue could have a different scheduling discipline/ time quantum.
Lower quanta for higher priorities generally.
Defined by:

• # of queues
• scheduling algo for each queue
• when to upgrade a priority
• when to demote

Attacks both efficiency and response time problems.

• Give newly runnable process a high priority and a very short time slice. If process uses up the time slice without blocking then decrease priority by 1 and double its next time slice.
• Often implemented by having a separate queue for each priority.

How are priorities raised? By 1 if it doesn't use time slice? What happens to a process that does a lot of computation when it starts, then waits for user input? Need to boost priority a lot, quickly.