[CS Study] - 3주차

• Semaphore / Mutex
• IPC (Inter Process Communication)
• 가상 메모리
• 페이징 / 세그멘테이션

들어가기 전에

들어가기 전에 semaphore에 대해 간단하게 알아보도록 하겠다. Semaphore는 깃발이라는 뜻이다. 옛날에는 기찻길에서 깃발 표식으로 파란색이 걸려있으면 지나가도 되고 빨간색이 걸려있으면 섰다가 다른 기차가 지나가면 지나가게끔 하는 용도로 깃발을 사용했었다. 이 깃발을 semaphore라고 부른다.

그림에서처럼 겹치는 기찻길 부분이 두 기차가 공유하는 critical section이다. 그림에서도 critical section을 지나가도 된다 안된다를 알려주는 단어로 쓰인 것이다.

lock의 경우는 0 또는 1인 반면, 세마포어는 shared data의 개수를 의미한다. 그래서 0 또는 1 또는 2 또는... 등이 될 수 있다. 위의 그림에서는 공유 자원이 한 개이므로 (겹쳐지는 기찻길) semaphore의 값은 0 또는 1이다. 즉, 어떤 기차가 지나가고 있으면 내가 사용할 수 없으니 0이고 비어있으면 1의 값을 가지게 되는 것이다. 이렇게 0 또는 1의 값만 갖는 세마포어를 binary semaphore라고 한다.

이처럼 누가 사용하면 0이 되고 비어있으면 1이 되는, 즉 0과 1만 갖는 binary semaphore는 Lock하고 작동 원리가 반대이다. 0하고 1이 왔다갔다 하는 것은 동일하지만 세마포어는 초기화가 1이고 누가 사용하면 0인데, lock은 누가 사용했을 경우 1이기 때문이다.

0과 1뿐만 아니라 2,3,4 등의 값들 또한 가질 수 있는, 즉 도메인이 제한 없는 counting semaphore의 예시를 들어보겠다.

프린터 5대가 연결되어 있는 서버를 생각해보자. 사용자가 프린터를 사용하려고 서버에 요청한다. 그러면 공유 자원 프린터가 5개가 있으니까 5로 설정이 된다. 그리고 프린터를 사용자가 사용할 때마다 하나씩 감소하는 것이다. 그러다가 사용할 프린터가 없어지면 세마포어는 0이되고 누군가가 프린터를 다 쓰고 반환하면 세마포어가 다시 1이 증가한다.

다시 말하지만 여기서 세마포어는 단순히 공유 자원의 개수를 나타내는 변수이다.

Counting semaphore는 자원이 몇 개로 한정되었을 때, 이 자원에 접근하는 것을 컨트롤 하는데 사용된다. 그리고 세마포어는 사용 가능한 자원의 개수로 초기화 된다.

Semaphore / Mutex

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두어야 한다.

이를 위해 나온 것이 '세마포어'이다.

세마포어: 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

semaphore 접근 함수 - wait(), signal()

그러면 자원을 어떻게 사용하고 반납할까? 이를 위해 wait(), signal() 함수가 제공된다. 이 함수들은 사용하면 -1을 해주고, 반납할 때 +1을 해주면 된다. 다만 세마포어 자체가 공유 자원이 되면 안되니까 쪼개지지 않는 함수로 구성된다. shared data를 보호하려고 세마포어를 사용하는데 세마포어 자체가 shared data가 되면 말이 안되기 때문이다. 두 줄로 구성되지 않고 끼어들 틈이 없게 atomic하게 한 번에 수행시켜야 한다.

세마포어 변수 S는 결국 초기화를 제외하면 atomic operation인 wait()와 signal()로만 접근 가능한 정수 타입의 변수이다. 이 두 함수는 P 또는 V라고 많이 칭한다.

여담이지만, P는 네덜란드어 "테스트하다" 단어의 Probern에서 유래됐고, V는 "증가하다" 단어의 verhogen 단어에서 유래됐다고 한다. 이 단어들이 미국으로 건너가면서 영어로 표현할 때에는 -1하는 함수를 wait, +1하는 함수를 signal로 불리게 됐다고 한다.
shared data를 사용하려고 했는데 shared data가 없는 경우 기다려야 하니까 이 함수를 wait라고 지었고, 지금 비어있는 shared data가 있으면 기다리지 않고 사용하는 것이다. (-1) 그런데 만약 semaphore의 값이 0이라면 남은게 하나도 없다는 뜻이니까 동일하게 기다려야 한다. (wait) 다 사용하고 나서는 세마포어 값을 +1 해줘야 한다. 내가 다 사용한 이 shared data를 사용하려고 기다리는 누군가에게 신호를 보내줘야 하니까 signal() 함수이다.

임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

세마포어 P, V 연산

P: 임계 구역에 들어가기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정한다.)

V: 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

구현 방법

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

semaphore 구현 / wait 함수와 signal 함수의 구현

위의 구현 방법에 이어서 좀 더 자세히 알아보도록 하겠다.

전체적인 구조는 들어갈 때 wait, 나갈 때 signal이다. 그러므로 위 처럼 critical section에 들어가기 직전에 wait로 세마포어 1 감소, critical section 이후에 signal을 해줘서 세마포어 값을 증가해준다.

시작 전에 세마포어를 초기화 해준다. 여기서 세마포어를 구조체로 구현하였다. 세마포어를 의미하는 변수에 기다리는 프로세스를 관리하기 위해 프로세스 리스트를 구현하였다.

wait 함수를 구현해보면 다음과 같다. (S → 세마포어)

signal 함수를 구현해보면 다음과 같다.
wakeup(P)는 P 프로세스를 ready queue에다가 넣는 것을 말한다.

lock과 unlock을 value++에 해준 이유

value++; 이나 value--;는 atomic한 명령이 아니다. (여기서 atomic한 명령이라는 것은 컴퓨터의 가장 낮은 단일 언어일 때 한 사이클에 이루어지는 명령을 말한다. 쉽게 말해서 어셈블리어 명령어를 생각하면 된다.) value++; 가 한 줄이라 한 번에 처리되는 명령이라고 생각하기 쉬운데, 사실 이 명령은 세 개의 명령으로 이루어져있다.

count++ 처럼 하나 증가시키는 이 명령어는 사실, 실제 메모리에 있는 변수 값을 레지스터에다가 넣고, 레지스터를 1 증가시킨 후 다시 이 변수에다가 넣어주는 3개 절차의 명령으로 구성되어 있다. count--의 경우에도 마찬가지다. 즉, atomic instruction이 아니므로 연산 사이에서 얼마든지 인터럽트가 발생 될 가능성이 있고 이는 context switching이 발생할 수 있다는 의미이다. 또한 이는 동시 접근을 허용할 수 있다는 의미이므로 결론적으로 공유 자원 충돌 문제가 발생할 수 있다는 것이다.

따라서 value++; 이나 value--; 연산을 하기 전에 lock() 처리를 해준 것이다. 이 3줄짜리 명령어 (value++;)가 실행되는 동안에는 잠깐 인터럽트가 밀려도 큰 지장이 없을 것이다. 그래서 lock과 unlock를 해주어 발생할 수 있는 문제를 막아주는 것이 중요하다.

예시

최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계 구역에 들어간다.
2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
3. A가 임계 구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계 구역으로 들어가 수행한다.

뮤텍스: 임계 구역을 가진 스레드들의 실행 시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술 즉, 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘이다.

상호 배제 (Mutual Exclusion)의 약자이다.

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

• lock: 현재 임계 구역에 들어갈 권한을 얻어온다. (만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기)
• unlock: 현재 임계 구역을 모두 사용했음을 알린다. (대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음)

뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 한다.

뮤텍스 알고리즘

1. 데커(Dekker) 알고리즘
flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

• flag: 프로세스 중 누가 임계 영역에 진입할 것인지 나타내는 변수
• turn: 누가 임계 구역에 들어갈 차례인지 나타내는 변수
  

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

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

그림으로 보는 Semaphore와 Mutex의 차이

위에서도 계속 언급했지만, 동시성 프로그래밍의 가장 큰 숙제는 '공유 자원 관리' 일 것이다. 공유 자원을 안전하게 관리하기 위해서는 상호배제(Mutual exclusion)를 달성하는 기법이 필요하다. Mutex와 Semaphore는 이를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성한다. 이 둘의 차이를 "Toilet problem"이라는 재미있는 글에 빗대어 예시를 들어보겠다.

Mutex는 화장실이 하나 밖에 없는 식당과 비슷하다. 화장실을 가기 위해서는 카운터에서 열쇠를 받아가야 한다.

당신이 화장실을 가려고 하는데 카운터에 키가 있으면 화장실에 사람이 없다는 뜻이고 당신은 그 열쇠를 이용해 화장실에 들어갈 수 있다.

당신이 화장실에서 행복한 시간을 보내고 있는데 다른 테이블에 있던 어떤 남자가 화장실에 가고 싶어졌다. 이 남자는 아무리 용무가 급하더라도 열쇠가 없기 때문에 화장실에 들어갈 수 없다. 결국 이 남자는 당신이 용무를 마치고 나올 때까지 카운터에서 기다려야 한다. 곧이어 옆 테이블에 있는 남자도 화장실에 가고 싶어졌고 이 남자 또한 화장실에 들어가기 위해서는 카운터에서 대기해야 한다. 이제 당신이 화장실에서 나와 카운터에 키를 돌려놓았다. 기다리던 사람들 중 맨 앞에있던 사람은 키를 받을 수 있고 이를 이용해 화장실에 갈 수 있다.

이것이 Mutex가 동작하는 방식이다. 화장실을 이용하는 사람은 프로세스 혹은 쓰레드이며 화장실은 공유자원, 화장실 키는 공유자원에 접근하기 위해 필요한 어떤 오브젝트이다.
즉, Mutex는 Key에 해당하는 어떤 오브젝트가 있으며 이 오브젝트를 소유한 쓰레드 혹은 프로세스 만이 공유자원에 접근할 수 있다.

반면, Semaphore는 손님이 화장실을 좀 더 쉽게 이용할 수 있는 레스토랑이다. 세마포어를 이용하는 레스토랑의 화장실에는 여러 개의 칸이 있다. 그리고 화장실 입구에는 현재 화장실 빈 칸 개수를 보여주는 전광판이 있다. 만약 당신이 화장실에 가고 싶다면 입구에서 빈 칸의 개수를 확인하고 빈 칸이 1개 이상이라면 빈 칸의 개수를 하나 뺀 다음에 화장실로 입장하면 된다. 그리고 나올 때 빈 칸의 개수를 하나 더해준다. 모든 칸에 사람이 들어갔을 경우 빈 칸의 개수는 0이 되며 이 때 화장실에 들어가고자 하는 사람이 있다면 빈 칸의 개수가 1로 바뀔 때까지 기다려야 한다. 사람들은 용무를 보고 나오면서 빈 칸의 개수를 1씩 더한다. 그리고 기다리던 사람은 이 숫자에서 다시 1을 뺀 다음 화장실로 들어가면 된다.

이처럼 세마포어는 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성한다.

세마포어도 아까와 동일하게 화장실이 공유자원이며 사람들이 쓰레드, 프로세스이다. 그리고 화장실 빈칸의 개수는 현재 공유자원에 접근할 수 있는 쓰레드, 프로세스의 개수를 나타낸다.

정리를 해보면 다음과 같다.
Mutex: 한 쓰레드, 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법
Semaphore: Signaling mechanism. 현재 공유자원에 접근할 수 있는 쓰레드, 프로세스의 수를 나타내는 값을 두어 상호배제를 달성하는 기법

세마포어와 뮤텍스의 차이점

1. 가장 큰 차이점은 동기화 대상의 개수이다.

   • Mutex는 동기화 대상이 only 1개일 때 사용
   • Semaphore는 동기화 대상이 1개 이상일 때 사용

2. 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.

   • Mutex는 0, 1로 이루어진 이진 상태를 가지므로 Binary Semaphore이다.

3. Mutex는 자원 소유 가능 + 책임을 가지는 반면, Semaphore는 자원 소유가 불가하다.

   • Mutex는 상태가 0, 1 뿐이므로 lock을 가질 수 있다.

4. Mutex는 소유하고 있는 스레드만이 이 Mutex를 해제할 수 있다.

   • 반면, Semaphore는 Semaphore를 소유하지 않는 스레드가 Sempaphore를 해제할 수 있다.

5. Semaphore는 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재한다.

   • 반면, Mutex는 프로세스의 범위를 가지며 프로세스 종료될 때 자동으로 Clean up 된다.

뮤텍스와 세마포어는 모두 완벽한 기법은 아니므로, 데이터 무결성을 보장할 수 없으며 모든 교착 상태를 해결하지는 못한다. 하지만, 상호배제를 위한 기본적인 기법이며 여기에 좀 더 복잡한 메커니즘을 적용해 개선된 성능을 가질 수 있도록 하는 것이 중요하다.

IPC (Inter Process Communication)

우리가 사용하는 프로세스들은 모두 유저 공간(User-mode)에서 각각 OS로부터 할당한 독립된 공간에서 실행된다. 여기서 말하는 독립되어 있다는 의미는 다른 프로세스의 영향을 받지 않는다는 장점이 있지만, 독립되어 있는 만큼 별도의 설비 없이는 서로 간에 통신이 어렵다는 문제가 있다. 하지만 하나의 프로그램을 실행하더라도 여러 프로세스끼리 협력이 필요한 상황이 있다. (스레드는 프로세스 안에서 자원을 공유하므로 영향을 받는다.)

예를 들어 특정 Task를 여러 개의 Sub Task로 나누어 더 빠르게 수행해야 한다거나, 동시에 많은 Task를 한 번에 처리해야 하는 경우가 있다. 이를 해결하고자 커널 영역(Kernel-mode)에서 IPC라는 프로세스들 간에 통신을 제공하고 있다.

즉, 프로세스 간의 통신을 해야 하는 상황에서 이를 가능하도록 해주는 것이 IPC 통신이다.

커널이란?
운영체제의 핵심적인 부분으로, 다른 모든 부분에 여러 기본적인 서비스를 제공해줌

IPC 설비 종류도 여러가지가 있다. 필요에 따라 IPC 설비를 선택해서 사용해야 한다.

IPC 종류

1. 익명 PIPE
파이프는 두 개의 프로세스를 연결하는데 하나의 프로세스는 데이터를 쓰기만 하고, 다른 하나는 데이터를 읽기만 할 수 있다.

한쪽 방향으로만 통신이 가능한 반이중 통신이라고도 부른다.

따라서 양쪽으로 모두 송/수신을 하고 싶으면 2개의 파이프를 만들어야 한다.
매우 간단하게 사용할 수 있는 장점이 있고, 단순한 데이터 흐름을 가질 땐 파이프를 사용하는 것이 효율적이다. 단점으로는 전이중 통신을 위해 2개를 만들어야 할 때는 구현이 복잡해지게 된다.

2. Named PIPE(FIFO)
익명 파이프는 통신할 프로세스를 명확히 알 수 있는 경우에 사용한다. (부모 - 자식 프로세스 간 통신처럼)

Named 파이프는 전혀 모르는 상태의 프로세스들 사이의 통신에 사용한다.

즉, 익명 파이프의 확장된 상태로 부모 프로세스와 무관한 다른 프로세스도 통신이 가능한 것이다. (통신을 위해 이름있는 파일을 사용) 하지만 Named 파이프 역시 읽기/쓰기가 동시에 불가능하다. 따라서 전이중 통신을 위해서는 익명 파이프처럼 2개를 만들어야 된다.

3. Message Queue
입출력 방식은 Named 파이프와 동일하다. 다른 점은 메시지 큐는 파이프처럼 데이터의 흐름이 아니라 메모리 공간이다. 사용할 데이터에 번호를 붙이면서 여러 프로세스가 동시에 데이터를 쉽게 다룰 수 있다.

4. 공유 메모리
파이프, 메시지 큐가 통신을 이용한 설비라면, 공유 메모리는 데이터 자체를 공유하도록 지원하는 설비이다.

프로세스의 메모리 영역은 독립적으로 가지며 다른 프로세스가 접근하지 못하도록 반드시 보호되어야 한다. 하지만 다른 프로세스가 데이터를 사용하도록 해야하는 상황도 필요할 것이다. 파이프를 이용한 통신을 통해 데이터 전달도 가능하지만, 스레드처럼 메모리를 공유하도록 해준다면 더욱 편할 것이다.

공유 메모리는 프로세스간 메모리 영역을 공유해서 사용할 수 있도록 허용해 준다.

프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당해주고 이후 모든 프로세스는 해당 메모리 영역에 접근할 수 있게 된다.

중개자 없이 곧바로 메모리에 접근할 수 있어서 IPC 중에 가장 빠르게 작동한다.

5. 메모리 맵
공유 메모리처럼 메모리를 공유해준다. 메모리 맵은 열린 파일을 메모리에 맵핑시켜서 공유하는 방식이다. (즉, 공유 매개체가 파일 + 메모리)

주로 파일로 대용량 데이터를 공유해야 할 때 사용한다.

6. 소켓
네트워크 소켓 통신을 통해 데이터를 공유한다. 클라이언트와 서버가 소켓을 통해서 통신하는 구조로, 원격에서 프로세스 간 데이터를 공유할 때 사용한다.

서버(bind, listen, accept), 클라이언트(connect)

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

위에서 말한 것을 정리해보면, 프로세스는 다른 프로세스에게 영향을 끼치지도 받지도 않는 독립적인 프로세스와, 영향을 주고 받으며 자원을 공유하는 협력적인 프로세스로 나눌 수 있다. 그리고 IPC는 cooperating process 사이에서 서로 데이터를 주고 받는 행위 또는 그에 대한 방법이나 경로를 말한다.

그럼 협력 프로세스를 왜 사용하고 허용하는 것일까?

1. Information sharing
만약에 여러 사람들이 하나의 파일을 공유하고 싶어한다면 그 파일(정보)에 동시 접근이 가능한 환경을 제공해주어야 한다. 자원을 다른 사람들과 공유하는 것이 협력 프로세스인 것이고 협력 프로세스를 통해 자원을 공유해야하는 것이다.

2. Computation speedup
1번과 같이 자원을 공유하고자 할 뿐만 아니라, 속도를 높일 때에도 사용한다. 만약 어떤 작업이 더 빨리 완성되고 싶다면 그 작업을 세부 작업으로 쪼개서 각 작업들이 동시에 진행되게 하면 배로 빨라질 것이다. 그럼 그 프로세스들은 다른 프로세스들과 협력하면서 동시에 진행될 것이다.

3. Modularity
모듈화를 말한다. 어떤 시스템을 모듈 방식으로 개발한다 하면, 시스템 기능을 여러개의 프로세스나 스레드로 나눈다. 즉, 여러 프로세스가 협력하는 상황이 생긴다.

4. Convenience
이 뿐만 아니라 우리 개인도 사실 한번에 많은 일을 진행한다. (멀티 태스킹) 편집하면서 음악도 듣고 이런것에도 협력 프로세스가 사용된다.

Messaging passing (메시지 교환) VS Shared memory (데이터 공유)

IPC에는 기본적인 두 가지 방법(모델)이 있다. 메시지 교환과 데이터 공유이다.

1. Message passing
커널(OS)가 memory protection을 위해 대리 전달해주는 것을 말한다. 따라서 안전하고 OS가 알아서 동기화 해주기 때문에 동기화 문제가 없다. 하지만 성능이 떨어지는 단점을 가지고 있다. Message passing은 direct communication과 indirect communication이 있다.

2. Shared memory
두 프로세스간의 공유된 메모리를 생성 후 이용하는 것을 말한다. 성능이 좋지만 동기화 문제가 발생한다. (App에서 직접 동기화를 해주어야 한다.)

예시를 들어보면, 프로세스 A가 있고 프로세스 B가 있다. process A에 rss1이 있고, process B에 rss2가 있다고 가정해보자. 이 두 프로세스가 서로 자원들을 주고 받으려면 어떻게 해야할까? process B가 A의 rss1에 접근하려고 하면 Memory protection에 의해서 막힐 것이다. 자신이 아닌 다른 프로세스로의 접근을 안막으면 큰일난다. A프로세스가 B프로세스를 죽일 수도 있기 때문이다. B의 rss2 뿐만 아니라 다른데에도 접근해서 죽일 수 있기 때문에 Memory protection에 의해 이러한 방법을 불가능하다.

Messaging passing

따라서 서로 자원을 협력하려면 운영체제가 도와줄 수 밖에 없다.
아래 그림과 같이, 프로세스 A가 커널로 메시지를 보내면 그것을 커널이 B에게 보내주는 것이 메시지 교환 방식이다.

위의 그림은 direct communication으로 커널에 메시지를 직접 주고 그것을 커널이 B에게 메시지를 직접 전달하는 방법이다.

반면, indirect communication 방법은 아래의 그림과 같다.

위의 그림처럼 indirect communication은 A가 '커널에 ABC라는 메시지 박스에 넣어둘 테니까 너가 거기서 읽어가'라고 하면 B가 ABC라는 메시지 박스에 가서 읽어오는 방식을 말한다. 둘 다 커널을 이용한 Message passing이지만 커널이 직접 전달하냐 아니냐로 방법이 나뉘는 것이다.

위의 그림에서 쌓여있는 메시지들을 확인할 수 있다. indirect communication의 단점은 번거롭고 오버헤드가 크다는 것이다.

Messaging passing의 특징

• 커널 메모리 영역에 메시지 전달을 위한 채널을 만들어서 협력하는 프로세스들 사이에 메시지 형태로 정보를 Send/Receive 하는 방법이다.
• 커널을 경유하여 메시지를 송/수신자끼리 주고 받으며, 커널에서는 데이터를 버퍼링한다.
• 예를 들어, A 프로세스가 커널로 메시지를 보내면 커널이 B에게 메시지를 보내주는 방식이다.
• 프로세스 간 메모리 공유 없이 동작이 가능하다.

Messaging passing의 장점

커널에서 데이터를 주고 받는 것을 컨트롤 할 수 있어 별도의 동기화 로직이 없어도 된다.

Messaging passing의 단점

• 커널을 통해서 데이터를 주고 받기 때문에 Shared Memory 보다 느리다.

Shared memory

그렇다면, Process A와 Process B가 모두 읽고 쓸 수 있는 메모리를 만들고 거기서 주고 받고 할 수 있도록 하는 것은 어떨까? 이 방법이 Shared memory이다. 성능은 Messaging passing 방식에 비해 우수하지만 동기화라는 문제점이 있다.

동기화
프로세스 A에서 쓰고 B에서 읽는데, 만약 B가 조금 일찍 읽는 상황이라면 지금 A가 이걸 쓴건지 안쓴건지 알 수가 없다. 그래서 A가 이걸 썼는지 B가 아는, 즉 확인하는 기법이 추가적으로 필요한 경우

Shared memory의 특징

• 두 개 이상의 프로세스들이 주소 공간의 일부를 공유하며, 공유한 메모리 영역에 읽기/쓰기를 통해 통신을 수행한다. (Read and Write)

• 프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당 해주게 되고, 이후 어떤 프로세스건 해당 메모리 영역에 접근할 수 있다. 공유 메모리가 설정되면, 그 이후의 통신은 커널의 관여 없이 진행이 가능하다.

Shared memory의 장점

• 커널의 관여 없이 메모리를 직접 사용하여 IPC 속도가 빠르다.

• 프로그램 레벨에서 통신 기능을 제공하여, 자유로운 통신이 가능하다.

Shared memory의 단점

• 메시지 전달 방식이 아니기에 데이터를 읽어야 하는 시점을 알 수 없다.
• 예를 들어, 프로세스 A가 공유 메모리에 데이터를 전달해도 프로세스 B가 그것을 알 수 없다.
• 그렇기 때문에 별도의 동기화 기술이 필요하다.
• 동시에 같은 메모리 위치를 접근하는 상황이 발생할 수 있다. (공유 메모리에 접근할 프로세스 간의 Lock 메커니즘이 필요하다.)

결국, IPC란 두 개의 프로세스 간 통신을 말하는데 하나의 컴퓨터에 있는 두 개의 프로세스만을 의미하지는 않는다. 서로 다른 컴퓨터에 있는 두 개의 프로세스가 통신하는 일명 네트워킹도 IPC이다. 그 두 개의 프로세스가 네트워크로 연결된 다른 컴퓨터에 존재할 뿐이다.

이것을 소켓이라고 하는 것이 있고, RPC (Remote Procedure Call;C++)이라고도 하고 JAVA의 경우 RMI라고 부르는 결국 다 동일한 맥락이라고 할 수 있다.

가상 메모리

주제에는 가상메모리만 작성 해놨지만 메인 메모리, 캐시 메모리, 가상 메모리에 대해서 알아보도록 하겠다.

1. 메인 메모리 (Main memory)

메인 메모리는 CPU가 직접 접근할 수 있는 기억 장치이다. 프로세스가 실행되려면 프로그램이 메모리에 올라와야 한다.

메인 메모리는 주소가 할당된 일련의 바이트들로 구성되어 있다. CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져온다. 명령어 수행 시 메모리에 필요한 데이터가 없으면 해당 데이터를 우선적으로 가져와야 하는데 이 역할을 하는 것이 MMU이다.

MMU (Memory Management Unit; 메모리 관리 장치)

• 논리 주소를 물리 주소로 변환해 준다.
• 메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어이다.

메모리의 공간이 한정적이기 때문에 사용자에게 더 많은 메모리를 제공하기 위해 '가상 주소' 라는 개념이 등장하였다. (가상 주소는 프로그램 상에서 사용자가 보는 주소 공간이라고 보면 된다.)

이 가상 주소에서 실제 데이터가 저장 되어있는 곳에 접근하기 위해 빠른 주소 변환이 필요한데, 이를 MMU가 도와준다.

즉, MMU의 역할은 다음과 같다.

• MMU가 지원되지 않으면, Physical address를 직접 접근해야 하기 때문에 부담이 있다.
• MMU는 사용자가 기억장소를 일일이 할당해야 하는 불편을 없애준다.
• 프로세스의 크기가 실제 메모리의 용량을 초과해도 실행될 수 있게 해준다.

또한, 메인 메모리의 직접 접근은 비효율적이므로 CPU와 메인 메모리 속도를 맞추기 위해 캐시가 존재한다.

MMU의 메모리 보호
프로세스는 독립적인 메모리 공간을 가져야 되고, 자신의 공간만 접근해야 한다. 따라서 한 프로세스에게 합법적인 주소 영역을 설정하고, 잘못된 접근이 오면 Trap을 발생시키며 보호한다.

base와 limit 레지스터를 활용하여 메모리를 보호한다.
base 레지스터는 메모리상의 프로세스 시작 주소를 물리 주소로 저장하며 limit 레지스터는 프로세스의 사이즈를 저장한다.

그러므로 프로세스의 접근 가능한 합법적인 메모리 영역(x)는 다음과 같다.
이 영역 밖에서 접근을 요구하면 Trap을 발생시키는 것이다.

안전성을 위해 base와 limit 레지스터는 사용자 모드에서는 직접 변경이 불가능하고 커널 모드에서만 수정 가능하도록 설계되어 있다.

메모리 과할당 (Over allocating)

실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스에 할당한 상황

페이지 기법과 같은 메모리 관리 기법은 사용자가 눈치 채지 못하도록 눈속임을 통해 메모리를 할당해준다. (가상 메모리를 이용해서)

하지만, 과할당 상황에 대해서 사용자를 속인 것을 들킬만한 상황이 존재한다.
1. 프로세스 실행 도중 페이지 폴트 발생
2. 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
3. 메모리의 빈 프레임에 페이지를 올려야 하는데, 모든 메모리가 사용중이라 빈 프레임이 없음

이러한 과할당을 해결하기 위해서는 빈 프레임을 확보할 수 있어야 한다.
1. 메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻는다.
2. 프로세스 하나를 swap out하고 이 공간을 빈 프레임으로 활용한다.

swapping 기법을 통해 공간을 바꿔치기하는 2번 방법과 달리 1번 방법은 사용자에게 페이징 시스템을 들킬 가능성이 매우 높아서 사용하면 안된다. 페이징 기법은 사용자 모르게 시스템 능률을 높이기 위해 선택한 일이므로 들키지 않게 처리해야 한다.
따라서, 2번과 같은 해결책을 통해 페이지 교체가 이루어져야 한다.

페이지 교체

메모리 과할당이 발생했을 때, 프로세스 하나를 swap out해서 빈 프레임을 확보하는 것을 말한다.

1. 프로세스 실행 도중 페이지 부재가 발생
2. 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾는다.
3. 메모리에 빈 프레임이 있는지 확인한다.
   • 빈 프레임이 있으면 해당 프레임을 사용하고 빈 프레임이 없으면 victim 프레임을 선정하여 디스크에 기록하고 페이지 테이블을 업데이트 한다.
4. 빈 프레임에 페이지 폴트가 발생한 페이지를 올리고, 페이지 테이블을 업데이트 한다.

페이지 교체가 이루어지면 아무일이 없었던 것처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야 한다. 이때, 아무일도 일어나지 않은 것처럼 하려면, 페이지 교체 당시 오버헤드를 최대한 줄여야 한다.

오버헤드를 감소시키는 해결법
이처럼 빈 프레임이 없는 상황에서 victim 프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 두 번의 디스크 접근이 이루어진다. 페이지 교체가 많이 이루어지면 이러첨 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생한다.

방법1

변경비트를 모든 페이지마다 두어서, victim 페이지가 정해지면 해당 페이지의 비트를 확인한다.

• 해당 비트가 set 상태이면? → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 의미이다. 즉, 페이지가 메모리에 올라온 이후 한번이라도 수정이 일어났다는 것이므로 디스크에 기록해야 한다.

• 비트가 clear 상태이면? → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황이다. 즉, 디스크와 내용이 동일해서 기록할 필요가 없다.

비트를 활용해 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법이다.

방법2

페이지 교체 알고리즘을 상황에 따라 잘 선택해야 한다. 현재 상황에서 페이지 폴트를 발생할 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용해야 한다.

ex) FIFO, OPT, LRU

캐시 메모리

주기억장치에 저장된 내용의 일부를 임시로 저장해두는 기억장치이다. CPU와 주기억장치의 속도 차이로 성능 저하를 방지하기 위한 방법이다.

CPU가 이미 봤던 것을 다시 재접근할 때, 메모리 참조 및 인출 과정에 대한 비용을 줄이기 위해 캐시에 저장해둔 데이터를 활용한다.

캐시는 플리플롭 소자로 구성되어 SRAM으로 되어있어서 DRAM보다 빠르다는 장점을 가지고있다.

CPU와 기억장치의 상호작용

CPU에서 주소를 전달 → 캐시 기억장치에 명령이 존재하는지 확인

• 존재한다면 Hit
  해당 명령어를 CPU로 전송 → 완료

• 존재하지 않는다면 Miss
  명령어를 가지고 주기억장치로 접근 → 해당 명령어를 가진 데이터를 인출 → 해당 명령어 데이터를 캐시에 저장 → 해당 명령어를 CPU로 전송 → 완료

이처럼 캐시를 잘 활용한다면 비용을 많이 줄일 수 있다. 따라서 CPU가 어떤 데이터를 원할지 어느정도 예측할 수 있어야 한다. (캐시에 자주 활용되는 정보가 들어있어야 성능이 높아짐)

적중률을 극대화 시키기 위해 사용되는 것이 지역성의 원리 이다.

지역성

기억 장치 내의 정보를 균일하게 엑세스 하는 것이 아니라 한 순간에 특정 부분을 집중적으로 참조하는 특성

지역성의 종류는 시간과 공간으로 나누어진다.
시간 지역성: 최근에 참조된 주소의 내용은 곧 다음에도 참조되는 특성
공간 지역성: 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

캐싱 라인

빈번하게 사용되는 데이터들을 캐시에 저장했더라도, 내가 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비이다.

즉, 캐시에 목적 데이터가 저장 되어있을 때 바로 접근하여 출력할 수 있어야 캐시 활용이 의미있다. 따라서 캐시에 데이터를 저장할 때, 자료구조를 활용해 묶어서 저장하는데 이를 캐싱 라인 이라고 부른다.

즉, 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하면서 빠르게 원하는 정보를 찾는 것이다. (set이나 map 등을 활용한다.)

가상 메모리

기존에는 프로세스가 실행되는 코드의 전체를 메모리에 로드해야 했고, 메모리 용량보다 더 큰 프로그램은 실행시킬 수 없었다. 하지만 실제로는 코드의 일부에서만 대부분의 시간을 사용하고, 프로세스는 특정 순간에는 항상 작은 양의 주소 공간을 사용하기 때문에 이러한 방식은 매우 비효율적이다.

가상 메모리 (Virtual Memory)는 이러한 물리적 메모리 크기의 한계를 극복하기 위해 나온 기술이다. 프로세스를 실행할 때 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크에 두는 것이다.

이를 통해 프로세스 전체가 물리적 메모리에 있는 것처럼 수행되는, 즉 물리적 메모리가 훨씬 많이 있는 것처럼 보이게 된다. 결과적으로 메모리에 작은 양의 주소 공간만 있으면 충분히 프로세스를 수행할 수 있고, 그에 따라 더 많은 프로그램을 동시에 실행할 수 있게 된다.

이처럼 현재 필요한 page만 메모리에 올리는 것을 Demand Paging이라고 한다.

페이징 / 세그먼테이션

페이징과 세그먼테이션을 하는 이유

• 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요하기 때문이다.

메모리 관리 기법

1. 연속 메모리 관리

프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 한다.

• 고정 분할 기법: 주기억장치가 고정된 파티션으로 분할 (내부 단편화 발생)
• 동적 분할 기법: 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

Reference
https://jhnyang.tistory.com/101?category=815411
https://icksw.tistory.com/167
https://worthpreading.tistory.com/90
https://gyoogle.dev/blog/computer-science/operating-system/IPC.html
https://rebro.kr/179
https://steady-coding.tistory.com/508