가희와 읽기 쓰기 놀이 : 브루트 포스로 race condition 상황을 시뮬레이션 해 봅시다.

 이 글에서는 제가 출제했던 문제인 가희와 읽기 쓰기 놀이를 왜 냈는지, 그리고 어떻게 풀어야 하는지 써 보도록 하겠습니다. 가희와 읽기 쓰기 놀이는, race condition을 주제로 만들어진 문제입니다. 그리고 N과 C가 9보다 작거나 같기 때문에, brute force를 돌려도 됨을 알 수 있어요. N과 C가 9보다 작거나 같다는 조건을 읽은 순간, 아. 그냥 백트래킹 돌려도 되겠구나. 이게 와야 해요.

 

 출제 의도가 race condition이라고 했는데, 어째서 경쟁 상태일까요? 단순히 턴제 게임 아니였나요? 턴제 게임은 맞습니다. 맞는데, 다른 관점에서 봐 봅시다. 1번 사람이 1번, 2번 카드 순으로 내고, 2번 사람이 3번 카드를 낼 수 있다고 합시다. 그리고 1번은 a를 뒤에 추가, 2번은 b를 뒤에 추가, 3번은 c를 뒤에 추가하는 operation입니다.

 

 예제 2번의 그림인데요. b를 추가하는 작업은, a를 추가하는 작업 다음에 이루어질 수 있어요. 이외에 선후 관계는 없어요.

 

 

 그래서, 처음에 'a'가 먼저 들어갈 수도 있습니다. 그런데, 'c'가 먼저 들어갈 수도 있어요.

 

 

 그러면 결과값은 a??나 c??가 나올 수 있습니다. 여기서, 게임에 참가하는 유저 1과 유저 2를 Thread로 둡시다. 그리고 카드들은 어떻게 보면 좋을까요? 예를 들어 카드에 add 'c'와 add 'd'가 있었다고 해 봅시다.

 

 

 카드에 add 'c'와 add 'd'가 동시에 있었다고 해 봅시다. 그러면, 해당 카드를 들고 있는 유저는 이 2개를 다 수행한 후에 턴을 종료해야 한다는 조건이 들어가 있었어요. 이를 다시 풀어 보면, 카드 내에 있는 연산들을 수행하는 작업들은 atomic, 즉 원자적으로 실행된다고 할 수 있어요.

 

 

 이렇게 쪼개지지는 않는다는 거에요. 그러면 카드 하나에 적혀져 있는 일련의 연산들은 synchronized 블록으로 묶였다고 보면 될까요? 혹은, 해당 유저가 카드에 있는 연산을 실행하게 되면 lock을 걸고, 연산을 끝내면 lock을 풀어버린다고 해석해도 될까요? 이 문제에서는 그렇습니다.

 

 

---

 그런데, 왜 결과가 달라질까요? 경쟁하고 있는 유저가 여러 명이 될 수 있고, 유저 여럿이서 공용 자원인 list에 연산을 수행한 결과를 반영하기 때문이에요. 다시 말하면, 유저 여러명이 list를 볼 수 있기 때문입니다. 사실 1명이면 별 문제가 발생하지 않아요. 문제는 둘 이상일 때입니다. 아래 그림을 봅시다.

 

 

 두 명이 누가 먼저 카드를 낼 지 경쟁하고 있어요. 만약에 2번이 먼저 냈다면 어떻게 될까요? list의 맨 뒤에 'c'가 먼저 추가됩니다.

 

 

 다음에, 1번이 실행한다면, 'a'가 리스트의 맨 뒤에 추가될 겁니다. 만약에 1번이 먼저 턴을 실행하고 2번이 실행하면 'a' 뒤에 'c'가 올 거에요. 이제 race condition과 이 문제의 접점을 찾으셨나요? 이제 본론으로 들어가겠습니다. 이 문제에서 봐야 할 것은, 덩어리 연산이 어느 단위로 이루어 지는지입니다. 덩어리 연산은 카드 단위로 이루어 진다. 만약에 카드에 add 'c', add 'd'가 적혀져 있다면, c가 추가되고 d가 추가되는 연산이 한 덩어리 연산이 되어 버립니다. 자바로 치면 synchronized로 묶여진 단위가 되어 버립니다. 이것을 잘 읽어냈는지, 그리고 조건을 정확하게 파악해서 상황에 맞는 접근 방법을 선택할 수 있는지, 그리고 설계 능력을 보고자 하였습니다.

 

 제가 위에서 언급한 내용에 대해서 조금 더 자세히 알고 싶으시면, 주니온님 11강 운영체제 강의를 보시면 더 좋을 듯 해요.

 

---

 브루트 포스, 백 트래킹인 것은 알았으니, 어떻게 데이터를 처리할 지, 그리고 어떻게 데이터를 넘겨줄 지 생각해 봅시다. 턴을 수행하는 것은 프로세스나 쓰레드가 단위 연산을 실행한다. 카드에 있는 연산들은 단위 연산이다. list는 쓰레드나 프로세스가 공통으로 보고 있는 자원 정도로 생각하면 된다고 했어요. 이제, 문제를 풀어 봅시다. 문제에서는 어떤 사람이 1, 2, 4번 카드를 냈을 때, 이 순서를 지키라고 했어요. 예를 들어 1, 2, ?, 4 순서는 됩니다. 그런데, 1, ?, 4, ?, 2 순서는 안 됩니다. 왜냐하면 2번 다음에 4번이 와야 하는데, 4번 다음에 2번이 왔기 때문입니다.

 

 예제 2번을 보면 1번 사람은 1, 2번 카드 순으로, 2번 사람은 3번 카드만 내라고 했어요.

 

 이 상황을 그려보면 위와 같아요. 한 사람이 여러 카드를 낼 수도 있으니, 이에 대한 것은 arrayList로 처리하겠습니다.

 

 cardTurn[x]는 x번 사람이 어떤 카드 순으로 냈는지를 저장합니다.

 

 

 그러면 x번 사람이 어떤 순으로 냈는지 입력을 받으면 그것을 cardTurn[x]에 추가하면 됩니다. 이제 어떻게 brute force를 돌려야 할 지가 문제인데요.

 

 2번 사람이 3번 카드에 있는 연산을 수행했어요. 그러면, 2번 사람은 카드 1개를 이미 쓴 겁니다.

 

 

 다음에 1번 사람이 1번 카드를 썼다면 1번 사람도 카드 1개를 쓴 건가요? 따라서, x번 사람이 카드를 몇 개 썼는지를 넘겨줘야 합니다. 그런데, 그것만 넘기면 다일까요? 아닙니다. 1번, 2번이 카드 1개, 1개씩 썼다고 해도, 2번이 쓰고 1번이 쓴 경우가 있고, 1번이 쓰고 2번이 쓴 경우도 있어요.

 

 따라서, 어떤 순서로 썼는지도 넘겨줄 필요가 있어요. 그리고 몇 명이 참여하는지까지 넘겨주면 됩니다.

 

 

 dfs 함수를 보면, curLoc과 stack, n이 있는데요. 각각 x번 사람이 몇 개의 카드를 소모했는지, 어떤 순서대로 턴이 진행되었는지, 사람이 몇 명인지를 나타냅니다. 37번째 줄에 check 메서드가 있는데요. 모든 사람이 카드를 소모한 경우, if문에 걸려서 work를 수행할 겁니다.

 

 

 그렇지 않으면, 이 부분을 도는데요. i번 사람이 모든 카드를 다 쓴 경우 42번째 줄 if문이 참이 됩니다. 이 경우는 continue를 걸어주면 됩니다. 그렇지 않으면, i번 사람이 그 다음 카드를 선택하게끔 하면 됩니다. 이것은 45번째 줄에 구현되어 있습니다. dfs를 돈 다음에는, 당연하게도 이전 상태로 와야 하기 때문에, 47번째 줄에 복구하는 로직도 추가하였습니다.

 

 나머지 부분은 제 깃헙 링크에 있는 소스 코드를 보시면 좋을 듯 합니다.