Chapter Six Notes Flashcards
Race condition
A situation where several processes access
and manipulate the same data concurrently and the
outcome of the execution depends on the
particular order in which the access takes place
Multiple processes can be in the critical section at once (T/F)
False
Critical section problem
To design protocol to solve this the processes must synchronize their activity so as to cooperatively share data. Each process must
request permission to enter its critical section.
Each process must ask permission to enter critical section
in remainder section, may follow critical section with exit
section, then entry section
(T/F)
False, entry section -> critical section -> exit section -> remainder section
Solution to critical section problem must include
1) Mutual Exclusion - If process Pi is executing in its
critical section, then no other processes can be
executing in their critical sections
2) Progress - If no process is executing in its critical
section and there exist some processes that wish to
enter their critical section, then the selection of the
processes that will enter the critical section next
cannot be postponed indefinitely
3) Bounded Waiting - A bound must exist on the
number of times that other processes are allowed
to enter their critical sections after a process has
made a request to enter its critical section and
before that request is granted
Assume that each process executes at a
nonzero speed
No assumption concerning relative speed of
the n processes
Preemptive kernel
Allows preemption of process
when running in kernel mode.
* Pre-emptive kernels are especially
difficult to design for SMP architectures
* But a preemptive kernel may be more
responsive.
* A preemptive kernel is more suitable for
real-time programming
Non-preemptive kernel
Runs until exits kernel
mode, blocks, or voluntarily yields CPU
* Essentially free of race conditions in
kernel mode
Petersons Solution
Two process solution; assumed load and storage are atomic (uninterruptible); variable turn is used to determine which process’ turn it is to enter critical section, the flag array is used to indicate if a process is ready to enter.
Meets all three CS requirements.
Problem with Peterson’s Solution
Peterson’s solution is not guaranteed to work on modern
computer architectures for the primary reason that, to improve
system performance, processors and/or compilers may reorder
read and write operations that have no dependencies.
Hardware instructions
1) test_and_set() instruction: operates on two words atomically
2) compare_and_swap() instruction: operates on two words atomically, but uses a
different mechanism that is based on swapping the content of two
words
Bounded waiting
A bound must exist on the number of times that other processes are
allowed to enter their critical sections after a process has made a request to enter its critical
section and before that request is granted
Mutex Lock
Requires busy waiting, is called a spinlock.
acquire() a lock, then release() a lock. Calls must be atomic. Can be implemented using CAS. No context switch is required.
Semaphore
- Synchronization tool that provides more
sophisticated ways (than Mutex locks) for process
to synchronize their activities. - Can only be accessed via two indivisible (atomic)
operations - wait() and signal()
- Can be implemented with no busy waiting.
Counting semaphore
integer value can range over
an unrestricted domain
Binary semaphore
integer value can range only
between 0 and 1
* Same as a mutex lock
