Process Part3.pdf

Processes - Part III Amir H. Payberah [email protected] Sep. 20, 2023 CPU Scheduling 1 / 45 CPU Scheduling I CPU scheduling is the basis of multiprogrammed OSs. I By switching the CPU among processes, the OS makes the computer more productive. 2 / 45 Basic Concepts I In a single-processo...

Processes - Part III Amir H. Payberah [email protected] Sep. 20, 2023 CPU Scheduling 1 / 45 CPU Scheduling I CPU scheduling is the basis of multiprogrammed OSs. I By switching the CPU among processes, the OS makes the computer more productive. 2 / 45 Basic Concepts I In a single-processor system, only one process can run at a time. I Others must wait until the CPU is free and can be rescheduled. I The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization. 3 / 45 Basic Concepts I CPU-I/O burst cycle: process execution consists of a cycle of CPU execution and I/O wait. I CPU burst followed by I/O burst. I CPU burst distribution is of main concern. 4 / 45 CPU Scheduler I CPU scheduler selects from among the processes in ready queue, and allocates the CPU to one of them. I CPU scheduling decisions may take place when a process: 1. 2. 3. 4. Terminates. Switches from running to waiting (e.g., an I/O request). Switches from running to ready (e.g., interrupt). Switches from waiting to ready (e.g., I/O completion). I For situations 1 and 2, there is no scheduling choice, as a new process must be selected for execution (non-preemptive). I But, There is a choice, for situations 3 and 4 (preemptive). 5 / 45 Scheduling Criteria I Different CPU-scheduling algorithms have different properties. I CPU utilization: keep the CPU as busy as possible (Max). I Throughput: # of completed processes per time unit (Max). I Turnaround time: amount of time to execute a particular process (Min). I Waiting time: amount of time a process has been waiting in the ready queue (Min). I Response time: amount of time it takes from when a request was submitted until the first response is produced (Min). 6 / 45 Scheduling Algorithms 7 / 45 Scheduling Algorithms I First-Come, First-Served Scheduling I Shortest-Job-First Scheduling I Priority Scheduling I Round-Robin Scheduling 8 / 45 First-Come, First-Served (FCFS) Scheduling 9 / 45 FCFS Scheduling (1/2) I Suppose that the processes arrive in the order: P1 , P2 , P3 I Waiting time for P1 = 0; P2 = 24; P3 = 27 I Average waiting time: I FCFS scheduling is non-preemptive: process keeps the CPU until it releases the CPU (either by terminating or by requesting I/O). I Convoy effect: all the other processes wait for the one big process to get off the CPU. 0+24+27 3 = 17 10 / 45 FCFS Scheduling (2/2) I Suppose that the processes arrive in the order: P2 , P3 , P1 I Waiting time for P1 = 6; P2 = 0; P3 = 3 I Average waiting time: I Much better than previous case. 6+0+3 3 =3 11 / 45 Shortest-Job-First (SJF) Scheduling 12 / 45 SJF Scheduling (1/2) I Associate with each process the length of its next CPU burst. I Use these lengths to schedule the process with the shortest time. I SJF is optimal: gives minimum average waiting time for a given set of processes. I The difficulty is knowing the length of the next CPU request. 13 / 45 SJF Scheduling (2/2) I Select the processes according to their burst time (from shorter to longer). I Waiting time for P1 = 3; P2 = 16; P3 = 9, P4 = 0 I Average waiting time: 3+16+9+0 4 =7 14 / 45 Determining Length of Next CPU Burst I Estimate the length, and pick process with shortest predicted next CPU burst. I The next CPU burst 1. tn = actual length of nth CPU burst 2. τn+1 = predeicted value for the next CPU burst 3. τn+1 = αtn + (1 − α)τn , where 0 ≤ α ≤ 1 I α = 0 then τn+1 = τ I α = 1 then τn+1 = tn I Commonly, α set to 1 2 15 / 45 Preemptive SJF I The SJF algorithm can be either preemptive or non-preemptive. I Preemptive version called shortest-remaining-time-first 16 / 45 Example of Shortest-Remaining-Time-First I Now we add the concepts of varying arrival times and preemption to the analysis. I Average waiting time: (10−1)+(1−1)+(17−2)+(5−3) 4 = 26 4 = 6.5 17 / 45 Priority Scheduling 18 / 45 Priority Scheduling (1/2) I A priority number (integer) is associated with each process. I The CPU is allocated to the process with the highest priority. • • Smallest integer = Highest priority Preemptive and non-preemptive I SJF is priority scheduling where priority is the inverse of predicted next CPU burst time. I Problem: starvation - low priority processes may never execute I Solution: aging - as time progresses increase the priority of the process 19 / 45 Priority Scheduling (2/2) I Average waiting time: 0+1+6+16+18 5 = 8.2 20 / 45 Round-Robin (RR) Scheduling 21 / 45 RR Scheduling (1/2) I Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. I After this time has elapsed, the process is preempted and added to the end of the ready queue. I 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 in chunks of at most q time units at once. I No process waits more than (n − 1)q time units. 22 / 45 RR Scheduling (2/2) I Time quantum q = 4 I Average waiting time: (10−4)+4+7 3 = 5.66 23 / 45 Time Quantum and Context Switch Time (1/2) I Timer interrupts every quantum to schedule next process. I Performance • • q large ⇒ FIFO q small ⇒ q must be large with respect to context switch, otherwise overhead is too high. 24 / 45 Time Quantum and Context Switch Time (2/2) I q should be large compared to context switch time. 25 / 45 26 / 45 Linux Scheduling (1/2) I Completely Fair Scheduler (CFS) I n users want to share a resource, e.g., CPU. CPU • I 1 n of the shared resource. Generalized by max-min fairness. • • I Solution: allocate each Handles if a user wants less than its fair share. E.g., user 1 wants no more than 20%. Generalized by weighted max-min fairness. • • Give weights to users according to importance. E.g., user 1 gets weight 1, user 2 weight 2. 27 / 45 Linux Scheduling (2/2) I Quantum calculated based on nice value from -20 to +19. 28 / 45 Modifying the Nice Value I nice() increments a process’s nice value by inc and returns the newly updated value. I Only processes owned by root may provide a negative value for inc. #include <unistd.h> int nice(int inc); 29 / 45 Retrieving and Modifying Priorities I The getpriority() and setpriority() system calls allow a process to retrieve and change its own nice value or that of another process. #include <sys/resource.h> int getpriority(int which, id_t who); int setpriority(int which, id_t who, int prio); 30 / 45 Thread Scheduling 31 / 45 Thread Scheduling (1/2) I Distinction between user-level and kernel-level threads. I Process-Contention Scope (PCS) • • I In many-to-one and many-to-many models. Scheduling competition is within the process. System-Contention Scope (SCS) • • In one-to-one model. Scheduling competition among all threads in system. 32 / 45 33 / 45 Pthread Scheduling I API allows specifying either PCS or SCS during thread creation. • • I PTHREAD SCOPE PROCESS schedules threads using PCS scheduling. PTHREAD SCOPE SYSTEM schedules threads using SCS scheduling. pthread attr setscope and pthread attr getscope set/get contention scope attribute in thread attributes object. #include <pthread.h> int pthread_attr_setscope(pthread_attr_t *attr, int scope); int pthread_attr_getscope(const pthread_attr_t *attr, int *scope); 34 / 45 Pthread Scheduling API int main(int argc, char *argv[]) { pthread_t t1, t2; pthread_attr_t attr; pthread_attr_init(&attr); pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); pthread_create(&t1, &attr, thread_func, NULL); pthread_create(&t2, &attr, thread_func, NULL); pthread_join(t1, NULL); pthread_join(t2, NULL); } void *thread_func(void *param) { /* do some work ... */ pthread_exit(0); } 35 / 45 Multi-Processor Scheduling 36 / 45 Multiple-Processor Scheduling I Asymmetric multiprocessing • • I Only one processor does all scheduling decisions, I/O processing, and other system activities. The other processors execute only user code. Symmetric multiprocessing (SMP) • • Each processor is self-scheduling All processes in common ready queue, or each has its own private queue of ready processes. 37 / 45 Processor Affinity I Processor affinity: keep a process running on the same processor. I Soft affinity: the OS attempts to keep a process on a single processor, but it is possible for a process to migrate between processors. I Hard affinity: allowing a process to specify a subset of processors on which it may run. 38 / 45 39 / 45 CPU Affinity I sched setaffinity() and sched getaffinity() sets/gets the CPU affinity of the process specified by pid. #define _GNU_SOURCE #include <sched.h> int sched_setaffinity(pid_t pid, size_t len, cpu_set_t *set); int sched_getaffinity(pid_t pid, size_t len, cpu_set_t *set); 40 / 45 CPU Affinity Macros I CPU ZERO() initializes set to be empty. I CPU SET() adds the CPU cpu to set. I CPU CLR() removes the CPU cpu from set. I CPU ISSET() returns true if the CPU cpu is a member of set. #define _GNU_SOURCE #include <sched.h> void CPU_ZERO(cpu_set_t *set); void CPU_SET(int cpu, cpu_set_t *set); void CPU_CLR(int cpu, cpu_set_t *set); int CPU_ISSET(int cpu, cpu_set_t *set); 41 / 45 CPU Affinity Macros I The process identified by pid runs on any CPU other than the first CPU of a four-processor system. cpu_set_t set; CPU_ZERO(&set); CPU_SET(1, &set); CPU_SET(2, &set); CPU_SET(3, &set); sched_setaffinity(pid, sizeof(set), &set); 42 / 45 Summary 43 / 45 Summary I CPU scheduling I Scheduling criteria: cpu utilization, throughput, turnaround time, waiting time, response time I Scheduling algorithms: FCFS, SJF, Priority, RR I Thread scheduling: PCS and SCS I Multi-processor scheduling: SMP, processor affinity 44 / 45 Questions? Acknowledgements Some slides were derived from Avi Silberschatz slides. 45 / 45