Process Synchronization

Front 1

Why allow cooperating processes/threads?

Back 1

§ Speedup – overlap I/O and Computation, take
advantage of parallelism for multiprocessor systems
§ Modularity – divide and conquer

Front 2

Why are cooperating processes important?

Back 2

Need to ensure correct operation with concurrent processes/threads
§ If process/thread scheduler can schedule threads in any way, programs must work under all circumstances
§ Processes/threads can be run truly concurrently or interleaved in any manner

Front 3

why can Cooperating processes affect each other’s execution?

Back 3

They share a logical address space or share data through files and messages

Front 4

Why can Concurrent access to shared data result in intermittent incorrect behavior?

Back 4

Because the outcome may be affected by concurrency or interleaving of the execution

Front 5

Scheduling order does not affect operation

Back 5

Independent processes

Front 6

Shared state between threads, scheduling order can affect operation without proper synchronization among processes/threads

Back 6

Cooperating processes/threads

Front 7

When several processes access and
manipulate the same data concurrently and the outcome of the execution depends on the order in which the access takes place

Back 7

Race Condition

Front 8

What should happen to ensure correct operation in certain code sequences?

Back 8

They should be uninterruptable and/or should
not be executed at the same time in more than one process/thread (critical section)

Front 9

Why are race conditions bad?

Back 9

Race conditions lead to non-deterministic behavior

Front 10

How can race conditions be avoided?

Back 10

Ensure that only one of process
can manipulate shared data at a time

Front 11

Ensuring that only one thread does a
particular thing at a time

Back 11

Mutual Exclusion (One thread excludes the others while doing its task)

Front 12

Piece of code that only one thread can
execute at once. Only one thread at a time will get into this section of code.

Back 12

Critical Section (requires mutual exclusion )

Front 13

What requirements should be satisfied by a solution to the critical section problem?

Back 13

Mutual Exclusion

Progress

Bounded waiting

Front 14

If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are looking to enter their critical sections decide
which process will enter its critical section next and this selection cannot be postponed indefinitely

Back 14

Progress

Front 15

There must exist a bound on the number of
times other processes are allowed to enter their critical section after a process has made a request to enter its critical section and
before it is allowed to

Back 15

Bounded waiting (avoid starvation)

Front 16

Use a turn variable to signal whose turn it is to enter the critical section as well as a flag per process that indicates whether a process wants to enter its critical section

Back 16

Peterson’s Algorithm

Front 17

Locking mechanism to
ensure mutual exclusion

Back 17

Disabling Interrupts

/* disable interrupts */
/* critical section */

/* enable interrupts */

Front 18

Problems with disabling interrupts

Back 18

§ Does not guarantee mutual exclusion for multiprocessor systems (disabling interrupts across multiprocessors is expensive; message passing)
§ Limits the ability of the OS to provide timesharing
§ Could allow a process to monopolize the processor

Front 19

Use a variable to lock access to critical section
Need hardware support to guarantee an update to a lock variable cannot be interrupted

(needs to be an atomic operation )

Back 19

Lock Variables

Front 20

Problems with Lock variables approach

Back 20

•Busy waiting is employed
•Starvation is possible, because selection of next process to enter
critical section is arbitrary

Front 21

Problems with Busy Waiting

Back 21

• Very inefficient because waiting process
consumes CPU cycles (depends on time to unlock, if short then busy wait is preferable to waiting with a context switch)
• Waiting process may take cycles away from
process that is holding the lock

Front 22

§ Priority Inversion for Strict Priority Scheduler

Back 22

• If busy-waiting thread has higher priority than
thread holding lock ---> no progress
§ the high priority process that busy waits never lets lower priority process finish its critical section

Front 23

Integer that is accessed through two
atomic operations

Back 23

Semaphores

Front 24

Problems with semaphores

Back 24

§ A process will busy wait or spin waiting for the semaphore (this type of semaphore is also referred to as a spinlock)
§ Good when the wait time is short, context switch can be avoided
§ Bad when the wait time is long, waste CPU cycles constantly checking semaphore status

Front 25

Binary semaphore

Back 25

only two values (0, 1)

Front 26

Used when there are a finite number of instances of some resource

Back 26

Counting semaphore

Front 27

Who and in which year were semaphores introduced?

Back 27

Edsgar Dijkstra in the late 1960s

Front 28

How can busy waiting be fixed?

Back 28

changing implementation of
wait() to cause a process to block itself if the semaphore is not positive (• waiting process gets put on a waiting queue associated with the semaphore & • signal() is changed to wakeup the process at the head of the wait queue
for the semaphore)

Front 29

Since processes are queued as they wait on a semaphore, name one
method to determine the next process that can be employed

Back 29

Process Scheduling

Front 30

• P0 executes wait(S) and acquires this semaphore
• P1 execute wait(Q) and acquires this semaphore
• P0 blocks on the call to wait(Q)
• P1 blocks on the call to wait(S)

Back 30

Example of Deadlock since neither process will be receive the signal() they are waiting for

Front 31

Allow a process to inherit
the priority of a higher priority process that is
waiting until this process complete is use of a
resource

Back 31

Priority Inheritance

Front 32

A lower priority process M, is able to affect the
performance of process H

Back 32

Priority Inversion