Thread Interaction Flashcards
Where does thread interaction operations occur at?
They occur at the OS Kernel level. They are second important functional area of a OS microkernel beside thread management.
What are the types of interactions between threads and the relation between them? Where is the interaction object located?
Communication, Cooperation and Coordination.
Both communication and cooperation require coordination (in time) between threads.
The interaction object may be located at the source thread (sender), target thread (receiver) or between the threads.
An interaction may include more than two threads and more than one interaction object.
Describe the concept of coordination in relation to mutual exclusion?
Coordination at the kernel level requires mutual exclusion since coordinating threads are accessing critical sections which need to be reserved/protected to be safe (accessing shared data in the kernel level).
Here we deal with coordination outside the kernel level.
What is signaling? its goal and what kernel OPs allow for it?
The goal of signaling is to establish a temporal order of activities.
Section A in thread T1 is to be executed prior to a section B in another thread T2. When section A in thread T1 is done executing, a signal is sent for which thread T2 is waiting and it can then start executing its section B.
Kernel OPs signal (at T1) and wait (busy waiting at T2) that use a shared binary variable s allow for signaling between threads.
What mutual synchronization?
It is when two threads T1 and T2 wait for each at one execution point. It is equivalent to two signal and wait operations.
What is group signaling? What are the two types of it?
Group signaling is when more than 2 threads are participating in a signaling operation.
AND-Signaling: A thread is allowed to proceed only when several threads have sent a signal (AND-OP at signal side)
AND-Wait: Several threads wait for a signal from another thread (AND-operation at wait side)
AND-Signaling-Wait: Multiple threads are waiting for all other multiple threads to send a signal.
What is signaling with buffering?
n:1 signaling: Many threads may deposit signals at a signaling object. A waiting thread is deblocked if at least one signal is stored.
1:m signaling: Many threads may wait at a signaling object. When a signal arrives, one of the waiting threads (for example, the first one) is deblocked.
Both cases combined lead to arbitrary n:m relations. Here we have a queue of waiting threads in which we add blocked threads on the wait call and increase the count and then deblock the first waiting thread in the queue and decrease count on signal sent. The capacity initial value is what determines the n:m signaling relation.
What is mutual group synchronization?
All threads synchronize mutually at the same point. The threads may continue only when all other threads have reached the same synchronization point.
What are locks?
Used to secure critical sections for mutually exclusive executions in two threads. Using the OPs lock and unlcok to set/reset a variable set. The first thread that calls lock(s) continues its execution and sets the s variable while the second thread that calls lock(s) gets blocked and only deblocked when the first thread calls unlock(s) after finishing executing its critical section.
Describe the structure of a channel object, its parameters and operations, and describe the implementation depending on the order of sending/receiving and what are the variants of this message transfer. What type of communication is this?
A channel is a data object that provides send and receive OPs.
It has the name of the channel object (CO) and the address of the message buffer to send and address where the received message should be written.
OPs: send(CO, buffer_send), receive(CO, buffer_receive)
- First send, then receive: msg is stored in CO and can be retrieved later in the receive OP (by copying msg in the receive buffer).
- First receive, then send: receive buffer address is stored on receiver thread, send OP later copies the message to that address.
Variants of the message transfer include:
- By value: msg itself is buffered in the channel (two copy OPs)
- By reference: the address of the message is buffered in the channel (one copy OP)
Since sender and receiver do not wait for their communication partner, this is called asynchronous communication.
What are the 4 types of coordinated communication?
- Async send / Async receive: receiver and sender do not wait for each other.
- Async send / Sync receive: receiver is blocked until the sender sends the message
- Sync send / Async receive: sender sends message and is blocked until the receiver retrieves it
- Sync send / Sync Receive: Mutual sync where both sender and receiver are blocked and wait for receiving / sending the message respectively.
What is polling/probing in terms of sending/receiving a message?
It is with a async send and on the receiver end, when it calls receive, if there is a message it takes it (copy), if not, it just continues its normal execution.
Describe how to achieve the ability to buffer more than one message then the ability to buffer many receive operations? How to adapt the data structures for this purpose and what problem may arise?
- Buffer more than one message: Many threads send messages to a central server thread through a n:1 channel object.
- Buffer many receive operations: One thread sends a message to a 1:n channel object with a server consisting of many replicated threads with receive requests the from the shared 1:n channel
- Many messages and many receivers: Combine both solutions
The channel object data structure must include a queue for waiting senders, queue for stored messages, queue for waiting receivers, queue for stored target buffer addresses depending on the use case. The capacity of the channel object can be unlimited (requires dynamic memory management) or limited (requires mechanisms for overflow by overwritting, refusing OP or blocking until capacity is available again depending on the application).
Describe how to physically assign a channel object to a specific thread?
When channel objects are statically/physically assigned to a thread. It can be done at either sides:
- Sender thread owns the channel to deposit all outgoing messages, in this case it is called an exit port. Exit ports are 1:n.
- Receiver thread owns the channel from which it receives all messages, it is called an entry port. Entry ports are n:1 channels. They are the most commonly used communication objects in today’s OSs.
Describe group communication and its variants.
-In one-to-one channel communication (single cast), we have one thread sending a message which is received by exactly one other thread.
- In one-to-many channel communication (broadcast, multicast, replication), we have a thread that sends identical messages to many receiver threads in one operation.
- In many-to-one channel communication (combination), we have many threads sending messages to one receiver thread that receives a combination of the messages in one operation.
- many-to-many channel communication (all-to-all broadcast): we have a combination of both of the above.
