Sync

Question 1

What are the 2 main ways to structure parallel programs?

Answer 1

1) Threads communicate via shared data structures

2) Threads send messages directly to one another (only one possible in distributed systems)

Question 2

What is the only way of structure parallel programs in distributed systems?

Answer 2

Threads sending messages directly to another

Question 3

What is a shared memory segment?

Answer 3

Pages mapped into virtual memory of several processes

Question 4

Name a flaw with Dekker’s Alg

Answer 4

Hard to generalise for 3 or more processes

Question 5

Explain the Producer-Consumer problem

Answer 5

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.

Question 6

What are the three tests for critical regions?

Answer 6

1) Mutual exclusion
2) Progress
3) Bound-waiting

Question 7

Give an example of a race condition

Answer 7

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.

Question 8

What conditions are required for having parallel processes cooperate effectively and efficiently using shared data?

Answer 8

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

Question 9

Explain the process of disabling interrupts to achieve mutual exclusion. What is the problem with this?

Answer 9

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

Question 10

Explain the process of lock variables to achieve mutual exclusion. What is the problem with this?

Answer 10

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.

Question 11

Explain the process of strict alternation to achieve mutual exclusion. What is the problem with this?

Answer 11

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.

Question 12

Explain the process of the TSL Solution to achieve mutual exclusion. What is the problem with this?

Answer 12

(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

Question 13

What issues arise with TSL solution and Peterson’s Solution to achieve mutual exclusion?

Answer 13

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

Question 14

What is a semaphore?

Answer 14

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.

Question 15

What can we use to solve the Producer-Consumer problem? How?

Answer 15

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).

Question 16

How can different processes share the same ‘turn’ variable (Peterson’s Solution), semaphores or a common buffer?

Answer 16

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

Question 17

How can mutual exclusion be implemented on monitor entries?

Answer 17

It is up to the compiler with common ways being using a mutex or binary semaphore

Question 18

How can monitors solve the problem of mutual exclusion?

Answer 18

Critical regions are to be turned into monitor procedures - only one process can be active in a monitor at a time

Question 19

How do we handle blocking with the use of monitors?

Answer 19

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.

Question 20

What are some drawbacks to the use of monitors?

Answer 20

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.

Question 21

What is a drawback to semaphores?

Answer 21

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

Question 22

Explain the dining philosophers problem

Answer 22

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

Question 23

What are solutions to the dining philosophers problem? Do they work? Why/why not?

Answer 23

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)

Question 24

Explain the readers and writers problem

Answer 24

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

Question 25

What is a solution to the readers and writers problem? Are there issues with this?

Answer 25

a) The first reader does a down on a semaphore. Subsequent readers increment a counter, decrementing it as they leave. The last one to leave then does an up on the semaphore, allowing writers to enter. Issues are that a writer may never get in.
b) same as above, but if a reader arrives when a writer is waiting, the reader does not enter. This means the writer just has to wait for readers in database at time of arrival. Issues are that this achieves less concurrency.

Question 26

Explain the sleeping barber problem

Answer 26

There is a barber shop with 1 barber, 1 barber chair and n chairs for waiting customers. If there are no customers, the barber goes to sleep. Arriving customers must wake sleeping barber. If the barber is cutting someone’s hair, additional arriving customers will either wait in waiting chairs or leave (if waiting chairs are full).

Question 27

What is test and set?

Answer 27

This is an instruction that tests and sets value of variable in one action (cannot be interrupted)

Question 28

What is the advantage to using semaphores over Dekker’s algorithm?

Answer 28

Semaphores can be used on any number of processes

Question 29

What is granularity or grain size?

Answer 29

Amount of data protected by a lock

kernels have large grains on infrequently used data

Question 30

What is the fix to priority inversion?

Answer 30

Priority inheritance

Question 31

Describe priority inheritance

Answer 31

The priority of a thread is the larger of its own priority and the priority of any threads waiting for locks held by this process

Question 32

What’s a resource?

Answer 32

Commodity required for process to execute

Question 33

What types of resources are there?

Answer 33

Serially reusable resources: eg. memory space, CPU cycles, etc
Consumable resources: produced/required by process. eg. messages, buffers of info, interrupts

Question 34

What 4 conditions must be satisfied for a deadlock to occur?

Answer 34

1) Processes must have exclusive access to resources
2) Resource cannot be forcibly taken from a process until the process explicitly releases the resources
3) Process currently holding resource can request more resources
4) Must be circular chain of processes such that each process in chain is waiting on resource held by next member in chain

Question 35

What is deadlock?

Answer 35

Every process in set is waiting on an event that can only be caused by another process within the set

Question 36

How can we avoid deadlocks?

Answer 36

1) Ostrich Method (ignore)
2) Detect and recover
3) Prevent deadlocks by permanently negating one of the four conditions for deadlock to occur
4) Avoid deadlocks dynamically by not allocating resource to a process if allocation can be part of deadlock chain