OS - Thread & Synchronization

Thread & Synchronization

이번 실습을 통하여 스레드의 이해와 CPU 스케줄링에 대한 이해를 하는데에 목적을 둔다. 리눅스 환경에서 POSIX 스레드를 생성 및 처리하는 프로그램을 구현하여 분산처리의 이해와 스레드 간의 커뮤니케이션 및 Synchronization의 해결을 구현을 진행한다. 그리고 CPU 스케줄링 알고리즘에 따른 실제 연산속도를 비교를 통하여 CPU 알고리즘(FIFO, Round Robin, Other)을 이해할 수 있다.

SourceCode

1. 다중 쓰레드로 수행하는 프로그램 작성

Makefile

all: gen_file.c gen_thread.c

gcc -o gen_file gen_file.c

gcc -o gen_thread gen_thread.c -lpthread

gen_file.c

//

//  gen_thread.c

//

//  Created by Eon on 14/11/2017.

//  Copyright © 2017 Eon. All rights reserved.

#include <stdio.h>

#include <dirent.h>

#include <string.h>

#include <sys/stat.h>

#include <sys/types.h>

#include <stdlib.h>

#include <linux/sched.h>

#define MAX_THREAD 4

struct stat st = {0};

int main(void) {

int i = 0;

char current_dir[1024] = {0, };

char number[6] = {0, };

if (stat("./tmp1", &st) == -1)

    mkdir("./tmp1", 0700);

for(i=0; i<MAX_THREAD*2; i++) {

getcwd(current_dir, 1024); //get current working directory

sprintf(number, "%d", i);

strcat(current_dir, "/tmp1/");

strcat(current_dir, number);

FILE* f_write = fopen(current_dir, "w"); //file open

if(f_write==NULL)    //if file open error

      printf("file open fail. \n");

fprintf(f_write, "%d", (int)(1 + rand()%9)); //write random number into "./tmp1/i" file

fclose(f_write);

memset(current_dir, 0, 1024);

}

return 0;

}

gen_thread.c

//

//  gen_thread.c

//

//  Created by Eon on 14/11/2017.

//  Copyright © 2017 Eon. All rights reserved.

/*

 

 step 1. MAX_THREAD 만큼 쓰레드를 생성

 step 2. 각 스레드마다 2개의 파일을 읽음.

 step 3. 각 스레드는 2개의 숫자를 더함.

 ==> 하나의 값만 남을 때까지 반복

 

 **Lock은 Mutex로 구현하기.

 

 */

#include <stdio.h>

#include <pthread.h>

#include <linux/unistd.h>

#include <string.h>

#include <sys/stat.h>

#define MAX_THREAD 4 //최대 스레드의 개수

void* thread_func(void *arg); //스레드들이 처음에 파일 읽기위한 함수

void* thread_func_final(void *arg); //스레드들이 덧셈만 수행하는 함수

int sum[MAX_THREAD]={0, }; //전역변수로 덧셈들을 모음

int step = 0; //덧셈의 step을 알기위한 전역변수

int main(int argc, const char * argv[]) {

    pthread_t tid[MAX_THREAD]; //pthread_t 타입의 tid를 쓰레드 수 만큼 생성

    pthread_t tid_final;

    int i = 0;

    if (chdir("tmp1")!=0) { //현재 디렉토리에 tmp1이 있는지 확인, 없으면 에러 출력 후 종료

        printf("'tmp1' directory is not found!!\n");

        return 0;

    }

    

#ifdef MUTEX

    int lock = pthread_mutex_init(&mutex, NULL); //뮤텍스 선언

    if (lock) { //뮤텍스 생성 에러시 프로그램 종료

        printf("Mutex initialization error!\n");

        return 0;

    }

#endif

    

        for (i=0; i<MAX_THREAD; i++) {

            pthread_create(&tid[i], NULL, thread_func, (void*)i); //쓰레드를 count만큼 생성, 각각의 쓰레드는 thread_func를 수행하고, 인자 i를 각각의 쓰레드의 입력으로 전달.

            pthread_join(tid[i], NULL);

        }

    

    int count = MAX_THREAD/2; //피라미드 형식으로 계산하기위한 인자

    while (count) {

        for (i=0; i<count; i++) {

            pthread_create(&tid_final, NULL, thread_func_final, (void*)i); //파일입출력말고 덧셈만 수행하는 스레드 생성

            pthread_join(tid_final, NULL);

        }

        count= count/2; //0으로 떨어질 때까지 수행

    }

    printf("FINAL RESULT: %d\n", sum[0]); //최종 결과를 출력

    

#ifdef MUTEX

    pthread_mutex_destroy (&mutex); //뮤텍스 제거

#endif

    

    return 0;

}

void* thread_func(void *arg) {

    FILE *f_first;

    FILE *f_second;

    char name[10] = {0, };

    int list = (int)arg;

    int i=list*2;

    int first = 0;

    int second = 0;

    

    //첫번째 파일 읽음

    sprintf(name, "%d", i);

    f_first=fopen(name, "r+");

    if (f_first==NULL) {

        printf("file read error\n");

        return (void*)0;

    }

    fscanf(f_first, "%d", &first);

    fclose(f_first);

    

    //두번째 파일 읽음

    i++;

    sprintf(name, "%d", i);

    f_second=fopen(name, "r+");

    if (f_second==NULL) {

        printf("file read error\n");

        return (void*)0;

    }

    fscanf(f_second, "%d", &second);

    fclose(f_second);

    

#ifdef MUTEX

    pthread_mutex_lock(&mutex); //뮤텍스 잠금

#endif

    

    sum[list] = first + second; //덧셈 연산 수행

    printf("step: %d, %d + %d = %d\n", ++step, first, second, sum[list]); //로그 출력

    

#ifdef MUTEX

    pthread_mutex_unlock(&mutex); //뮤텍스 잠금해제

#endif

    return (void*)1;

}

void* thread_func_final(void *arg) {

    int list = (int)arg;

    int first = list*2;

    

#ifdef MUTEX

    pthread_mutex_lock(&mutex); //뮤텍스 잠금

#endif

    printf("step: %d, %d + %d = ", ++step, sum[first], sum[first+1]); //로그 출력    

    sum[list] = sum[first] + sum[first+1]; //덧셈 연산 수행

    printf("%d\n", sum[list]);

#ifdef MUTEX

    pthread_mutex_unlock(&mutex); //뮤텍스 잠금해제

#endif

    

    return (void*)1;

}

2. 다중 프로세스로 수행하는 프로그램 작성

Makefile

all: gen_file.c schedtest.c

gcc -o gen_file gen_file.c

gcc -o schedtest schedtest.c -lrt

gen_file.c

//

//  gen_file.c

//  gen_file

//

//  Created by Eon on 13/11/2017.

//  Copyright © 2017 Eon. All rights reserved.

//

#include <stdio.h>

#include <dirent.h>

#include <string.h>

#include <sys/stat.h>

#include <sys/types.h>

#include <stdlib.h>

#include <linux/sched.h>

#define MAX_THREAD 10000

struct stat st = {0};

int main(void) {

int i = 0;

char current_dir[1024] = {0,};

char number[6] = {0,};

if (stat("./tmp2", &st) == -1)

    mkdir("./tmp2", 0700);

for(i=0; i<MAX_THREAD; i++) {

getcwd(current_dir, 1024); //get current working directory

sprintf(number, "%d", i);

strcat(current_dir, "/tmp2/");

strcat(current_dir, number);

FILE* f_write = fopen(current_dir, "w"); //file open

if(f_write == NULL)    //if file open error

      printf("file open failed. \n");

fprintf(f_write, "%d", (int)(1 + rand()%9)); //write random number into "./tmp2/i" file

fclose(f_write);

memset(current_dir, 0, 1024);

}

return 0;

}

schedtest.c

//

//  schedtest.c

//  schedtest

//

//  Created by Eon on 13/11/2017.

//  Copyright © 2017 Eon. All rights reserved.

//

#include <stdio.h>

#include <string.h>

#include <sys/types.h>

#include <stdlib.h>

#include <time.h>

#include <unistd.h>

#include <fcntl.h>

#include <sched.h>

#include <linux/sched.h>

#define MAX_PROCESSES 10000

#define BUFF_SIZE 1024

int main(){

    pid_t pid;

    struct timespec Start_id, End_id;

    struct sched_param param;

    int i = 0, fd = 0;

    char current_dir[1024] = {0, };

    char number[6] = {0, };

    char buff[BUFF_SIZE] = {0, };

    param.sched_priority = 1;    //스케줄러를 NORMAL로 테스트 할려면 0, FIFO, RR로 테스트 할려면 1

    

    clock_gettime(CLOCK_REALTIME, &Start_id);   //시작하는 시간을 측정.

    

    for(i = 0; i < MAX_PROCESSES; i++){   //프로세스를 MAX_PROCESSES만큼 생성

        getcwd(current_dir, 1024);

        strcat(current_dir, "/tmp2/");

        sprintf(number, "%d", i);

        strcat(current_dir, number);

        

        if((pid = fork()) < 0) { //포크로 프로세스 생성, 에러시 종료.

            printf("Fork Failed \n");

            return -1;

        }

        else if(pid == 0){   //프로세스가 자식 프로세스라면

            if(sched_setscheduler(getpid(), SCHED_RR, &param) != 0){ //CPU 스케줄링을 바꿈.. SCHED_FIFO, SCHED_RR, SCHED_OTHER

                printf("Chage CPU scheduler failed!!\n");

                return 0;

            }

            if (0 < ( fd = open(current_dir, O_RDONLY))) {

                read(fd, buff, BUFF_SIZE);   //파일을 읽음.

                close(fd);

            }

            else

                printf("File open error!!\n");

            return 0;

        }

        memset(current_dir, 0, 1024);

        memset(number, 0, 6);

        memset(buff, 0, BUFF_SIZE);

    }

    

    while( (wait(NULL)) > 0 ); // 자식들을 기다림..

    

    clock_gettime(CLOCK_REALTIME, &End_id);   //완료된 시간을 측정.

    

    printf("Elapsed time to completion: %f\n",

           ((End_id.tv_sec-Start_id.tv_sec) + (double)(End_id.tv_nsec-Start_id.tv_nsec)/1000000000));

    

    return 0;

}

Analysis

1. 다중 쓰레드로 수행하는 프로그램 작성

먼저 gen_file를 구현하였다. 이 프로그램에서는 tmp1이라는 디렉토리를 일단 만들고 전역변수로 선언이 된 MAX_THREAD의 수의 2배만큼 파일을 tmp1이라는 디렉토리 안에 생성을 한다. 파일들은 모두 9이하의 난수들이 들어있으며 난수의 숫자가 입력이된 파일을 생성하는 것이 이 프로그램의 목적이다. 

gen_file을 구현을 완료하고 gen_thread 프로그램을 구현하였다. gen_thread가 2-1 문제에서 가장 중요한 프로그램이다. 이 프로그램은 POSIX 스레드를 사용하여 동시다발적으로, 병렬로 덧셈을 계산하는 것이 가장 핵심 알고리즘이다. 먼저 MAX_THREAD의 전역변수를 선언하였다. 그리고 pthread.h 라이브러리를 선언하여 pthread_t 타입의 배열을 선언하였다. 이 배열의 길이는 MAX_THREAD 만큼 길이가 지정이 되었다. 그리고 pthread_create 함수를 사용하여 MAX_THREAD 만큼 쓰레드를 생성하였다. 쓰레드의 인자로는 선언한 쓰레드 pthread_t 타입의 배열과, 따로 구현을 한 함수인 thread_func가 세번째 인자로 들어가고 4번째 인자로 쓰레드에 argument를 입력해주는 I 값이 들어간다. 각각의 쓰레드들은 병렬적으로 수행이 된다. 쓰레드들은 모두 thread_func를 실행을한다. thead_func은 일단 파일을 첫번째 파일과 두번째 파일을 읽는다. 첫번째와 두번째는 쓰레드에 입력으로 들어온 argument의 값에 따라서 어떤 파일을 읽을 건지 결정이된다. 예를 들어서 첫번째 쓰레드는 tmp1 디렉토리에 들어있는 0,1 파일의 난수를 읽어서 숫자를 first, second integer 변수로 가지고 온다. 그리고 최종적으로 두 값을 전역변수인 sum 배열에 저장을 하고 함수(쓰레드)는 종료된다. 즉, thread_func는 두 파일을 읽고 숫자로 변환하여 덧셈을 전역변수에 저장하는 함수이다. MAX_THREAD * 2만큼의 파일이 존재함으로 두 파일의 숫자를 더하는 쓰레드는 총 MAX_THREAD 만큼 존재를 한다. 아래의 그림과 같이 만약 MAX_THREAD가 4이면 총 8개의 난수가 적힌 파일이 생성이 되고, 각각의 쓰레드들은 두 파일을 읽어서 덧셈을 수행을 한다. 이러한 역할을 해주는 함수가 thread_func()가 수행을 한다.

각각의 파일로 부터 덧셈을 수행을 한 후에 쓰레드들끼리의 결과를 덧셈을 수행하는 쓰레드가 따로 존재하도록 구현을 하였다. thread_func_final()함수를 수행하는 쓰레드를 따로 구현하여 파일을 읽지 않고 1~4쓰레드에서 결과를 읽어드려서 수행하는 쓰레드가 따로 존재를 한다. 즉 피라미드 형식으로 계속 덧셈 연산을 수행하는 구조로 구현을 하였다. 

위의 다이어그램처럼 프로그램이 진행이 된다. 파란색 부분은 모두 thread_func으로 연산을 수행하는 쓰레드들이고 주황색부분은 모두 thread_func_final 함수를 통하여 연산을 수행하는 쓰레드들이 존재를 한다. 즉 MAX_THREAD가 많으면 많을 수록 위와 같은 피라미드 규모, 쓰레드의 수가 기하급수적으로 많아지게 되어있다. 

또한 코드를 보다시피 Mutex를 사용하여 쓰레드들끼리의 Lock을 통하여 앞선 연산을 방지하였다. 다른 메인 함수에서 Mutex를 생성하였고 thread_func, thread_func_final에서 덧셈 연산을 수행하는 코드를 진행하기 전에 Lock을 수행하고 덧셈 코드가 끝나면 Lock을 해제하였다. 나머지부분은 쓰레드들 끼리 영향을 미치지 않지만 만약 thread1이 결과를 출력하기 전에 thread5가 연산을 수행할 수도 있기 때문에 덧셈 코드 한줄만 임계구역으로 지정하여 구현을 하였다. 아래의 스크린샷과 같이 연산을 성공적으로 수행을 하였다. 

 




2. 다중 프로세스로 수행하는 프로그램 작성

먼저 gen_file를 구현하였다. 이 프로그램에서는 tmp2이라는 디렉토리를 일단 만들고 전역변수로 선언이 된 MAX_THREAD의 수 만큼 파일을 tmp2이라는 디렉토리 안에 생성을 한다. 파일들은 모두 9이하의 난수들이 입력되어 있으며, 난수의 숫자가 입력이된 파일을 생성하는 것이 이 gen_file 프로그램의 목적이다. 

gen_file을 구현한 후에 schedtest를 구현하였다. schedtest 프로그램은 CPU 스케줄링 알고리즘을 변경하여 MAX_PROCESSES 만큼 프로세스들을 생성하여 tmp2에 들어있는 파일들의 integer 값을 읽는 것이 전체 흐름이다. 그리고 마지막에 수행한 시간을 출력하여 CPU 알고리즘 마다 속도를 비교하는 것이 이 프로그램의 목적이다. 

먼저 전역벽수 MAX_PROCESSES를 10000으로 선언을 하였다. 10000개 정도의 프로세스들을 생성해야 성능을 비교할 수 있을 정도가 된다. 그리고 main 함수에서 pid, time을 측정하기위한 timespec 타입의 구조체를 시작과 끝을 선언을 하였다. 그리고 스케줄링 우선순위를 사용하기위해서 sched_param 타입의 구조체를 선언을 하였다. 그밖에 디렉토리, 변수등을 위한 value들을 선언을 하였다. 수행을 하기에 앞서서 clock_gettime 함수를 사용하여 시작하는 시간을 측정을하였다. 그리고 반복문을 선언을 하여 MAX_PROCESSES만큼 파일을 읽고 fork를 통한 프로세서를 생성하였다. 자식 프로세서에서는 sched_setssheduler 함수를 선언을 하여 현재 프로세서의 ID와 스케줄링 알고리즘, param 값을 파라미터로 전달하였다 그리고 디렉토리의 파일을 읽고 자식 프로세서는 종료가 된다. 부모프로세서는 모든 자식 프로세서를 기다리고 모두 종료가 되었으면 clock_gettime 함수를 통하여 타임을 측정을 한다. 그리고 start_id, end_id 값을 가지고 end-start를 연산을 통하여 총 걸린 시간을 출력하고 프로그램이 종료가 된다. 여기서 핵심은 sched_setscheduler에서 두번째 인자를 바꿔가면서 프로그램을 다시 컴파일하고 수행하면서 Other, FIFO, Round Robin를 비교하였다. 결과는 아래와 같다.

CPU 스케줄링 Other 결과

0.569

0.563 

CPU 스케줄링 FIFO 결과

0.499

0.496

CPU 스케줄링 Round Robin 결과

0.463

0.491

위의 스크린샷 결과들을 비교해 볼 때, Round Robin과 FIFO는 거의 동일한 타이밍을 보였고 Other는 0.56으로 좀 더 느리게 결과가 나왔다. 즉, FIFO ≈ Round Robin > Other로 결과가 나왔다.

Evaluation

2-1을 진행을 하면서 gen_file 프로그램의 구현은 매우 간단하여 쉽게 구현할 수 있었다. 2-2의 gen_file도 마찬가지로 거의 동일하여 구현하기 쉬웠다. 핵심은 바로 2-1에서는 gen_thread이였다. 일단 쓰레드가 병렬로 처리가되어 이론적으로 이해하기가 쉬웠고 다이어그램을 보면 되게 간단한 프로그램이였다. 하지만 쓰레드로 구현을 하니 생각해야될 것도 매우 많았고 세마포어, 뮤텍스 등 락을 하는 것 또한 구현을 해야되었다. 하나의 프로세스에서 하나의 쓰레드로 이 프로그램을 구현을 한다면 되게 간단하게 구현을 할 수 있을 것 같다. 하지만 쓰레드로 병렬 프로그램이 구현하기가 되게 어렵다는 것을 깨닫았다. 이번 실습을 통하여 쓰레드의 개념을 확실이 이해를 하였고 POSIX 쓰레드를 사용하면서 실제 듀얼 코어, 쿼드 코어 등등 멀티 코어의 컴퓨터에서 어떻게 빠르게 프로그래밍을 할 수 있는 지 실제로 와닫는 계기가 되었다.  실제로 컴퓨터에 많은 CPU의 자원이 있다면 프로그램도 이 자원을 최대한 활용할 수 있게 구현을 할 수 있는 쓰레드의 유용성과 효율성을 배울 수 있어서 매우 기쁘게 생각한다.

2-2를 진행하면서 CPU 스케줄링에 대해서 실제로 컴퓨터의 성능에 어떠한 영향을 주는지 알 수 있었다. 특히 현대 컴퓨터의 멀티테스킹을 통하여 CPU의 스케줄링이 매우 중요하다고는 생각한다. 하지만 실제로 이러한 스케줄링 알고리즘이 성능에 어떻게 미치는 지, 수학적인 계산과 비교를 통하여 알 수 있었던 실습인 것 같다. 하지만 MAX_PROCESSES를 10000이 아닌 더 큰 숫자를 통하여 Round Robin과 FIFO가 10000에서는 거의 동일하게 시간이 나타났는데, MAX_PROCESSES를 더 크게 늘려서 Round Robin과 FIFO 중에 어떤 알고리즘이 더 효율적인지 비교될 정도로 큰 수를 사용하여 한번 더 비교해보고 싶다. 실제 CPU 알고리즘의 구현은 아니였지만 여러 CPU 스케줄링 알고리즘을 비교하여 어떤것이 더 좋은 알고리즘인지 알 수 있었던 계기가 되었다.