thread example

첨부한 프로그램 소스코드의 TODO를 완성하여 실행파일과 같이 동작하도록 수정해주세요.

(1) matrix_sum.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define N 4

int A[N][N], sum[N];

void * func (void *arg)	{ // threads function
  int j, row;
  pthread_t tid = pthread_self ();	// get thread ID number
									//
  row = (int*)arg;		// get row number from arg
  printf ("Thread %d [%lu] computes sum of row %d\n", row, tid, row);

  // compute sum of A[row]in global sum[row]
  /*TODO*/

  printf ("Thread %d [%lu] done: sum[%d] = %d\n", row, tid, row, sum[row]);

  pthread_exit ((void *) 0);	// thread exit: 0=normal termination
}

int main (int argc, char *argv[]) {
  pthread_t thread[N];		// thread IDs
  int i, j, r, total = 0;
  void *status;
  printf ("Main: initialize A matrix\n");

  for (i = 0; i < N; i++) {
      sum[i] = 0;
      for (j = 0; j < N; j++) {
		A[i][j] = i * N + j + 1;
		printf ("%4d ", A[i][j]);
	}
      printf ("\n");
  }

  printf ("Main: create %d threads\n", N);
  /*TODO*/

  printf ("Main: try to join with threads\n");
  /*TODO*/

  printf ("Main: compute and print total sum: ");
  /*TODO*/

  pthread_exit (NULL);
}

(2) quick_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N 10

typedef struct {
  int upperbound;
  int lowerbound;
} PARM;

int A[N] = { 5, 1, 6, 4, 7, 2, 9, 8, 0, 3 };	// unsorted data

int
print ()			// print current a[] contents
{
  int i;
  printf ("[ ");
  for (i = 0; i < N; i++)
    printf ("%d ", A[i]);
  printf ("]\n");

  return 0;
}

void *q_sort (void *aptr)
{
  PARM *ap, aleft, aright;
  int pivot, pivotIndex, left, right, temp;
  int upperbound, lowerbound;
  pthread_t me, leftThread, rightThread;
  me = pthread_self ();
  ap = (PARM *) aptr;
  upperbound = ap->upperbound;
  lowerbound = ap->lowerbound;
  pivot = A[upperbound];
  left = lowerbound - 1;
  right = upperbound;
  if (lowerbound >= upperbound)
    pthread_exit (NULL);
// pick low pivot value
// scan index from left side
// scan index from right side
  while (left < right) { // partition loop
	/*TODO*/
  }

  print ();
  pivotIndex = left;		// put pivot back
  temp = A[pivotIndex];
  A[pivotIndex] = pivot;
  A[upperbound] = temp;
// start the "recursive threads"
  aleft.upperbound = pivotIndex - 1;
  aleft.lowerbound = lowerbound;
  aright.upperbound = upperbound;
  aright.lowerbound = pivotIndex + 1;
  printf ("%lu: create left and right threads\n", me);
  pthread_create (&leftThread, NULL, q_sort, (void *) &aleft);
  pthread_create (&rightThread, NULL, q_sort, (void *) &aright);
// wait for left and right threads to finish
  pthread_join (leftThread, NULL);
  pthread_join (rightThread, NULL);
  printf ("%lu: joined with left & right threads\n", me);
}

int
main (int argc, char *argv[])
{
  PARM arg;
  int i, *array;
  pthread_t me, thread;
  me = pthread_self ();
  printf ("main %lu: unsorted array = ", me);
  print ();
  arg.upperbound = N - 1;
  arg.lowerbound = 0;
  printf ("main %lu create a thread to do QS\n", me);
  /*TODO*/
// wait for QS thread to finish
  /*TODO*/

  printf ("main %lu sorted array = ", me);
  print ();
}

여덟 번째 과제는 여러 개의 스레드를 생성해 행렬의 행별 합 계산과 병렬 퀵 정렬을 구현하는 것이다.

행별 합 계산에서는 각 스레드가 하나의 행을 나누어 계산하고, 병렬 퀵 정렬에서는 부분 배열을 나누어 정렬하도록 한다.

두 작업 모두 여러 스레드가 동시에 실행되도록 멀티스레드를 사용하며 필요한 경우 공유 데이터의 충돌을 막기 위해 뮤텍스를 사용할 수 있다.

구현

matrix_sum.c

1. 첫 번째 TODO

int row_indices[N];
for (i = 0; i < N; i++) {
    row_indices[i] = i;  
    pthread_create(&thread[i], NULL, func, (void *)&row_indices[i]);
}

스레드 생성

• pthread_create를 사용해 N개의 스레드를 생성한다.
• 각 스레드에 행 인덱스(i)를 넘겨주면서 각 스레드가 자신에게 할당된 행(row)을 계산한다.

2. 두 번째 TODO

for (i = 0; i < N; i++) {
    pthread_join(thread[i], &status);
    printf("Main: joined with %d [%lu]: status=%d\n", i, thread[i], (int)(size_t)status);
}

스레드 종료(조인)

• pthread_join을 사용해 모든 스레드가 종료될 때까지 기다린다.
• 각 스레드의 종료 상태를 출력하여 스레드가 정상적으로 완료되었는지 확인한다.

3. 두 번째 TODO

for (i = 0; i < N; i++) {
    total += sum[i];  
}
printf("total = %d\n", total);

전체 합 계산

• sum[] 배열에 각 스레드가 계산한 행별 합이 저장되었으므로 이를 합산하여 전체 합을 계산한다.

quick_sort.c

1. 첫 번째 TODO

while (left < right) { // partition loop
    left++;
    while (left < upperbound && A[left] < pivot) {
        left++;
    }

    right--;
    while (right > lowerbound && A[right] > pivot) {
        right--;
    }

    if (left < right) {
        temp = A[left];
        A[left] = A[right];
        A[right] = temp;
    }
}

partiction loop

• left와 right 포인터를 사용해 배열의 양쪽 끝에서부터 값을 비교하고 피봇보다 큰 값과 작은 값을 교환한다.
• 이 과정을 통해 피벗을 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이 배치되도록 한다.

2. 두 번째 TODO

pthread_create(&thread, NULL, q_sort, (void *)&arg);  
pthread_join(thread, NULL);

메인 스레드에서 정렬 시작

• pthread_create를 사용해 메인 스레드에서 q_sort 함수를 실행하는 스레드를 생성한다.
• pthread_join을 통해 생성된 스레드의 작업이 완료될 때까지 메인 스레드는 기다린다.