HOME

Top 10 List of Week 08

1. CPU Scheduling
   Almost all programs have some alternating cycle of CPU number crunching and waiting for I/O of some kind. ( Even a simple fetch from memory takes a long time relative to CPU speeds. ) A scheduling system allows one process to use the CPU while another is waiting for I/O, thereby making full use of otherwise lost CPU cycles.

2. CPU-I/O Burst Cycle
   Almost all processes alternate between two states in a continuing cycle. A CPU burst of performing calculations, and An I/O burst, waiting for data transfer in or out of the system. The Quora thread above simply put the explanation.

3. First Come First Serve
   Simplest scheduling algorithm that schedules according to arrival times of processes. First come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first. It is implemented by using the FIFO queue.

4. Comparison between scheduling algorithms
   FCFS can cause long waiting times, especially when the first job takes too much CPU time. Both SJF and Shortest Remaining time first algorithms may cause starvation. Consider a situation when the long process is there in the ready queue and shorter processes keep coming. If time quantum for Round Robin scheduling is very large, then it behaves same as FCFS scheduling.

5. Preemptive Scheduling
   Preemptive scheduling is used when a process switches from running state to ready state or from waiting state to ready state. More on this available on geeks on geeks link attached above. Algorithms based on preemptive scheduling are: Round Robin ,Shortest Remaining Time First, Priority .

6. Non-preemptive Scheduling
   Non-preemptive Scheduling is used when a process terminates, or a process switches from running to waiting state. Geeks for geeks visualization above helps me to grasp the concept. Algorithms based on non-preemptive scheduling are: Shortest Job First and Priority

7. Evaluation of Process Scheduling Algorithm
   To do this we need to decide on the relative importance of the factors we listed above (Fairness, Efficiency, Response Times, Turnaround and Throughput). The web I referred above lists down 4 methods including Deterministic Modeling, Queuing Models, Simulations, Implementation. Check out the link for details.

8. Convoy Effect
   is phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to few slow processes. FCFS algorithm is non-preemptive in nature, that is, once CPU time has been allocated to a process, other processes can get CPU time only after the current process has finished. This property of FCFS scheduling leads to the situation called Convoy Effect.

9. Lottery Process Scheduling
   Lottery Scheduling is type of process scheduling, somewhat different from other Scheduling. Processes are scheduled in a random manner. In this scheduling every process have some tickets and scheduler picks a random ticket and process having that ticket is the winner and it is executed for a time slice and then another ticket is picked by the scheduler.

10. Linux Scheduling
    Prior to version 2.5, Linux used a traditional UNIX scheduling algorithm. Version 2.6 used an algorithm known as O(1), that ran in constant time regardless of the number of tasks, and provided better support for SMP systems. However it yielded poor interactive performance. Starting in 2.6.23, the Completely Fair Scheduler, CFS, became the standard Linux scheduling system.