[병렬프로그래밍] Concurrent Objects

Concurrent Objects : 여러 쓰레드가 하나의 Object에 동시에 접근

Queue에서 하나의 enqueuer thread와 하나의 dequeuer thread만 있을 때라고 가정
Bounded Queue, Non Blocking

1. 가장 쉬운 방법
  ㄴ 모든 method 에서 lock을 잡음
2. wait-free (wait-free 개념은 후에 나옴)
  ㄴ enqueue : non blocking 이므로, 꽉 차 있을 때 에러를 발생한다. tail을 1 증가시키고 element 추가
  ㄴ dequeue : non blocking 이므로, 비어있을 때 에러를 발생한다. element 값을 저장 한 후 head를 1 증가
  ㄴ lock을 잡을 필요도 없고, 일정 step 내에 끝남

Concurrent Objects에서 중요한 요소
safety : implementation correct
liveness : system, thread not crush

Sequential Vs Concurrent
Sequential's method call is an event
Concurrent's method call is an interval (methods take overlapping time)

Sequential object needs state
Concurrent object never be between method call (because method callas overlaps)

Linearizable

Object is correct if this "sequential" behavior is correct

 

 

 

Invocation Notation 과 Response Notation

Concurrent Object 의 method는 interval 이기 때문에, 시작지점(Invocation)과 끝 지점(Response)이 있다.

 

Invocation Notation

A q:enq(x)

A - thread, q - object, enq - method, x - arguments

 

Response Notation

A q:void

A - thread, q - object, void - result

 

History : Sequence of invocation and responses

 

Match : Invocation & Response match if ( thread name same & object name same )

 

Projection : Subhistory for thread or object

 

Complete Subhistory : pending 된 method를 제거 (Final pending Invocation 은 상관 없음)