Classic Synchronization Problems (Reader-Writer Problem) Midterm Review TopicsCS241 AdministrativeOutlineFirst Reader-Writer ProblemFirst Readers-Writers Problem (Readers have priority)Slide 6First Reader-Writer SolutionMidterm ReviewTopics: Hardware/OS OverviewTopics: ProcessesTopics: ThreadsTopics: Concurrency (Mutual Exclusion)Topics: Thread SynchronizationTopics: SchedulingTopics: SignalsTopics: TimersTopics: Classical Sync ProblemsSummaryCS 241 Spring 2007System Programming 1Classic Synchronization Problems (Reader-Writer Problem)Midterm Review TopicsLecture 19Klara Nahrstedt2CS241 AdministrativeRead Chapter 5.6 in StallingsHomework 1 due 3/2 4pm in Anda Ohlsson’s OfficeMIDTERM – MONDAY, March 5, 11am (will talk about Midterm at the end of lecture)3OutlineReaders/ Writers Problem4First Reader-Writer Problem•readers: read data•writers: write data•Rule:–Multiple readers can read the data simultaneously–Only one writer can write the data at any time–A reader and a writer cannot in critical section together.•Locking table: whether any two can be in the critical section simultaneouslyReaderWriterReader OK NoWriter NO No5First Readers-Writers Problem(Readers have priority)Let processes reading do so concurrentlyLet processes writing do so one at a timeIntroduce semaphores Semaphore mutex = 1; Semaphore wrt = 1;int readc = 0; /* reader counter */6Writer while (TRUE) {Think_up_data(); /*noncritical section*/lock(&wrt); do writing unlock(&wrt); }Reader while (TRUE) { lock(&mutex); readcount =readcount+1; if readcount == 1 then lock(&wrt); unlock(&mutex); do reading lock(&mutex)readcount=readcount-1; if readcount == 0 then unlock(&wrt); unlock(&mutex); Use read data }7First Reader-Writer SolutionDoes it work? What if?Problem with this solutionMutex m, wrt; int readcount; // shared and initialized to 0// Writer // Reader Lock(&m); readcount:=readcount+1; Lock(&wrt); if (readcount == 1) lock(&wrt); ...... unlock(&m); writing performed .... ..... reading performed lock(&m); Lock(&wrt); readcount:=readcount-1; if (readcount == 0) unlock(&wrt); Unlock(&m);8Midterm ReviewReviewLecture NotesAll quizzes until todaySMP Quizzes and Regular QuizzesReview homework 1 solutionsReview Stallings and R&R book materialMidterm - Monday 11-11:50am, 1404 SCReview Session – Sunday 2-3:30pm in 1404 SC You need to bring questions, TAs will respondMidterm closed book, closed notes, NO calculator or other calculating electronic devicesNo cell-phones9Topics: Hardware/OS OverviewChapter 1.1-1.7 (Stallings)Chapter 2.1-2.2 (Stallings) Chapter 1 (R&RKeywords Need to know Processors – registersInterrupts and Interrupt HandlingPolling and Programmed I/OBasic Memory principlesKernel mode, user modeMultiprogramming, uni-programmingTime sharingBuffer Overflow and security10Topics: ProcessesChapter 3.1-3.4 (Stallings) Chapter 2 and 3 (R&R)Keywords need to knowWhat is process?What is the difference between process and program? What is the program image layout? Understand argument arraysWhat does it mean to have a thread-safe function? What is the difference between static and dynamic variables? What are the major process states? What is the difference between dispatcher and scheduler? What is PCB?What happens when process switches from running to ready state?What is process chain, process fan?11Topics: ThreadsChapter 12.1-12.5 (R&R)Chapter 4.1, 4.5 (Stallings) Keywords need to knowWhat is the difference between processes and threads?What is the difference between user-level threads and kernel-level threads? Detaching and joining threadsWhat happens if you if you call exit(1) in a thread? What is a graceful way to exit a thread without causing process termination?12Topics: Concurrency (Mutual Exclusion)Chapter 14.1-14.3 (R&R)Chapter 5.1-5.3 (Stallings – and don’t forget Appendix A about the Software Solutions)Keywords need to knowWhat are the four conditions to provide appropriate synchronization and enter critical region? What is the difference between counting semaphore and mutex? What do sem_wait and sem_post do? How can counting semaphores be implemented using binary semaphores? How can test_and_set be used for synchronization? How can you make a function atomic? Consider increment (i++) and decrement function (i--). How do you ensure that race condition does not occur on the shared variable ‘i’ when two processes use them at the same time?13Topics: Thread Synchronization Chapter 13.1-13.2 (R&R)Keywords to knowWhat are mutex locks? How do you initialize mutex locks? When would you use mutex instead of counting semaphore?When would you use counting semaphore instead of mutex? Are mutex functions interrupted by signals?14Topics: Scheduling Chapter 9.1-9.2 Scheduling (Stallings) Keywords need to knowScheduling policiesFCFC, SJF, Round Robin, Priority SchedulingPreemptive vs. Non-Preemptive SchedulingQueues in Process management – what is ready queue? How are process states related to process management queues? What is average waiting time? What is the difference between process waiting time and turn-around time?15Topics: SignalsChapter 8.1-8.5 (R&RKeywords need to knowSignal basic concepts – generating signals, blocked, pending signals, delivered signals, ignored signals, …What is signal mask and what are the operations to modify signal mask? What is signal handler? What is the role of sigaction? How do you wait for signals?16Topics: TimersChapter 9.1-9.3 (R&R)Keywords need to know Understand what the various time functions are forGettimeofdayUnderstand the different clock resolutionsSleep function What are time intervals? What are they great for?17Topics: Classical Sync ProblemsChapter 5.3 and 6.6 (Stallings )Keywords need to knowWhat is the producer-consumer problem? What are the various semaphores in the producer/consumer solution for? What is the dining philosopher problem? What is the danger of a simple solution for dining philosopher problem?18Summary Good Luck with the Exam!!!Please, come to class little earlier (10:55am) so that we can start
View Full Document