Process Synchronization

Set of vocabulary flashcards focusing on key terms and definitions related to process synchronization in operating systems.

A race condition ____.

Results when several threads try to access and modify the same data concurrently

An instruction that executes atomically ____.

executes as a single, uninterruptible unit

A counting semaphore ____.

Essentially an integer variable used to control access to a resource.

A mutex lock ____.

Essentially a boolean variable used to ensure mutual exclusion.

In Peterson's solution, the ____ variable indicates if a process is ready to enter its critical section.

flag[i]

The first readers-writers problem ____.

requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database.

A ___ type presents a set of programmer-defined operations that are provided mutual exclusion within it.

monitor

____________ occurs when a higher-priority process needs to access a data structure that is currently being accessed by a lower-priority process.

Priority inversion

What is the correct order of operations for protecting a critical section using mutex locks?

acquire() followed by release()

What is the correct order of operations for protecting a critical section using a binary semaphore?

wait() followed by signal()

_____ is not a technique for handling critical sections in operating systems.

Peterson's solution

A solution to the critical section problem does not have to satisfy which of the following requirements?

atomicity

A(n) _______ refers to where a process is accessing/updating shared data

critical section

_____ can be used to prevent busy waiting when implementing a semaphore.

Waiting queues

Signal() operation

A semaphore operation that increments the semaphore and potentially wakes a waiting thread.

Assume an adaptive mutex is used for accessing shared data on a Solaris system with multiprocessing capabilities. Which of the following statements is not true?

Condition variables and semaphores are never used in place of an adaptive mutex.

What is the purpose of the mutex semaphore in the implementation of the bounded-buffer problem using semaphores?

It ensures mutual exclusion.

How many philosophers may eat simultaneously in the Dining Philosophers problem with 5 philosophers?

2

Which of the following statements is true?

Spinlocks can be used to prevent busy waiting in the implementation of semaphore

_____ is/are not a technique for managing critical sections in operating systems.

Peterson's solution

When using semaphores, a process invokes the wait() operation before accessing its critical section, followed by the signal() operation upon completion of its critical section. Consider reversing the order of these two operations—first calling signal(), then calling wait(). What would be a possible outcome of this?

Several processes could be active in their critical sections at the same time.

Which of the following statements is true?

Operations on atomic integers do not require locking.

A(n) ___________ is a sequence of read-write operations that are atomic.

memory transaction

The OpenMP #pragma omp critical directive ___________.

behaves much like a mutex lock

Another problem related to deadlocks is ____________.

indefinite blocking

What three conditions must be satisfied in order to solve the critical section problem?

In a solution to the critical section problem, no thread may be executing in its critical section if a thread is currently executing in its critical section. Furthermore, only those threads that are not executing in their critical sections can participate in the decision on which process will enter its critical section next. Finally, a bound must exist on the number of times that other threads are allowed to enter their critical state after a thread has made a request to enter its critical state.

Explain two general approaches to handle critical sections in operating systems

Critical sections may use preemptive or nonpreemptive kernels. A preemptive kernel allows a process to be preempted while it is running in kernel mode. A nonpreemptive kernel does not allow a process running in kernel mode to be preempted; a kernel-mode process will run until it exits kernel mode, blocks, or voluntarily yields control of the CPU. A nonpreemptive kernel is essentially free from race conditions on kernel data structures, as the contents of this register will be saved and restored by the interrupt handler.

Write two short methods that implement the simple semaphore wait() and signal() operations on global variable S.

wait (S) {

while (S <= 0);

S--;

}

signal (S) {

S++;

}

Explain the difference between the first readers–writers problem and the second readers–-writers problem.

The first readers–writers problem requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database; whereas the second readers–writers problem requires that once a writer is ready, that writer performs its write as soon as

Describe the dining-philosophers problem and how it relates to operating systems

The scenario involves five philosophers sitting at a round table with a bowl of food and five chopsticks. Each chopstick sits between two adjacent philosophers. The philosophers are allowed to think and eat. Since two chopsticks are required for each philosopher to eat, and only five chopsticks exist at the table, no two adjacent philosophers may be eating at the same time. A scheduling problem arises as to who gets to eat at what time. This problem is similar to the problem of scheduling processes that require a limited number of resources.

What is the difference between software transactional memory and hardware transactional memory?

Software transactional memory (STM) implements transactional memory entirely in software, no special hardware is required. STM works by inserting instrumentation code inside of transaction blocks and typically requires the support of a compiler. Hardware transactional memory (HTM) implements transactional memory entirely in hardware using cache hierarchies and cache coherency protocols to resolve conflicts when shared data resides in separate caches.

Assume you had a function named update() that updates shared data. Illustrate how a mutex lock named mutex might be used to prevent a race condition in update().

void update()

{

mutex.acquire();

// update shared data

mutex.release();

}

Describe the turnstile structure used by Solaris for synchronization.

Solaris uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or a reader–writer lock. The turnstile is a queue structure containing threads blocked on a lock. Each synchronized object with at least one thread blocked on the object's lock requires a separate turnstile. However, rather than associating a turnstile with each synchronized object, Solaris gives each kernel thread its own turnstile.

Explain the role of the variable preempt_count in the Linux kernel

Each task maintains a value preempt_count which is the number of locks held by each task. When a lock is acquired, preempt_count is incremented. When a lock is released, preempt_count is decremented. If the task currently running in the kernel has a value of preempt_count > 0, the kernel cannot be preempted as the task currently holds a lock. If the count is zero, the kernel can be preempted.

Describe how an adaptive mutex functions

An adaptive mutex is used in the Solaris operating system to protect access to shared data. On a multiprocessor system, an adaptive mutex acts as a standard semaphore implemented as a spinlock. If the shared data being accessed is already locked and the thread holding that lock is running on another CPU, the thread spins while waiting for the lock to be released, and the data to become available. If the thread holding the lock is not in the run state, the waiting thread sleeps until the lock becomes available. On a single processor system, spinlocks are not used and the waiting thread always sleeps until the lock becomes available.

Describe a scenario when using a reader–writer lock is more appropriate than another synchronization tool such as a semaphore.

A tool such as a semaphore only allows one process to access shared data at a time. Reader–writer locks are useful when it is easy to distinguish if a process is only reading or reading/writing shared data. If a process is only reading shared data, it can access the shared data concurrently with other readers. In the case when there are several readers, a reader–writer lock may be much more efficient.

Explain how Linux manages race conditions on single-processor systems such as embedded devices.

On multiprocessor machines, Linux uses spin locks to manage race conditions. However, as spin locks are not appropriate on single processor machines, Linux instead disables kernel preemption which acquiring a spin lock, and enables it after releasing the spin lock.

Race conditions are prevented by requiring that critical regions be protected by locks.

True

The value of a counting semaphore can range only between 0 and 1.

False

A deadlock-free solution eliminates the possibility of starvation.

False

The local variables of a monitor can be accessed by only the local procedures.

True

Every object in Java has associated with it a single lock.

True

Monitors are a theoretical concept and are not practiced in modern programming languages

False

A thread will immediately acquire a dispatcher lock that is the signaled state

True

Mutex locks and counting semaphores are essentially the same thing.

False

Mutex locks and binary semaphores are essentially the same thing

True

A nonpreemptive kernel is safe from race conditions on kernel data structures

True

Linux mostly uses atomic integers to manage race conditions within the kernel

False

Disabling interrupts frequently can affect the system’s clock. Explain why this can occur and how such effects can be minimized.

The system clock is updated at every clock interrupt. If interrupts were disabled—particularly for a long period of time—it is possible the system clock could easily lose the correct time. The system clock is also used for scheduling purposes. For example, the time quantum for a process is expressed as a number of clock ticks. At every clock interrupt, the scheduler determines if the time quantum for the currently running process has expired. If clock interrupts were disabled, the scheduler could not accurately assign time quantums. This effect can be minimized by disabling clock interrupts for only very short periods

Explain why Windows, Linux, and Solaris implement multiple locking mechanisms. Describe the circumstances under which they use spin- locks, mutex locks, semaphores, adaptive mutex locks, and condition variables. In each case, explain why the mechanism is needed

These operating systems provide different locking mechanisms depending on the application developers’ needs. Spinlocks are useful for multiprocessor systems where a thread can run in a busy-loop (for a short period of time) rather than incurring the overhead of being put in a sleep queue. Mutexes are useful for locking resources. Solaris 2 uses adaptive mutexes, meaning that the mutex is implemented with a spin lock on multiprocessor machines. Semaphores and condition variables are more appropriate tools for synchronization when a resource must be held for a long period of time, since spinning is inefficient for a long duration.

What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer

Busy waiting means that a process is waiting for a condition to be satisfied in a tight loop without relinquishing the processor. Alternatively, a process could wait by relinquishing the processor, and block on a condition and wait to be awakened at some appropriate time in the future. Busy waiting can be avoided but incurs the overhead associated with putting a process to sleep and having to wake it up when the appropriate program state is reached

Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems

Spinlocks are not appropriate for single-processor systems because the condition that would break a process out of the spinlock can be obtained only by executing a different process. If the process is not relinquishing the processor, other processes do not get the opportunity to set the program condition required for the first process to make progress. In a multiprocessor system, other processes execute on other processors and thereby modify the program state in order to release the first process from the

spinlock.

Show that, if the wait() and signal() semaphore operations are not executed atomically, then mutual exclusion may be violated

A wait operation atomically decrements the value associated with a semaphore. If two wait operations are executed on a semaphore when its value is 1, if the two operations are not performed atomically, then it is possible that both operations might proceed to decrement the semaphore value, thereby violating mutual exclusion

Illustrate how a binary semaphore can be used to implement mutual exclusion among n processes.

The n processes share a semaphore, mutex, initialized to 1. Each process Pi is organized as follows:

do {

wait(mutex);

/* critical section */

signal(mutex);

/* remainder section */

} while (true);