OS #4 PCB, IPC, Semaphore & Mutex

Process Management : 프로세스가 여러개일 때 CPU 스케줄링을 통해 관리하는 것을 말함
이때 CPU는 각 프로세스들이 누군지 알아야 관리가 가능하다.
프로세스들의 특징을 갖고있는 것이 바로 Process Metadata이고 이들은 프로세스가 생성되면 PCB이라는 곳에 저장된다. 따라서 각 프로세스가 생성되면 고유의 PCB가 생성되고 프로세스가 완료되면 PCB는 제거된다.

✅ PCB(Process Control Block)

🎈 PCB가 왜 필요한가?

CPU에서 프로세스 상태에 따라 교체작업이 이루어진다.
(인터럽트가 발생해 할당받은 프로세스가 대기 상태가 되고 타 프로세스를 running으로 바꿔 올릴 때)

: 프로세스 메타데이터들을 저장해 놓는 곳, 한 PCB 안에는 한 프로세스의 정보가 담김

• OS 커널의 자료구조
• OS가 프로세스를 표현한 것

🎈 PCB에 저장되어 있는 정보

• 프로세스 현재 상태 : 준비, 대기, 실행 등의 프로세스 상태
• 포인터 (부모 프로세스에 대한) : 부모 프로세스의 주소 기억
• 포인터 (자식 프로세스에 대한) : 자식 프로세스의 주소 기억
• 포인터 (프로세스가 위치한 메모리에 대한) : 현재 프로세스가 위치한 주소 기억
• 포인터 (할당된 자원에 대한) : 프로세스에 할당된 각 자원에 대한 주소 기억
• 프로세스 고유 식별자 : 프로세스를 구분할 수 있는 고유의 번호
• 스케줄링, 프로세스 우선순위 : 프로세스 실행될 우선순위
• CPU 레지스터 정보 : Accumulator, Index Register, 범용 레지스터, PC 등에 대한 정보
• 주기억장치 관리 정보 : Base Register, Page Table에 대한 정보
• 입/출력 상태 정보 : 입출력장치, 개방된 파일 목록
• 계정 정보 : CPU 사용 시간, 실제 사용 시간, 한정된 시간

참고사항
Page Table : 페이징 기법에서 주소 변환을 위해 페이지가 존재하는 주기억장치의 위치 정보를 가지고 있는 테이블을 의미 (메모리가 여려 개 있을 때 SEGMENT(code, heap) 등 가변적인 정보가 점점 커지다 보면, 실제 메모리보다 비대해지는 현상을 unit 으로 끊어 정리해준 테이블

이때, 앞으로 수행할 대기 중인 프로세스에 관한 저장 값을 PCB에 저장해두는 것이다.

🎈 PCB가 관리되는 방식

• 양방향 Linked List 방식으로 관리
• PCB List Head에 PCB들이 생성될 때마다 붙게 된다. 주소값으로 연결이 이루어져 있는 연결리스트이기에 삽입/삭제가 용이한 것이 특징
• 즉 프로세스가 생성되면 해당 PCB가 생성되고 프로세스 완료 시 제거된다.
  이렇게 수행 중인 프로세스를 변경할 때 CPU의 레지스터 정보가 변경되는 것을 Context Switching이라고 한다.

✍️ Context Switching

: CPU가 이전 프로세스 상태를 PCB에 보관하고 또 다른 프로세스의 정보를 PCB에 읽어 레지스터에 적재하는 과정
여기서 Context란 CPU가 프로세스를 실행시키기 위해 필요한 정보들을 의미한다.
ex ) 프로세스의 데이터, CPU 레지스터 값

• 인터럽트가 발생하거나, 실행 중인 CPU 사용 허가시간을 모두 소모하거나, 입출력을 위해 대기해야 하는 경우 Context Switching이 발생한다.
  (즉, 프로세스가 Ready → Running, Running → Ready, Running → Waiting처럼 상태 변경 시 발생!)

💡 Context Switching 발생하는 유형 3가지

1. 멀티 태스킹 : 실행 가능한 여러 프로세스들이 OS 스케줄러에 의해 우선순위에 따라 수행됨 즉, CPU를 할당 받는 프로세스가 변경될 때마다 Switching 발생
2. 인터럽트 핸들링 : 컴퓨터 시스템에서 예외 상황 발생 시, 이를 CPU에게 알려 실행중이던 프로세스 정보를 저장하고 발생한 예외 상황을 처리하기 위해 Switching
3. convert from user mode to kernel mode : OS에 따라 발생 가능(Switching이 필수 X)

• ❗ Context Switching의 Overhead란?
  Overhead라는 단어로 안 좋다라는 느낌이 강할 수 있지만, 프로세스 작업 중에는 Overhead를 감수해야 하는 상황이 있다.
  프로세스를 수행하다가 입출력 이벤트가 발생해서 대기 상태로 전환 시키는데, 이때 CPU를 가만히 두는 것보단 다른 프로세스를 수행시키는 것이 효율적이다.
  즉, CPU에서 계속 프로세스를 수행시키도록 하기 위해 현재 프로세스에 이벤트 발생 시, 다른 프로세스를 실행시켜 Context Swiching하는 것.

✅ IPC

• 프로세스는 독립적인 메모리 영역을 CPU로부터 할당받아 실행되는데, 이런 독립적인 구조를 가진 프로세스 간의 통신을 위해 IPC통신을 활용한다.
• 프로세스는 커널이 제공하는 IPC 설비를 이용해 프로세스 간의 통신이 가능케 된다.

커널 : OS의 핵심적인 부분, 다른 모든 부분에 여러 기본적인 서비스를 제공해줌

✍️ IPC 종류

1. 익명 PIPE - pipe() 시스템콜
   부모-자식 프로세스 간 통신과 같이 통신할 프로세스를 명확하게 알 수 있는 경우에 사용한다.
   한 쪽 방향으로만 통신이 가능한 반이중 통신 (2개의 프로세스를 연결하는데 하나의 프로세스는 데이터를 쓰기 기능만, 한 쪽은 Read만 가능하다)
   따라서 양 방향 통신을 위해선 2개의 파이프를 만들어야 하는 구현에 어려움이 있다.
2. Named PIPE(FIFO) - mkfifo() 시스템콜
   전혀 모르는 상태의 프로세스들 사이에 통신에 사용
   앞서 설명한 익명 PIPE의 확장된 상태로 부모 프로세스와 무관한 타 프로세스도 통신이 가능케 됨
   그러나, 읽기/쓰기가 동시에 일어날 수 없고 양방향을 위해 2개의 PIPE를 사용해야 하는 어려움이 있다.
3. Message Queue (FIFO)
   커널에 존재하며 입출력 방식은 Named PIPE와 동일하지만, 파이프처럼 데이터의 흐름이 아닌 메모리 공간으로 되어 있어 사용할 데이터에 번호를 매겨 여러 프로세스가 동시에 데이터를 쉽게 다룰 수 있다. FIFO 구조로 순서가 보장된다.
4. Shared memory
   PIPE, Messasge queue가 통신을 이용한 설비라면, 공유 메모리는 데이터 자체를 공유하도록 지원하는 설비
   공유 메모리는 프로세스 간 메모리 영역을 공유해서 사용할 수 있도록 허용해준다.
   중개자 없이 곧바로 메모리에 접근할 수 있어서(유저모드에서도) IPC에 가장 빠르게 작동
5. 메모리 맵
   공유 메모리처럼 메모리를 공유해준다. 메모리 맵은 열린 파일을 메모리에 맵핑시켜서 공유하는 방식 (즉 공유 매개체가 파일 + 메모리)
   주로 파일로 대용량 데이터를 공유해야할 때 사용
6. 소켓
   네트워크 소켓 통신을 통해 데이터를 공유
   클라이언트와 서버와 소켓을 통해 통신하는 구조, 원격에서 프로세스 간 데이터를 공유할 때 사용

이러한 IPC 통신에서 프로세스 간 데이터를 동기화하고 보호하기 위해 세마포어와 뮤텍스를 사용한다.

✅ Semaphore & Mutex

Semaphore, Mutex 학습 전 Critical Section에 대해 학습해보고자 한다.

• ✍️ Critical Section : 여러 프로세스, 스레드가 데이터를 공유하며 수행될 때 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분.
  -> 이렇게 임계 구역에 여러 프로세스, 스레드가 함부로 접근할 수 없도록 관리가 필요한데 대표적인 방식이 Semaphore, Mutex

🎈 Mutex

• 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 단독으로 실행되도록 하는 기술
  (상호배제)
• 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나)
• 한 프로세스에 의해 소유될 수 있는 key를 기반으로 한 상호배제 기법. key에 해당하는 object가 있으며 해당 객체를 소유한 프로세스, 스레드만 공유자원에 접근 가능 (자원 소유 가능)
• 다중 프로세스들의 공유 리소스 접근 조율을 위해 동기화, 락을 사용 (상태가 0, 1 뿐)
• 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없다. (동기화 대상이 오직 1개)

💡 Mutex Algorithms

1. Dekker Algorithm
   flag, turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드 결정하는 방식
   flag : 프로세스 중 누가 임계 영역에 진입할 지 결정
   turn : 누가 임계구역에 들어갈 차례인지 나타낸 변수

while True 
	# 프로세스 i가 임계 구역 진입 시도
	flag[i] = True 
    # 프로세스 j가 현재 임계 구역에 있는지 확인
    while flag[j]:
    	# j가 임계 구역 사용 중이면
    	if turn == j:
    		# 프로세스 i 진입 취소
            flag[i] = False
            # turn이 j에서 변경될 때까지 대기
			while turn == j:
            	#  j turn이 끝나면 다시 진입 시도
                flag[i] = True       
# // ------- 임계 구역 ---------
# 임계 구역 사용 끝나면 turn을 넘김
turn = j  
# flag 값을 false로 바꿔 임계 구역 사용 완료를 알림
flag[i] = false 

2. Peterson algorithm
   데커와 유사하지만 상대 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있다.

while True:
	# 프로세스 i가 임계 구역 진입 시도
    flag[i] = True
    # 다른 프로세스에게 진입 기회 양보
    turn = j
    다른 프로세스가 진입 시도시 대기
    while flag[j] and turn == j:
# 임계 구역 사용 완료
flag[i] = False 

3. Bakery Algorithm
   여러 프로세스, 스레드에 대해 처리가 가능한 알고리즘. 가장 작은 수의 번호 표를 가진 프로세스가 임계 구역에 진입

while True:
	# 번호표 준비
    isReady[i] = True
    # 현재 실행 중인 프로세스 중에 가장 큰 번호 배정
    number[i] = max(number[0 ~ n-1]) + 1
    # 번호표 수령 완료
    isReady[i] = False
    # 모든 프로세스 번호표 비교
    for j in range(n):
    	# 비교 프로세스가 번호표 받을 때까지 대기
        while isReady[j]:
        while number[j] and number[i] and j < i:
        # 프로세스 j가 번호표 가지고 있어야 하고 j번호표 < i번호표 여야 한다.
# 임계구역 사용 종료
number[i] = 0

🎈 Semaphore

공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나 이상)

• 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근가능
• 사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성.
• 세마포어를 사용하는 프로세스는 그 값을 확인하고 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 대기하도록 해야 한다.
• 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있다
• 세마포어는 이진수를 사용하거나 추가적인 값을 사용할 수 있다.

💯 Mutex VS Semaphore

1. Mutex는 동기화 대상이 오직 1개일 때 사용, Semaphore는 동기화 대상이 1개 이상일 때 사용
2. Mutex는 자원 소유 가능, Semaphore는 자원 소유 불가
3. Mutex는 상태가 0,1인 Binary Semaphore, Mutex는 Semaphore가 될 수 없으나 역은 가능
4. Mutex는 소유 중인 스레드만이 Mutex를 해제할 수 있는 반면, Semaphore는 소유 하지 않은 스레드도 해제 가능
5. Semaphore는 시스템 범위에 걸쳐 있고 파일 시스템 상 파일로 존재하지만, Mutex는 프로세스 범위를 가지며 프로세스 종료될 때 자동으로 clean-up 된다.

< 정리 >
Mutex, Semaphore 모두 완벽한 기법이 아니기에 데이터 무결성을 보장할 수 없고 모든 lock 상태 해결은 불가능하지만, 상호배제를 위한 기본적인 기법이기에 추가로 더 복잡한 메커니즘을 적용해 개선된 성능을 가질 수 있도록 하는 것이 중요하다.