Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
31 Cards in this Set
- Front
- Back
State two shared resources |
- Send/receive data to/from the same device - Use the same file or a block of RAM to store data |
|
What is the role of the OS? |
To avoid incorrect operation or programs due to shared resource clashes. |
|
What are race conditions? |
Situations when two or more processes are reading or writing some shared data and the result depends on the order of execution. |
|
What is the part of the program where shared memory is accessed? |
The critical region |
|
State 3 things successful synchronisation requires |
- Mutual Exclusion - Progress - Bounded wait |
|
Define mutual exclusion |
No two processes should be in their critical region at the same time |
|
Define progress (in terms of successful synchronisation) |
No process running outside the critical region may block other processes |
|
Define a bounded wait |
Each process should enter its critical region eventually |
|
A process accessing a shared resource can... (3 things) |
1. Disable all interrupts 2. Access the shared resource 3. Re-enable interrupts |
|
The absence of interrupts ensures that... |
the process is not interrupted when it accesses the shared resource |
|
Advantage of disabling interrupts |
Achieves mutual exclusion. |
|
Disadvantage of disabling interrupts |
Prevents any other processes running even if it does not need the shared resource. |
|
How does access in turns work? |
- A pre-emptive scheduling policy is needed - The resource is associated with a shared variable "turn" that can take values 0 or 1 - P0 accesses the resources only if turn == 0; P1 only if turn == 1 (for example). - When a process finishes it re-assigns the turn to the other number. |
|
State a disadvantage of access in turns |
It causes a lot of useless busy waiting. - If it's not its turn, a process cannot start using the resource even if the other process is not interested. - Hence performing the while loop wastes CPU time |
|
Informally state Peterson's algorithm |
- Keep track of which processes are interested in accessing the critical region. - Assume there are only two processes; P0 and P1. - Each process uses a boolean flag[pid] to express interest in entering their critical condition - Both flag[0] and flag[1] are initialised to false |
|
When using Peterson's algorithm, to avoid _____ it must occur that: |
Deadlock; the process that starts the entry protocol last is allowed to proceed to the critical section first. |
|
The while loop in Peterson's algorithm performs: |
busy waiting |
|
Waiting is performed... |
only if the other process is interested in accessing the resource |
|
State 3 issues with Peterson's solution |
- The entry/exit protocols are directly programmed using busy-waiting - Busy-waiting protocols are difficult to design, understand, generalise, and analyse. - No separation between variables used for synchronisation and "normal" variables. Hence often error-prone and inefficient. |
|
Semaphores in a concurrent program provide a _____ _____ mechanism to implement _____ _____ and ______ ______ . |
basic signalling; mutual exclusion; condition synchronisation. |
|
Define a semaphore |
An integer variable that takes only non-negative values |
|
Semaphores represent... |
the quantity of a resource available |
|
State the two operations permitted on a semaphore |
- Wait(s) (aka P(s) for Prolaag) If s > 0 then decrement s else block the calling process - Signal(s) (aka V(s) for Verhogen) If processes are blocked on s then unblock one else increment s |
|
What is block-waiting used for
|
Efficiently implementing semaphores with hardware facilities, in the kernel of OSs |
|
Wait() and Signal() need to be implemented as _______ methods |
synchronised |
|
True or false: Wait() should wait until the semaphore value becomes > 0 |
True |
|
Signal() should release... |
other processes waiting on the semaphore |
|
Wait() and Signal() use what as opposed to busy-waiting? |
Block-waiting |
|
True or false: a blocked process uses CPU time |
False; a blocked process uses no CPU time |
|
State the two types of semaphore and what they take |
Binary takes only 0 or 1 Anything more and it's called general (or counting) |
|
What must you ensure with semaphores? |
That the initial value is >= 0 and overflow should not occur by increment |