3.2 Strict 2PL Lock Table - KeonYeong/LKY GitHub Wiki

Overview :

As soon as program starts, it takes 3 numbers as inputs of numbers of threads, records and executions. Then threads are created with data of each. threads mainly executes 3 processes on the record, and after that it commits a 'commit log' on its own file containing the commit ID, record numbers and their content. Through all these steps, locks are essential functionality that need to be implemented. Hence with the lock tables allocated to each records threads complete their duty until the commit ID exceeds execution number.

Data Structure:

There are two big structures that are mainly used, each named rwQ and Record.

  • Thread Node :: rwQ

    This is structure that is assigned to thread, so there is one rwQ per one thread. It's used in order to implement in lock table. This thread node, rwQ will be inserted into the linked list (or queue) of the record that thread is interested. When there are no other nodes preceding itself in same list, the node will perform the transaction on certain record. All variables in this structure (node) are created and modified in order to facilitate the use of lock table. There is only one node used in all lock tables for one thread, because when it's time for the thread to get lock on the record, it just passes its id and type of lock to record. The node itself is released from the list of the certain record and ready for being inserted on the other record. image

    • tid : containing the id of certain thread
    • curRec : It contains the record ID of the lock table where current thread node exist. Its initial value is -1.
    • owning[2] : It is the array containing two elements. Each element contains the record ID of the lock table where current thread locked before (sequentially read-lock and write-lock). It's necessary when deadlock handling occurs. Their initial values are -1.
    • myCond : It's unique condition variable per each thread.
    • read : It's boolean variable that marks the which kind of lock is the current thread trying to get on certain record.

  • Record structure :: Record

    This is structure that represents a certain record, hence every records are implemented through this structure. Lock tables are also contained within the record structure, it owns its own lock table pointer. Moreover, few variables or flags also exist in this. image

    • next : This is the rwQ lock table pointer for the certain record.
    • ownerTid : It contains the id of the thread holding the lock on the current record. Default is -1.
    • ownerIsRead : It indicates the type of lock held on (Read or Write), if it's true it means read lock is held on the record.
    • readShares : This variable tells you how many read locks are held on the current record.
    • rid : The id of the current record.
    • content : The unique real number just for the record owning.
    • emptyRec : The flag telling you whether the current record is locked or not.

Procedures:

  • Transaction

    • Input values are N, R, E. Each represents the number of threads (N), the number of records (R), execution number (E).
    • First of all, we choose random numbers i, j, k which indicates the id of records that we are going to perform transaction. Numbers are totally randomly chosen without overlapping.
    • After then it's time to get read lock on the record interested (record i), but before that the thread gets a global lock named 'globalMtx' in order to look through the lock table of the that record. If there's no lock held on that record it gets read lock on it and unlock the global lock. Then finally the thread reads the record.
    • Following read action, then it needs to write certain value on record j and record k. Same as read action, global lock needs to be held again before write action, then thread looks through the lock table and it gets lock only if there're no lock already held, if not add itself on the queue and waits for its turn. Anyway when it successfully gets a write lock on certain record, unlocks the global lock and writes a value (current value + record i's content + 1) to record j. For record k, same thing happens as record j, but the value is different (current value - record i's content).
    • When all the read / write actions are done, thread tries to get global lock again in order to commit the log on the text file. Right after global lock is held, it first unlocks all the read or write locks that it got before, then it checks whether commit id is exceeding the value E (execution number), if it does thread undo the transaction and does not commit the log. If everything is OK commit log, log contains the information of 'commit ID, i, j, k, the content of record i, the content of record j, the content of record k'.
    • If commit id exceeds E, thread ends its loop and exits, if not it repeats all steps above.

    Baasic Order : Choose random number -> global lock -> read lock -> global unlock -> read -> global lock -> write lock 1 -> global unlock -> write 1 -> global lock -> write lock 2 -> global unlock -> write 2 -> global lock -> read, write 1, write 2 unlock -> check commit id and commit log -> global unlock.

  • Lock-Table Implement

    • Read lock : If readlock function is called, thread first check whether the lock is held already or not and its lock type if exist. If there is no other lock on the record thread passes its id, lock type to the record structure and save them there. Besides some flags are also changed in order to tell the other threads. If lock is already held but the type is read lock, then thread just passes through the lock. If the lock is write lock, thread inserts its node into the queue (linked list) of that record, and wait for other preceding threads end their jobs (on its own conditional variable). If the thread becomes the first one of the queue, lock holder thread will signal it and the thread waiting will wake up and become the lock holder. If the next thread is waiting with the type 'read' then the woken thread also immediately signal the next thread. At last, it removes itself from the list and changes the variables related.
    • Read unlock : When read unlock function is called, it simply changes some variables of record in order to imply that the record is not in-use. Also thread take a look through the waiting queue and signals the next thread in the list. But before those procedure, thread must check whether the ownerTid in the record is same as its own, if it's not same the thread doesn't signal and just quit (In case of multiple readers).
    • Write lock : The process until the insertion into the list is same as the read lock's. However in write lock, after insertion the thread must progress the 'Dead lock detection'. If dead lock is detected, the thread will unlock all locks that it was holding at that time and abandon the current transaction. If no dead lock is detected thread will keep on the transaction and move to the next step - waiting on its own conditional variable. Then after it wakes up, it checks if there're any other readers not yet finished by using the 'readShares' variable. If the value of 'readShares' is 0, the thread starts to get a write lock on the record and updates several variables related to owner of record.
    • Write unlock : All the steps are exactly same as the read unlock's except for checking the ownerTid in the record, no matter what ownerTid is, the thread must update the values in record.

Deadlock Issue:

  • Deadlock Detection

    Dead lock means that several locks from different threads are intervened weirdly so that cycle is created and no more threads are able to proceed on their job. Hence in order to detect the deadlock, every time the thread puts itself into the waiting queue, it needs to see whether the cycle occurs due to the addition of itself. Way is simple, the thread find out the header (or owner) thread's id of the record of that it just added on the list, then it check if there are another node with same id of owner in other records' waiting queue. Next, it again finds out the owner thread's id of that queue and check if there are another node with same id of owner in other's again. These steps are repeated until owner's id is found -1 (Because it means there is no other node in other queue ultimately implying no cycle is existing). Moreover in every loop, the id found will be compared with the id of the thread that started the deadlock detection. If the id is same, it means cycle exists and immediately deadlock handler is called and the thread abandons current transaction. If not it continues. Also curRec(record id where certain thread is waiting on) is also checked because if the record id is -1 (the initial value, it is changed to -1 if the node is the lock holder (or owner) of that record)and the thread id is not same with the detecting thread, it means there is no cycle and so the thread just breaks the loop.

  • Deadlock Handler

    If deadlock is detected deadlock handler function is called. The jobs that the handler do are simple, it unlocks all the locks that the thread related is holding. Simply the steps are same as what unlock functions do - changing variables of the record related to owner and signal the next node if exists.

Corner-cases:

  • Multiple Readers

    Due to the property of RWlock, read lock should allow another read lock to pass through but not block. Hence this implies that there can be several different read locks held at the same time. In order to notify how many different read locks are held, 'readShares' variable is incremented if any read lock comes, and also in write lock there is one more condition checking readShares to assure the mutual exclusiveness between read and write locks. The 'readShares' variable will be decreased by one immediately after the read action of one multiple reader ends and corresponding thread moves on to write action. This could be weird because that reader didn't unlock the read lock yet. However this is possible because reading the record doesn't effect the upcoming writing-on-record action at all, and since there is only one owner that can be checked in record other readers also need to be protected even if the owner thread unlock the read lock. Hence when owner thread unlocks the read lock and also the 'readShares' becomes 0 (which implying no more read actions gonna be happened), the next node (write lock) gets the write lock. All these procedures suppress the dead lock situation occurring due to multiple readers (Because the dead lock detection can only examine one of the multiple readers in my design).

return