DOC PREVIEW
Columbia COMS W4118 - Sched Linux

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

W4118 Operating Systems Instructor: Junfeng YangOutline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues1Motivation No one-size-fits-all schedulerDifferent 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 algorithmForeground processes: RRBackground processes: FCFS Must choose scheduling algorithm to schedule between queues. Possible algorithmsRR between queuesFixed priority for each queueOutline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues4Multiprocessor scheduling issues Shared-memory Multiprocessor How to allocate processes to CPU?CPU0 CPU1 CPU2 CPU3processes5Symmetric multiprocessorArchitectureSmall number of CPUsSame access time to main memoryPrivate cacheCPU0 CPU1 CPU2 CPU3Shared Memory$ $ $ $6Global queue of processesOne ready queue shared across all CPUsAdvantagesGood CPU utilizationFair to all processesDisadvantagesNot scalable (contention for global queue lock)Poor cache localityLinux 2.4 uses global queueCPU0 CPU1 CPU2 CPU37Per-CPU queue of processesStatic partition of processes to CPUsAdvantagesEasy to implementScalable (no contention on ready queue)Better cache localityDisadvantagesLoad-imbalance (some CPUs have more processes)• Unfair to processes and lower CPU utilizationCPU0 CPU1 CPU2 CPU38Hybrid approachUse both global and per-CPU queuesBalance jobs across queuesProcessor AffinityAdd process to a CPU’s queue if recently run on the CPU• Cache state may still presentLinux 2.6 uses a very similar approachCPU0 CPU1 CPU2 CPU39SMP: “gang” schedulingMultiple processes need coordinationShould be scheduled simultaneouslyScheduler on each CPU does not act independentlyCoscheduling (gang scheduling): run a set of processes simultaneouslyGlobal context-switch across all CPUsCPU0 CPU1 CPU2 CPU310Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues11Real-time schedulingReal-time processes have timing constraintsExpressed as deadlines or rate requirementsE.g. gaming, video/music player, autopilot…Hard real-time systems –required to complete a critical task within a guaranteed amount of timeSoft real-time computing –requires that critical processes receive priority over less fortunate onesLinux supports soft real-time12Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues13Linux scheduling goalsAvoid starvationBoost interactivity Fast response to user despite high load Achieved by inferring interactive processes and dynamically increasing their prioritiesScale well with number of processes O(1) scheduling overheadSMP goals Scale well with number of processors Load balance: no CPU should be idle if there is work CPU affinity: no random bouncing of processesReference: Documentation/sched-design.txt14Algorithm overviewMultilevel Queue SchedulerEach queue associated with a priorityA process’s priority may be adjusted dynamicallyTwo classes of processesReal-time processes: always schedule highest priority processes• FCFS (SCHED_FIFO) or RR (SCHED_RR) for processes with same priorityNormal 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 priorityReal-time: [0,100)Normal: [100, 140) MAX_PRIO and MAX_RT_PRIOinclude/linux/sched.h16runqueue data structure kernel/sched.c struct prio_arrayArray of priority queues struct runqueueTwo 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 runqueue140 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-zeroHardware instruction to find the first 1-bit• bsfl on Intel sched_find_first_bit() in include/asm-i386/bitops.h21Outline Advanced scheduling issuesMultilevel queue schedulingMultiprocessor scheduling issuesReal-time scheduling Scheduling in LinuxScheduling algorithmSetting priorities and time slicesOther implementation issues22Priority related fields in struct task_struct static_prio: static priority set by administrator/usersDefault: 120 (even for realtime processes)Set use sys_nice() or sys_setpriority()• Both call set_user_nice() prio: dynamic priorityIndex to prio_array rt_priority: real time priorityprio = 99 – rt_priority include/linux/sched.h23Adjusting priorityGoal: dynamically


View Full Document

Columbia COMS W4118 - Sched Linux

Download Sched Linux
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sched Linux and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sched Linux 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?