From e4066e00c63d3b6705bcb24c417fd2f69ca44009 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 14 Mar 2021 21:09:00 -0600 Subject: answer concurrency questions in assignment 2 --- doc/assignment2.md | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) (limited to 'doc/assignment2.md') diff --git a/doc/assignment2.md b/doc/assignment2.md index 7347588..cc571a6 100644 --- a/doc/assignment2.md +++ b/doc/assignment2.md @@ -109,8 +109,62 @@ a physical limitation or on the self-adjusting nature of human users. 1. Define critical section, and explain two general approaches for handling critical sections in operating systems. (8 marks) +Each process has a segment of code, called a critical section, in which the process may be changing +common variables, updating a table, writing a file, and so on. + +The important feature of the system is that, when one process is executing in its critical section, +no other process is to be allowed to execute in its critical section. That is, no two processes +are executing in their critical sections at the same time. + +The critical-section problem is to design a protocol that the processes can use to cooperate. +Each process must request permission to enter its critical section. The section of code +implementing this request is the entry section. The critical section may be followed by an +exit section. The remaining code is the remainder section. + +The general structure is: + +```c + do { + lock(something) { + //critical section + } + // remainder section + } while(1); +``` + +A solution to the critical-section problem must satisfy the following three requirements: + + * Mutual exclusion: if process Pi is executing in its critical section, then no other processes can be executing in their critical sections. + * Progress: + If no process is executing in its critical section and some processes wish to enter their critical sections, + then only those processes that are not executing in their remainder sections can participate in deciding which + will enter its critical section next, and this selection cannot be postponed indefinitely. + * Bounded waiting: + There exists a bound, or limit, on the # of times that other processes are allowed to enter their critical section and before that request is granted. 1. Describe the dining-philosophers problem, and explain how it relates to operating systems. (6 marks) + +Five philosopher spend their lives thinking and eating. +The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. +In the center of the table is a bowl of rice, and the table is laid with five single chopsticks. +When a philosopher thinks, she does not interact with her colleagues. +From time to time, a philosopher gets hungry and tries to pick up the two chopsticks +that are closest to her. +A philosopher may pick up only one chopstick at a time. +Obviously, she cannot pick up a chopstick that is already in the hand of a neighbour. +When a hungry philosopher has both her chopsticks at the same time, she eats without releasing +her chopsticks. +When she is finished eating, she puts down both of her chopsticks and starts thinking again. + +This is considered a classic synchronization problem because it is an example of a large class +of concurrency-control problems. It is a simple representation of the need to allocate several +resources among several processes in a deadlock-free and starvation-free manner. + +This relates to operating systems because pick up a chopstick is like entering a critical-section in a +process. It is also similar to how the operating system scheduled work to be done and which +process gets to execute next. Processes sometimes need to access resources (chopsticks) and they +need to be able to do this in a safe way without contention (sharing a chopstick). + 1. Define the two-phase locking protocol. (6 marks) 1. Describe how an adaptive mutex functions. (6 marks) 1. Describe a scenario in which the use of a reader-writer lock is more appropriate than using another synchronization tool, such as a semaphore. (6 marks) -- cgit v1.2.3