* Mode
- Process Contention Scope
- System Contention Scope
* Types
- Time Sharing with Equal or Dynamic Priority (Fair)
- Realtime with Different and Static Priority (Non-fair in order to have predicable response): Preemptive for different priority and Round-Robin (time slicing) for the same priority
* Priority Assignment
Pre-condition:
All tasks have worst-case execution times that are less than or equal to their deadlines.
- Rate Monotonic Scheduling
For periodic tasks and task deadlines are in the end of period, tasks with shorter period have higher priority.
- Minimum Interarrival Time Scheduling
For aperiodic tasks and task deadlines are equal to their minimum interarrival time, tasks with shorter arrival time have higher priority.
- Deadline Monotonic Scheduling
For periodic or aperiodic tasks and task deadlines are shorter than their periods or minimum interarrival time, tasks with shorter deadline have higher priority.
* Issues
- Priority inversion
It involves at least three threads of different priorities. The solutions are priority inheritance and priority ceiling. Mutex supports to solve this problem generally. When use the preemptive lock, the priority inversion might happen since the task with higher priority could not be executed in time.
Showing posts with label Thread. Show all posts
Showing posts with label Thread. Show all posts
Sunday, August 19, 2007
Communications
* Types of Communication
- Loosely coupled comm.
- Tightly coupled comm.
* Approaches
Shared Data Structure
- Resource sync needed.
Message Passing (Message Queue)
- Provide sync and comm together
- No owner and mutual exclusion implemented internally
- Value passing for small messages and reference passing for large messages
- Semaphore implementation: a mailbox of one valid message
Usage for Comm
- Loosely coupled one-way comm: ONE message queue
- Tightly coupled one-way comm: ONE message queue and ONE binary semaphore
- Tightly coupled two-way comm (Rendezvous): TWO message queues with one or multiple entries
Note: the task model here could be "one to one", "multiple to one" and "one to multiple", etc.
- Loosely coupled comm.
- Tightly coupled comm.
* Approaches
Shared Data Structure
- Resource sync needed.
Message Passing (Message Queue)
- Provide sync and comm together
- No owner and mutual exclusion implemented internally
- Value passing for small messages and reference passing for large messages
- Semaphore implementation: a mailbox of one valid message
Usage for Comm
- Loosely coupled one-way comm: ONE message queue
- Tightly coupled one-way comm: ONE message queue and ONE binary semaphore
- Tightly coupled two-way comm (Rendezvous): TWO message queues with one or multiple entries
Note: the task model here could be "one to one", "multiple to one" and "one to multiple", etc.
Synchronization
* Types of Synchronization
- Resource sync: critical section and resource mutual exclusion
- Activity sync
* Approaches
Low weight ones: TSL(Test Set Lock, H/W), semaphore, mutex, conditional variable
High weight ones: message passing, spinlock, monitor, read-write lock, barrier, interrupt lock, and preemption(scheduling) lock.
- Resource sync
Resource could be either data or codes:
mutex for single shared resource access
recursive mutex for recursive shared resource access
counting semaphore plus mutex, the mixing of non-blocking and blocking mutexes for multiple shared resource access
interrupt lock for the shared resource with ISR
preemption lock for the shared resource without waiting
read-write lock for multiple reads and exclusive write (broadcasting)
locking hierarchy and locking chain for dependent resources
- Activity sync
1) Single-task waiting and single-task signaling: conditional variable and semaphore
2) Multiple-task waiting and single-task signaling: conditional variable(broadcasting) and semaphore(flushing)
3) Single-task waiting and multiple-task signaling: ONE semaphore with iterative checking MULTIPLE input sources from ISR; ONE counting semaphore associated with the each input queue which might be redesigned.
4) Flow control: counting semaphore
5) Rendezvous and barrier sync: TWO semaphore without comm. Two conditional variables. TWO message queues of one entry for comm. Callback mechanism with comm. And barrier for multiple tasks.
6) Event occurrence: conditional variable or event object, counting semaphore (support to count the times of event happening)
* Issues
- Race
A race occurs when two or more threads try to get something or do something at the same time. Only one can win. Race is the result of resource conflicts caused by insufficient sync. Race is difficult to diagnose since every thread would keep going.
- Deadlock
Deadlock is the result of resource conflicts caused by wrong sync. It is easy to be detected since threads stop. In general, if multiple mutexes are used sequentially for dependent resources, deadlock happens probably. The general solutions are:
1) fixed locking hierarchy and
2) try and backoff with reverse unlocking sequence.
Note: Lock chaining is a special case of locking hierarchy, where the scope of two locks overlap. With one mutex locked, the code enters a region where another mutex is required. After successfully locking that second mutex, the first is no longer needed, and can be released.
* Sleep and Non-sleep
Many facilities would make current threads to sleep, like semaphore, mutex, etc. However, in the following cases it is not allowed to sleep:
- ISR
- critical sections
* Semaphore, mutex and conditional variable
- Binary semaphore is too simple to use since programmers need to make sure both mutual exclusion and synchronization of threads by using multiple semaphores. Semaphore has no owner and anyone could release it. Also it needs no predicate associated.
- Mutex is for mutual exclusion and it has its owner which needs to release mutex after using it. Mutex supports to task delete safety, recursive access and priority inheritance for priority inversion.
- Conditional variable is for thread synchronization and is dependent of a SINGLE (not multiple) predicate of the shared resource. Always test your predicate; and then test it again by using while loop. It must be associated with a mutex. But a mutex may have any number of condition variables associated with it.
* Spinlock and monitor
- Spinlock can be effective in very restricted circumstances. The critical section must be short, you must have significant contention for the lock, and you must be running on more than one CPU since it would not block the task. The trylock of mutex could be used to implement it. Spinlock could be used in ISR to do resource sync due to its non-sleep & non-interruptible property.
- Monitor integrates the shared resource with its mutual exclusion utilities together. In many situations, monitors are an excellent synchronization technique. By forcing the programmer to manipulate shared data via monitored code, you ensure that there can never be a failure to lock its use, and that the access methods will be well-defined. Monitors cannot handle all types of locking situations, however. When you want to use the “trylock” functions, you must use regular mutexes.
* Initialization/destroy and blocking/non-blocking
All these utilities need to be initialized before using them and deleted in the end. It is possible that memory associated is allocated within the initialization. Therefore this memory should be freed in the delete routine. Also, it must be sure that when they are deleted, no other tasks are waiting or holding them so that no deadlock happens. One general deletion is:
{
lock(mutex);
unlock(mutex);
delete(mutex);
}
On the other hand, when these utilities are used, two types of functions are provided in general, i.e. blocking access and non-blocking or time-out access.
- Resource sync: critical section and resource mutual exclusion
- Activity sync
* Approaches
Low weight ones: TSL(Test Set Lock, H/W), semaphore, mutex, conditional variable
High weight ones: message passing, spinlock, monitor, read-write lock, barrier, interrupt lock, and preemption(scheduling) lock.
- Resource sync
Resource could be either data or codes:
mutex for single shared resource access
recursive mutex for recursive shared resource access
counting semaphore plus mutex, the mixing of non-blocking and blocking mutexes for multiple shared resource access
interrupt lock for the shared resource with ISR
preemption lock for the shared resource without waiting
read-write lock for multiple reads and exclusive write (broadcasting)
locking hierarchy and locking chain for dependent resources
- Activity sync
1) Single-task waiting and single-task signaling: conditional variable and semaphore
2) Multiple-task waiting and single-task signaling: conditional variable(broadcasting) and semaphore(flushing)
3) Single-task waiting and multiple-task signaling: ONE semaphore with iterative checking MULTIPLE input sources from ISR; ONE counting semaphore associated with the each input queue which might be redesigned.
4) Flow control: counting semaphore
5) Rendezvous and barrier sync: TWO semaphore without comm. Two conditional variables. TWO message queues of one entry for comm. Callback mechanism with comm. And barrier for multiple tasks.
6) Event occurrence: conditional variable or event object, counting semaphore (support to count the times of event happening)
* Issues
- Race
A race occurs when two or more threads try to get something or do something at the same time. Only one can win. Race is the result of resource conflicts caused by insufficient sync. Race is difficult to diagnose since every thread would keep going.
- Deadlock
Deadlock is the result of resource conflicts caused by wrong sync. It is easy to be detected since threads stop. In general, if multiple mutexes are used sequentially for dependent resources, deadlock happens probably. The general solutions are:
1) fixed locking hierarchy and
2) try and backoff with reverse unlocking sequence.
Note: Lock chaining is a special case of locking hierarchy, where the scope of two locks overlap. With one mutex locked, the code enters a region where another mutex is required. After successfully locking that second mutex, the first is no longer needed, and can be released.
* Sleep and Non-sleep
Many facilities would make current threads to sleep, like semaphore, mutex, etc. However, in the following cases it is not allowed to sleep:
- ISR
- critical sections
* Semaphore, mutex and conditional variable
- Binary semaphore is too simple to use since programmers need to make sure both mutual exclusion and synchronization of threads by using multiple semaphores. Semaphore has no owner and anyone could release it. Also it needs no predicate associated.
- Mutex is for mutual exclusion and it has its owner which needs to release mutex after using it. Mutex supports to task delete safety, recursive access and priority inheritance for priority inversion.
- Conditional variable is for thread synchronization and is dependent of a SINGLE (not multiple) predicate of the shared resource. Always test your predicate; and then test it again by using while loop. It must be associated with a mutex. But a mutex may have any number of condition variables associated with it.
* Spinlock and monitor
- Spinlock can be effective in very restricted circumstances. The critical section must be short, you must have significant contention for the lock, and you must be running on more than one CPU since it would not block the task. The trylock of mutex could be used to implement it. Spinlock could be used in ISR to do resource sync due to its non-sleep & non-interruptible property.
- Monitor integrates the shared resource with its mutual exclusion utilities together. In many situations, monitors are an excellent synchronization technique. By forcing the programmer to manipulate shared data via monitored code, you ensure that there can never be a failure to lock its use, and that the access methods will be well-defined. Monitors cannot handle all types of locking situations, however. When you want to use the “trylock” functions, you must use regular mutexes.
* Initialization/destroy and blocking/non-blocking
All these utilities need to be initialized before using them and deleted in the end. It is possible that memory associated is allocated within the initialization. Therefore this memory should be freed in the delete routine. Also, it must be sure that when they are deleted, no other tasks are waiting or holding them so that no deadlock happens. One general deletion is:
{
lock(mutex);
unlock(mutex);
delete(mutex);
}
On the other hand, when these utilities are used, two types of functions are provided in general, i.e. blocking access and non-blocking or time-out access.
Concurrency Control
* In order to create concurrent execution context, and control how they operate within the library and application, three facilities need to be provided:
- Execution context: the state of a concurrent entity.
- Scheduling: to determine which execution context and/or CPU
- Synchronization: to cooperate between concurrent execution contexts
* Thread
- All threads in one process would share all the resources, like virtual address space, file descriptor/pointer, working directory, etc..
- A thread's registers, PC, stack and heap memory are private for the thread unless the thread communicates pointer to that memory to other threads.
- A thread is fully synchronous with itself unless some asynchronous events happen, like ISR.
* Thread Working Modes
- Pipeline
A task is broken into a series of suboperations, each of which is handled in series, but concurrently, by a different thread.
- Client/Server
Multiple clients contact with an independent server for each job anonymously (Multiple to one).
- Manager/worker
A single thread, the manager assigns work to other threads, the workers(One to multiple). Typically, the manager handles all input and parcels out work to the other tasks. At least two forms of the manager/worker model are common: static worker pool and dynamic worker pool.
- Work Crew
Multiple threads work together independently. A special form of manager/worker mode since the manager would join the workers after it creates workers.
- Execution context: the state of a concurrent entity.
- Scheduling: to determine which execution context and/or CPU
- Synchronization: to cooperate between concurrent execution contexts
* Thread
- All threads in one process would share all the resources, like virtual address space, file descriptor/pointer, working directory, etc..
- A thread's registers, PC, stack and heap memory are private for the thread unless the thread communicates pointer to that memory to other threads.
- A thread is fully synchronous with itself unless some asynchronous events happen, like ISR.
* Thread Working Modes
- Pipeline
A task is broken into a series of suboperations, each of which is handled in series, but concurrently, by a different thread.
- Client/Server
Multiple clients contact with an independent server for each job anonymously (Multiple to one).
- Manager/worker
A single thread, the manager assigns work to other threads, the workers(One to multiple). Typically, the manager handles all input and parcels out work to the other tasks. At least two forms of the manager/worker model are common: static worker pool and dynamic worker pool.
- Work Crew
Multiple threads work together independently. A special form of manager/worker mode since the manager would join the workers after it creates workers.
Subscribe to:
Posts (Atom)
