Chapter 14. Critical Sections and Semaphores

중요한 부분 (Critical Sections)

• 정의: 상호 배타적으로 실행되어야 하는 코드 세그먼트, 공유 장치는 한 번에 하나의 프로세스만 액세스할 수 있으므로 이를 배타적 자원이라고 부름
• 예제 (Program 14.1):
  • (1) 프로세스 체인(원래 프로세스가 자식 프로세스를 만들고, 부모 프로세스를 삭제 이 과정을 반복)을 생성하고 메시지를 한 번에 한 문자씩 출력
  • 각 문자를 출력한 후의 지연 시간을 명령줄 인수로 제공
    • 지연 시간이 0에 가까우면 각 프로세스는 일반적으로 전체 줄을 출력, 지연 시간이 충분히 크면 각 프로세스는 CPU를 잃기 전에 한 번에 한 문자씩만 출력 -> 딜레이 값이 작으면 프로세스가 종료되기 전 전부 출력, 딜레이 값이 크면 프로세스를 전환하여 여러 개의 프로세스가 실행되는 형식

프로세스가 딜레이가 발생할 동안, Context Switch가 발생하여 프로세스 간 전환하여 여러 개의 프로세스가 실행됨, 그렇기에 여러 개의 프로세스가 섞여서 출력이 되게 됨!

((1) 2(프로세스 개수) 100(딜레이가 100, 작은 값) -> 자신의 버퍼에 있는 프로세스를 전부 실행(정상적, 프로세스 간 코드 영역을 침범x)
((2) 2 100000(딜레이가 십만, 큰 값) -> 한 개의 프로세스가 완료되기 전 다음 프로세스가 실행되어 2개의 프로세스가 섞여서 실행된 상태 (프로세스의 코드 영역을 침범하여 발생한 문제)

 
n = 프로세스 개수(2개), delay값을 제공 / for 루프를 돌면서 프로세스를 생성하는데 1부터 n보다 작을 떄까지 돌려서 fork로 프로세스를 생성
-> 빠져나온 프로세스는 sprintf 함수로 화면에 출력할 내용을 버퍼에 string값(process ID, parent ID, child ID)을 씀
dummy 변수로 아무 의미 없는 루프를 반복함

코드 내 중요한 구분 요소

1. Entry section (입력 섹션)  : 공유 변수 또는 자원을 수정할 수 있는 권한을 요청하는 코드 포함(critical section에 들어가기 전에 반드시 Entry section을 os에게 허가를 요청해야 함)
2. Critical section (중요 섹션) : 공유 자원에 접근하거나 재진입 불가능한(nonreentrant) 코드를 실행하는 코드 포함
3. Exit section (종료 섹션) : 다음 실행 스레드가 중요 섹션에 진입할 수 있도록 입력 섹션에 알리는 데 필요 (대기 중인 다음 프로세스에게 권한을 넘기기 위해서 반드시 호출해야 함!)
4. Remainder section (잔여 섹션) : 접근 권한을 해제한 후, 스레드가 실행할 수 있는 다른 코드 포함

 

Critical Section 문제 해결 방안 - 3가지 조건을 모두 만족할 경우 해결 가능!

1. Mutual Exclusion (상호 배제) : 프로세스 Pi가 Critical Section을 실행 중일 경우, 다른 어떤 프로세스도 그들의 Critical Section을 실행할 수 없음
2. Progress (진행) : 어떤 프로세스도 Critical Section을 실행 중이지 않을 때, Critical Section에 진입하려는 프로세스들이 존재한다면, Remainder Section에 있는 프로세스들만 다음 Critical Section에 진입할 프로세스를 결정하는 데 참여 가능 -> 이 결정은 무한정 연기될 수 없음
3. Bounded Waiting (유한 대기) : 한 프로세스가 Critical Section에 진입을 요청한 후 해당 요청이 승인되기 전에 다른 프로세스들이 Critical Section에 진입할 수 있는 횟수에 제한이 있어야 함 (가장 먼저 요청한 프로세스만 승인됨)4
   • 각 프로세스는 0 이상의 속도로 실행된다고 가정, 프로세스 N의 상대적 속도에 대한 가정은 없음.

세마포어 (Semaphores)

• 정의 : 상호 배제와 동기화를 관리하기 위해 2가지 원자적 연산(wait와 signal)을 사용하는 정수형 변수
• 연산
  1. wait - 세마포어 값을 1개 감소(정수 값을 줄임) / S는 세마포어 값
     • S>0이면, S를 검사하고 감소시킴
     • S=0이면, S를 검사하고 호출자를 차단 -> 세마포어 값은 음수가 존재하지 않음!
  2. signal - 세마포어 값을 1개 증가(정수 값을 늘림) / S는 세마포어 값
     • 스레드가 S에서 차단된 상태라면, S=0이 되고 대기 중인 스레드 중 하나를 차단 해제
     • 대기 중인 스레드가 없으면 S를 증가시킴 -> 대기 중이 신호를 깨우고 없으면 세마포어 값을 증가시킴
• 조건 : wait와 signal은 반드시 원자적이어야 함 - 2개의 함수(wait & signal)로 스레드와 프로세스의 동기화를 해결함!

 

세마포어 예제 (Semaphore Examples)

• 세마포어를 사용한 Critical Section
  • 초기화: S=1 -> critical section 효과를 가짐!, S값이 1보다 크면 critical section 효과를 가지지 않음!
  • 코드 흐름: 대기중인 신호가 있을 경우 신호를 깨우고(바로 critical section으로 진입 가능), S값을 0으로 유지 / 대기 중인 신호가 없을 경우 S값을 1 증가
  • wait(&S); // 세마포어 대기 <critical section> // 중요 섹션 실행 signal(&S); // 세마포어 신호 <remainder section> // 나머지 섹션 실행
•  조건별 동작
  1. S=0인 경우: 모든 wait(&S) 호출이 차단되고 다른 프로세스가 signal을 호출하지 않으면 교착 상태(deadlock) 발생 - 데드락 (계속 기다리는 상태)
  2. S=8인 경우: 동시에 최대 8개의 프로세스가 자신의 Critical Section을 실행 가능 -> 신호가 7,6 이렇게 작성, 이렇게 되면 critical section이 깨지게 됨 (출제가능!)

작업 순서 강제의 예시

• Process 1은 문장 a를 실행한 후 signal(&sync)를 호출
• Process 2는 wait(&sync)를 호출한 후 문장 b를 실행
• 결과적으로, Process 1이 문장 a를 먼저 실행해야만 Process 2가 문장 b를 실행 가능
• 초기 조건 sync=0 일 때, Process 2는 wait(&sync)에서 차단되고 Process 1이 signal(&sync)를 호출할 때까지 대기 상태에 머무름

세마포어 다른 예시

•  

프로세스 1 실행 흐름:

for(;;) {
    wait(&S);   // 세마포어 S 대기
    a;          // 작업 a 수행
    signal(&Q); // 세마포어 Q 신호 -> 세마포어 값을 증가 or 다른 신호를 깨움
}

프로세스 2 실행 흐름:

for(;;) {
    wait(&Q);   // 세마포어 Q 대기
    b;          // 작업 b 수행
    signal(&S); // 세마포어 S 신호
}

• 초기 조건 및 결과
  1. S=1, Q=1일 경우:
     • 두 프로세스 중 어느 것이 먼저 wait를 실행할지 알 수 없음.
     • 특정 프로세스는 다른 프로세스보다 최대 한 번의 반복만 더 실행 가능.
  2. 한 세마포어가 1, 다른 세마포어가 0일 경우 : 두 프로세스는 엄격히 교대로 실행됨 (S를 1, Q를 0으로 초기화 했을 경우, 프로세스들이 a와 b가 교대로 실행됨, 세마포어를 1로 초기화하여 소비하는 프로세스인 S가 먼저 실행!)
  3. S=0, Q=0일 경우: 교착 상태 (Deadlock) 발생 - 두 프로세스 모두 대기 상태에 빠져 진행하지 못함 (P1은 P2가 깨워줄 수 있고 P2는 P1이 깨어줄 수 있는데 2개의 프로세스 모두 잠들어서 서로를 깨우지 못하는 상황!)

세마포어 다른 예시

프로세스 1 실행 흐름:

for(;;) {
    wait(&Q);   // 세마포어 Q 대기
    wait(&S);   // 세마포어 S 대기
    a;          // 작업 a 수행
    signal(&S); // 세마포어 S 신호
    signal(&Q); // 세마포어 Q 신호
}

프로세스 2 실행 흐름:

for(;;) {
    wait(&S);   // 세마포어 S 대기
    wait(&Q);   // 세마포어 Q 대기
    b;          // 작업 b 수행
    signal(&Q); // 세마포어 Q 신호
    signal(&S); // 세마포어 S 신호
}

• 초기 조건: S=1,Q = 1
  • 결과는 프로세스들이 CPU를 점유하는 순서에 따라 달라짐
  • 프로세스 1이 wait(&Q)를 실행한 후 CPU를 잃고 프로세스 2가 실행을 시작하면:
    • 두 프로세스가 두 번째 wait 호출에서 차단됨 or 교착 상태 (Deadlock)가 발생

POSIX:SEM Unnamed Semaphores

• POSIX:SEM 세마포어란?
  • sem_t 타입의 변수(세마포어 변수 - 정수값) - 이름 있는 세마포어 or 이름 없는 세마포어로 구분됨
• 지원 조건 : POSIX:SEM 세마포어를 지원하려면, unistd.h에 _POSIX_SEMAPHORES가 정의되어 있어야 사용 가능
• 세마포어 변수 선언

#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)
  • POSIX:SEM 세마포어는 사용 전에 반드시 초기화되어야 함
  • sem_init() 함수:
    • 이름 없는 세마포어를 sem 포인터가 가리키는 세마포어와 value 값으로 초기화(value 값은 음수일 수 없음)
  • pshared 옵션:
    • 0 (False) : 세마포어는 세마포어를 초기화한 프로세스의 스레드만 사용할 수 있음
    • 0이 아닌 값 (True) : 세마포어를 접근할 수 있는 모든 프로세스에서 사용 가능
  • 반환값: 성공 시 0, 실패 시 -1을 반환하고 errno를 설정.
• 제거 (Destroy)
  • 이름 없는 세마포어를 제거하기 위해 사용
  • sem_destroy() 함수: 이름 없는 세마포어를 파괴
  • 반환값: 성공 시 0, 실패 시 -1을 반환하고 errno를 설정

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);

1. sem_post() : 전통적인 세마포어 신호를 구현, Signal-safe하여 신호 핸들러에서 호출 가능
2. sem_wait() : 전통적인 세마포어 대기를 구현, 세마포어 값이 0이면 대기 상태로 진입
3. sem_trywait() : 세마포어 값이 0인 경우 차단되지 않음, 대신 -1을 반환하고 errno를 EAGAIN으로 설정

• 반환값 : 성공 시: 0, 실패 시: -1 반환 및 errno 설정

POSIX:SEM 세마포어 연산

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

• sem_getvalue() 함수
  • 사용자에게 이름 있는 세마포어나 이름 없는 세마포어의 값을 확인할 수 있는 기능 제공
  • 세마포어 상태에 영향을 주지 않고, sval이 참조하는 정수를 세마포어 값으로 설정
• sval 값 : 호출 시점에서 세마포어가 가졌던 값을 보유하고 반환 시점에서의 값은 보장되지 않음 (불확실한 시점의 값)
• 반환값 : 성공 시: 0 반환, 실패 시: -1 반환 및 errno 설정

sval이라는 공유 변수를 여러 프로세스들이 동시에 접근 가능한 상황이고 그렇기에 critical section이 되어야 함, 따라서 현재 공유변수의 값을 알기 위해 getshared() 함수로 호출하여 incshared함수로 공유 변수의 값을 변경함 -> shared 변수가 여러 프로세스가 공유하과 그 shared값을 읽어오는데 읽기 전에 *sval = shared를 critical section으로 만들기 위해 sem_wait와 sem_post를 양쪽으로 호출하여 사이의 값을 critical section으로 만들어줌 (단, 사용중인 세파포어인 &sharedsem값을 1로 초기화하여야 함 -> initshared() 함수를 호출하여 초기화를 진행함

• 프로그램 기능 (Program 14.2)
  1. getshared(): 현재 공유 변수의 값을 반환
  2. incshared(): 공유 변수를 원자적으로 증가시킴
  3. sem_wait(): 신호에 의해 인터럽트된 경우 다시 시작함
• 요약
  • initshared(int val)로 세마포어와 공유 변수를 초기화
  • getshared()로 공유 변수 값을 안전하게 읽음
  • incshared()로 공유 변수 값을 원자적으로 증가
  • 세마포어를 통해 동기화를 보장

POSIX:SEM 이름 있는 세마포어 (Named Semaphores)

• 기능 : 이름 있는 세마포어는 공유 메모리를 사용하지 않는 프로세스들 간 동기화를 가능하게 함
• 속성 : 이름 있는 세마포어는 이름, 사용자 ID, 그룹 ID, 파일과 유사한 권한을 가짐
• 이름 규칙
  • 세마포어 이름이 슬래시("/")로 시작할 경우: 동일한 이름의 세마포어를 열어 사용하는 두 프로세스나 스레드는 동일한 세마포어를 참조
  • POSIX는 슬래시로 시작하지 않는 이름의 경우: 두 프로세스가 동일한 이름을 참조할 때의 동작을 명시하지 않음

생성 및 열기 (Creating and Opening)

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

• sem_open() 함수 : 이름 있는 세마포어와 sem_t 값 간의 연결을 설정.
• 매개변수 (Parameters)
  • name: 세마포어를 식별하는 문자열 (open할 세마포어의 이름)
  • oflag:
    • 세마포어가 생성되는지, 단순히 접근만 하는지를 결정
    • O_CREAT 플래그: 세마포어를 생성해야 하며, 추가로 두 개의 매개변수가 필요:
      • mode: mode_t 타입으로 권한을 설정
      • value: 세마포어의 초기값 (unsigned 타입)
      • O_EXCL 플래그가 설정되지 않으면, 세마포어가 이미 존재하는 경우 무시  
  • O_CREAT와 O_EXCL 둘 다 설정된 경우: 세마포어가 이미 존재하면 오류 반환
• 반환값 (Return Values) : 성공: 세마포어의 주소 반환, 실패: SEM_FAILED 반환 및 errno 설정

생성 및 열기 예제 (Creating and Opening Example)

• getnamed() 함수
  • 세마포어가 존재하지 않을 경우, 이름 있는 세마포어를 생성
  • 세마포어가 이미 존재하면, O_CREAT와 O_EXCL 비트 없이 세마포어를 열려고 시도
• 매개변수 (Parameters)
  1. 세마포어 이름, 세마포어에 대한 포인터를 가리키는 포인터 (이중 포인터 사용) => 이중 참조는 함수가 포인터를 변경해야 하기 때문, 세마포어 초기값

getnamed 함수로 1번째 파라미터로 name, 2번째 파라미터로 이중 포인터 -> 포인터의 위치 정보를 넘기는 것(함수 내부에서 포인터 값을 변경할 수 있다는 것), 마지막 파라미터로 초깃값을 지정한 것!, 새로 성공적으로 생성되면 반환하여 종료하고, while문은 sem_open함수의 반환 값이 SEM_FAILED이고 에러코드가 EINTR이면 멈춘거면 다시 sem_open함수를 반복하여 호출하는 것 / sem_open함수가 반환된 포인터 값이 SEM_FAILED가 아니면 성공적으로 반환하여 0을 반환하고 EEXIST가 아닌 다른 이름의 에러가 발생한 경우 -1을 반환함

닫기 및 연결 해제 (Closing and Unlinking)

POSIX:SEM 이름 있는 세마포어

• 이름 있는 세마포어는 단일 프로그램 실행을 넘어 지속성을 가짐
• POSIX:SEM은 어떤 이름 있는 세마포어가 존재하는지 확인하는 방법을 제공하지 않음:
  • 디렉토리 내용을 표시할 때 보이지 않을 수 있음
  • 시스템 재부팅 시 삭제되지 않을 수 있음

sem_close() 함수

• 이름 있는 세마포어를 닫음 (시스템에서 제거되지 않음)
• 반환값: 성공 시 0, 실패 시 -1과 함께 errno 설정

sem_unlink() 함수

• 이름 있는 세마포어를 시스템에서 제거:
  • 모든 프로세스가 세마포어를 닫은 후 제거 수행
  • 이후 동일한 이름으로 sem_open 호출 시 새로운 세마포어 참조
  • 다른 프로세스가 세마포어를 열고 있어도 즉시 반환
• 반환값: 성공 시 0, 실패 시 -1과 함께 errno 설정

설명

1. sem_close() 호출:
   • 이름 있는 세마포어를 닫으려고 시도
   • 실패 시 오류 코드 (errno)를 저장
2. sem_unlink() 호출:
   • 세마포어의 이름을 시스템에서 제거
   • sem_close()가 실패해도 sem_unlink()는 호출됨
3. 오류 처리: 첫 번째로 발생한 오류를 기록하고 반환

특징

• 세마포어 닫기 (sem_close)가 실패해도 이름 제거 (sem_unlink)는 시도.
• 세마포어의 닫기와 삭제 작업이 모두 실패한 경우, 첫 번째 오류를 반환.