Critical Sections and Semaphores - 시스템프로그래밍

Critical sections

• process chain ( 프로세스가 계속 자식을 만들어나가는 방식 ) 을 만들고 각각의 프로세스는 정보를 출력한다. 바로 출력하는 것이 아니라 char buffer에 저장해두었다가 loop를 돌면서 char 하나씩 출력하는 것임 with delay ( 딜레이동안 context switch가 일어날 가능성이 있음 ).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>
#include "restart.h"
#define BUFSIZE 1024

int main(int argc, char *argv[]){
	char buffer[BUFSIZE];
	char *c;
	pid_t childpid = 0;
	int delay;
	volatile int dummy = 0;
	int i, n;

	if(argc != 3){
		fprintf(stderr, "Usage: %s processes delay\n", argv[0]);
		return 1;
	}

	// n개의 프로세스
	n = atoi(argv[1]);
	// char를 프린트 할 때마다 얼마나 딜레이를 시킬 것이냐.
	delay = atoi(argv[2]);
	// 프로세스가 자식 프로세스를 만들고 본인은 loop를 나오는 형식
	for(i = 1; i < n; i++)
		if(childpid = fork()) break;
	
	// buffer에 출력 ( 버퍼에 담는다 )
	snprintf(buffer, BUFSIZE, "i:%d process ID:%ld child ID:%ld\n", i, (long)getpid(), (long)getpid(), (long)childpid);
		
	// 버퍼의 시작 주소를 포인터에 대입
	c = buffer;
	
	/**************** start of critical section *****************/
	// snprintf는 끝에 자동으로 null을 넣어주기 때문에
	while(*c != '\0'){
		// c 포인터가 가리키고 있는 값을 stderr에 출력
		fputc(*c, stderr);
		c++;
		for(i = 0; i < delay; i++)
			dummy++;
	}
	/**************** end of critical section *****************/	
	if(r_wait(NULL) == -1)
		return 1;
	return 0;
}

Critical sections

• Entry section
• critical section의 진입 영역
• 커널에게 critical section에 접근해도 되는지 권한을 물어봄

• Critical section
• 코드의 특정 부분을 critical section으로 만드는 것
• shared resource를 access하는 영역을 포함하는 코드 혹은 한번에 하나만 접근하려고 하는 경우

• Exit section
• 다음 프로세스에게 lock을 넘겨주기 위해 lock을 release

• Remainder section
• Exit section 이후의 코드

Solution to Critical-section Problem

1. Mutual Exclusion

2. Progress
• 만약 어떤 프로세스도 critical section에 있지 않고 critical section에 진입하고자 하는 프로세스가 있다면 ( entry section에서 대기 ), 그러한 프로세스들 ( remainder section에 있지 않은 ) 중에서 다음 프로세스를 선택해서 critical section으로 진입할 수 있어야 한다.

3. Bounded Waiting
• critical section에 들어가고자 하는 프로세스가 대기하는 시간은 bound가 있어야 한다. ( 주구장창 기다리게 하지 마라 )
• critical section 접근하려고 대기하는 프로세스들에게는 fair한 기회를 줘야하기 때문이다.

Semaphores

• OS에서 관리하는 resource. 프로세스들이 동기화할때 사용하는 방식

• semaphore는 두 가지 atomic operation ( 다른 operation이 낄 수 없는 / 커널 영역에서 지원해 줌 ) 이 있는 integer 변수 이다.
• atomic operations: wait / signal
• mutual exclusion과 synchronization을 구현할 수 있다.

• wait
• 만약 S > 0, S -= 1
• 만약 S == 0, 호출한 프로세스를 block

• signal
• block된 프로세스가 있는 경우, S를 0으로 만들고 block 되어있는 프로세스 중 하나를 깨워주는 역할
• 아무 프로세스도 block 되어있지 않다면, S += 1

Pseudo code

void wait(semaphore_t *sp){
	if( sp->value > 0 ) sp->value--;
	else {
		// 즉 waiting queue에 넣고 block 시켜버림
		<add this process to sp->list>
		<block>
	}
}

void signal(semaphore_t *sp){
	if( sp->list != NULL ) <remove a process from sp->list>
	else sp->value++;
}

Semaphore examples

• 초기값 S = 1; wait(&s); <critical section> signal(&s); <remainder section>

• 초기값 S = 0
• 만약 다른 프로세스가 signal을 호출하지 않는다면, 모든 wait 함수 호출은 block될 것이고, deadlock이 일어날 것이다.

• 초기값 S =8
• 최대 8개의 프로세스가 concurrent하게 critial section에 진입할 수 있다.

• 두 프로세스의 수행 순서에 제한을 두려 한다.
⇒ 무조건 a가 먼저 실행 되게 할 것이다.

• 위의 예시는 어떠한 상황에서든 a가 먼저 실행된다.

• 자세히 보면 semaphore 변수를 두 개 사용하고 있다.

• s = 1, q = 1
• 어떤 프로세스든 먼저 실행될 수 있다.
• 무조건 다른 프로세스와의 iteration 횟수 차이는 1보다 크지 않다.

• 하나는 1, 하나는 0
• strict alternation. 즉 프로세스가 번갈아가면서 실행된다.
• 1로 초기화된 semaphore를 먼저 소비하는 쪽이 먼저 실행된다.
• 즉, 만약 S = 1이라면, process 1이 먼저 실행된다.

• s = 0, q = 0
• deadlock ⇒ 깨워줄 놈이 없다..

• S = 1, Q = 1
• 어떤 프로세스가 CPU를 먼저 차지하느냐에 따라 결과가 달라진다.
• 만약 process1이 모두 실행되고 나서 process2가 실행된다면 잘 진행 됨.
• process1이 wait(&Q)만 실행하고 나서, process2가 실행되면 deadlock
 

POSIX:SEM Unnamed Semaphores

• type sem_t: named / unnamed semaphore 모두 사용

• 만약 unistd.h에 _POSIX_SEMAPHORES가 정의되어 있다면, POSIX:SEM를 사용할 수 있다.

#include <semaphore.h>
sem_t sem;

Initialization/Destroy

#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned value);
int sem_destroy(sem_t *sem);

• Initialization
• sem: sem_t의 포인터
• pshared: 공유할 것이냐?
• 0: 이 semaphore를 initialize한 프로세스의 threads만 사용할 수 있다.
• nonzero: sem 변수에 access할 수 있다면 모든 프로세스가 이 semaphore를 사용할 수 있다.
• value: 초기 값 ( 당연히 양수 )
• return values
• 성공했을 시 0 / 실패했을 시 -1

• Destroy
• 사용했던 semaphore를 파라미터로 넣음
• return values
• 성공했을 시 0 / 실패했을 시 -1

POSIX:SEM Semaphore Operations

#include <semaphore.h>
int sem_post(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_wait(sem_t *sem);

• sem_post()
• signal 역할을 하는 함수
• signal handler에서도 사용할 수 있는 signal-safe한 함수.

• sem_wait()
• wait 역할을 하는 함수

• sem_trywait()
• 비동기식 호출
• 현재 값이 0이라면 block하는 것이 아니라 -1 return with errno EAGAIN

• return values
• 성공했을 시 0 / 실패했을 시 -1

#include <semaphore.h>
int sem_getvalue(sem_t *restrict sem, int *restrict sval);

• 현재 semaphore의 값을 확인

• sval: output parameter. 현재의 값이 이 값에 세팅이 된다.
• 하지만 어느 시점의 값인지 확정되지 않기 때문에 주의해서 사용하자.

• return values
• 성공했을 시 0 / 실패했을 시 -1

POSIX:SEM Semaphore Example

• shared 라는 값을 여러 프로세스에서 access할 수 있는 상황

• shared는 critical section이 되어야 한다.

#include <errno.h>
#include <semaphore.h>

static int shared = 0;
static sem_t sharedsem;

int initshared(int val) {
	// 프로세스 내의 thread들 끼리만 쓰겠다.
	// 초기 값은 1
	if (sem_init(&sharedsem, 0, 1) == -1) return -1;
	shared = val;
	return 0;
}

int getshared(int *sval) {
	while (sem_wait(&sharedsem) == -1)
		if (errno != EINTR)	return -1;

	*sval = shared;
	return sem_post(&sharedsem);
}

int incshared() {
	while (sem_wait(&sharedsem) == -1)
		if (errno != EINTR) return -1;

	shared++;
	return sem_post(&sharedsem);
}

POSIX:SEM Named Semaphores

• memory를 공유하지 않더라도, 이름만 알고 있다면 semaphore를 사용할 수 있다.

• Named semaphores는 name, a user ID, a group ID and permissions 를 가진다. ( file처럼 )

• 이름이 “/”로 시작.
• “/”로 시작하지 않는 상황은 POSIX에서 명시하고 있지 않다.

Creating and opening

#include <semaphore.h>
sem_t *sem_open(const char *name, int oflag, …);

• name: semaphore의 이름

• oflag
• 0: 그냥 열기
• O_CREAT: 파일을 생성해서 사용하겠다. 만약 같은 이름이 존재한다면 기존의 semaphore를 사용
• 추가 값들
• access permission (0XXX 4글자): 쓰기권한은 없기 때문에 0
• 초기 값
• O_CREAT with O_EXCL: semaphore가 이미 존재한다면 에러 리턴

• return values
• 성공했을 시 semaphore의 주소 / 실패했을 시 SEM_FAILED with errno set

Creating and opening example

#include <errno.h>
#include <fcntl.h>
#include <semaphore.h>
#include <sys/stat.h>
#define PERMS (mode_t)(S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
#define FLAGS (O_CREAT | O_EXCL)

int getnamed(char *name, sem_t **sem, int val){
	// sem_open 함수는 같은 name이 없을 경우에 새로 만들 것이며, 이미 있다면 에러를 뿜을 것
	// 권한 644
	// 초기 값은 파라미터로 받음
	// 만약 interrupted되어 실행되지 않았다면 다시 실행
	while(((*sem = sem_open(name, FLAGS, PERMS, val)) == SEM_FAILED && (errno == EINTR));
	// 에러가 나지 않았다면 0 리턴
	if(*sem != SEM_FAILED) return 0;
	// 에러가 났으며, 그 에러의 내용은 이미 존재한다라는 것이 아니라면 -1 리턴
	if(errno != EEXIST) return -1;
	// 이미 존재하는 semaphore를 open 하겠다.
	while(((*sem = sem_open(name, 0)) == SEM_FAILED)  && (errno == EINTR));
	// open이 에러가 나지 않았다면 0 리턴
	if(*sem != SEM_FAILED) return 0;
	// open이 에러났다면 -1 리턴
	return -1;
}

#include <errno.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include "restart.h"
#define BUFSIZE 1024
int getnamed(char *name, sem_t **sem, int val);

int main(int argc, char *argv[]){
	char buffer[BUFSIZE];
	char *c;
	pid_t childpid = 0;
	int delay;
	volatile int dummy = 0;
	int i, n;
	sem_t *semlockp;

	if (argc != 4){
		fprintf(stderr, "Usage: %s processes delay semaphorename\n", argv[0]);
		return 1;
	}
	n = atoi(argv[1]);
	delay = atoi(argv[2]);
	for(i = 1; i < n; i++)
		if(childpid = fork()) break;
	
	snprintf(buffer, BUFSIZE, "i:%d process ID:%ld child ID:%ld\n", i, (long)getpid(), (long)getppid(), (long)childpid);
	c = buffer;
	
	if(getnamed(argv[3], &semlockp, 1) == -1){
		perror("Failed to create named semaphore");
		return 1;
	}
	/* entry section */
	while(sem_wait(semlockp) == -1)
		if(errno != EINTR){
			perror("Failed to lock semlock");
			return 1;
		}
	
	/* critical section */
	while(*c != '\0'){
		fputc(*c, stderr);
		c++;
		for(i = 0; i < delay; i++) dummy++;		
	}

	/* exit section */
	if(sem_post(semlockp) == -1){
		perror("Failed to unlock semlock");
		return 1;
	}

	/* remainder section */
	if(r_wait(NULL) == -1) return 1;
	return 0;
}