[병렬프로그래밍] Shared Memory

Modern Multiprocessors 에서 사용되는 shared memory 는 어디에서 부터 온 것일까? 에 대한 내용

 

Register : Holds a (binary value), Can be read & written

 

Register 의 종류

Safe Register : valid 한 값을 읽으면 safe (some valid value)

  ㄴ ex) binary 1bit register read 0 or 1 (safe), read "hi" (unsafe)

Regular Register : Old Vluae if no overlap, Old or one of new values if overlap

  ㄴ Regualr != Linearlizable

Atomic Register : Linearizable to sequential safe register

 

Register Space

 

가장 약한 Weakest Register 에서 Modern Multiprocessors 에서 사용되는 Register 까지 만들어보자

SRSW Safe Boolean -> Atomic Snapshots

 

M : Multi

R : Reader

W : Writer

 

 

 

SRSW Safe Boolean Register - 1bit 에 writer 한명이 쓰고, reader 한명이 읽는 간단한 형태

 

SRSW Safe Boolen Reagister -> MRSW Safe Boolen Reagister

 ㄴ writer만큼의 register 배열을 만들어서 입력

 

SRSW Safe Multi-Value -> MRSW Safe Multi-Value 도 똑같이 적용 가능

 

MRSW Safe Boolean -> MRSW Regular Boolean

Safe Register 로 Regular Register 를 만들때 old 값을 저장 해둠.

만약 Register 에 old 와 같은 값을 write 했는데 다른 결과가 나옴 (0, 0을 썼는데 1이 나오면 not regular)

내부적으로 Safe Register로 만들면서 Regular 의 성질을 유지하기 위해 같은 값을 쓸 때 무시

 

MRSW Safe Multi-Value -> MRSW Regular Multi-Value

0000 에 1111을 쓸 때 모든 bit에 다 쓰기 전 1100 같은 값을 읽을 수 있어서, old값을 저장하는 것 만으로는 만들 수 없음

해결책 : n-bit representation 을 사용

1000 0000 = 0

0100 0000 = 1

...

0000 0001 = 7

 

write 할 때는 가장 오른쪽 bit를 표시한 후, 왼쪽으로 가면서 모든 bit를 0으로 만듬

read 할 때는 가장 왼쪽에서 맨 처음 1을 만날때 까지 순회

 

SRSW Regular -> SRSW Atomic

SRSW 일 때는 Regular 와 Atomic 이 같음

 

SRSW Atomic -> MRSW Atomic

overlap 되어 있을 때, old or new를 읽는 property에서 linearlizable 하게 바꾸기 위해 timestamp 를 check

가로로 read, 세로로 write

읽는 도중 update 된 timestamp를 발견하, reader가 표를 update

MRSW Atomic -> MRMW Atomic

Write timestamp 로 관리

 

-- 여기까지 MRMW Atomic Register --

 

Snapshot

Atomic MRSWRegister 의 배열에서 어떤 순간에 가질 수 있는 값들의 모습

계속해서 Register 값이 변경되는 와중에 정확한 모습을 찾는 것이 목표

 

Update : Register의 값을 변경

Collect : 현재 배열의 상태를 순회하면서 얻음

 ㄴ 중간에 바뀔 수 있음

Scan : Snapshot 의 값들을 얻음

 

Clean Collect

 Collect 를 하는 도중에 변할 수 있기 때문에, clean collect를 얻어내야함

 

Simple Snapshot ( 아직 Atomic 하지 않음 )

 Collect를 두번 해서 값이 같으면 중간에 변하지 않았다는 것을 이용

 그러나 같은 값을 써서 사실 중간에 변했을 수도 있으므로, Label을 사용함

왼쪽 그림에서 배열 0번에 x, y를 쓴 후, 배열 1번에 z, w를 쓰는 곳에서

x와 z 가 같이 보일 수 없는 상태인데, Label이 없다면 두번 같은 결과가 나옴으로 올바른 값을 얻지 못함

그래서 Label을 사용하여, 중간에 값이 바뀐 것을 탐지

 

Wait-Free Snapshot

 

Wait-Free : 일정 step 내에 method를 처리 할 수 있음

현재 Simple Snapshot 은 같은 collect를 찾을 때 까지 반복해야 하는 것을 해결한 것이 Wait-Free Snapshot

update 를 할 때도 scan을 미리 해서, 저장해둠. 이전에는 그냥 변수와 라벨 값만 업데이트 - Writer의 도움을 받자

같은 값이 두번 수정되는 것을 scan 에서 발견했다면, 이미 Clean Collect를 다른 쓰레드에서 발견했다는 것을 의미하므로 가져다 씀.

 

- 나중에 소스코드 올릴 자리