Concurrency Flashcards
independent processes
can’t be affected by others and vice versa
cooperating processes
can be affected and can affect other processes
reasons for communication
- 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)
Ctrl+Z
suspends a process, doesn’t terminate
signal types
Hardware-induced (e.g., SIGILL)
Software-induced (e.g., SIGQUIT or SIGPIPE)
actions
term
ign
core
stop
cont
catching signals
- Process registers signal handler
- OS delivers signal and allows process to run handler
- Current execution context needs to be saved/restored
kernel delivers the signal
→ Stops code currently executing (after saving contacts- states of registers- of the current program)
→ Saves context
→Executes signal handling code
→Restores original context
signal info pushed onto the stack
floating point state
ucontext: SP and IP
siginfo - info about the signal
sigreturn - SP; address to where to return after the signal handler finishes
upon sigreturn, the kernel
- 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
reasons for synchronisation
- To account for dependencies
- To avoid processes getting in each other’s way
- Also applies to multithreaded execution
fork()
- creates a separate, duplicate process
- new PID
- continues after
exec()
- the program specified in the parameter will replace the entire process - including all threads
- same PID
- doesn’t continue after
race conditions
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
spooler directory
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
critical region
a code region with access to shared resources
requirements to avoid race conditions
- No two processes may be simultaneously in their critical regions
- No assumptions may be made about speeds or number of CPUs
- No process running outside its critical region may block others
- No process should have to wait forever to enter its critical region
a solution to the critical region problem must satisfy
- mutual exclusion: when one process is executing in its critical region, no other process is to be allowed to execute in its critical region
- progress: no process should have to wait forever to enter its critical region
- 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
Peterson’s solution
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
semaphore
- a nonnegative int variable shared between processes
- it can be accesses through two standard atomic operations: wait() and signal()
semaphore idea
- 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
- down (wait):
binary seamphores
mutex locks
only 0 or 1
spinlock semaphore
busy waiting wastes CPU cycles that some other process might be able to use - the process “spins” while waiting for the lock
Readers/Writers
- 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?
monitors
- 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
shared memory systems
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)
unbounded buffer
no size limit ⇒ the consumer might have to wait for new items, but the producer can always produce new items
bounded buffer
size limit ⇒ the producer must wait if the buffer is full, the consumer has to wait if its empty
message passing
- 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
message passing messages
send(destination, &message);
receive(source, &message);
receive(ANY, &message);
priority inversion
Read-Copy-Update
- 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
marshalling
packing the parameters into a form that can be transmitted over a network
RPC
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
The bounded buffer problem
- 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
The dining philosophers problem
resource allocation problem
