Job Scheduling

1. Objective

• maximum CPU utilization obtained with multiprogramming
• CPU-I/O Burst Cycle- Process execution consist of a cycle of CPU execution and I/O wait

2. CPU Scheduler

• Selects from among the processes in ready queue, and allocates the CPU to one of them
• queues may be ordered in various ways
• CPU scheduling decisions may take place when a process
• switches from running to waiting sate
• switches from running to ready state
• switches from waiting to ready state
• terminate
• scheduling under 1 and 4 is non-preemptive
• all other scheduling is preemptive
• consider access to shared data
• consider preemption while in kernel mode
• consider interrupts occurring during crucial OS activicites

3. Dispatcher

• Dispacher module gives control of the CPU to the process selected by the short-term scheduler; this involves
• switching context
• switching to user mode
• jumping to the proper location in the user program to restart that program
• Dispatch latency
• time it takes for the dispatcher to stop one process and start another running

4. Scheduling Criteria

• CPU utilization
• keep the CPU as busy as possible
• Throughput 
• # of processes that complete their execution per time unit
• Turnaround time
• amount of time to execute a particular process
• Waiting time
• amount of time a process has been waiting in the ready queue

5. First-Come. First-Server (FCFS) Scheduling

6. Shortest-Job-First (SJF) Scheduling

• associate with each process the length of its next CPU burst
• use these lengths to schedule the process with the shortest time
• SJF is optimal
• gives minimum average waiting time for a given set of processes
• the difficult is knowing the length of the next CPU request

7. Determine the length of next CPU burst

• can only estimate the length
• should be similar to the previous one
• then pick process with shortest predicted next CPU burst
• can be done by using the length of previous CPU bursts, using exponential averaging
• $t_n$ = average length of the n-th CPU burst
• $\tau_{n+1}$ = predicted value of the next CPU burst
• $\alpha, 0 \leq \alpha \leq (1-\alpha) \tau_n$
• commonly, $\alpha$ set to 1/2
• preemptive version called shortest-remaining-time-first

8. Example of Exponential Averaging

• $\alpha = 0$
• \tau_{n+1} = \tau_n
• recent history does not count
• $\alpha = 1$
• $\tau_{n+1} = n \tau_n$
• only the actual last CPU burst counts
• If we expand the formula, we get
• $\tau_{n+1} = \alpha \tau_n + (1-\alpha) \tau_{n-1} + ...$
•                     $= (1-\alpha)^j \alpha \tau_{n-j} + ... $
•                     $= (1-\alpha)^{n+1} \tau_0$
• since both $\alpha$ and $1-\alpha$ are less than or equal to 1, each successive term has less weight than its predecessor

9. Example of Shortest Remaining-time-first

10. Priority Scheduling

• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority (smaller integer = highest priority)
• preemptive
• non-preemptive
• SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
• Problem = starvation 
• low priority processes may never execute
• Solution = aging
• as time progresses, increase the priority of the process

11. Round Robin

• Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds.
• after this time has elapsed, the process is preempted and added to the end of the ready queue
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time is chunks of at most q time units at once. 
• No process waits more than (n-1)q time units.
• Time interrupts every quantum to schedule next process
• Performance
• q large : FIFO
• q small: q must be large with respect to context switch, otherwise, overhead is too high
• Example of Round robin with time Quantum =4 

12. Multilevel Queue

• Ready queue is partitioned into separate queues, e..g,
• forground (iterative)
• background (batch)
• Process permanently in a given queue
• Each queue has its own scheduling algorithm
• forground-RR
• background-FCFR
• Scheduling must be done between the queues
• fixed priority scheduling: i.e., serve all from foreground then from background
• possibility starvation
• time slices: each queue gets a certain amount of CPU time which it can schedule amongst its processes, i.e., 80% to foreground in RR
• 20% to background in FCFS

13. Multi-level feedback queue

• a process can move between the various queues;
• aging can be implemented this way
• multi-level-feedback-queue scheduler defined by the following parameters
• number of queues
• scheduling algorithms for each queue
• method used to determine when to upgrade a process
• method used to determine when to demote a process
• method used to determine which queue a process will enter when that process needs service
• Example of multilevel feedback queue
• three queues
• $Q_0$: time quantum 8 milliseconds
• $Q_1$: time quantum 16 milliseconds
• $Q_2$; FCFS
• scheduling
• a new job enters queue $Q_0$ which is served FCFS
• when it gains CPU, job received 8 milliseconds
• if it does not finish in 8 milliseconds, job is moved to queue $Q_1$
• at $Q_1$ job is again served FCFS and receives 16 additional milliseconds
• if it still does not complete, it is preempted and moved to queue $Q_2$

14. Thread Scheduling

• Distinction between user-level and kernel-level threads
• when threads supported, threads scheduled, not processes
• many-to-one and many-to-many methods, thread library schedules user-level threads to run on LWP
• known as process-contention scope (PCS) since scheduling competition is within the process
• typically thread scheduled onto available CPU is system contention scope (SCS)
• competition among all threads in the system

15. Multi-Processor Scheduling

• CPU scheduling more complex when multiple CPUs are available
• Homogeneous processors within a multiprocessor
• Asymetric multiprocessing
• only one processor accesses the system data structures, alleviating the need for data sharing
• Symmetric multiprocessing (SMP)
• each processor is self-scheduling, all processes in common ready queue
• or each has its own private queue of ready processes
• Processor Affinity
• process has affinity for processor on which it is currently running
• soft affinity
• hard affinity
• variation including processor sets

16. Multiplecore Processor

• recent trend to place multiple processor cores on the same physical chip
• faster and consumes lees power 
• multiple threads per core also growing
• takes advantage of memory stall to make progress on another thread while memory retrieve happens