Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
Tram Anh Ton Nu
verified elite notetaker
verified elite notetaker
FLGR 1010 - 005
verified elite notetaker
Popular in Computer Information Technology
This 43 page Class Notes was uploaded by Haylie Satterfield on Saturday September 19, 2015. The Class Notes belongs to CISC361 at University of Delaware taught by Staff in Fall. Since its upload, it has received 44 views. For similar materials see /class/207178/cisc361-university-of-delaware in Computer Information Technology at University of Delaware.
Reviews for OperatingSystems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
Processes A process is a running program The cpu can be used by one process while another is waiting on lO Multiprogramming can switch from one program to another interleave them To user seems like more than one program running at a time on a single cpu V th a multiprocessor can run more than one at a time Processes A process is an executing program with values for program counter registers and variables Also owns resources Example 3 processes A B C Processes Must have a scheduling algorithm to decide when to stop a running process and how to pick another one to run Processes have different states New Running Ready Blocked wait Process Switching During a process switch the state of the current process must be saved Then the new process can be given time on the cpu context switch The process that was taken off the cpu can be loaded back on some time later Must save program counter contents of registers etc to do so Takes some amount of time Processes 08 Must have a way to create and terminate processes Start off with initial process init pid 1 Then create more processes to form a tree How to create a process allocate resources create process table entry fork2 ps command pid parent pid Processes Processes have three sections Stacquot l Text section code can be shared T between Data processes Text Memory Process Hierarchy SVR4 Use ps and ptree commands Process Termination Normal voluntary exit Error voluntary exit involuntary fatal error killed by another process free up resources remove process table entry How many processes can a system support Process Table Array of structures about active processes process state program counter stack pointer memory allocation open files other stuff Interrupt handling suspend current process save registers etc run handler then process scheduler Chapter Process Thread and Schedulan Scheduler Class and Priority XJANG Yong xyon g sing huaedu cn openSOLanS Outline El Scheduling Class and Priority El Dispatch Queues amp Dispatch Tables El Thread Priorities amp Scheduling El Turnstiles amp Priority Inheritance Scheduling Class and Priority ElSolaris supports multiple scheduling classes gt Allows for the coexistence of different priority schemes andscheduling algorithms policies within the kernel gt Each scheduling class provides a classspecific function to manage thread priorities administration creation termination etc El The dispatcher is the kernel subsystem gt Manages the dispatch queues run queues handles thread selection context switching preemption etc openSOLanS Scheduling Classes IITraditionaI Timeshare TS class gt attempt to give every thread a fair shot at execution time El Interactive IA class gt Desktop only gt Boost priority of active current focus window gt Same dispatch table as TS El System SYS gt Only available to the kernel for OS kernel threads I Realtime RT gt Highest priority scheduling class gt Will preempt kernel SYS class threads gt Intended for realtime applications Scheduling Classes Con d EIFair Share Scheduler FSS Class gt Same priority range as TSIA class gt CPU resources are divided into shares gt Shares are allocated projectstasks by administrator gt Scheduling decisions made based on shares allocated and used not dynamic priority changes EIFixed Priority FX Class gt The kernel will not change the threads priority gt A batch scheduling class P o es global priorities 15 E 3 3 50 E user priority 3 my 60 TS System x xg 333 3 Timeshare TS 450 Interactive 1A 139 60 39 Fair Share F SS r 7 user pnan IA i nd 11 E p o ty S range quotquotquot 39 r u Irange openSOLans Scheduling Class Structures EIThe kernel maintains an array of sclass structures for each loaded scheduling class ElThread pointer to the class functions array and perthread classspecific data structure EIScheduling class operations vectors and CLXXX macros allow a single central dispatcher to invoke schedulingclass specific functions System Clan Arm t clfunts cldata cltlata 5 ts tscpupri ts up l39ilim ts nice openSOLanS Scheduling Class Specific Functions Ulmplemented via macros El define CLENTERCLASSt cid clparmsp credp bufp El sclasscid c1funcs gtthreadclenterclass t cid El void clparmsp credp bufp EICIass management and priority manipulation functions gt xxadmin xxgetclinfo xxparmsin xxparmsout xxgetclpri xxenterclass xxexitclass xxpreempt xxsleep xxtick xxtrapret xxfork xxparmsget set xxdonice xxyield xxwakeup Outline El Scheduling Class and Priority El Dispatch Queues amp Dispatch Tables El Thread Priorities amp Scheduling El Turnstiles amp Priority Inheritance Dispatcher III The kernel subsystem that mana es the dispatch queues run ueues handles reemption finging the next runnable thread t e idle loop initia ng context switching etc El Solaris implements perprocessor dispatch queues actually a queue of queues El Several dispatcherrelated variables maintained in the CPU structure as well gt cpurunrun preemption flag do it soon cpukprunrun kernel preemption ag do it now cpudisp dispatcher data and root of queues cpuchosenlevel priority of next selected thread cpudispthread kthread pointer III A systemwide or perprocessor set queue exists for realtime threads VVV V openSOLans Dispatch Queues EIPerCPU run queues gt Actually a queue of queues ElOrdered by thread priority ElQueue occupation represented via a bitmap EIFor Realtime threads a systemwide kernel preempt queue is maintained gt Realtime threads are placed on this queue not the perCPU queues gt If processor sets are configured a kernel preempt queue exists for each processor set PerCPU Dispatch Queues cpu structures cpu t cpurum39u39nx cpukprunruii cpudispthread T T cpudisp cpukprunrun cpudispthrea l T T cpudisp cpurunrun cpukprunrun cpudispthread T T lisp t 115th kthread t kernel kernel d is gt SgspAlntk dq Ehls Head s n n EMS in llLruncut dispiqnmm p lthirn 4 dis maxrunpn Ill 135 thread dispnnlnnahle chruncnt A queue for cvcy global priority lqfirst n rIlLlnst dqruncnt 1q rst i rIrLla st rlqruncut kernel kernel kernel I Dispatch Tables ElPer scheduling class parameter tables EITime quantums and priorities Eltuneable via dispadmin1 M TS Dispatch Table EITS and IA class share the same dispatch table gt RES Defines the granularity of tsquantum gt tsquantum CPU time for next ONPROC state gt tstqexp New priority if time quantum expires gt tsslpret New priority when state change from TSSLEEP to TSRUN gt tsmaxwait waited too long ticks gt tslwait New priority if waited too long RT FX amp FSS Dispatch Tables I RT gt Time quantum only gt For each possible priority I FX gt Time quantum only gt For each possible priority I FSS gt Time quantum only gt Just one not de ned for each priority level gt Because FSS is share based not priority based II SYS gt No dispatch table gt Not needed no rules apply I INT gt Not really a scheduling class openSOLanS Setting A RT Thread s Priority priocntl e c RT p 59 program kth readLWP rtproc rtpri Oi Dispatch Queue Placement ElQueue placement is based a few simple parameters gtThe thread priority gt Processor bindingProcessor set gtProcessor thread last ran on Warm affinity gtDepth and priority of existing runnable threads gtMemory Placement Optimization MPO enabled will keep thread in defined locality group lgroup openSOLanS Dispatch Queue Manipulation Elsetfrontdqo Elsetbackdqo EIA thread will be placed on either the front of back of the appropriate dispatch queue depending on Outline El Scheduling Class and Priority El Dispatch Queues amp Dispatch Tables El Thread Priorities amp Scheduling El Turnstiles amp Priority Inheritance Thread Priorities amp Scheduling II Every thread has 2 priorities a global priority derived based on Its scheduling class and potentia Iy and Inherited priority II Priority inherited from parent alterable via priocnt1 command or system call IITypicay threads run as either T5 or IA threads gt IA threads created when thread is associated with a wnndownng system I RT threads are explicitly created IZISYS class used by kernel threads and for TSIA threads when a higher priority IS warranted gt A temporary boost when an important resource is being held El Interrupts run at interrupt priority openSOLans Thread Selection IIThe kernel dispatcherimplements a selectandratify thread selection algorithm gt dispgetbest Go find the highest priority runnable thread and select it for execution gt dispratify Commit to the selection Clear the CPU preempt flags and make sure another thread of higher priority did not become runnable gt If one did place selected thread back on a queue and try again EIWarm affinity is implemented gt Put the thread back on the same CPU it executed on last gt Try to get a warm cache gt rechooseinterva kernel parameter gt Default isScIockticks openSOLanS Thread Preemption ElTwo classes of preemption gt User preemption gt A higher priority thread became runnable but it39s not a realtime thread gt Flagged via cpurunrun in CPU structure gt Next clock tick you39re outta here gtKerne preemption gtA realtime thread became runnable Even OS kernel threads will get preempted gt Poke the CPU crosscall and preempt the running thread now openSOLanS Thread Execution EIRun until gt A preemption occurs gt Transition from SONPROC to SRUN gt placed back on a run queue gt A blocking system call is issued gt eg read2 gt Transition from SONPROC to SSLEEP gt Placed on a sleep queue gt Done and exit gt Clean up gt Interrupt to the CPU you39re running on gt pinned for interrupt thread to run gt unpinned to continue Sleep amp Wakeup ElCondition variables used to synchronize thread sleepwakeup gtA block condition waiting for a resource or an event enters the kernel cvxxx functions gtThe condition variable is set and the thread is placed on a sleep queue gtWakeup may be directed to a specific thread or all threads waiting on the same event or resource gt One or more threads moved from sleep queue to run queue OpenSOLaI39IS SIeepWakeup Kernel Subsystem sleep Device Drivers Kernei Modules I wakeup 39 quot 1 L A condition W waim CV wait Signl cv 5i l A gna 0 cvbroadcast vanable cvt1medwa1t cvtlmedwalisngj W Imsleep interfaces cvblodku l t sneep sleepqwakeonechan queue sleequnsertcj sleepqwakeallchan Interfaces sleepqunsleep w m 3 g g I g CI 3 0 a c wakeup quot 4 a a u 33 g 91 a w 9 D Outline El Scheduling Class and Priority El Dispatch Queues amp Dispatch Tables El Thread Priorities amp Scheduling El Turnstiles amp Priority Inheritance openSOLans Turnstiles amp Priority Inheritance EITurnstile A special set of sleep queues for kernel threads blocking on mutex or RW locks EIPriority inversion a scenerio where a thread holding a lock is preventing a higher priority thread from running because the higher priority thread needs the lock EIPriority inheritance a mechanism whereby a kernel thread may inherit the priority of the higher priority kernel thread EITurnstiles provide sleepwakeup with priority inheritance for synchronization primitives OpenSOLaI39IS Priority Inversion T1 T2 T3 pri 40 pri 50 pri 46 T1 runs T3 comes and acqunres T2 runs along with lock L1 attempts a Denier I L1 L0 t L1 priority than H I 395 T1 and he by T1 prevents T1 from I running i T3 with the best priority is prevented from i Q running due to lower priority threads openSOLans Turnstiles EIAII active turnstiles reside in turnstiletabe index via a hash function on the address of the synchronization object EIEach hash chain protected by a dispatcher lock acquired by turnstilelookup EIEach kernel thread is created with a turnstile in case it needs to block on a lock Elturnstileblock put the thread to sleep on the appropriate hash chain and walk the chain applying PI where needed openSOLans Turnstiles con d Elturnstilewakeup waive an inherited priority and wakeup the speCIfIc kernel threads EIFor mutex locks wakeup is called to wake all kernel threads blocking on the mutex IIFor RW locks gt If no waiters just release the lock gt If a writer is releasing the lock and there are waiting readers and writers waItIn readers get the lock If they are of the same or hIg er priority than the waiting writer gt A reader releasing the lock gives priority to waiting writers Turnstiles con d turnsiietable tcfrst tclock l39 tc rst tco ck tc rst tclock tc rst tc0ck 1 LOCK J ts ep turnstile tsnext gt tsnext t5free a t5free tssobj tssobj tswaite rs tswaiters tse rI tsinheritor I t5inheritor tsprioirw tsprioinv tssleepq tssleepq rst I s first Eq rst ecu rst quotquotquot quotFre39e lTs tquot39 tsnext ts free tswaiters r1 tsjnheritor tsprioirw ts slee p q rst f kthread kthre ad queue sleep kthre ad OpenSOLaI39IS openSOLans Reference EIRichard McDougall James Mauro quotSOLARIS Kernel Performance Observability amp Debuggingquot USENIX3905 2005 t2solarisslidespdf ElSoIaris internals and performance management Richard McDougaII 2002 ca550802pdf End 20060219
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'