Sync Flashcards
(36 cards)
What are the 2 main ways to structure parallel programs?
1) Threads communicate via shared data structures
2) Threads send messages directly to one another (only one possible in distributed systems)
What is the only way of structure parallel programs in distributed systems?
Threads sending messages directly to another
What is a shared memory segment?
Pages mapped into virtual memory of several processes
Name a flaw with Dekker’s Alg
Hard to generalise for 3 or more processes
Explain the Producer-Consumer problem
This works with a producer placing things into a holding buffer, and a consumer removing them. There is a variable, count (the number of items in the buffer), accessible to both. The consumer sleeps if the buffer is empty. The producer sleeps if buffer is full. These can be awakened by each other. In the case where the consumer reads count to be 0, then before it sleeps the scheduler allocates CPU to the producer. The producer adds an item to the buffer, then sends a wake up signal to the consumer. This signal is ignored as the consumer is awake. The CPU switches to consumer who immediately goes to sleep. The consumer will not wake up as no more signals to wake will be sent. The producer will keep adding items until buffer is full, then go to sleep. Both sleep forever.
What are the three tests for critical regions?
1) Mutual exclusion
2) Progress
3) Bound-waiting
Give an example of a race condition
Two processes, A & B, reading a file containing information about free memory slots and memory slots with files to print. If A reads and decides memory slot 2 is free, then interrupt occurs and B runs, B may store data in Memory slot 2. Control returns to A who then overwrites data in slot 2.
What conditions are required for having parallel processes cooperate effectively and efficiently using shared data?
1) No 2 processes may be in their critical regions at the same time
2) No assumptions made about speed or number of CPUs
3) No process running outside its critical region may block other processes
4) No process should have to wait forever to enter its critical region
Explain the process of disabling interrupts to achieve mutual exclusion. What is the problem with this?
Each processes disables interrupts upon entering its critical region, and reenables them just before leaving it. If a user forgets to enable interrupts again, problems occur. If the processor is multicore, interrupts will only be disabled on the CPU that the process is running on
Explain the process of lock variables to achieve mutual exclusion. What is the problem with this?
Processes have a single shared lock variable that defaults to 0 if no process is in critical region, but is changed to 1 when a process is in critical region. Processes must check lock variable before entering shared data. The problem is if a process reads and sees that the lock is 0, then an interrupt occurs and another process then sets the lock to 1, the first process will set the lock to 1 when control is returned to it.
Explain the process of strict alternation to achieve mutual exclusion. What is the problem with this?
Some variable keeps track of whose turn it is to enter the critical region. Once the critical region is left, the turn variable is changed to signify it is the turn of another process to access critical region. This uses busy waiting, which wastes CPU and so should generally be avoided. It wastes time if one process is significantly slower than another. Only strict alternation is allowed - no process may enter critical region twice in a row.
Explain the process of the TSL Solution to achieve mutual exclusion. What is the problem with this?
(test and set lock) A lot of computers have the following instruction: TSL RX, LOCK Reads the contents of the memory word lock into register RX. It can set and change the value of lock. During this process the memory bus is locked so other processes cannot make changes. Requires busy waiting
What issues arise with TSL solution and Peterson’s Solution to achieve mutual exclusion?
These both require busy waiting Priority Inversion Problem: Low priority process is running, high priority process wants to run, but has to wait. Low will never stop running, so high doesn’t get to enter the critical region
What is a semaphore?
A semaphore is a variable that stores the number of a particular resource that is available for future use. Two operations are wait and signal: signal increments semaphore, wait decrements it when semaphore > 0. if semaphore == 0, causes it to wait until a signal occurs.
What can we use to solve the Producer-Consumer problem? How?
Semaphores. 3 semaphores are used in this solution: full (how many slots are full), empty (how many slots are empty) and mutex (make sure buffer isn’t accessed by producer and consumer at same time).
How can different processes share the same ‘turn’ variable (Peterson’s Solution), semaphores or a common buffer?
1) Certain data structures (eg. semaphores) can be stored in the kernel and accessed via system calls
2) Most modern OSs offer the ability for processes to share parts of their address space
3) A shared file can be used
How can mutual exclusion be implemented on monitor entries?
It is up to the compiler with common ways being using a mutex or binary semaphore
How can monitors solve the problem of mutual exclusion?
Critical regions are to be turned into monitor procedures - only one process can be active in a monitor at a time
How do we handle blocking with the use of monitors?
This is done via condition variables, which have two operations (wait and signal). Waiting on a condition variable means waiting until variable takes on a certain value. For example, waiting on a variable, full, causes calling process to block. Waking up processes can be done by signalling the variable that process is waiting on. A process that signals must exit immediately.
What are some drawbacks to the use of monitors?
Most real languages (eg. C) do not support/recognise monitors, as the recognition must be done on compiler level. These languages also don’t have semaphores, but adding semaphores is easy.
What is a drawback to semaphores?
Semaphores don’t work in distributed system with multiple CPUs that don’t have access to same memory. That is, there’s no way to exchange data between machines
Explain the dining philosophers problem
This is a synchronisation problem. Five philosophers are seated around a table, each with a plate of spaghetti and one fork on either side of them. The philosophers are either thinking or eating at any one time. The philosophers can only eat if both left and right forks are available. The problem is finding a solution such that a philosopher never gets stuck
What are solutions to the dining philosophers problem? Do they work? Why/why not?
1) Philosopher does down on mutex before looking at forks. After forks are put back down, do up on mutex. This only allows one philosopher to eat at a time though.
2) Array, state, used to determine if philosopher is eating, thinking or trying to gather forks. A philosopher may only move into eating if neither neighbour is eating. Uses array of semaphores with 1 per philosopher (allows gathering philosophers to block)
Explain the readers and writers problem
This has to do with database access. The concept is a reservation system, where multiple processes are able to read the database at once. Only one process may ever write to the database at a time, and no processes can read the database while it is being written to
