6. Process Synchronization _ 1 , Peterson's Solution

Backgorund

프로세스 통신 방법

- Message passing 

- Shared memory    ->   충돌이 일어날 수 있다.     ex) producer-consumer problem

 

두 프로세스가 동시에 작동하여 일어날 수 있는 문제들 :

Producer-consumer problem

 

• Concurrent Access of Shared Data

문제가 있는 알고리즘

modification operation 중에 switching 이 일어날 수 있다.

=> Synchronization 문제가 발생한다.  (아래 표 같은 상황이 일어날 수 있다.)

Problematic situation

 

- Race Condition   (문제점)

매우 안 좋은 현상이다.

동일한 코드여도 실행되는 순서에 따라 다른 값을 낼 수 있다.

      -> 버그로 이어진다 (concurrent 한 상황에서 발생한다. 수정하기에도 어렵다.)

프로세스들이 shared data를 통해 커뮤니케이션 할 때 race condition 이 발생한다.

 

- Synchronization (해결 방법)

Race Conditon이 일어나지 않도록 미연에 방지하는 방법이다.

어떤 순서로 실행해도 항상 동일한 값을 내도록 프로세스들을 coordination 하게 한다.

      -> 한번에 하나의 프로세스만 공유 데이터에 접근할 수 있도록 한다.

 

 

---

 

 

The critical - section problem

컴퓨터에서 나타나는 여러 synchronization 문제들을 추상화해서 아주 대표적인 문제로 만든 것이다.

 

n개의 프로세스가 동시에 시스템에서 실행되고 있다고 하자. 각 프로세스는 공유 데이터에 access하기를 원한다.

코드를 두 구간으로 나눌 수 있다:

 

- Critical section 

   마치 피팅룸같은 역할, 프로세스가 공유되는 데이터에 접근하는 부분. (shared memory를 읽어오는 것도 해당)

   Entry secion : critical section에 들어가도 되는지 확인하고, 들어가서 문을 잠그는 것. (다른 프로세스들이 못들어오게)

   Exit section : critical section에서 나올 때는 문을 열어서 다른 프로세스들이 들어갈 수 있게 해줘야 한다.

 

- Remainder section

   프로그램 코드가 shared memory를 access하지 않는 부분. (race condition이 절대 발생하지 않는다.)

 

이 중 하나만 critical section에 들어갈 수 있다.

 

• The Critical-Section Problem의 solution이 가져야 하는 조건

- Mutal exclusion : 한 프로세스가 critical section에 있으면 다른 프로세스는 shared data에 접근할 수 없다.

- Progress : critical section에 아무도 없을 때 들어가고 싶어하는 프로세스 중 하나를 즉시 선택해서 critical section에 들어가는 것을 허락해준다. (선택이 지연되면 안된다.)

- Bounded waiting : 어떤 프로세스가 기다리는 횟수가 제한되어 있다 (전체 프로세스 갯수보다 더 기다리면 안된다와 같은 bound를 걸어준다.) 이로인해, 한 프로세스가 계속해서 기다리는 경우를 방지한다.

 

 

kernel 자체가 critical-section의 중요한 예이다. 

Kernel은 본질적으로 shared resource이다. 

 

• Non-preemptive kernel :  kernel 내부에서는 race-condition이 잘 발생하지 않는다.
      
     -> critical-section 문제가 심각하게 발생하지 않는다.
  
  
  
• Preemptive kernel : kernel 모드에서 돌아가는 system call 중간에도 switching을 당할 수 있다면, 공유 데이터에 접근할 때  언제든지 race-condition이 발생 가능하다. 
  
     -> Synchronizatoin을 제대로 해줘야 한다.

* preemptive kernel & preemptive scheduling 의 차이점? 

Scheduling은 preemptive여도 kernel 내부에서 switching을 하지 않으면 kernel 자체는 non-preemptive이다.

 

 

 

• Peterson's Solution

Critical Section probelm을 위한 S/W solution이다.

 

두개의 프로세스 P0과 P1이 있다고 하자 (절대적인 프로세스의 index, i 또는 j로 표시 가능) 

P0은 현재 실행하고 있는 프로세스이고, P1은 상대 프로세스이다.

두 프로세스는 서로 경쟁한다.

 

int turn;   // 프로세스가 실행되는 것을 허락했다는 표시. 0이라면 P0이 critical section에 들어간 것이다. P1은 기다려야한다.

그러니까 turn 변수는 누가 critical section에 들어갈 차례인지 나타낸다.

 

boolean flag[2];  // 두개의 프로세스는 두개의 flag를 갖는다. 현재 각 프로세스가 critical section에 있는지 없는지 또는 들어가려고 하는지 확인한다. flag[i]가 TRUE라면, Pi는 critical section에 들어가려고 하는 것이다.

그러니까 flag 값은 프로세스 중 누가 criticatl section에 진입할 것인지 나타낸다.

 

 

- 앞에 세 조건 (Mutal exclusion, Progress, Bounded waiting) 을 만족하는 Peterson's Solution

먼저, P0을 보자면 flag[0]=true로 설정하여 P0이 critical section으로 진입하고 싶다고 표시한다. 이 때, trun=1로 해주면서 P1이 먼저 들어가라고 양보 해준다.

여기서 만약 P1이 flag[1]==false 상태이면 P0은 while 문에 걸리지 않고, critical section으로 들어간다.

그러면 P1은 while statement에서 기다리고 있다가 turn이 0또는 1이 된다.

turn이 0이 되면, P0은 critical section에 있는데

그게 아니라 turn이 1이라면 P1이 critical section에 들어간다.

P1이 critical section에서 나오면, P1은 flag[1]을 false로 설정하고 P1이 turn을 0으로 만들기 때문에 P0이 critical section으로 들어간다.

그러므로, P0은 critical section으로 들어가 최대한 다른 프로세스를 기다린다.

 

1. flag[0] = true로 설정하여 0번 스레드가 임계 영역 진입을 하고 싶다고 표시한다.

2. 이때 turn = 1을 주며 1번 프로세스가 먼저 들어가라고 양보해준다.

3. 만약 이때 컨텍스트 스위칭이 되지 않았다면 while문에 갇히게 된다.

4. 1번 프로세스가 이제 모든 작업을 끝내면 turn = 0, flag[1] = false가 되므로 0번 프로세스가 다시 돌 수 있다.

 

 

---

 

Peterson's Algorithm in Process Synchronization

(출처 : https://www.geeksforgeeks.org/petersons-algorithm-in-process-synchronization/ )

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <time.h> 
#include <sys/types.h> 
#include <sys/ipc.h> 
#include <sys/shm.h> 
#include <stdbool.h> 
#define _BSD_SOURCE 
#include <sys/time.h> 
#include <stdio.h> 
  
#define BSIZE 8 // Buffer size 
#define PWT 2 // Producer wait time limit 
#define CWT 10 // Consumer wait time limit 
#define RT 10 // Program run-time in seconds 
  
int shmid1, shmid2, shmid3, shmid4; 
key_t k1 = 5491, k2 = 5812, k3 = 4327, k4 = 3213; 
bool* SHM1; 
int* SHM2; 
int* SHM3; 

int shm_nattch=0;
  
int myrand(int n) // Returns a random number between 1 and n 
{ 
    time_t t; 
    srand((unsigned)time(&t)); 
    return (rand() % n + 1); 
} 

//main 함수
int main() 
{ 

	//공유 메모리 생성
    shmid1 = shmget(k1, sizeof(bool) * 2, IPC_CREAT | 0660); // flag 
    shmid2 = shmget(k2, sizeof(int) * 1, IPC_CREAT | 0660); // turn 
    shmid3 = shmget(k3, sizeof(int) * BSIZE, IPC_CREAT | 0660); // buffer 
    shmid4 = shmget(k4, sizeof(int) * 1, IPC_CREAT | 0660); // time stamp 
  
    //공유 메모리 생성에 실패했을 때
    if (shmid1 < 0 || shmid2 < 0 || shmid3 < 0 || shmid4 < 0) { 
        perror("Main shmget error: "); 
        exit(1); 
    } 
    
    
    //buffer 공유 메모리를 프로세스 몸안으로 첨부한다. 
    //shmat가 성공하면 시스템은 shmid_nattch를 +1한다.
    //성공하면 attach된 shared memory segment(프로세스에서의 공유 메모리 주소)를 반환하고 실패하면 -1을 반환한다.
    SHM3 = (int*)shmat(shmid3, NULL, 0); 
    
    if(SHM3 == -1){
    	perror("Shmat failed! \n");
        exit(0);
    }
    else
    	shmid_nattch ++;
    
    //버퍼 초기화 시켜주기
    int ix = 0; 
    while (ix < BSIZE) // Initializing buffer 
        SHM3[ix++] = 0; 
  
  /* 
  struct timeval{
  	long tv_sec;
    long tv_usec;
 }
 */
    struct timeval t; 
    time_t t1, t2; 
    gettimeofday(&t, NULL);  //마이크로 초까지 현재 시간을 가져온다.
    t1 = t.tv_sec; 
  
    int* state = (int*)shmat(shmid4, NULL, 0); 
    *state = 1; 
    int wait_time; 
  
    int i = 0; // Consumer   -> 부모
    int j = 1; // Producer   -> 자식
  
    if (fork() == 0) // Producer code  자식 프로세스
    { 
        SHM1 = (bool*)shmat(shmid1, NULL, 0); 
        SHM2 = (int*)shmat(shmid2, NULL, 0); 
        SHM3 = (int*)shmat(shmid3, NULL, 0); 
        if (SHM1 == (bool*)-1 || SHM2 == (int*)-1 || SHM3 == (int*)-1) { 
            perror("Producer shmat error: "); 
            exit(1); 
        } 
  
        bool* flag = SHM1; 
        int* turn = SHM2; 
        int* buf = SHM3; 
        int index = 0; 
  
        while (*state == 1) { 
            flag[j] = true; 
            printf("Producer is ready now.\n\n"); 
            *turn = i; 
            while (flag[i] == true && *turn == i) 
                ; 
  
            // Critical Section Begin 
            index = 0; 
            while (index < BSIZE) { 
                if (buf[index] == 0) { 
                    int tempo = myrand(BSIZE * 3); 
                    printf("Job %d has been produced\n", tempo); 
                    buf[index] = tempo; 
                    break; 
                } 
                index++; 
            } 
            if (index == BSIZE) 
                printf("Buffer is full, nothing can be produced!!!\n"); 
            printf("Buffer: "); 
            index = 0; 
            while (index < BSIZE) 
                printf("%d ", buf[index++]); 
            printf("\n"); 
            // Critical Section End 
  
            flag[j] = false; 
            if (*state == 0) 
                break; 
            wait_time = myrand(PWT); 
            printf("Producer will wait for %d seconds\n\n", wait_time); 
            sleep(wait_time); 
        } 
        exit(0); 
    } 
  
    if (fork() == 0) // Consumer code 
    { 
        SHM1 = (bool*)shmat(shmid1, NULL, 0); 
        SHM2 = (int*)shmat(shmid2, NULL, 0); 
        SHM3 = (int*)shmat(shmid3, NULL, 0); 
        if (SHM1 == (bool*)-1 || SHM2 == (int*)-1 || SHM3 == (int*)-1) { 
            perror("Consumer shmat error:"); 
            exit(1); 
        } 
  
        bool* flag = SHM1; 
        int* turn = SHM2; 
        int* buf = SHM3; 
        int index = 0; 
        flag[i] = false; 
        sleep(5); 
        while (*state == 1) { 
            flag[i] = true; 
            printf("Consumer is ready now.\n\n"); 
            *turn = j; 
            while (flag[j] == true && *turn == j) 
                ; 
  
            // Critical Section Begin 
            if (buf[0] != 0) { 
                printf("Job %d has been consumed\n", buf[0]); 
                buf[0] = 0; 
                index = 1; 
                while (index < BSIZE) // Shifting remaining jobs forward 
                { 
                    buf[index - 1] = buf[index]; 
                    index++; 
                } 
                buf[index - 1] = 0; 
            } else
                printf("Buffer is empty, nothing can be consumed!!!\n"); 
            printf("Buffer: "); 
            index = 0; 
            while (index < BSIZE) 
                printf("%d ", buf[index++]); 
            printf("\n"); 
            // Critical Section End 
  
            flag[i] = false; 
            if (*state == 0) 
                break; 
            wait_time = myrand(CWT); 
            printf("Consumer will sleep for %d seconds\n\n", wait_time); 
            sleep(wait_time); 
        } 
        exit(0); 
    } 
    // Parent process will now for RT seconds before causing child to terminate 
    while (1) { 
        gettimeofday(&t, NULL); 
        t2 = t.tv_sec; 
        if (t2 - t1 > RT) // Program will exit after RT seconds 
        { 
            *state = 0; 
            break; 
        } 
    } 
    // Waiting for both processes to exit 
    wait(); 
    wait(); 
    printf("The clock ran out.\n"); 
    return 0; 
} 

 

 

내가 고쳐 본 코드

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <time.h> 
#include <sys/types.h> 
#include <sys/ipc.h> 
#include <sys/shm.h> 
#include <stdbool.h> 
#define _BSD_SOURCE 
#include <sys/time.h> 
#include <stdio.h> 
  
#define BSIZE 8 // Buffer size 

int shm_nattch=0;
int i = 0; // Consumer   
int j = 1; // Producer   

void Producer(int shm_id);		
void Consumer(int shm_id);		

typedef struct {
    bool flag[2];
    int turn;
    int buf[BSIZE];
} Buffer;

int num=0;

Buffer global_buffer;


int myrand(int n){
	time_t t;
	srand((unsigned)time(&t));
	return (rand()%n+1);
}


int main() 
{ 

    int shm_id=0; 

	
    shm_id = shmget((key_t)1234, sizeof(Buffer), IPC_CREAT | 0660);

    if(shm_id ==-1){
		perror("Shmget Error");
		exit(0);
	}

    Buffer *buffer = &global_buffer;
    buffer=shmat(shm_id, (void *)0, IPC_CREAT |0660);

    if(buffer==(void*)-1){
		perror("shmat attach is failed:");
		exit(0);
	}
    else
        shm_nattch++;


    
    int ix=0;

    while(ix<BSIZE)
        buffer->buf[ix++] =0;

    /*
    shmid1 = shmget(k1, sizeof(bool) * 2, IPC_CREAT | 0660); // flag 
    shmid2 = shmget(k2, sizeof(int) * 1, IPC_CREAT | 0660); // turn 
    shmid3 = shmget(k3, sizeof(int) * BSIZE, IPC_CREAT | 0660); // buffer 


    //
    if (shmid1 < 0 || shmid2 < 0 || shmid3 < 0 || shmid4 < 0) { 
        perror("Main shmget error: "); 
        exit(1); 
    } 
    */

    
  
    if (fork() == 0) // Producer code 
    { 
        Producer(shm_id);
    } 
  
    if (fork() == 0) // Consumer code 
    { 
        Consumer(shm_id);
    } 

    if(-1==shmdt((void*)buffer)){
		perror("failed shmdt");
		exit(0);
	}
    else
    {
        shm_nattch--;
    }
  
    // Waiting for both processes to exit 
    int status=0;
	wait(&status); 
    wait(&status); 
    
    if(shm_nattch==0){  
        if(shmctl(shm_id, IPC_RMID,0)){       
            printf("Failed to deallocate the shared memory block\n");
            exit(-1);
        }
    }
    else
    	printf("Could not deallocate shared memory.\n");
    
    return 0; 
} 

void Consumer(int shm_id){

    Buffer *buffer = &global_buffer;
    buffer=shmat(shm_id, (void *)0, IPC_CREAT |0660);

    if(buffer==(void*)-1){
		perror("shmat attach is failed:");
		exit(0);
	}
    else
        shm_nattch++;


    int index = 0; 
    buffer->flag[i] = false; 
    num++;

    sleep(5); 

    while(num<=500){
        //Entry Section
        buffer->flag[i] = true; 
        printf("Consumer is ready now.\n\n"); 
        buffer->turn = j; 

        while (buffer->flag[j] == true && buffer->turn == j); 
    
        // Critical Section Begin 
        if (buffer->buf[0] != 0) { 
            printf("Job %d has been consumed\n",buffer->buf[0]); 
            buffer->buf[0] = 0; 
            index = 1; 

            while (index < BSIZE) // Shifting remaining jobs forward 
            { 
                buffer->buf[index - 1] = buffer->buf[index]; 
                index++; 
            } 
                    
            buffer->buf[index - 1] = 0; 
        } 
        
        else
            printf("Buffer is empty, nothing can be consumed!!!\n"); 
                
        printf("Buffer: "); 
        index = 0; 
                
        while (index < BSIZE) 
            printf("%d ", buffer->buf[index++]); 
        printf("\n"); 
        // Critical Section End 
    
        //Exit Section
        buffer->flag[i] = false;
		sleep(1);
    }
    
    if(-1==shmdt((void*)buffer)){
		perror("failed shmdt");
		exit(0);
	}
    else
    {
        shm_nattch--;
    }
    
    exit(0);
}

void Producer(int shm_id){

    Buffer *buffer = &global_buffer;
    buffer=shmat(shm_id, (void *)0, IPC_CREAT |0660);

    if(buffer==(void*)-1){
		perror("shmat attach is failed:");
		exit(0);
	}
    else
        shm_nattch++;

   
    int index = 0; 
    num++;
  
    while(num<=500){
        //Entry Section
        buffer->flag[j] = true; 
        printf("Producer is ready now.\n\n"); 
            
        buffer->turn = i; 
        while (buffer->flag[i] == true && buffer->turn == i); 
    
            
        // Critical Section Begin 
        index = 0; 
        while (index < BSIZE) { 
            if (buffer->buf[index] == 0) { 
                int tempo = rand()%(BSIZE*3)+1; 
                printf("Job %d has been produced\n", tempo); 
                buffer->buf[index] = tempo; 
                break; 
            } 
            index++; 
        } 
            
        if (index == BSIZE) 
            printf("Buffer is full, nothing can be produced!!!\n"); 
            
        printf("Buffer: "); 
        index = 0; 
            
        while (index < BSIZE) 
            printf("%d ", buffer->buf[index++]); 
        printf("\n"); 
        // Critical Section End 
    
        //Exit Section
        buffer->flag[j] = false; 
    	sleep(1);
	}

    if(-1==shmdt((void*)buffer)){
		perror("failed shmdt");
		exit(0);
	}
    else
    {
        shm_nattch--;
    }
    
    exit(0);

}