시작이 반이다.

페이징 (Paging)

페이징과 세그먼테이션은 메모리 관리 기법 중 하나로
물리적 메모리를 작은 고정 크기의 블록이나 페이지로 나누는 것을 말한다.

가상 메모리 시스템에서 물리적인 메모리를 가상으로 나눈 작은 단위를 페이지(Page)라고 하고,

프로세스가 실행되는 동안, 그 프로세스의 코드와 데이터는 페이지로 나누어져 디스크에 저장된다.

페이지는 보통 고정된 크기를 가지며, 이 크기는 시스템에 따라 다를 수 있다.
일반적으로 페이지의 크기는 1 ~ 4KB이다.

물리적인 메모리(RAM)를 가상 메모리의 페이지와 일치시키는 데 사용되는 물리적인 단위를 
페이지 프레임(Page Frame)이라고 한다.

페이지 프레임의 크기는 페이지와 동일하며, 주로 4KB 또는 4MB와 같이 고정 크기를 가진다.
페이지 프레임은 페이지를 실제로 메모리에 로드하고 저장하는 데 사용된다.
페이지 프레임들이 메모리에 적절히 배치되어야 프로세스 페이지들을 효과적으로 관리할 수 있다.

분할된 페이지는 가상 메모리와 연결되어, 프로세스가 필요한 메모리를 할당받을 때 빈 페이지를 사용한다.

페이징은 메모리 단편화를 줄이고, 프로세스 간의 격리를 쉽게 구현할 수 있도록 도와준다.

세그멘테이션 (Segmentation)

메모리를 서로 다른 크기의 논리적 단위인 세그먼트(Segment)로 분할하는 방식을 기반으로 하는 기법이다.
각 세그먼트는 서로 다른 종류의 데이터나 프로그램 코드를 나타내며, 고유한 이름과 크기를 갖는다.

세그먼테이션은 메모리를 동적으로 할당하고 확장하기에 적합한 방법을 제공한다.
각 세그먼트는 필요한 크기로 확장될 수 있으며 메모리에 새로운 세그먼트를 할당함으로써
새로운 데이터나 프로그램을 쉽게 추가할 수 있다.

세그먼테이션은 복잡한 메모리 관리 요구사항을 다룰 때 유용하다.

예를 들어, 다중 프로그램 실행 환경에서 각 프로세스가 독립적으로 메모리를 사용하고,
가상 메모리시스템과 결합하여 물리적 메모리를 효과적으로 활용할 수 있도록 한다.

세그먼테이션은 다른 메모리 관리 기법과 함께 사용되기도 하며,
주로 운영체제나 컴파일러에서 메모리 할당과 보호를 구현하는 데 활용된다.
이를 통해 시스템의 안정성, 보안, 효율성을 향상할 수 있다.

페이징과 세그먼테이션의 차이점

• 주요 원리
  - 페이징: 메모리를 고정 크기의 페이지로 분할하고, 프로세스를 동일한 크기의 페이지로 나누어 저장한다.
  페이지는 물리적 메모리의 프레임에 매핑되며, 페이지 번호를 사용하여 프로세스의 주소 공간을 추상화한다.
  페이지 크기는 일반적으로 고정되며, 프로세스의 크기가 페이지 크기의 배수가 아니더라도 페이지 단위로 할당한다.
  
  - 세그먼테이션: 세그먼테이션은 프로세스의 주소 공간을 논리적으로 관련된 세그먼트로 분할한다.
  각 세그먼트는 서로 다른 크기를 가질 수 있으며, 각각은 독립적으로 메모리에 로드될 수 있다.
  세그먼트는 이름과 길이를 가지며, 논리적인 구조를 반영하기 때문에 프로그래머가 프로세스를 쉽게 관리할 수 있다.

• 내부 단편화
  - 페이징: 페이징은 내부 단편화가 발생하지 않는다.
    페이지 크기가 고정되어 있으므로 효율적인 메모리 사용이 가능
  
  - 세그먼테이션: 세그먼테이션은 서로 다른 크기의 세그먼트로 메모리를 분할하기 때문에 내부 단편화가 발생할 수 있다. 큰 세그먼트가 작은 세그먼트 뒤에 위치할 때 작은 공간이 남을 수 있다.

• 외부 단편화
  -  페이징: 외부 단편화 문제가 발생할 수도 있다.
  메모리가 분산된 페이지들로 채워질 때, 페이지 사이에 남는 작은 공간이 발생할 수 있다.
  
  - 세그먼테이션: 세그먼테이션은 외부 단편화를 감소시킬 수 있다.
  각 세그먼트는 독립적으로 관리되므로 더 나은 메모리 할당 및 해제가 가능하며, 공간을 효율적으로 활용할 수 있다.

• 구현 복잡성
  - 페이징: 비교적 구현이 간단하며 하드웨어 지원이 용이하다.
  페이지 테이블을 사용하여 논리 주소와 물리 주소 간의 매핑을 관리한다.
  -세그먼테이션: 구현이 복잡할 수 있다. 각 세그먼트의 시작 주소와 길이를 관리해야 하며, 세그먼트의 크기가 동적으로 변할 수 있다.
  
  

요약하자면, 페이징은 내부 단편화를 방지하고 구현이 간단한 반면, 외부 단편화 문제가 발생할 수 있다.
세그먼테이션은 논리적 구조를 유지하고 외부 단편화를 줄일 수 있지만 구현이 복잡하며 내부 단편화 문제가 있을 수 있다. 선택은 운영 체제의 요구 사항과 메모리 사용 패턴에 따라 달라진다.

내부 단편화(Internal Fragmentation)와 외부 단편화(External Fragmentation)

내부 단편화는 메모리 할당과 관련이 있다. 컴퓨터 메모리는 일반적으로 고정 크기의 블록으로 나누어져 있으며,
프로세스나 데이터가 할당될 때 메모리 블록이 할당된다.

내부 단편화는 메모리 블록의 일부가 사용되지 않고 남아 있을 때 발생한다.
예를 들어 4KB의 메모리 블록을 할당하고, 실제 프로세스는 2KB만 사용한다면 2KB가 낭비되는 것이 내부 단편화이다.

외부 단편화는 메모리 할당과 해제로 인해 발생하는 메모리 조각화를 나타낸다.
메모리에 사용 가능한 작은 조각들이 흩어져 있어서, 큰 메모리 요청을 수용하기 어렵게 만드는 상황을 의미한다.
외부 단편화는 주로 동적 메모리 할당 시 발생하는데, 프로세스나 데이터가 메모리를 할당하고 해제할 때 메모리의 여백이 불균형하게 발생할 수 있다.

요약하자면, 내부 단편화는 메모리 블록 내에서 발생하는 것이며,
외부 단편화는 메모리 할당 및 해제로 인한 메모리 조각화로 발생한다.

IPC(Inter Process Communication)

IPC는 프로세스 간 통신이라는 뜻으로 프로세스들 사이에 서로 데이터를 주고받는 행위 또는 방법이나 경로를 뜻한다.

프로세스는 독립적으로 실행되기 때문에 다른 프로세스에 영향을 받지 않는다.
반대로 스레드는 프로세스 안에서 자원을 공유하므로 영향을 받는다.

이런 상황에서 프로세스 간의 통신이 필요한 상황이 있을 것이다.
그런 경우에 이를 가능하게 해주는 것이 바로 IPC 통신이다.
프로세스는 커널이 제공하는 IPC 설비를 이용해 프로세스 간 통신을 할 수 있게 된다.

커널(Kernel)

운영 체제의 핵심적인 부분으로 운영 체제의 핵심 기능 및 자원 관리를 담당하며, 하드웨어와 응용 프로그램 간의 통신을 중재합니다. 대표적인 커널로 linux 커널, Window 커널, macOS 커널 등이 있다.

IPC에도 몇 가지 메커니즘이 존재하는데 이에 대해 알아보자.

• 익명 파이프 (Unnamed Pipe) : 두 개의 프로세스를 연결하는 데 하나의 프로세스는 데이터를 쓰기만 하고, 다른 하나는 데이터를 읽기만 할 수 있다. 한쪽 방향으로만 통신이 가능한 반이중 통신이라고도 부른다.
• 이름이 있는 파이프 (Named Pipe 또는 FIFO) : 통신할 프로세스를 명확히 알 수 있는 경우(ex) 부모 자식 프로세스 통신)에 사용한다. Named Pipe도 익명 파이프와 동일하게 단방향 통신 메커니즘을 갖고 있다.
• 메시지 큐 (Message Queue) : 프로세스 간에 메시지를 비동기적으로 전달하는 데 사용된다. 메시지 큐를 통해 메시지를 보내고 받는 프로세스는 독립적으로 실행된다. 파이프와 다른 점은 데이터의 흐름이 아니라 메모리 공간이다.
• 공유 메모리 (Shared Memory) : 데이터 자체를 공유하도록 지원하는 설비이다. 프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당해 주고 이후 모든 프로세스는 해당 메모리 영역에 접근할 수 있게 된다. 중개자 없이 곧바로 메모리에 접근할 수 있어서 IPC 중에 가장 빠르게 작동한다.
• 소켓 (Socket) : 네트워크 소켓 통신을 통해 데이터를 전송하는 데 사용되며 IPC의 확장된 형태이다. 클라이언트와 서버가 소켓을 통해서 통신하는 구조이다.

IPC는 다양한 운영 체제에서 지원되며, 프로세스 간 통신 및 협력을 허용하여 복잡한 응용 프로그램 및 시스템을 개발하는 데 중요한 역할을 한다.

이러한 IPC 통신에서 프로세스 간 데이터를 동기화하고 보호하기 위해 사용하는 게
세마포어(Semaphore) & 뮤텍스(Mutex)이다.
공유된 자원에 한 번에 하나의 프로세스만 접근시킬 때 사용한다.

임계 구역

세마포어와 뮤텍스를 이해하려면 임계 구역(Critical Section)을 알아야 한다.

임계 구역(Critical Section)은 다중 프로세스 또는 다중 스레드 환경에서 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분이다. 다른 말로는 공유 변수 영역이라고 한다.

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못될 결과를 만들 수 있기 때문에 충돌을 방지하고 데이터 무결성을 유지하기 위한 메커니즘이다.

임계 구역은 다음과 같은 3가지 특성을 갖고 있다.

1. 상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 들어가 있으면 다른 프로세스는 들어갈 수 없다.
2. 한정 대기(bounded wating) : 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
3. 진행의 융통성(progress flexibility) : 자기의 임계구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.

이러한 특성은 경쟁 조건(Race Condition)과 같은 문제를 방지하고 공유 자원을 안정할 수 있도록 한다.

경쟁 조건(Race Condition)은 두 프로세스가 서로 경쟁하여 데이터에 손상을 일으키는 경우를 말한다.

이러한 임계 구역을 만족하기 위해서 구현하는 방법들이 세마포어와 뮤텍스이다.

세마포어(Semaphore)

세마포어는 다중 프로세스 또는 다중 스레드 환경에서 동기화와 상호 배제를 관리하기 위한 동기화 도구 중 하나이다.

세마포어는 데이터나 자원에 대한 접근을 조절하는 데 사용된다.

세마포어 P, V 연산
P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)
V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

구현 예시

procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

이를 통해 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다.

세마포어는 크게 두가지 유형으로 나뉜다.

• 이진 세마포어 (Binary Semaphore): 값이 0 또는 1만 가질 수 있는 세마포어로, 주로 임계 구역의 이진 상태를 관리하는 데 사용됩니다. 이러한 이진 세마포어를 뮤텍스(Mutex)라고도 부른다.
• 카운팅 세마포어 (Counting Semaphore): 값이 양수 또는 음수가 될 수 있는 세마포어로, 여러 프로세스나 스레드가 동시에 접근할 수 있는 자원의 수나 작업 허용량을 관리하는 데 사용된다.

세마포어를 사용하면 공유자원에 대한 안전한 접근을 조절하고, 다중 프로세스 또는 스레드 간의 동기화 문제를 해결할 수 있지만 올바르게 사용하려면 주의 깊은 설계와 구현이 필요하다.

 뮤텍스(Mutex)

뮤텍스는 mutual exclusion의 약자로 상호 배제라는 뜻이다. 임계 구역을 가진 스레드들의 실행 시간이 서로 겹치지 않고 단독으로 실행되게 하는 기술을 말한다.

해당 접근을 조율하기 위해 lock과 unlock을 사용한다

lock은 현재 임계 구역에 들어갈 권한을 얻어오며, unlock은 현재 임계 구역을 모두 사용했음을 알린다.

뮤텍스는 상태가 0,1로 이진 세마포어라고도 불린다.

뮤텍스는 일반적으로 단일 소유권을 가지며, 잠긴 상태에서 다른 스레드 또는 프로세스가 잠금을 얻을 수 없다. 이로써 공유 자원에 대한 동시 액세스를 방지할 수 있다.

뮤텍스는 다른 스레드가 뮤텍스를 이미 잠갔을 경우, 새로운 스레드는 뮤텍스가 해제될 때까지 대기한다. 이러한 특성을 통하여 경쟁 조건(Race Condition)을 방지하고 공유 자원의 일관성 유지에 도움을 준다.

lock과 unlock을 사용한 이진 세마포어 알고리즘 외에도 여러가지가 있다.

1. 데커 알고리즘 : flag와 turn이라는 변수로 임계 영역에 들어갈 프로세스나 스레드를 결정하는 방식이다.

flag는 프로세스 중 누가 임계 영역에 진입할 것인지를 나타내는 변수이며,
turn은 누가 임계 구역에 들어갈 차례인지 나타내는 변수이다.

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

2. 피터슨 알고리즘 : 데커와 유사하지만 상대방 프로세스,스레드에게 진입 기회를 양보하는 것에 차이가 있는 알고리즘

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

3. 제과점(Bakery) 알고리즘 : 여러 프로세스,스레드에 대한 처리가 가능한 알고리즘이다. 가장 작은 수의 변호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {
    
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료