Study Guide

Study the following:

1. Race condition

2. An example of race condition in a bounded-buffer solution for the

producer/consumer problem using a counter

3. Critical section problem, and requirements of solution to the critical-section

problem

4. Algorithms for the critical-section problem with two processes: two simple algorithms and their deficiencies, Peterson’s algorithm

5.Needs of handling of critical sections in OS, approach differs depends on if kernel is non-preemptive or preemptive

6. Hardware support for solving critical-section problem in preemptive kernel:

7. Disable interrupts, how it works, and its drawbacks

8. Provide atomic hardware instructions (e.g., test_and_set, swap) to be used to

implement “locking” mechanism, how it works, why such instructions are

needed, drawbacks

9. Solving critical-section problem using test_and_set:

10. Solution without bounded-waiting

11. Solution with bounded-waiting

12. Software support for solving critical-section problem:

13. Mutex lock

14. Semaphore (can be used for enforcing mutual exclusion and other

synchronization)

15. With busy waiting

16. Without busy waiting

17. Semaphore solution for classical problems of synchronization

18. Bounded-buffer problem

19. Readers and writers problem

20. Dining philosophers problem

21. Problems with semaphores

22. Incorrect use of semaphore operations

23. Deadlock and starvation possible

24. Monitor: what is it, and what does a monitor consist of?

25. Declaration of encapsulated data, including the shared data that need protection

26. Code for initialization of encapsulated data, if necessary

27. Procedures to provide operations on encapsulated data

28. Condition variables with wait and signal operations to support synchronization

requirements other than mutual exclusion

29. Implicit entry queue to restrict only one process to be active within the monitor

at a time

30. Monitor solution to the following problems

31. Dining philosophers problem

32. Bounded-buffer problem

33. Single resource allocation problem, with priority condition queue

34. Mechanisms provided on Linux: atomic integer, mutex lock, semaphore, spinlock, reader-writer versions of both semaphore and spinlock, conditional variable

Flash Cards:

Cooperating process: Can affect or be affected by the execution of another process

Race Condition: A situation in which two threads are concurrently trying to change the value of a variable

Process Synchronization: Coordination of access to data by two or more threads or processes.

Coordination: Ordering of the access to data by multiple threads or processes

A race condition can occur ____.: when several threads try to access and modify the same data concurrently

Critical Section: A section of code responsible for changing data that must only be executed by one thread or process at a time to avoid a race condition

Entry Section: Section of code requesting permission to enter the critical section

Exit Section: The section of code within a process that cleanly exits the critical section

Remainder Section: Whatever code remains to be processed after the critical and exit sections

Preemptive kernel: A type of kernel that allows a process to be preempted while it is running in kernel mode.

Nonpreemptive kernel: A type of kernel that 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(n) _______ refers to the section of the code which is accessing data that may be modified by another process executing concurrently.: critical section

_________ is the requirement that if a process is in its critical section, no other processes can be in their critical sections at the same time.: Mutual exclusion

Which of the following types of operating system kernel is free from race conditions?: Nonpreemptive kernel

To prove that Peterson's solution is correct for solving the critical-section problem:: 1. Mutual exclusion is preserved, 2. The process requirement is satisfied 3. The bounded-waiting requirement is met

In Peterson's solution, the ____ variable indicates if process i is ready to enter its critical section.: flag[i]

What best explains why Peterson's solution does not solve the critical section problem on modern computer architectures?: Modern computer architectures may reorder instructions

What is Peterson's Solution?: a software-based algorithm that uses two shared variables (a boolean flag array and a turn variable) rather than hardware locks to manage mutual exclusion

If one process is in the critical section, no other process is in it.: Mutual exclusion

If no process is in the critical section, the one that is waiting must be allowed to enter.: Progress

A time limit when the process waits before entering the critical section, between the time processes has requested access to their critical state and when it is actually granted.: Bounded waiting

Which of the following is NOT an algorithm used to solve the critical section problem?: Shailam's algorithm

In the turned-based approach, each process takes turns entering the critical section. What is the deficiency of this approach?: A process may wait if it does not need a critical section

In the flag-based approach, each process sets a flag to indicate it wants to enter the critical section. What is the deficiency of this approach?: Potential for deadlock or live lock

Why is handling needed for a critical section in OS?: Many kernel-mode processes may be active in the OS that need to manipulate shared data structures

New processes have to wait until the running process is done and has easier to manage critical section: Non-preemptive kernel

Allows a running process to be interrupted by a high-priority process and has more complex handling: Preemptive kernel

Strongly ordered (memory model): memory modification on one processor is immediately visible to all other processors

Weakly ordered (memory model): memory modifications to memory on one processor may not be immediately visible to other processors

How computer architecture determines what memory guarantees it will prove to an application program is known as its ________.: memory model

If lock = 0, the function call compare_and_swap(&lock,0,1) sets lock to ____ and returns _____. a. 0, 0, b. 0, 1, c. 1, 0, d. 1, 1: 1, 0

A _________ instruction ensures that all loads and store operations are completed before additional load and store operations are performed. a. memory barrier, b. atomic variable, c. memory model, d. single variable: memory barrier

An instruction that executes atomically ________. a. must consist of only one machine instruction, b. executes as a single, uninterruptible unit, c. cannot be used to solve the critical section problem, d. executes as multiple, interruptible units: executes as a single, uninterruptible unit

Computer architecture memory guarantee, usually either strongly ordered or weakly ordered.: memory model

Computer instructions that force any changes in memory to be propagated to all other processors in the system.: memory barriers and fences

A programming language construct that provides atomic operations on basic data types such as integers and booleans.: atomic variable

One hardware support for solving the critical-section problem is to disable interrupts during critical section execution. What is the drawback to this support?: Not good for multiprocessor systems and reduced system responsiveness

What are the two instructions to atomic hardware?: "test_and_set" and "swap"

Test_and_Set Without Bounded-Waiting: No process is forced to wait for available resources, and no process can wait forever.

Test_and_set With Bounded-Waiting: Once a process intends to enter the critical section, it will only be passed by other processors for a limited time. Depends on the total number of processes.

In Mutex Lock, the critical section is protected using ________ and ________.: acquire() and release()

What is the correct ordering for solving the critical section problem using mutex locks?: acquire, critical section, release, remainder section

A mutex lock ____. a. is another term for a boolean variable, b. can be used to solve the critical section problem, c. is not guaranteed to have atomic operations, d. is a password for the linux/unix system: can be used to solve the critical section problem

What is the best scenario for implementing a mutex lock as a spinlock? a. On a single-core system where the lock is held for a short duration., b. On a multi-core system where the lock is held for a long duration., c. On a multi-core system where the lock is held for a short duration., d. On a single-core system where the lock is held for a long duration.: On a multi-core system where the lock is held for a short duration.

Which of the following code statements correctly fixes the race condition in the deposit() function using a mutex lock with the acquire() and release() operations?

double deposit(double amount) { -- code here --}: acquire(); balance += amount; release(); return balance;

Which of the following code statements correctly fixes the race condition in the withdraw() function using a mutex lock with the acquire() and release() operations? double withdraw(double amount) {-- code here --}: acquire(); if (amount <= balance) {balance -= amount;} release(); return balance;

A lock is considered ________ if a thread blocks while trying to acquire the lock. If a lock is available when a thread attempts to acquire it, the lock is considered ________.: contended; uncontended

What is busy waiting?: A practice that allows a thread or process to use CPU time continuously while waiting for something. An I/O loop in which an I/O thread continuously reads status information while waiting for I/O to complete

What is spinlock?: A locking mechanism that continuously uses the CPU while waiting for access to the lock

To use a binary semaphore to solve the critical section problem, the semaphore must be initialized to 1 and _____ must be called before entering a critical section and _____ must be called after exiting the critical section. a. wait(), signal(), b. signal(), wait(), c. Mutex locks - not semaphores - are used to solve the critical section problem.: wait(), signal()

True or False: a counting semaphore can be used as a binary semaphore-: True

________ can be used to prevent busy waiting when implementing a semaphore.: Waiting queues

A semaphore ________ . a. contains an integer value, b. is not guaranteed to have atomic operations, c. Uses the same acquire() and release() operations as a mutex lock.: contains an integer value

Which of the following statements are false?: Semaphores are equivalent to mutex locks.

A monitor ________ . a. represents programmer-defined data and a set of functions that provide mutual exclusion, b. is similar to a semaphore, c. allows multiple threads to be active within the monitor at the same time-: represents programmer-defined data and a set of functions that provide mutual exclusion

A process that calls the wait() function on a condition variable is blocked ________. a. only if another process is active in the monitor, b. until another process calls signal() on the condition variable, c. only if at least 1 other process has also called wait() on the condition variable: until another process calls signal() on the condition variable

Which of the following is not considered a liveness failure? a. Deadlock, b. Indefinite waiting, c. A race condition: A race condition

____________ can occur when a higher-priority process needs to access a data structure that is currently being accessed by a lower-priority process. a. Priority inversion, b. Deadlock, c. Infinite loop: Priority inversion

A set of properties that a system must satisfy to ensure that processes make progress during their execution life cycle.: Liveness

The state in which two processes or threads are stuck waiting for an event that can only be caused by one of the processes or threads.: Deadlocked

A scheduling challenge arising when a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process.: Priority inversion

A protocol for solving priority inversion in which all processes that are accessing resources needed by a higher-priority process inherit that higher priority until they are finished with the resources in question.: Priority-inheritance protocol

Under _______ loads, CAS protection will be faster than traditional synchronization.: Moderately-contended

Under ______ loads, both traditional and CAS-based protection will be fast.: Uncontended

What is the purpose of the semaphore mutex in the implementation of the bounded-buffer problem using semaphores?: It ensures mutual exclusion

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

What best describes the situation in the dining philosophers problem if all five philosophers attempt to eat at the same time?: Deadlock will occur

A Windows dispatcher object is available when the dispatcher object is in a ______ state.: signaled

On SMP machines the fundamental locking mechanism in the Linux kernel is _____.: a spinlock

What best describes the advantage of POSIX named semaphores? a. The functions for using a named semaphore are easier for programmers to work with than unnamed semaphores., b. Only POSIX named semaphores can be provided an initial value., c. Multiple, unrelated processes can use a named semaphore and only threads belonging to the same process can use an unnamed semaphore.: Multiple, unrelated processes can use a named semaphore and only threads belonging to the same process can use an unnamed semaphore.

How do POSIX condition variables provide mutual exclusion? a. By using a condition variable within a monitor., b. By associating a condition variable with a mutex lock., c. Mutual exclusion is part of the condition variable type.: By associating a condition variable with a mutex lock.

A call to pthread_cond_signal() ________. a. releases the mutex lock and signals one thread waiting on the condition variable, b. signals one thread waiting on the condition variable, but does not release the mutex lock, c. signals all threads waiting on the condition variable, but does not release the mutex lock: signals one thread waiting on the condition variable, but does not release the mutex lock

race condition: A situation in which two threads are concurrently trying to change the value of a variable.

process synchronization: Coordination of access to data by two or more threads or processes.

coordination: Ordering of the access to data by multiple threads or processes.

critical section: A section of code responsible for changing data that must only be executed by one thread or process at a time to avoid a race condition.

entry section: The section of code within a process that requests permission to enter its critical section.

exit section: The section of code within a process that cleanly exits the critical section.

remainder section: Whatever code remains to be processed after the critical and exit sections.

preemptive kernel: A type of kernel that allows a process to be preempted while it is running in kernel mode.

nonpreemptive kernels: A type of kernel that 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.

Mutual exclusion: The requirement that if a process is in its critical section, no other processes can be in their critical sections at the same time.

flag[ i ]: In Peterson's solution, this variable indicates if process i is ready to enter its critical section.

Modern computer architectures may reorder instructions: What best explains why Peterson's solution does not solve the critical section problem on modern computer architectures?

Peterson's solution: A historically interesting algorithm for implementing critical sections.

memory model: Computer architecture memory guarantee, usually either strongly ordered or weakly ordered.

memory barriers/memory fences: Computer instructions that force any changes in memory to be propagated to all other processors in the system.

atomically: A computer activity (such as a CPU instruction) that operates as one uninterruptable unit.

atomic variable: A programming language construct that provides atomic operations on basic data types such as integers and booleans.

mutex lock: A mutual exclusion lock; the simplest software tool for assuring mutual exclusion.

contended: A term describing the condition of a lock when a thread blocks while trying to acquire it.

uncontended: A term describing a lock that is available when a thread attempts to acquire it.

busy waiting: A practice that allows a thread or process to use CPU time continuously while waiting for something. An I/O loop in which an I/O thread continuously reads status information while waiting for I/O to complete.

spinlock: A locking mechanism that continuously uses the CPU while waiting for access to the lock.

waiting queues: can be used to prevent busy waiting when implementing a semaphore

semaphore: An integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal().

counting semaphore: A semaphore that has a value between 0 and N, to control access to a resource with N instances.

binary semaphore: A semaphore of values 0 and 1 that limits access to one resource (acting similarly to a mutex lock).

monitor: A high-level language synchronization construct that protects variables from race conditions.

abstract data type (ADT): A programming construct that encapsulates data with a set of functions to operate on that data that are independent of any specific implementation of the ADT.

conditional-wait: A component of the monitor construct that allows for waiting on a variable with a priority number to indicate which process should get the lock next.

priority number: A number indicating the position of a process in a conditional-wait queue in a monitor construct.

liveness: A set of properties that a system must satisfy to ensure that processes make progress during their execution life cycle.

deadlocked: The state in which two processes or threads are stuck waiting for an event that can only be caused by one of the processes or threads.

priority inversion: A scheduling challenge arising when a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process.

priority-inheritance protocol: A protocol for solving priority inversion in which all processes that are accessing resources needed by a higher-priority process inherit that higher priority until they are finished with the resources in question.

Uncontended: Although both options are generally fast, CAS protection will be somewhat faster than traditional synchronization.

Moderate contention: CAS protection will be faster—possibly much faster—than traditional synchronization.

High contention: Under very highly contended loads, traditional synchronization will ultimately be faster than CAS-based synchronization.

lock: An algorithm that provides protection from race conditions without requiring the overhead of locking.

readers-writers problem: A synchronization problem in which one or more processes or threads write data while others only read data.

reader-writer lock: A lock appropriate for access to an item by two types of accessors, read-only and read-write.

dining-philosophers problem: A classic synchronization problem in which multiple operators (philosophers) try to access multiple items (chopsticks) simultaneously.

dispatcher objects: A Windows scheduler feature that controls dispatching and synchronization. Threads synchronize according to several different mechanisms, including mutex locks, semaphores, events, and timers.

event: A Windows OS scheduling feature that is similar to a condition variable.

critical-section object: A user-mode mutex object that can often be acquired and released without kernel intervention; a Windows OS scheduling feature.

named semaphore: A POSIX scheduling construct that exists in the file system and can be shared by unrelated processes.

unnamed semaphore: A POSIX scheduling construct that can only be used by threads in the same process.

entry set: In Java, the set of threads waiting to enter a monitor.

wait set: In Java, a set of threads, each waiting for a condition that will allow it to continue.

scope: The time between when a lock is acquired and when it is released.