CS241 System Programming Review Session – Final ExamFinal Exam DateFinal Exam MaterialTextbook ChaptersSlide 5How to Study for the Final ExamA peek into UnixSteps in Making a System CallProgram LayoutThreads in User SpaceThreads in the KernelSynchronization RequirementsSolution HistoryConditions for DeadlockDeadlock TopicsFile System ImplementationContiguous AllocationLinked AllocationIndexed AllocationVariable Partitions and FragmentationCompactionHow Bad Is Fragmentation?Storage Placement StrategiesPaging BasicsReduce PagingThrashing and CPU UtilizationNetwork ServiceReview Questions (Memory)Review Questions (Memory)Review Questions (Virtual Memory)Slide 31Review Questions (File Systems)Slide 33Review Questions (Networks)Review Questions/Answers (Memory)Review Questions/Answers (Memory)Review Questions/Answers (Virtual Memory)Slide 38Review Questions/Answers (File Systems)Slide 40Review Questions/Answers (Networks)Slide 42CS241 System ProgrammingReview Session – Final ExamKlara NahrstedtReview for Final Exam 5/3/200601/14/19 CS 241 - System Programming, Klara Nahrstedt2Final Exam DateMay 11, Thursday, 8-11amRoom Allocation–Last Name A-L go to room 1404 SC–Last Name M-Z go to room 151 LoomisBring with you Student ID and penExam is closed book, closed notes, no calculatorsComprehensive Exam01/14/19 CS 241 - System Programming, Klara Nahrstedt3Final Exam Material Topics (before Midterm) – will cover 1/3 of exam–Process and Thread Management–Synchronization–Scheduling–Signals and Timers–DeadlocksTopics (after Midterm) – will cover 2/3 of exam –Principles of I/O –Memory Management–File Systems–Communication Protocols01/14/19 CS 241 - System Programming, Klara Nahrstedt4Textbook ChaptersTanenbaum Chapters: –Chapter 2 (2.1-2.4) –Chapter 3 (3.1-3.3.5) –Chapter 4 (4.1-4.5), except 4.4.7 and 4.5.4 –Chapter 5 (5.1-5.5) Lecture Notes01/14/19 CS 241 - System Programming, Klara Nahrstedt5Textbook ChaptersRobins&Robins –Chapter 2 (2.1-2.11)–Chapter 3 (3.1-3,7)–Chapter 4 (4.1-4.4 and 4.6.1-4.6.2)–Chapter 5 –Chapter 8 (8.1-8.5)–Chapter 9 (9.1-9.5)–Chapter 12 (12.1-12.6)–Chapter 13 (13.1-13.6)–Chapter 14 (14.1-14.5)–Chapter 15 (15.1, 15.3, 15.4)–Chapter 18 (18.1-18.7)–Chapter 20 (20.1-20.8)01/14/19 CS 241 - System Programming, Klara Nahrstedt6How to Study for the Final ExamReview Slides/Questions for Midterm Review Review Class Notes and Textbooks chapters Review QuizzesReview Discussion Section SlidesReview Additional (Handwritten) Material on the web siteReview Shadow Homework and Regular Homework ProblemsWork on Relevant Problems after each chapter in Tanenbaum and also on Exercises in R&R Book01/14/19 CS 241 - System Programming, Klara Nahrstedt7A peek into UnixApplicationPortable OS LayerLibrariesMachine-dependent layerUser space/levelKernel space/level• User/kernel modes are supported by hardware •Some systems do not have clear user-kernel boundary01/14/19 CS 241 - System Programming, Klara Nahrstedt8Steps in Making a System Call read (fd, buffer, nbytes)01/14/19 CS 241 - System Programming, Klara Nahrstedt9Program Layout01/14/19 CS 241 - System Programming, Klara Nahrstedt10Threads in User SpaceA user-level threads package01/14/19 CS 241 - System Programming, Klara Nahrstedt11Threads in the KernelA threads package managed by the kernel01/14/19 CS 241 - System Programming, Klara Nahrstedt12Synchronization RequirementsMutual ExclusionProgressBounded WaitNo Blocking Forever01/14/19 CS 241 - System Programming, Klara Nahrstedt13 Solution HistoryApproaches:1. Turn Mutual Exclusion2. Other Flag Mutual Exclusion3. Two Flag Mutual Exclusion4. Two Flag and Turn Mutual Exclusion01/14/19 CS 241 - System Programming, Klara Nahrstedt14Conditions for DeadlockThe following four conditions are both necessary and sufficient for deadlock:1. Mutual exclusion2. Hold and wait condition3. No preemption condition4. Circular wait condition01/14/19 CS 241 - System Programming, Klara Nahrstedt15Deadlock TopicsDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDeadlock Recovery01/14/19 CS 241 - System Programming, Klara Nahrstedt16File System ImplementationA possible file system layout01/14/19 CS 241 - System Programming, Klara Nahrstedt17Contiguous Allocation01/14/19 CS 241 - System Programming, Klara Nahrstedt18Linked Allocation01/14/19 CS 241 - System Programming, Klara Nahrstedt19Indexed Allocation01/14/19 CS 241 - System Programming, Klara Nahrstedt20Variable Partitions and FragmentationMonitor Job 1 Job 2 Job 3 Job 4Free1Monitor Job 1 Job 3 Job 4Free2Monitor Job 1 Job 3 Job 4FreeJob 53Monitor Job 3 Job 4FreeJob 5 Job 64Monitor Job 3FreeJob 5 Job 6Job 7 Job 8501/14/19 CS 241 - System Programming, Klara Nahrstedt21CompactionMonitor Job 3FreeJob 5 Job 6Job 7 Job 85Monitor Job 3FreeJob 5 Job 6Job 7 Job 86Monitor Job 3FreeJob 5 Job 6Job 7 Job 87Monitor Job 3FreeJob 5 Job 6Job 7 Job 88Monitor Job 3FreeJob 5 Job 6Job 7 Job 8901/14/19 CS 241 - System Programming, Klara Nahrstedt22How Bad Is Fragmentation?Statistical arguments - Random sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationI.e. 33% of memory may be unusable!!!Known as 50% RULE01/14/19 CS 241 - System Programming, Klara Nahrstedt23Storage Placement StrategiesBest fit. Use the hole whose size is equal to the need, or if none is equal, the whole that is larger but closest in size. First fit. Use the first available hole whose size is sufficient to meet the need.Worst fit. Use the largest available hole.01/14/19 CS 241 - System Programming, Klara Nahrstedt24Paging BasicsProvide user with virtual memory that is as big as user needsStore virtual memory on diskCache parts of virtual memory being used in real memoryLoad and store cached virtual memory without user program intervention01/14/19 CS 241 - System Programming, Klara Nahrstedt25Reduce Paging page replacement:optimalFIFO LRUsecond chance, page classes ad hoc techniques01/14/19 CS 241 - System Programming, Klara Nahrstedt26Thrashing and CPU Utilization01/14/19 CS 241 - System Programming, Klara Nahrstedt27Network ServiceService ExampleConnection-orientedReliableMessage streamPages in bookReliable byte stream Remote loginUnreliable connection Digitized VoiceConnectionless Unreliable datagram Test packetsAcknowledged Datagram Registered mailRequest-Reply Database
View Full Document