Software-based Solutions for Critical section problem

• Dekker’s Algorithm

  2개의 프로세스가 공유 자원을 문제 없이 사용할 수 있는 알고리즘

• Eisenberg & McGuire’s Algorithm:

  n개의 프로세스를 사용하여 n - 1 이하의 대기 시간을 보장하는 알고리즘

• *Peterson’s Algorithm*

  Critical Section Problem 가장 완전하게 해결한 알고리즘.

  But, load & store와 같은 기계어 명령이 현대 컴퓨터에서 제대로 작동할 것이라는 보장이 안된다.

Peterson’s Algorithm

• 기본적으로 2개의 프로세스를 이용하며, 필요한 경우 확장할 수 있음.

while (true)
{
	flag[i] = true;
	turn = j;

	while (flag[j] && turn == j) // entry section
		;

	/* critical section */

	flag[i] = false; // exit section

	/* remainder section */
}

i, j 두 개의 프로세스 존재

• i 프로세스는 j 프로세스가 exit section에 도달해 flag[j] = false; 가 되면 Critical section 진입
• j 프로세스가 remainder section 종료 후 다시 entry section으로 돌아와서 turn = i; 가 되면 Critical section 진입

→ i, j 두 개의 프로세스가 동시에 Critical section에 진입 불가능

<간단하게 구현>

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

#define true 1
#define false 0

int sum = 0;

int turn;
int flag[2];

int main()
{
	pthread_t tid1, tid2;
	pthread_create(&tid1, NULL, producer, NULL);
	pthread_create(&tid2, NULL, consumer, NULL);
	pthread_join(tid1, NULL);
	pthread_join(tid2, NULL);
	printf("sum = %d\\n", sum);
}

<생산자 코드>

void* producer(void* param)
{
	for (int k = 0; k < 10000; ++k)
	{
		/* entry section */
		flag[0] = true;
		turn = 1;

		while (flag[1] && turn == 1)
			;

		/* critical section */
		sum++;

		/* exit section */
		flag[0] = false;

		/* remainder section */
	}
	pthread_exit(0);
}

<소비자 코드>

void* consumer(void* param)
{
	for (int k = 0; k < 10000; ++k)
	{
		/* entry section */
		flag[1] = true;
		turn = 0;

		while (flag[0] && turn == 0)
			;

		/* critical section */
		sum--;

		/* exit section */
		flag[1] = false;

		/* remainder section */
	}
	pthread_exit(0);
}