New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fair::(recursive_)timed_mutex; part2 #7

Closed
yohhoy opened this Issue Jan 24, 2017 · 2 comments

Comments

Projects
None yet
1 participant
@yohhoy
Owner

yohhoy commented Jan 24, 2017

Implement fairness mutex that support timeout. (related issue #5)

Basic strategy:

  • It represents waiting thread queue for lock acquisition by doubly linked list.
  • Each node of the list is placed on caller thread's stack frame to accomplish FIFO ordering without dynamic memory allocation.
  • When lock request is timeout, remove corresponding node from the list and keep FIFO ordering.
@yohhoy

This comment has been minimized.

Owner

yohhoy commented Jan 26, 2017

Algorithm:

locked : node  // placeholder node
queue : node  // anchor node (pointer to front/back node)

lock():
  if !queue.empty():
    request : node
    queue.push_back(request)
    while queue.front() != request:
      cv.wait()
    queue.pop_font()  // erase request
  queue.push_front(locked)
  // acquire

try_lock():
  if !queue.empty():
    return false
  queue.push_front(locked)
  return true

try_lock_timeout():
  if !queue.empty():
    request : node
    queue.push_back(request)
    while queue.front() != request:
      if (cv.wait() == timeout):
        if queue.front() == request:
          break
        queue.erase(request)
        return false
    queue.pop_font()  // erase request
  queue.push_front(locked)
  // acquire
  return true

unlock():
  assert (queue.front() == locked)
  queue.pop_front()
  cv.notify_all()
  // release

@yohhoy yohhoy referenced this issue Jan 26, 2017

Merged

add yamc::fair::(recursive_)timed_mutex #8

3 of 3 tasks complete
@yohhoy

This comment has been minimized.

Owner

yohhoy commented Jan 26, 2017

migrate to PR #8. close this issue.

@yohhoy yohhoy closed this Jan 26, 2017

yohhoy added a commit that referenced this issue Jan 27, 2017

add yamc::fair::timed_mutex (#7)
implement FIFO queue by doubley linked list.

@yohhoy yohhoy referenced this issue Feb 4, 2017

Merged

add yamc::fair::shared_(timed_)mutex #13

5 of 5 tasks complete
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment