Synchronization Tools

Question 1

Why do processes and threads cooperate with each other? (3 things)

Answer 1

• information sharing
• computation speed up
• Modularity

Question 2

Data can be shared with _____ ______ or _______ ________

Answer 2

shared memory, message passing

Question 3

In shared memory, process A ____ shared memory, process B _____ this memory to their own _____ space and then is treated as ______ memory

Answer 3

creates, attaches, address, regular

Question 4

In shared memory, ________ is needed to coordinate conflicting accesses

Answer 4

synchronization

Question 5

POSIX APIs to shared memory synchronization include ______, _____ and ____

Answer 5

shm_open, shm_at, mmap

Question 6

In message passing, process A sends message to B via _______

Answer 6

kernel

Question 7

In message passing, processes can ____ for the message to be delivered

Answer 7

wait

Question 8

The pros of shared memory is ______ and _______

Answer 8

speed, convenience

Question 9

The cons of shared memory is having to ______ conflicts

Answer 9

manage

Question 10

The pros of message passing is that there is no ______ and it is easy to _____ messages

Answer 10

conflict, exchange

Question 11

The cons of message passing include high _______, ______ involvement, and the usage of several ______

Answer 11

overhead, kernel, syscalls

Question 12

In the producer consumer problem, 2 _______ share a _______

Answer 12

threads, buffer

Question 13

In the producer consumer problem, the producer places ______ into the buffer and must wait if it is ____

Answer 13

items, full

Question 14

In the producer consumer problem, the consumer _____ items from the buffer and must wait if it is _____

Answer 14

takes, empty

Question 15

In the producer consumer problem, we can coordinate producer and consumer by keeping a ______ on the # of items in the buffer

Answer 15

counter

Question 16

In the producer consumer problem, how is count++ implemented?

Answer 16

register1 = count
register1 = register1 + 1
count = register1

Question 17

In the producer consumer problem, how is count– implemented?

Answer 17

register2 = count
register2 = register2 -1
count = register2

Question 18

In the producer consumer problem, consumers and producers run on the ____ core or _______ cores in parallel

Answer 18

same, different

Question 19

In the producer consumer problem, the CPU scheduler can switch between producer and consumer at ___ time

Answer 19

any

Question 20

In the producer consumer problem, when can the counter start at 6, call count++, call count–, and end up at 7?

Answer 20

When the CPU decides to swap the process to the consumer and finish the consumer process before the producer finishes

Question 21

What is a race condition?

Answer 21

When multiple processes manipulate shared data concurrently and the result depends on the order of manipulation

Question 22

A ______ _____ is code that manipulates shared data

Answer 22

critical section

Question 23

To handle race conditions, make sure that when one _______ is executing the __, no other processes can

Answer 23

process, CS

Question 24

What 3 requirements must be satisfied for a solution the CS problem?

Answer 24

• Mutual Exclusion
• Progress
• Bounded Waiting

Question 25

Mutual Exclusion makes sure there is only ____ thread allows in the CS

Answer 25

one

Question 26

Progress means that the thread should eventually _______

Answer 26

complete

Question 27

Bounded Waiting means the process must wait for a _____ amount of time

Answer 27

finite

Question 28

On _____________ systems, the CS problem can be solved by disabling _________ and ________

Answer 28

uniprocessor, interrupts, preemption

Question 29

A problem on making a solution for the CS problem on a uniprocessor system is that users can make a ______ CS making the system _________

Answer 29

large, unresponsive

Question 30

Solutions for the CS problem on multicore systems can use ______ only or be supported with _______

Answer 30

software, hardware

Question 31

_______ solution is a software solution to the CS problem for only _____ processes

Answer 31

Peterson's, two

Question 32

Peterson's solution assumes ____ and ______- are atomic

Answer 32

load, store

Question 33

Peterson's solution requires what 2 shared data items?

Answer 33

- integer named turn | - Boolean array named flag[2]

Question 34

What does the turn value in peterson's solution manage?

Answer 34

whose turn it is to enter CS

Question 35

What does the flag value in peterson's solution manage?

Answer 35

hether the process/thread is ready to enter CS

Question 36

Describe Peterson's solution in code

Answer 36

``` do { flag[i] = true; turn = j; while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true); ```

Question 37

Does Peterson's algorithm satisfy the 3 requirements?

Answer 37

yes

Question 38

Modern machines provide special _______ instructions that cannot be interrupted

Answer 38

atomic

Question 39

What does atomic swap do?

Answer 39

update the memory word with new value and return the old value

Question 40

What does Compare and swap do?

Answer 40

update one memory word if its original value matches a given value

Question 41

Describe a simple spinlock using atomic_swap

Answer 41

``` while(atomic_swap(&lock, 1)) { /* Do nothing */ } critical section lock = 0; remainder section ```

Question 42

Describe a simple spinlock using compare and swap

Answer 42

``` while(compare_and_swap(&lock, 0, 1)) { /* Do nothing */ } critical section lock = 0; remainder section ```

Question 43

Both simple spinlocks using atomic_swap and compare_and_swamp can cause _______ _______

Answer 43

indefinite waiting

Question 44

What are 2 software tools that are provided by libraries that can solve CS problems?

Answer 44

Mutex locks and semaphores

Question 45

_____ locks have an atomic acquire and release

Answer 45

Mutex

Question 46

Mutex/Spin locks can waste ____ _______, but prevents context switches

Answer 46

CPU cycles

Question 47

_______ _____ are widely used on multiprocessor systems

Answer 47

mutex locks

Question 48

A ________ is an integer variable accessed through two atomic operations: wait and signal

Answer 48

semaphore S

Question 49

What do semaphores do?

Answer 49

They control access to a finite number of instances of some resource

Question 50

In semaphores, wait ______ access to resources and signal _______ access

Answer 50

gains, releases

Question 51

In semaphores, S is initialized to the _____ of resource instances available

Answer 51

number

Question 52

In semaphores, S == 0 implies all _____ are being used

Answer 52

resources

Question 53

A binary semaphore is similar to a _____

Answer 53

mutex

Question 54

A _______ semaphore can be any integer value

Answer 54

counting

Question 55

What are the 3 use cases of semaphores?

Answer 55

- Ensuring mutual exclusion - Synchronizing steps in different processes - Controlling access to finite resources

Question 56

A busy-waiting semaphore keeps _________ in the wait call and may waste ____ __________, but improves _______ time

Answer 56

spinning, CPU, cycles, response

Question 57

A non-busy-waiting semaphore ______ up the CPU when while waiting

Answer 57

frees

Question 58

A non-busy-waiting semaphore has an additional _____ ______ in its struct

Answer 58

wait list

Question 59

A non-busy-waiting semaphore has 2 internal operations: _____ and ________

Answer 59

block, wakeup

Question 60

A non-busy-waiting semaphore's block operation _______ the process that invokes it, placing it in the ________ queue

Answer 60

suspends, waiting

Question 61

A non-busy-waiting semaphore's wakeup operation _______ the execution of a ______ process, placing it in the _______ queue

Answer 61

resumes, blocked, ready

Question 62

In semaphores, _____ and ______ operations must become ______ _________

Answer 62

wait, signal, CS

Question 63

A non-busy-waiting semaphore does not completely remove busy waiting. why?

Answer 63

The busy waiting just got shifted from application-level CS entry to semaphore's wait and signal commands, which are very short

Question 64

Why would we want to move busy waiting to the semaphore level rather than the user's CS?

Answer 64

User application may run for a long time, busy waiting can be costly

Question 65

How can we use semaphores so that process 2 runs after process 1?

Answer 65

``` Semaphore synch (0); Process 1 - Statement S1 - signal (synch) Process 2 - wait(synch) - Statement S2 ```

Question 66

When can a dead lock occur using semaphores?

Answer 66

if P0 acquires S while P1 holds Q, P0 and P1 will wait for each other indefinitely