Sudoku Solution Validator

이 글은 Operating System Concepts (9th Edition)의 Ch.4 Multi-Threaded Programming, Project 1의 내용이다.

코드의 실행 결과는 다음과 같다.

솔루션은 다음과 같다.

  1. 사용자에게 콘솔로 input file의 경로 혹은 이름을 입력받는다.
    input file의 format은 10×10의 텍스트 파일로 각각 배열 index 상의 0행, 0열은 -1 값이 입력되어 있다.
    (과제의 요구조건이기도 하고, 이렇게 해야 차후 index관리가 편함.)
  2. 입력받은 파일을 전역변수로 선언된 integer형 2차원 배열에 저장한다.
    전역변수로 저장하는 이유는 추후에, thread 함수에서의 접근을 쉽게 하기 위함.
    c++/java에서의 capsulation을 지향하는 경우에는 reference 혹은 주소값으로 access할 수도 있다.
  3. thread 함수의 parameter로 전달될 구조체를 동적할당 한다.
    구조체의 멤버로는 각 조건을 검사할 행과 열의 시작점, thread id 값이 저장된다.
  4. 3개의 thread는 행을, 3개의 thread는 열을, 9개의 thread는 3×3의 sub matrix를 sudoku 조건에 부합하는지 조사한다.
    *처음에 quick sort를 이용하여 chk함수에서 오름차순 정렬을 한 뒤, 총합이 45가 되는지, 그리고 끝번 index의 값이 9인지를 조사하여 sudoku 조건을 검사하는 코드를 짰었으나, 정확한 이유는 모르지만 디버깅을 해 보니, 행과 열을 검사하는 thread에서 계속 wait 상태가 되었다.
    따라서, quick sort 방식을 포기하고, 각각의 thread에서 한 행 혹은 열 혹은 sub matrix를 검사하는 chk 함수를 따로 호출하여, integer 형 배열 10칸짜리를 만들고, 원래 조사하던 배열의 값에 해당하는 index에 값이 있다면 1을 기록하는 방식으로 변경했다.
    예를 들어, sudoku[1][2] 의 값이 5 라면, chk 함수의 지역변수로 선언된 tmp_arr[10] 의 배열에서 tmp_arr[5]의 값을 1로 변경해주는 방식이다.
    각각의 값에 대해서 배열 인덱스에 저장만 해주는 방식으로 굳이 time complexity를 계산하게 된다면 O(n) 이 되지 않을까? (값과 인덱스를 비교하는 연산이 basic operation 이라고 생각한다.)
  5. 각각의 thread는 (총 15개) 조건 검사후, integer형 전역 변수로 선언된 크기 15개짜리 배열에 thread id 에 맞는 index에 값을 기록한다.
    조건이 맞을 경우 1을, 틀릴 경우 0을 초기값은 -1 이다.
    예를 들어, 4번 thread에서 조건 검사를 한 결과 조건이 맞다면 chk_thread[4] = 1; 이 되는 식이다.
  6. 모든 thread가 종료되고 main thread로 돌아오면, 다음으로 chk_thread의 값을 모두 더한다.
    더한 값이 15가 된다면, sudoku의 모든 조건을 만족하게 되므로, input solution은 유효한 sudoku solution이 된다.

아래는 gdb debugger를 기반으로 시각적으로 debugging을 할 수 있는 DDD debugger 이다.
개인적으로, 자료구조 시간에 배웠던 linked list를 공부할 때 매우 효과적인 툴이라고 생각한다.
(포인터를 display 하게 되면, 연결된 리스트를 바로 보여주며 해당 값도 확인할 수 있다.
명령어는 graphic display name 이다. 혹은 변수옆에 마우스 우클릭으로도 사용할 수 있다.)
ddd 툴을 가지고, 정말로 멀티스레드가 작동하는지 확인한 것이다.
status->threads 에서 확인할 수 있다.
첫 번째 그림은 worker_row 함수에 break point를 설정한 것으로 2번, 3번 thread가 동시에 running 중인 것을 보여준다.

마지막 그림은, 프로그램이 모두 돌고 main 함수에서 return한 뒤에 thread가 생성되고 소멸되는 것을 나타내는 것이다.
thread가 생성되는 순서와 무관하게 작업이 끝나는 순서대로 exited된 것을 확인할 수 있다.

pthread를 포함한 c코드를 컴파일할 때는 컴파일 옵션에 -lpthread를 추가해야 한다.

gcc -o {output} {input.c} -lpthread

디버거를 사용하려면, 

gcc -o -g {output} {input.c} -lpthread

 

댓글 남기기