For each row, the variable values shown are those after the indicated action(s) have completed. Following along with the "Action" column, the outcome based on the above pseudocode can be observed. The following table shows an example of ticket lock in action in a system with four processors (P1, P2, P3, P4) competing for access to the critical section. Thus, fairness of lock acquisition is ensured, enforcing a FIFO ordering. Since the my_ticket values are acquired in the order of thread arrival at the lock, subsequent acquisition of the lock is guaranteed to also be in this same order. This allows the thread with the next sequential my_ticket to exit from ticketLock_acquire() and enter the critical section. After the critical section of the code, the thread performs ticketLock_release() which increments now_serving. Once now_serving becomes equal to a given thread's my_ticket they are allowed to return from ticketLock_acquire() and enter the critical section of code. Once my_ticket has been received, each thread will spin in the while loop while now_serving isn't equal to its my_ticket. It is important to note that the fetch and increment is done atomically, thereby not allowing any other concurrent attempts at access. While ( 1 ) įollowing along with the pseudocode above we can see that each time a processor tries to acquire a lock with ticketLock_acquire(), fetch_and_inc is called, returning the current value of next_ticket into the thread private my_ticket and incrementing the shared next_ticket. A simple example will now be presented to show how a thread could be excessively delayed due to a lack of fairness in lock acquisition.Īssume a case where three threads, each executing on one of three processors, are executing the following pseudocode that uses a lock with no consideration for fairness. With no fairness guarantees, a situation can arise where a thread (or multiple threads) can take a disproportionately long time to execute as compared to others. If some type of fairness is implemented, it prevents a thread from being starved out of execution for a long time due to inability to acquire a lock in favor of other threads. The notion of fairness in lock acquisition applies to the order in which threads acquire a lock successfully. This permits the next waiting thread, the one with the next sequential ticket number, to enter the critical section. When a thread leaves the critical section controlled by the lock, it atomically increments the dequeue ticket. If they are not the same, then another thread must already be in the critical section and this thread must busy-wait or yield. If they are the same, the thread is permitted to enter the critical section. It then compares its ticket value, before the increment, with the dequeue ticket's value. The atomicity of this operation is required to prevent two threads from simultaneously being able to obtain the same ticket number. When a thread arrives, it atomically obtains and then increments the queue ticket. The queue ticket is the thread's position in the queue, and the dequeue ticket is the ticket, or queue position, that now has the lock (Now Serving).
The first value is the queue ticket, the second is the dequeue ticket. It adds the benefit of fairness of lock acquisition and works as follows there are two integer values which begin at 0. Like this system, a ticket lock is a first in first out (FIFO) queue-based mechanism. This allows all of the waiting customers to know how many people are still ahead of them in the queue or line. Each time the next ticket number (customer) is ready to be served, the "Now Serving" sign is incremented and the number called out. There is also typically a dynamic sign, usually digital, that displays the ticket number that is now being served. The dispenser usually has a sign above or near it stating something like "Please take a number". Generally, there is some type of dispenser from which customers pull sequentially numbered tickets upon arrival. This is the method that many bakeries and delis use to serve customers in the order that they arrive, without making them stand in a line. The basic concept of a ticket lock is similar to the ticket queue management system. Overview Example of a ticket and "Now Serving" sign used in the Ticket Queue Management System.
In computer science, a ticket lock is a synchronization mechanism, or locking algorithm, that is a type of spinlock that uses "tickets" to control which thread of execution is allowed to enter a critical section.
0 kommentar(er)
