Scheduling-2023-2

TASK SCHEDULING By Cristian Koliver Cristian.koliver@ufsc.br * Important aspect of multiprogramming. * Resources that are scheduled are processors and IO. SCHEDULING Goals are to achieve: * High processor utilization * High throughput (number of processes completed per unit time) * Low response time (time elapse from the submission of a request to the beginning of the response) SCHEDULING OS component that decides which process runs at a certain point in time * Non-preemptive * Preemptive SCHEDULER Types: * Long-term: which process to admit. * Medium-term: which process to swap in or out. * Short-term: which ready process to execute next. * I/O: the decision as to which process’s pending I/O request shall be handled by available I/O device SCHEDULER ready running destroyed blocked new blocked suspend short- term long-term medium- term medium- term long-term suspend ready medium- term Time-out ready Queue Release short-term scheduling processor medium-term scheduling Time-out ready Queue suspend ready queue Release short-term scheduling processor medium-term scheduling medium-term scheduling Time-out ready Queue suspend ready queue blocked queue event occurs event Wait Release short-term scheduling processor medium-term scheduling medium-term scheduling Time-out ready Queue suspend ready queue suspend blocked queue blocked queue event occurs event Wait Release short-term scheduling processor medium-term scheduling medium-term scheduling batch jobs Long-term scheduling Time-out interactive users ready Queue suspend ready queue suspend blocked queue blocked queue event occurs event Wait Release short-term scheduling processor First in, first out (FIFO), also known as first come, first served (FCFS), is the simplest scheduling algorithm. Simply queues processes in the order that they arrive in the ready queue. SCHEDULER * Switches only occur upon process termination -> scheduling overhead is minimal. * Throughput can be low. * No starvation. * Turnaround time, waiting time and response time depends on the order of their arrival and can be high for the same reasons above. SCHEDULER D C B A 20 0 12 35 40 FIFO Task Runtime A 12 B 8 C 15 D 5 D C B A 20 0 12 35 40 FIFO Task Runtime A 12 B 8 C 15 D 5 D C B A 20 0 12 35 40 FIFO Task Runtime A 12 B 8 C 15 D 5 D C B A 20 0 12 35 40 FIFO Task Runtime A 12 B 8 C 15 D 5 D C B A 20 0 12 35 40 FIFO Task Runtime A 12 B 8 C 15 D 5 Task Runtime Waiting time A 12 0 B 8 12 C 15 20 D 5 35 D C B A 20 0 12 35 40 FIFO Task Runtime Waiting time A 12 0 B 8 12 C 15 20 D 5 35 D C B A 20 0 12 35 40 FIFO average waiting time = 0 + 12 + 20 + 35 = 16,75 4 D C B A 20 0 28 40 5 Task Runtime D 5 C 15 B 8 A 12 FIFO D C B A 20 0 28 40 5 Task Runtime D 5 C 15 B 8 A 12 FIFO D C B A 20 0 28 40 5 Task Runtime D 5 C 15 B 8 A 12 FIFO D C B A 20 0 28 40 5 Task Runtime D 5 C 15 B 8 A 12 FIFO D C B A 20 0 28 40 5 Task Runtime D 5 C 15 B 8 A 12 FIFO D C B A 20 0 28 40 5 Task Runtime Waiting time D 5 0 C 15 5 B 8 20 A 12 28 FIFO D C B A 20 0 28 40 5 Task Runtime Waiting time D 5 0 C 15 5 B 8 20 A 12 28 FIFO average waiting time = 28 + 20 + 5 + 0 = 13,25 4 Shortest job next (SJN), also known as shortest job first (SJF) or shortest process next (SPN) selects for execution the waiting process with the smallest execution time. Shortest remaining time is a preemptive variant of SJF. SCHEDULER * Simple. * Minimizes the average amount of time each process has to wait until its execution is complete. * Potential for process starvation for processes which will require a long time to complete if short processes are continually added. SCHEDULER * The total execution time of a job must be known before execution. While it is impossible to predict execution time perfectly, several methods can be used to estimate it, such as a weighted average of previous execution times. SCHEDULER D C B A 5 0 13 25 40 SJF Task Runtime A 12 B 8 C 15 D 5 D C B A 5 0 13 25 40 SJF Task Runtime A 12 B 8 C 15 D 5 D C B A 5 0 13 25 40 SJF Task Runtime A 12 B 8 C 15 D 5 D C B A 5 0 13 25 40 SJF Task Runtime A 12 B 8 C 15 D 5 D C B A 5 0 13 25 40 SJF Task Runtime A 12 B 8 C 15 D 5 D C B A 5 0 25 40 SJF Task Runtime Waiting time A 12 13 B 8 5 C 15 25 D 5 0 D C B A 5 0 13 25 40 SJF Task Runtime Waiting time A 12 13 B 8 5 C 15 25 D 5 0 average waiting time = 13 + 5 + 25 + 0 = 10,75 4 In fixed priority, OS assigns a fixed priority rank to every process, and the scheduler arranges the processes in the ready queue in order of their priority. SCHEDULER * Lower-priority tasks get interrupted by incoming higher-priority tasks. * No particular advantage in terms of throughput over FIFO scheduling. SCHEDULER D C B A 20 0 28 40 5 Task Runtime Priority A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority Waiting time A 12 3 (lower) B 8 2 C 15 1 D 5 0 (higher) PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority Waiting time A 12 3 (lower) 28 B 8 2 20 C 15 1 5 D 5 0 (higher) 0 PRIORITY D C B A 20 0 28 40 5 Task Runtime Priority Waiting time A 12 3 (lower) 28 B 8 2 20 C 15 1 5 D 5 0 (higher) 0 PRIORITY average waiting time = 28 + 20 + 5 + 0 = 13,25 4 In round-robin (RR), OSassigns a fixed time unit per process (quantum or time-slice), and cycles through them. If process completes within that time-slice it gets terminated otherwise it is rescheduled after giving a chance to all other processes. SCHEDULER * Involves extensive overhead, especially with a small time unit. * Good average response time, waiting time is dependent on number of processes, and not average process length. * Starvation can never occur.. SCHEDULER D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR A D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime A 12 B 8 C 15 D 5 RR D C B A 20 0 28 36 40 Task Runtime Waiting time A 12 24 B 8 20 C 15 25 D 5 15 RR D C B A 20 0 28 36 40 Task Runtime Waiting time A 12 24 B 8 20 C 15 25 D 5 15 RR average waiting time = 24 + 20 + 25 + 15 = 21 4 Tries to improve response times of interactive users, while ensuring that low-priority, background jobs do not starve. Priority-based: * User-processes (50-127) are preempted; * Kernel-processes (0-49) are strictly non- preempted; UNIX 32 ready queues: doubly linked list of Process Control Blocks (PCB) for runnable processes. UNIX 16 : 19 12 : 15 4 : 7 8 : 11 0 : 3 20 : 23 24 : 27 28 : 31 Process Control Block (PCB) fields: p_pri: Current scheduling priority p_usrpri: User mode priority p_cpu: Measure of recent CPU usage p_nice: User-controllable nice factor Kernel: Sleeping priority UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity decay = (2*load_average)/(2*load_average+1) UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity decay = (2*load_average)/(2*load_average+1) UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity decay = (2*load_average)/(2*load_average+1) p_cpu = p_cpu* decay UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity decay = (2*load_average)/(2*load_average+1) p_cpu = p_cpu* decay p_usrpri = PUSER + (p_cpu/4) +(2*p_nice) UNIX User-processes priority depends on two factors: nice: 0-39 CPU usage Time-sharing: equal opportunity decay = (2*load_average)/(2*load_average+1) p_cpu = p_cpu* decay p_usrpri = PUSER + (p_cpu/4) +(2*p_nice) UNIX P_usrpri= 110 P_cpu = 80 Nice = 20 ooo P_usrpri= 120 P_cpu = 80 Nice=25 ooo time 1 t1 t0 P_usrpri= 110 P_cpu = 80 Nice = 20 ooo P_usrpri= 120 P_cpu = 80 Nice=25 ooo time 1 P_usrpri= 115 P_cpu = 100 Nice = 20 ooo P_usrpri= 110 P_cpu = 40 Nice = 25 ooo time 2 t1 t0 t1 t0 decay = 1/2 P_usrpri= 110 P_cpu = 80 Nice = 20 ooo P_usrpri= 120 P_cpu = 80 Nice=25 ooo time 1 P_usrpri= 115 P_cpu = 100 Nice = 20 ooo P_usrpri= 110 P_cpu = 40 Nice = 25 ooo time 2 P_usrpri= 102 P_cpu = 50 Nice = 20 ooo P_usrpri= 115 P_cpu = 60 Nice = 25 ooo time 3 t1 t0 t1 t0 t1 t0 decay = 1/2 Run Queue Manipulation: roundrobin(): for the processes with the same priority. schedcpu(): recomputes the priority once per second * removes the process from the run queue; * recomputes the priority; * puts it back. UNIX thanks! Any questions? You can find me at Cristian.koliver@ufsc.br