Reading...
Play button
Play button
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;
80 Cards in this Set
- Front
- Back
|
Name the five major topics covered in the IPS section
|
1) the critical section problem, 2) spin locks, 3) semaphores, 4) ptrhead synchronization, 5) monitors
|
|
|
What is shared when using shared memory?
|
if you can't answer this one no amount of flashcards is going to help
|
|
|
T/F when sharing files, two processes access the same file, but not simultaneously
|
F
|
|
|
What will happen if, while sharing files, two processes/threads of a process modify the same data at the same time?
|
inncorrect results
|
|
|
Make an analogy with which you could describe a shared memory to a layman. Write two simple functions that prove your example
|
ex: bank account management, see slides 6:16 for detailed solution, yours should be similar!
|
|
|
Define race condition.
|
two or more users/processes are updating the same file at the same time
|
|
|
What is a common race condition that results in conflicting increments?
|
ex1) both parent and child acces the same value of counter, ex2) double incrementing
|
|
|
What are the three possible means of solving race conditions?
|
1) disabling interrupts, 2) enforcing mutual exclusion, 3) using an atomic transaction mechanism
|
|
|
Of the three possible means of solving race conditions, which is preferable?
|
enforcing mutual exclusion
|
|
|
T/F Disabling interrupts is not safe for user programs.
|
T
|
|
|
Where are disabling interrupts used? What is their scope?
|
1) critical sections in kernel 2) VERY SHORT
|
|
|
T/F Multithreaded kernels runnning on multiprocessor architectures are particularly suited to disabling interupts.
|
F, they are incompatible
|
|
|
Define critical section.
|
portions of code where shared data is read and modified
|
|
|
What is the scope of mutual exclusion enforcement?
|
also short!
|
|
|
Describe enforcement of mutual exclusion.
|
a mechanism that guarantees no two processes will ever be at a critical section for the same data simultaneously is implemented
|
|
|
What do atomic transactions allow processes to do?
|
they allow several processes to access the same shared data without interference
|
|
|
T/F atomic transactions are a preferred solultion for database access. Justify your answer.
|
T, most databases are shared and their critical sections can demand a large number od disk accesses
|
|
|
List the four critera that a critical section solution should meet.
|
1) enforce mututal exclusion, 2) no assumptions about process speeds (all the mutual exclusion), 3) no unnecessary access prevention (nothing but mutual exclusion), 4) no starvation
|
|
|
List the four approaches to critical section solutions.
|
1) pure software (peterson's algorithm), 2) spin locks (xchg instruction), 3) semaphors, 4) locks and condition variables
|
|
|
T/F A pure software solution makes many assumptions about the hardware.
|
F, remember the solution criteria!
|
|
|
What do spin locks do?
|
spin locks use special instrucations to achieve an atomic test and set
|
|
|
Describe how tesing and setting are made to be "atomic."
|
lock testing and lock setting functions are put into a single instruction
|
|
|
T/F Atomic steps can be separated by an interrupt.
|
F
|
|
|
Name the five major topics covered in the IPS section
|
1) the critical section problem, 2) spin locks, 3) semaphores, 4) pthread synchronization, 5) monitors
|
|
|
What is shared when using shared memory?
|
if you can't answer this one no amount of flashcards is going to help
|
|
|
T/F when sharing files, two processes access the same file, but not simultaneously
|
F
|
|
|
What will happen if, while sharing files, two processes/threads of a process modify the same data at the same time?
|
incorrect results
|
|
|
Make an analogy with which you could describe a shared memory to a layman. Write two simple functions that prove your example
|
ex: bank account management, see slides 6:16 for detailed solution, yours should be similar!
|
|
|
Define race condition.
|
two or more users/processes are updating the same file at the same time
|
|
|
What is a common race condition that results in conflicting increments?
|
ex1) both parent and child access the same value of counter, ex2) double increment
|
|
|
What are the three possible means of solving race conditions?
|
1) disabling interrupts, 2) enforcing mutual exclusion, 3) using an atomic transaction mechanism
|
|
|
Of the three possible means of solving race conditions, which is preferable?
|
enforcing mutual exclusion
|
|
|
T/F Disabling interrupts is not safe for user programs.
|
T
|
|
|
Where are disabling interrupts used? What is their scope?
|
1) critical sections in kernel 2) VERY SHORT
|
|
|
T/F Multi-threaded kernels running on multiprocessor architectures are particularly suited to disabling interrupts.
|
F, they are incompatible
|
|
|
Define critical section.
|
portions of code where shared data is read and modified
|
|
|
What is the scope of mutual exclusion enforcement?
|
also short!
|
|
|
Describe enforcement of mutual exclusion.
|
a mechanism that guarantees no two processes will ever be at a critical section for the same data simultaneously is implemented
|
|
|
What do atomic transactions allow processes to do?
|
they allow several processes to access the same shared data without interference
|
|
|
T/F atomic transactions are a preferred solultion for database access. Justify your answer.
|
T, most databases are shared and their critical sections can demand a large number od disk accesses
|
|
|
List the four critera that a critical section solution should meet.
|
1) enforce mututal exclusion, 2) no assumptions about process speeds (all the mutual exclusion), 3) no unnecessary access prevention (nothing but mutual exclusion), 4) no starvation
|
|
|
List the four approaches to critical section solutions.
|
1) pure software (peterson's algorithm), 2) spin locks (xchg instruction), 3) semaphores, 4) locks and condition variables
|
|
|
T/F A pure software solution makes many assumptions about the hardware.
|
F, remember the solution criteria!
|
|
|
What do spin locks do?
|
spin locks use special instructions to achieve an atomic test and set
|
|
|
Describe how testing and setting are made to be "atomic."
|
lock testing and lock setting functions are put into a single instruction
|
|
|
T/F Atomic steps can be separated by an interrupt.
|
F
|
|
|
Use an exchange instruction (exch) to make a viable solution.
|
ex. see slides 54-60
|
|
|
What are the two underlying assumptions of Peterson's algorithm and spinlocks?
|
1) instructions execute in sequence, 2) instructions execute in an atomic fashion
|
|
|
Peterson's alg and spinlocks rely on ____, which wastes ___.
|
1) busy waits, 2) CPU cycles (unnecessary context switches slow everyone down!)
|
|
|
What is priority inversion?
|
It is when a high priority process doing a busy wait prevents a lower priority process from doing its work and leaving its critical region
|
|
|
T/F Busy waits must be avoided on single-core and multi-core architectures.
|
F, must be avoided on single core, but they can be used for short waits on multi-core arch.
|
|
|
What other means can an OS use to enact mutual exclusion (outside of a busy wait)?
|
it can put the waiting process in the blocked state until the resource is available
|
|
|
Define semaphore.
|
special integer variable that can be initialized to any value greater than zero and that can only be manipulated through two atomic operations
|
|
|
What are the two atomic operations that a semaphore is manipulated through?
|
P() and V()
|
|
|
What are P and V abbreviations of? Define each term.
|
P - Probeer(try/wait), V - Verhoog (increment/signal)
|
|
|
What recent RPG included Dutch computer scientist E. W. Dijkstra, famed for his lecture, "Over Seinpalen" ?
|
The Witcher 3
|
|
|
Really?
|
No.
|
|
|
What are other names for P and V? Why avoid them?
|
wait and signal, respectively; it is best to reserve them for operations on conditions and monitors
|
|
|
Explain the P() operation given semaphore values of 0 and 1.
|
0: wait until value becomes positive, 1+: decrements value
|
|
|
Explain the V() operation given semaphore values of 0 and 1.
|
value is irrelevant, increment the value of the semaphore
|
|
|
T/F Semaphores are implemented through system calls.
|
T
|
|
|
T/F Using semaphores eliminates busy waits.
|
T
|
|
|
If using semaphores eliminates busy waits, what happens when a zero value semaphore is introduced?
|
process waiting is put in the blocked state.
|
|
|
Who are Paula and Victor?
|
If you don't know this you need to read the slides!!
|
|
|
Why are semaphores implemented as kernel objects?
|
to avoid busy waits
|
|
|
What are binary semaphores typically used for?
|
they are used to provide mutual exclusion as their value can only be zero or one
|
|
|
T/F The semantics of P operations must be altered when using binary semaphores
|
F
|
|
|
When using binary semaphores, what value does V set a semaphore to?
|
one
|
|
|
How many semaphores are assigned to each grou pof data that constitutes a crtical seciton?
|
ONE!!!!
|
|
|
(semaphores) Before entering a critical region a process must (2)...
|
1) P(&mutex); 2) wait P(&waitforme) till region is free V(&waitforme);
|
|
|
(semaphores) After leaving a critical region a process must (2)...
|
1) V(&mutex); 2) signal the process is leaving the critical section
|
|
|
List the five principle advantages of semaphores.
|
1) machine-independent, 2) simple but general, 3) work with any number of processes, 4) as many critical regions allowes as there are seamphores assigned, 5) semaphores can be used for synchronization in an arbitary fashion
|
|
|
Define layering.
|
use a powerful/flexible mechanism that applies to many problems and improve the UI (user interface) later.
|
|
|
What are the two notable implementations of semaphores in UNIX?
|
1) V semaphores (old), 2) POSIX semaphores
|
|
|
Describe the two situations in which waiting occurs when using a bounded buffer.
|
1) buffer is full because processes put their output in buffer, 2) buffer is empty and processes are attempting to remove items from buffer
|
|
|
List the three rules that govern access to a bounded buffer.
|
1) producers cannot store items in the buffer when it is full, 2) consumers cannot take from empty buffer, 3) producers and consumers must access the buffer one at a time
|
|
|
Why does the order of P() operations matter?
|
P() order is VERY important, neither producer nor consumer should request exclusive access to the buffer before being sure they can perform their operation
|
|
|
Why does the order of V() operations matter?
|
the order of V() operations does not matter.
|
|
|
What are the two processes involved in reader-writers problem?
|
Readers (want to access), and writers (want to update)
|
|
|
What does a reader-writer problem essentially need?
|
mutual exclusion.
|
