W4118 Operating Systems Instructor: Junfeng YangOutline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues1Motivation No one-size-fits-all schedulerDifferent workloads Different environment Building a general scheduler that works well for all is difficult! Real scheduling algorithms are often more complex than the simple scheduling algorithms we’ve seenCombining scheduling algorithms Multilevel queue scheduling: ready queue is partitioned into multiple queues Each queue has its own scheduling algorithmForeground processes: RRBackground processes: FCFS Must choose scheduling algorithm to schedule between queues. Possible algorithmsRR between queuesFixed priority for each queueOutline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues4Multiprocessor scheduling issues Shared-memory Multiprocessor How to allocate processes to CPU?CPU0 CPU1 CPU2 CPU3processes5Symmetric multiprocessorArchitectureSmall number of CPUsSame access time to main memoryPrivate cacheCPU0 CPU1 CPU2 CPU3Shared Memory$ $ $ $6Global queue of processesOne ready queue shared across all CPUsAdvantagesGood CPU utilizationFair to all processesDisadvantagesNot scalable (contention for global queue lock)Poor cache localityLinux 2.4 uses global queueCPU0 CPU1 CPU2 CPU37Per-CPU queue of processesStatic partition of processes to CPUsAdvantagesEasy to implementScalable (no contention on ready queue)Better cache localityDisadvantagesLoad-imbalance (some CPUs have more processes)• Unfair to processes and lower CPU utilizationCPU0 CPU1 CPU2 CPU38Hybrid approachUse both global and per-CPU queuesBalance jobs across queuesProcessor AffinityAdd process to a CPU’s queue if recently run on the CPU• Cache state may still presentLinux 2.6 uses a very similar approachCPU0 CPU1 CPU2 CPU39SMP: “gang” schedulingMultiple processes need coordinationShould be scheduled simultaneouslyScheduler on each CPU does not act independentlyCoscheduling (gang scheduling): run a set of processes simultaneouslyGlobal context-switch across all CPUsCPU0 CPU1 CPU2 CPU310Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues11Real-time schedulingReal-time processes have timing constraintsExpressed as deadlines or rate requirementsE.g. gaming, video/music player, autopilot…Hard real-time systems –required to complete a critical task within a guaranteed amount of timeSoft real-time computing –requires that critical processes receive priority over less fortunate onesLinux supports soft real-time12Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues13Linux scheduling goalsAvoid starvationBoost interactivity Fast response to user despite high load Achieved by inferring interactive processes and dynamically increasing their prioritiesScale well with number of processes O(1) scheduling overheadSMP goals Scale well with number of processors Load balance: no CPU should be idle if there is work CPU affinity: no random bouncing of processesReference: Documentation/sched-design.txt14Algorithm overviewMultilevel Queue SchedulerEach queue associated with a priorityA process’s priority may be adjusted dynamicallyTwo classes of processesReal-time processes: always schedule highest priority processes• FCFS (SCHED_FIFO) or RR (SCHED_RR) for processes with same priorityNormal processes: priority with aging• RR for processes with same priority (SCHED_NORMAL)• Aging is implemented efficiently15Priority partition Total 140 priorities [0, 140) Smaller integer = higher priorityReal-time: [0,100)Normal: [100, 140) MAX_PRIO and MAX_RT_PRIOinclude/linux/sched.h16runqueue data structure kernel/sched.c struct prio_arrayArray of priority queues struct runqueueTwo arrays, active and expired17Scheduling algorithm1. Find highest priority non-empty queue in rq->active; if none, simulate aging by swapping active and expired2. next = first process on that queue3. Adjust next’s priority4. Context switch to next5. When next used up its time slice, insert nextto the right queue and call schedule againschedule() in kernel/sched.c1819Aging: the traditional algorithmfor(pp = proc; pp < proc+NPROC; pp++) {if (pp->prio != MAX)pp->prio++;if (pp->prio > curproc->prio)reschedule();}Problem: O(N). Every process is examined on each schedule() call!This code is taken almost verbatim from 6thEdition Unix, circa 1976.)Simulate aging Swapping active and expired gives low priority processes a chance to run Advantage: O(1)Processes are touched only when they start or stop running schedule() in kernel/sched.c20Find highest priority non-empty queue Use the bitmap field of struct runqueue140 queues 5 integers Time complexity: O(1)depends on the number of priority levels, not the number of processes Implementation: only a few compares to find the first that is non-zeroHardware instruction to find the first 1-bit• bsfl on Intel sched_find_first_bit() in include/asm-i386/bitops.h21Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues22Priority related fields in struct task_struct static_prio: static priority set by administrator/usersDefault: 120 (even for realtime processes)Set use sys_nice() or sys_setpriority()• Both call set_user_nice() prio: dynamic priorityIndex to prio_array rt_priority: real time priorityprio = 99 – rt_priority include/linux/sched.h23Adjusting priorityGoal: dynamically
View Full Document