Concurrency

Question 1

independent processes

Answer 1

can’t be affected by others and vice versa

Question 2

cooperating processes

Answer 2

can be affected and can affect other processes

Question 3

reasons for communication

Answer 3

• information sharing
• computational speedup (e.g. breaking down a big task to multiple small tasks)
• modularity (system is divided into modules that need to communicate)
• convenience (multitasking by the user, e.g. listening to music while writing a document)

Question 4

Ctrl+Z

Answer 4

suspends a process, doesn’t terminate

Question 5

signal types

Answer 5

Hardware-induced (e.g., SIGILL)
Software-induced (e.g., SIGQUIT or SIGPIPE)

Question 6

actions

Answer 6

term
ign
core
stop
cont

Question 7

catching signals

Answer 7

• Process registers signal handler
• OS delivers signal and allows process to run handler
• Current execution context needs to be saved/restored

Question 8

kernel delivers the signal

Answer 8

→ Stops code currently executing (after saving contacts- states of registers- of the current program)
→ Saves context
→Executes signal handling code
→Restores original context

Question 9

signal info pushed onto the stack

Answer 9

floating point state
ucontext: SP and IP
siginfo - info about the signal
sigreturn - SP; address to where to return after the signal handler finishes

Question 10

upon sigreturn, the kernel

Answer 10

• can simply take all the state on top of stack
• and restore:RIP = …
  RSP = …
  RAX = …
  RBX = …
  etc.
• vulnerability: not stored in the kernel so it can be modified by an user

Question 11

reasons for synchronisation

Answer 11

• To account for dependencies
• To avoid processes getting in each other’s way
• Also applies to multithreaded execution

Question 12

fork()

Answer 12

• creates a separate, duplicate process
  
  • new PID
  • continues after

Question 13

exec()

Answer 13

• the program specified in the parameter will replace the entire process - including all threads
  
  • same PID
  • doesn’t continue after

Question 14

race conditions

Answer 14

a situation in which 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

Question 15

spooler directory

Answer 15

a designated area where files are temporarily stored while they are being processed by a program or service, typically related to printing or job management

Question 16

critical region

Answer 16

a code region with access to shared resources

Question 17

requirements to avoid race conditions

Answer 17

1. No two processes may be simultaneously in their critical regions
2. No assumptions may be made about speeds or number of CPUs
3. No process running outside its critical region may block others
4. No process should have to wait forever to enter its critical region

Question 18

a solution to the critical region problem must satisfy

Answer 18

1. mutual exclusion: when one process is executing in its critical region, no other process is to be allowed to execute in its critical region
2. progress: no process should have to wait forever to enter its critical region
3. bounded waiting: there exists a bound 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 the request is granted

Question 19

Peterson’s solution

Answer 19

when a process wants to enter its critical region it sets its flag to true and it will set the turn to the other process, i.e. it gives the turn to the other process

Question 20

semaphore

Answer 20

• a nonnegative int variable shared between processes
• it can be accesses through two standard atomic operations: wait() and signal()

Question 21

semaphore idea

Answer 21

• Idea: introduce a special semaphore integer type with 2 operations:
  
  • down (wait):
    
    • if semaphore ≤ 0 then block the calling process
    • semaphore = semaphore - 1 otherwise
  • up (signal):
    
    • if there is a process blocking on semaphore, wake it up
    • semaphore = semaphore + 1 otherwise
  • OS guarantees all the operations are atomic by design
    
    • Disable interrupts on single processors
  • Spin locking on multiprocessors

Question 22

binary seamphores

Answer 22

mutex locks
only 0 or 1

Question 23

spinlock semaphore

Answer 23

busy waiting wastes CPU cycles that some other process might be able to use - the process “spins” while waiting for the lock

Question 24

Readers/Writers

Answer 24

• Idea: Build a queue of readers and writers
• Let several readers in at the same time
• Allow 1 writer when no readers are active
• How long may the writer have to wait?

Question 25

monitors

Answer 25

- more structured approach towards process synchronisation: - serialise the procedure calls on a given module - use condition variables to wait / signal processes - a monitor type presents a set of programmer-defined operations that provide mutual exclusion the monitor - requires dedicated language support

Question 26

shared memory systems

Answer 26

the shared memory region is typically in the address space of the process creating the shared-memory segment the other process attaches the region to its address space the processes can access each others memory (since the area is in the address spaces)

Question 27

unbounded buffer

Answer 27

no size limit ⇒ the consumer might have to wait for new items, but the producer can always produce new items

Question 28

bounded buffer

Answer 28

size limit ⇒ the producer must wait if the buffer is full, the consumer has to wait if its empty

Question 29

message passing

Answer 29

- allows processes to communicate and synchronise their actions without sharing the same address space - particularly useful in a distributed environment, where the communicating processes may reside on different computers connected by a network - Most common choice in multi-server OS designs

Question 30

message passing messages

Answer 30

send(destination, &message); receive(source, &message); receive(ANY, &message);

Question 31

priority inversion

Question 32

Read-Copy-Update

Answer 32

- An instance of **relativistic programming** - Do not try to avoid conflicts between readers and writers; tolerate them and ensure a correct result regardless of the order of events - Allow writer to update data structure even if other processes are still using it. - Parallel copies of a data structure. - Ensure that each reader either reads the old or the new version, but not some weird combination of the 2. - single-pointer readers/writers scheme

Question 33

marshalling

Answer 33

packing the parameters into a form that can be transmitted over a network

Question 34

RPC

Answer 34

protocol that one program can use to request a service from a program located in another computer on a network without having to understand the network’s details

Question 35

The bounded buffer problem

Answer 35

- also producer-consumer problem - the producer must not insert data when the buffer is full - the consumer must not remove data when the buffer is empty - the producer and consumer should not insert and remove data simultaneously

Question 36

The dining philosophers problem

Answer 36

resource allocation problem