Scheduling

• The list of processes running on the system are referred to as the workload.
• A scheduling metric is a way of measuring the performance of a scheduler. There are two main types of scheduling metrics:

  1. Turnaround time
  2. Jain's Fairness Index
• A FIFO scheduling algorithm processes the first item that arrives in its entirety before processing the next. The first process that arrives is the first one that finishes.
• FIFO is a horrible scheduling algorithm due to the convoy effect. If a large time consuming process is scheduled in front of less time consuming process, the turnaround time of the latter processes is unnecessarily excessive.
• The SJF scheduling algorithm processes the job that takes the least amount of time first assuming jobs arrive at the same time.
• The SJF scheduling fails when shorter processes arrive slightly late, which still leads to a convoy effect.
• A context switch is when the currently running process is stopped and another process is started.
• A scheduler is known as preemptive if it is willing to yield the runtime of a currently running process to another process. In other words, preemptive schedulers allow for context switches.
• Round Robin scheduling is a form of non-preemptive scheduling where all processes are given equal amounts of time on the processor. It is also called time slicing.
• The stages of a process are

  1. Creation
  2. Ready
  3. Running
  4. Blocked
  5. Termination
• After creation, the process enters the Ready to Run Queue. These are programs that have already been compiled and linked, but have not yet been run.
• The processes in the Ready to Run Queue are dispatched to the CPU to run.
• Steps of process creation

  1. Allocate memory
  2. Read the executable object file
  3. Assign a process identification index (PID)
  4. Call main
  5. After the process finishes, call exit to deallocate memory.
• When a process exits, it can exit as normal, without any errors, or abnormal, with an error such as a segmentation fault.
• There are three ways the process enters the ready to run queue.

  1. The process is created
  2. The process yields the CPU, but hasn't finished all its instructions (context switch)
  3. Process exits the blocked queue.
• The dispatch handler is an operating system function that executes the scheduling algorithm.
• The dispatch handler performs a CPU context switch by saving the CPU state of the yielding process (the state of the registers and the current instruction). Then, it loads the CPU context of the scheduled process.
• There are three ways that a running process can yield the CPU.

  1. The process terminates.
  2. An exception is raised. Dispatch handler adds process to blocked queue.
  3. Preemptive scheduling
• Preemptive scheduling is when the dispatch handler sets a timer on a CPU to interrupt it after some time. This places an upper bound on how long the process can run on CPU.
• When the process yields the CPU due to an asynchronous exception, it will transition to the blocked queue and wait for the exception to complete.
• The process control block is an additional section of memory allocated at runtime alongside the stack, the heap, the read only memory, and read write memory. The process control block contains the CPU context and the process management information.
• The CPU context contains information about the general purpose registers, the program counter registers, and the ALU condition (carry, overflow, etc.)
• The process management information includes the process ID, priority level, state, parent process ID, and other useful data.
• The process management and CPU context are accessibly only in kernel mode.
• The Ready to run queue is the data structure that stores the processes combined with the scheduling algorithm.
• The context switch is performed by the dispatch handler. It is a kernel mode process. In kernel mode, the dispatch handler updates the process control block (saving the CPU context), updates the yielding processes status, and gives the CPU a new process to run.
• In non-preemptive scheduling, when a process completes execution, the operating system must wait until all child processes have completed their executions before returning control to the user.
• Non-preemptive schedulers do not allow interruption unless the current process voluntarily yields the processor using a system call.
• A preemptive scheduler can interrupt any running process and give it back to the ready queue if its time slice has expired or another higher priority process becomes available.
• Time slicing involves dividing the processor's available time into equal intervals called time quanta or time slices.
• A preemptive scheduler can be implemented using either time slicing or round robin scheduling.
• The dispatch handler is a function call, so it needs its own kernel stack. Thus, each kernel associated with every process has its own kernel stack.
• A context switch happens only if a process enters the running state, or a process exits the running state.