mutex-lock.md

Architectural design of lock implementation

Data structures

• lock_t (enum)
• blocked_queue (linked list of pcb_t) for threads waiting on a resource

Functions

• lock_init(l) initializes lock l – no thread initially holds it
• lock_acquire(l):
  • if no thread holds l:
    • mark l as held
    • return
  • if another thread holds l:
    • use scheduler.c:block() to put the thread on the blocked_queue
  • if l has not been initialized:
    • return error
  • if l has already been acquired by this thread:
    • return error
• lock_release(l):
  • if no threads are waiting on the blocked_queue:
    • mark l as not being held
    • return
  • if at least one thread is waiting on the blocked_queue:
    • l remains locked
    • thread at the head of the blocked_queue is put at the tail of the ready_queue
      • use block() and unblock() correspondingly
  • if l has not been initialized:
    • return error
  • if this thread does not hold l:
    • return error
• block():
  • enqueue the curent_running thread to the block_queue
• unblock():
  • dequeue the current_running thread from the block_queue