DOC PREVIEW
CORNELL CS 414 - Review Session I

This preview shows page 1-2-3-18-19-36-37-38 out of 38 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 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 38 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 38 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 38 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 38 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 38 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 38 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 38 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS414 Review Session IToday’s AgendaProcesses vs ThreadsProcessesThreadsUser level threadsPlus and Minus of ULTsKernel Level ThreadsPlus and Minus of KLTsProcess/Thread State DiagramProcess/Thread SchedulingScheduling MetricsScheduling PoliciesMultiple Feedback QueuesSynchronization PrimitivesSemaphores (Operations)MonitorsSynchronization TipsHow to implement Semaphores?Things to avoid!!!Conditions for deadlockResource Allocation GraphExample 1 (review question 1)Example 1 contd…Solution 1 (Wrong)Solution 2Slide 27Example 1 (contd…)Example 2 (review question 2)Example 2 contd…Example 3 (review question 3)Example 4Example 4 contd…SolutionSolution to Example 4Solution contd…Slide 37Question TimeCS414 Review Session IRamaToday’s AgendaBrief Overview of Syllabus–Processes and Threads–Process Scheduling–Process Synchronization–DeadlocksExample Questions and SolutionsQuestion TimeProcesses vs ThreadsProcessesCode SegmentData SegmentsResources –Files open, Devices open, System resourcesProcess Control Block–Process state, book-keeping, access rightsThreadsIndividual Threads–Stack–Instruction Pointer–Thread Control BlockRegister image, thread state, priority info etc…Shared with other threads of that process–Memory segments, Code segments–ResourcesUser level threadsThe kernel is not aware of the existence of threadsAll thread management is done by the application, using a thread libraryThread switching does not require kernel mode privileges Scheduling is application specificPlus and Minus of ULTsAdvantages–Thread switching does not involve the kernel: no mode switching–Scheduling can be application specific: choose the best algorithm.–ULTs can run on any OS. Only needs a thread libraryInconveniences–Most system calls are blocking and the kernel blocks processes. So all threads within the process will be blocked–The kernel can only assign processes to processors. Two threads within the same process cannot run simultaneously on two processorsKernel Level ThreadsAll thread management is done by kernelNo thread library but an API to the kernel thread facilityKernel maintains context information for the process and the threadsSwitching between threads requires the kernelScheduling occurs on a thread basis, usuallyEx: Windows NT and OS/2Plus and Minus of KLTsAdvantages–the kernel can simultaneously schedule many threads of the same process on many processors–blocking is done on a thread level–kernel routines can be multithreadedInconveniences–thread switching within the same process involves the kernel. We have 2 mode switches per thread switch–this results in a significant slow downProcess/Thread State DiagramProcess/Thread SchedulingLong Term Scheduling–Admission Control– I/O bound vs CPU boundMedium Term Scheduling–Number of processes in memory (SWAPPER)Short Term Scheduling–Select from ready processes (Dispatcher)–Pre-emption vs non-preemptionScheduling MetricsCompletion Time–Finish time of a processTurn Around Time–Finish time – Start time–CPU bound jobsResponse Time–Time at which first response to user is given –I/O bound jobs Throughput–Number of processes completed per unit time.Scheduling PoliciesFirst Come First ServeShortest Job First (Shortest Remaining Time First)Round Robin SchedulingPriority Based SchedulingMultiple Feedback QueuesDifferent RQs may have different quantum valuesSynchronization PrimitivesSemaphoresCondition VariablesMonitorsSemaphores (Operations)Initialize counter (VERY IMPORTANT)Wait or P or Down (blocks process)Signal or V or Up (releases process)BEWARE–Don’t assign values to count (S.count = -1)–Don’t read values of count (if S.count == -1)–Use only the above operations.MonitorsShared Variables.Only one process currently inside a monitor.Block on a condition variable. –Wait( c )Another process releases the variable.–Signal( c )Synchronization TipsShared Variables–Always use mutex semaphores to access shared variables.–Or use monitors for shared variables.Synchronization–Use semaphores or condition variables for synchronization–Don’t forget to initialize.How to implement Semaphores?Hardware–Atomic instructions (tset, xchng)Software–Enable/disable interrupts–Spinlocks (multi-processor systems)Things to avoid!!!Race Conditions–NO SYNCHRONIZATIONDeadlocksBusy WaitingStarvationConditions for deadlockMutual ExclusionHold and WaitNo preemption (of resources)Circular WaitResource Allocation GraphP1 P2 P3R1 R3R2R4R1P1 is holding an instance of R2 and waiting for an instance of R1P2 is holding an instance of R1 and R2 and waiting for an instance of R3P3 is holding an instance of R3Example 1 (review question 1)Flight Reservation Algorithm(Ithaca, Miami, Dallas, San Diego, Seattle)One server per city and one request per server at a timeOnly decides about out going flightsConnecting flights => both legs confirmedEg: Mr. Mosse wants ticket from Ithaca to San Diego via Dallas–Server at Ithaca sends a request to server at dallas, waits for confirmed ticket before booking from ithaca to dallas.Example 1 contd…1a) Solve the synchronization problem using semaphores.Request should not be served until server is freeServer should not start until there is a requestWrite down procedures for client and server for booking tickets:Solution 1 (Wrong)ClientSynch := 0beginsubmit requestV(synch)P(mutex)processing requestendServerMutex := 1repeatP(synch)service requestV(mutex)until false;Solution 2Clientmutex := 1 synch := 0beginP(mutex)submit request;V(sync)process reply;endServerrepeatP(sync)service requestV(mutex)until falseExample 1 contd…1b) Describe a deadlock scenario in this problem. Show that all 4 conditions hold.Solution:Mutual exclusion : only one request at a timeHold-Wait : Wait for a connection flightNo Preemption : Got to wait for replyCircular Wait :A requests : Ithaca to San Diego via DallasB requests : Dallas to Ithaca via San DiegoC requests : San Diego to Dallas via IthacaExample 1 (contd…)1c) Give a strategy to remove deadlock.–Order Cities in alphabetical order.–Always process requests in alphabetical order–A requests from Dallas to San Diego before Ithaca to Dallas–B requests Dallas to San Diego before San Diego to IthacaRAG won’t work


View Full Document

CORNELL CS 414 - Review Session I

Documents in this Course
Security

Security

49 pages

Processes

Processes

24 pages

Deadlocks

Deadlocks

57 pages

Threads

Threads

5 pages

Threads

Threads

29 pages

Deadlocks

Deadlocks

36 pages

Load more
Download Review Session I
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 Review Session I 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 Review Session I 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?