![]() Releasing locks may require rollback, which leads to the same issues described above. Breaking hold-and-waitĬan break hold-and-wait by having threads release all locks and re-acquire them all at once. Once you tell the user you've started processing their order, you can't take it back. I/O is a well-known impediment to rollback: once some output has been performed, it may be impossible to return to a consistent state. It is not possible to make all resource preemptible. This state is called livelock: when competing threads are continuously being rolled back before they can finish. Although the system is not deadlocked (both threads seem to be making forward progress), the system may never actually finish its tasks. Once we allow computations to be rolled back, we introduce the possibility that two threads can continue to preempt each other forever. In order to do this, we need some mechanism for rollback: we need to be able to restore whatever program invariants that the resource was held in order to satisfy.įor example, if the resource is a lock protecting a shared variable, we could roll back the thread that holds the lock by restoring the state of the shared variable to the state it held before the lock was acquired, and restarting the process that was performing the update. If a process tries to acquire a resource that is held by another process, we can make it possible for the new process to steal the resource. In some situations we can make resources preemptable. Mutual exclusion is a good condition to break if you can, but often you can't. ![]() printers: can't print two documents simultaneously!). However, many resources are inherently non-shareable (e.g. ![]() Using a lock-free data structure is another way to allow multiple threads to access a data structure simultaneously (without blocking). For example, using a reader/writer lock instead of a mutex can make deadlock less likely (since many readers can share the read lock). In some cases, deadlock can be mitigated by making resources more shareable. We can design a system to avoid deadlock by making any of the 4 conditions impossible. key terms: optimistic concurrency, rollback, livelock.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |