Question about marking in concurrent linked list insertion.

[fairy-of-9]

안녕하세요,

영어를 잘 못해서... 한국어로 질문하겠습니다.

def insertion(Y): Z = Y.next if Z is marked: try again

이 insertion 함수에서 Z is marked 라는게, (1) Z가 지워질 예정, 즉 Z.next의 비트가 1이다. (2) Y가 지워질 예정, 즉 Z = Y.next에서 대입된 값의 비트가 1이다.

저는 (2)라고 생각해왔는데, 갑자기 혼란스럽네요. 둘 중 어느게 맞는건가요?

[jeehoonkang]

Y.next의 마지막 비트가 1로 마킹되었다면, Y가 지워졌다는 의미입니다.

[fairy-of-9]

@jeehoonkang 그렇다면 Y-Z 사이의 insertion은 Y가 지워졌는지를 체크한다고 보면 되나요?

[jeehoonkang]

@fairy-of-9 예 맞습니다.

[fairy-of-9]

https://github.com/kaist-cp/cs500-2019s/issues/63#issuecomment-499799998

---

T1 w = z.next fetch_add(z.next, 1) T2 w = z.next if w is marked, stop //w is not mark, so continue

---

그럼 여기서 T1이 z.next를 mark 했으니까, T2에서 w = z.next 는 mark 된 값이기 때문에 stop해야하지 않나요?

[jeehoonkang]

네 T1이 먼저 z.next를 mark했다면 T2는 멈춰야 할 것 같네요. T2 두번째줄에 if w is marked, stop 이라고 되어있습니다. 제가 아직 질문의 요지를 잘 파악 못했는데 정리해서 질문 올려주시겠어요?

[fairy-of-9]

제 질문은

if Z is marked: 의 의미가 (1) 변수값 Z. 즉 Z=Y.next를 통해 대입된 Y.next값이 marked이다. (2) Z는 지워졌다. 즉 Z.next가 marked이다.

무엇이 맞는 의미인가요?

였는데, (1)이 맞네요.

https://github.com/kaist-cp/cs500-2019s/issues/63#issuecomment-499799998 여기서는 @HaritzPuerto 님께서 (2)를 바탕으로 시뮬레이션을 하신거 같아서요..

[jeehoonkang]

아뇨 2가 맞습니다. Z.next가 marking되어 있으면 Z가 지워졌다는 의미입니다. https://github.com/kaist-cp/cs500-2019s/issues/75#issuecomment-500211058 참조하세요-

[fairy-of-9]

음 의미전달이 잘 안된거 같은데... 죄송합니다. 제가 한국어도 잘 못해서요..

어떤 노드의 next가 marked라면 해당 노드는 지워졌다는 의미인건 알겠습니다.

제 질문은 insertion 함수에서 (Y->Z 사이에 insert)

Z = Y.next
if Z is marked:
    == (1) if (Z & 1 == 1)          # Z(변수)의 마지막 비트가 1이다. (Y가 지워짐.)
    == (2) if (Z.next & 1 == 1)  # Z.next의 마지막 비트가 1이다. (Z가 지워짐.)

Z is marked 라는 뜻이 (1) Z를 변수값으로 봐야하는지 그냥 의미적으로 Z가 지워졌다는 뜻이여서 (2)로 봐야하는지가 헷갈렸습니다.

[jeehoonkang]

아 그렇다면 (1) 이 맞습니다: if (Z & 1 == 1) ...

[fairy-of-9]

네 감사합니다!!!