weasel의 우당탕탕 개발기

Why B 트리?

B 트리는 이진트리와 다르게 하나의 노드에 많은 정보를 가질 수 있는 트리를 의미한다. 노드의 최대 자식의 개수를 M이라고 할때, M차 B트리라고 한다.

B 트리는 고전적인 메모리 계층 구조의 물음에서 출발한다.
이진탐색트리의 시간복잡도가 최악이 될 때는 노드가 편향된 경우인데, 이를 해결하는 것이 AVL,RB 트리와 같은 균형이진트리다.

그런데 이것만으로 부족하다. 왜 그러냐면, O(logn) 을 보장하는 균형이진트리의 최악을 생각해보자.

최악이 있을까? 분명히 있다.

RB트리에서 원소가 1백만개라고 해보면, 트리의 높이는 최대 2*log(10^6)이다. 따라서 대략 20정도이다.

RB 트리에서 Red 노드는 최대 두개만 연속으로 되어있음을 생각하면 쉽게 알 수 있다.

그러면, 원하는 원소를 찾기 위해서 20번 정도의 노드 액세스가 필요한데,
만약 모든 노드가 메인 메모리에 있다고 생각해보면, 매우 비싼 20번의 메모리 접근이 일어나는 것이다.

심지어 메인 메모리가 아닌 디스크에 있다면? 더 많은 시간이 단순히 노드에 접근하는데 쓰일 것이다.

따라서 이러한 메모리, 디스크에 관한 접근을 줄여야 한다. 그러기 위해서는 트리의 탐색 높이를 줄여야 한다.
이진트리에서 log의 베이스가 2인 이유가 2개의 자식노드임을 기억했을때 degree를 늘려야 하는 것이다.

💡 실제로는 트리 노드들이 하나의 캐시 라인이나 디스크 블록을 채울 수 있는 가장 큰 차수를 사용하고 있다.

따라서 B 트리는 아주 많은 양의 데이터들이 존재하는 곳에 사용되고, 높이를 h 라고 할때, 조회,삽입,삭제 등등의 동작 모두 O(h) 의 디스크 접근을 요구한다.

B 트리는 노드에 가능한 최대의 키들을 삽입하면서 트리의 높이를 낮게 유지한다.

즉, Balanced를 삽입,삭제 과정에서 혼자서 유지한다는 것이다.

그렇기에 AVL,RB 트리와 비교해서 매우 낮은 디스크 접근을 수행한다.

💡 이게 뭔말인가 했더니 노드의 사이즈를 디스크 블록 사이즈와 거의 동일하게 유지한다는 말, 어차피 디스크 액세스할때 1K 읽나 , 1 Byte 읽나 오버헤드는 같으니까, 한번에 많이 읽어오면 되는거다.

이러한 여러가지 특성때문에 B 트리는 B+트리와 더불어서 DBMS에서 많이 사용되고 있다.

💡 인덱스 다룰때 많이 쓴다고 한다. 요즘에 MongoDB 만지는데 대놓고 공식문서에 인덱스는 B트리 쓴다고 되어 있다. 물론 PostgreSQL 이런건 B+트리도 쓰고, MySQL은 B 트리,B+트리, 해시 다 쓴다.

B 트리 정의

degree가 m인 B트리는 아래와 같은 특성을 가진다.

• 루트 노드는 적어도 2개의 자식을 가진다.
• 루트 노드와 외부 노드를 제외한 모든 내부 노드는 적어도 올림(m/2)개, 최대 m 개의 자식을 가진다.
  • m=2이면, 1~2개의 자식 노드 → 포화 이진 트리
  • m=3이면, 2~3개의 자식 노드 → 2-3 트리
  • m=4이면, 2~4개의 자식 노드 → 2-3-4 트리
• 모든 외부 노드들은 같은 레벨에 있다. (Perfectly Balanced)
  • 이게 매우 중요... 높이의 상한을 준다는 것이니까 디스크 접근에 대한 상한을 준다는 것.
  • 그림에서 {8,11}, {22,23}, {58,59} 같은 애들을 외부 노드라고 부른다.
• 각각의 노드는 적어도 [m/2] 개, 최대 m-1 개의 키를 가질 수 있다.
  • 아래 그림을 보면, m=3일때, [3/2]=1 ~ 3-1=2 개의 키를 가진다.
  • 
  • 이런 조건이 있는 이유는, 만약 m=5일때 , 1개의 키가 있다고 해보자. 다음 키는 그 키보다 작거나 크거나 즉 두개인데, 그러면 3-4-5 트리를 만족하지 않는다.

B 트리의 목적이 데이터를 넓게 흩뿌리면서 높이를 낮게 가져간다는 점을 생각해보면서, n개의 원소가 있다고 할 때, 높이의 상한에 대해서 계산해보자.

• Best Case
  • 최고의 경우는 가장 잘 흩뿌려질때니
  • logm(n) n=(log n)/(log m)=O(log n)
• Worst Case
  • 최악의 경우는 가장 덜 흩뿌려질때, 즉 노드가 최소의 자식을 가지는 올림(m/2) 갈래로 흩어질때임.
  • log올림(m/2)(n)=(log n)/(log(올림(m/2))=O(log n)

즉 모든 최고,최악의 경우 모두 O(log n) 의 높이가 보장됨을 알게 되었다.

조회

조회는 이진탐색의 그것과 매우 비슷하다. 이진 탐색에서 조회는 분기가 세가지다. (못 찾는 경우 제외)

내가 찾는 키를 k 라고 하고, 노드의 키를 v 라고 하면,

• k=v : 같거나 → 찾았다.
• k>v : 작거나 → 왼쪽 서브 트리로 간다.
• k<v : 크거나 → 오른쪽 서브 트리로 간다.

이것처럼 B 트리에서도 비슷한 방식대로 움직이는데, 분기가 두가지다.

• k=v : 같거나 → 찾았다.
• i-th v< k < i+1-th v 를 만족하는 i 를 찾고 i-th pointer 가 가르키는 서브트리로 간다.
  • 이때 만족하는 i 는 최대 m-1 개이므로, 루프를 돌아도 되고, 이진 탐색을 수행해도 된다. ← 루프를 돌아도 안전한게, 어차피 같은 메모리안에 올라와
    있다. 추가적인 디스크 액세스가 필요하지 않다.
    

    

삽입

삽입부터 B 트리가 복잡해지고, 또 그 과정에서 B 트리가 가지는 균형유지의 전략을 볼 수 있다.

일단, 조회의 과정을 거치고, 삽입할만한 적절한 리프 노드 위치를 찾는다. 그 다음부터 분기가 나뉜다.

💡 리프 노드에 넣는 이유는 아래에서 설명하겠지만 삽입시에 일어나는 분할이 상향식이기 때문이다.

• 삽입할 곳에 자리가 남아있다면 (current capacity<m-1) , 그냥 넣고 끝낸다.
• 삽입한 뒤에 넘친다면, 분할한다.

분할

리프노드에 삽입한 후에 m개의 키를 가진다면, 분할하는 과정을 거친다. m개의 키를 가진 노드에 대해서 세 그룹으로 분할한다. (아래 과정은 m이 홀수일때)

1. 중위순서의 키보다 작은 키들로 이루어진 노드들
2. 중위순서의 키
3. 중위순서의 키보다 큰 키들로 이루어진 노드들

그리고 1번과 3번 그룹의 부모를 2번으로 만든다. 즉, 여전히 성질이 깨지지 않게끔 하는 것.

만약 이때 부모가 넘친다면? 또 다시 진행한다. 그렇기에 리프노드에서의 넘침이 상향식으로 전파될 가능성이 있는것.

이게 루트까지 넘친다면, 루트에 대해서 두 개의 자식을 가지는 새로운 노드를 만든다.

예시를 다 보여주기에는 어려우니, 가장 복잡한 예시만 들면 아래와 같다.

우선 67이 들어갈 위치를 찾는 과정을 거치고, 넣을만한 곳을 찾았는데 넣는 순간 5개의 키를 가지면서 넘친다. 분할 발생!
중위순서의 키는 67이니, {55,66}, {67}, {68,70} 로 나눈 후 {55,66} → {67} ← {68,70} 으로 만든다.

근데 67이 들어갈 위치는 50의 옆이다. 그런데 그럼 루트에서 넘침이 생기니, 루트에 대해서 상향식으로 분할이 전파된다.

따라서 {5,10} → {22} ← {50,67}의 구조로 만든 후 체크하면 5개의 키를 안 넘치니 끝.

삭제

삭제는 삽입보다 복잡하다.

B트리에서의 삭제는 삭제된 후에 B트리의 성질을 유지하기 위해서 최소키의 개수를 만족하는지,
만족하지 않으면 추가적인 조치가 필요하기 때문이다.

B트리에서의 삭제는 크게는 두가지, 작게는 세가지 경우가 있는데 , 먼저 삭제할 키인 k가 리프에 있는지 없는지를 따져서 두가지로 나뉜다.

💡 모든 삽입, 삭제 과정에서 k가 들어갈 혹은 삭제될 위치를 찾는 조회과정이 선행된다.

k가 리프에 있을때

근데 여기서 또 나뉜다. 골치 아프다. 아래 과정에서 m은 3이다. (2-3트리)

• k가 있는 노드의 키의 개수가 최소 키의 개수보다 클때 → 그냥 k를 삭제해도 아무런 문제가 없다.
• 형제 노드 중 하나의 키의 개수가 최소 키의 개수보다 클때
  1. 부모 키의 값으로 k를 대체한다.
  2. 최소 키의 개수보다 큰 형제노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모 키로 대체한다.
  3. 
• 양 쪽 형제가 최소 키의 개수를 가지고 있고 , 부모 노드의 키가 최소 키의 개수보다 많다면,
  1. k를 삭제한 후, 부모 키와 형제 노드를 병합한다. → 정확히는 부모 키가 내려오는 것.
  2. 부모노드의 키를 하나 줄이고, 자식 수 역시 줄여서 B트리의 특성을 유지한다.
  
• 양 쪽 형제가 최소 키의 개수를 가지고 있고, 부모 노드 역시 최소 키의 개수면 → 부모를 루트로 한 서브 트리의 높이 자체가 줄어들기 때문에 재구조화가 이어진다. 아래 참조
  • 어디에서 가져오든, 무조건 빵꾸가 생기잖아요~

k가 내부노드에 있고, 현재 노드 혹은 자식 노드의 키의 개수가 최소 이상일때

k를 predecessor(왼쪽 서브트리의 가장 큰 값) 혹은 successor(오른쪽 서브트리의 가장 작은 값)와 교환해준다. 찾는 과정은 BST의 그것과 매우 유사.

그런 후에 리프 노드가 된 k 를 삭제한 후 필요에 의해서 리프노드에서의 삭제 핸들링 과정으로 넘어간다.

위의 그림에선, 양쪽 형제 모두 최소 키의 개수만큼 가지고 있고, 부모노드의 키의 개수가 최소개수 이상이니 15,17이 병합된다.

k가 내부노드에 있고, 현재 노드,자식 노드의 키의 개수가 최소개수일때

만약 이 상황에서 k를 삭제하면, 전체적인 높이가 낮아지면서 B 트리의 조건을 유지하려 함. 이를 트리의 재구조화라 한다.

1. k를 삭제하고, k의 자식을 하나로 합친다.
2. k 의 부모 키를 인접한 형제노드에 붙인다. (이때 k 는 당연히 루트가 아니다. 루트면 위에서 걸렸겟지)
3. 아까 병합한 노드를 2번의 자식노드로 설정한다. (왼쪽 혹은 오른쪽)
4. 만약 이럴때, 부모노드의 키의 개수에 따라 수행 과정이 다르다. 이에 대해서 또 분기한다.

• 새로 구성된 인접 형제노드(부모 키 붙인)가 오버플로우 나면, 삽입연산에서의 분할 수행
• 인접 형제노드가 구성되더라도, k의 부모 노드가 최소 키의 개수보다 작아진다면, 다시 위의 2번 과정부터 수행한다.

다른 예시

4를 삭제하자. 이러면 현재 노드, 자식 노드 모두 키가 최소다.

2와 6을 합치고,

내 부모 노드와 합친것을 자식-부모관계로 연결시켜준다.

이때 7,9,11이 오버플로우가 나니 중앙값인 9를 분할해 처리한다.

당연하게도 9,15에 대해서 분할의 propagation이 일어날 수 있다.

차수에 대한 고민

결국에 높이를 최대한 낮춘다는 것이 B 트리의 성능 개선점이라고 보았을때, 차수(degree 혹은 order)를 잘 고르는 것이 중요하다.

좋은 차수를 고르는 방법은, 페이지 사이즈에 꽉 맞춰 들어가는 최대한 큰 사이즈의 노드를 고르는 것이다.

만약에 디스크에서 읽어오는 데이터베이스를 B 트리를 통해서 구성하려 한다면,
각각의 노드가 디스크 페이지 크기에 딱 맞는 사이즈를 골라야 할 것이다.

만약에 In-memory 데이터베이스를 구성하려 한다고 해보자.
그 말은 데이터는 메모리<->메모리 간 이동이 많을 것이고 중간에 L2 혹은 L3 캐시에 적재될때가 가장 빠른 접근을 할 수 있을때이다.

따라서 최대한 캐시 효율을 누릴 수 있게 L2나 L3 캐시의 라인 사이즈에 맞게끔, 즉 초과해서 캐시 바깥의 노드를 읽을 필요가 없게끔 구성해야한다.

모든 케이스에서 어떤 차수를 사용하는지 고르기 전에 먼저 하드웨어에 대한 스펙을 봐야할것이고,
내가 구현하려는 기능에서 B 트리가 어떤 역할을 하는지 알아야 할 것이다.

💡 Typically, you'd choose the order so that the resulting node is as large as possible
while still fitting into the block device page size.
If you're trying to build a B-tree for an on-disk database, you'd probably pick the order
such that each node fits into a single disk page,
thereby minimizing the number of disk reads and writes necessary to perform each operation.
If you wanted to build an in-memory B-tree, you'd likely pick either the L2 or L3 cache line sizes as your target
and try to fit as many keys as possible into a node without exceeding that size.
In either case, you'd have to look up the specs to determine what size to use.

강점

B 트리가 어떻게 균형을 유지하는지는 알았는데 실용적으로 어떤 강점이 있을까?
HashTable의 grow 된다는 점을 생각하지 않았을때, O(1) 이어서 더 유리한거 아닌가?

분명한 건 해시테이블을 이용할때는 하나의 조회에 있어서 O(1)이 소요되는것은 맞다.
하지만, 이 조회는 어디까지나 Hash Table.eqaul(key) 의 결과물이지 DB에서 쓰이는 range 와 같은 연산을 수행하지 못한다.

💡 실제로 회사에서 설계를 하면서 Redis를 사용하자는 의견이 나왔을때, 이 근거로 반대했다. range 연산이 필요한 곳에서는 HashTable에 기반한 redis는 전혀 이점을 누릴 수 없다.

즉, range 와 같은 연산을 수행할때는 계속된 참조가 필요한 것이다. 또, 해시테이블에서 특별한 구현체를 제외하고는 일반적으로 데이터가 정렬되어 있지 않다. 그렇기에 range 와 같은 연산이 매우 비효율적인것이다.

그럼 해시테이블과 비교했을때 강점에 대해서는 알았는데, 다른 트리랑 비교하면 어떨까?
다른 트리에서도 O(log n) 을 지원하는데 그건 왜 사용되지 않을까?

앞서 말한 높이의 상한에 있어서의 엄격함과 더불어서 B 트리의 노드들의 데이터는 배열속에서 순차적으로 저장되어 있고,
연속적으로 메모리에 저장되어 있음을 뜻한다. 즉, 공간지역성이 높다는 것이다.

다시 말해서, B 트리노드 끼리 참조로 이동할때는 디스크 액세스가 필연적이지만, 노드 내부의 데이터들은 배열과 같은 구조로 저장되어 있기 때문에 Sequential access에 유리하다. 이는 공간지역성에 의해서 캐시효율이 높음을 의미한다.

그렇기에 같은 O(log n) 의 시간복잡도를 가져도, 다른 트리보다 빠른 접근이 가능한 것이다.

다른 트리는 노드끼리 이동할때 자연스럽게 추가적인 메모리 접근이 필요하지만, B 트리에서 노드 안의 데이터 접근은 공간지역성을 충분히 누릴 수 있다는 것.

정리하자면,

1. 항상 정렬된 상태이기에 부등호 연산에 유리하다.
2. 참조 포인터가 적어 빠르게 메모리 접근이 가능하다.
3. 데이터 탐색뿐 아니라 삽입, 삭제에도 O(h) = O(log n)의 시간 복잡도를 가진다.

   #define order 3
   struct B_node {
       int order; /* number of children /
       B_node *child[order]; / children pointers /
       int key[order-1]; / keys */
   }

```

💡 그런데 이제 h에 밸런싱을 곁들인...

요즘 MongoDB에 대해서 빡세게 사용중인데, 정말 자료구조가 중요함을 새삼 느낀다.
백엔드 개발자가 DB 모르는건 말이 안되니까.

GIL은 Global Interpreter Lock의 약자이다.

Global이 붙으니 전역적이라는 의미이고, Lock을 사용하니 무언가를 제한한다는것은 알겠는데 Interpreter는 뭘까?
인터프리터에 대해서 제한을 건다는 것이 어떤 의미일까?

아래에서 쭉 알아보자.

Interpreter

짧게 얘기하면 Python 인터프리터는 코드를 한 줄씩 읽으면서 실행하는 프로그램이다.

이 방식때문에 인터프리터 언어가 느리단 얘기가 나오는 것이고, Java에서 이를 개선해서 등장한 방식이 JIT다.

이 인터프리터의 구현체는 여러가지가 있는데 대표적인 구현체가 C로 구현한 것이고, 이를 CPython이라고 한다.

이 글에서는 CPython 기준으로 설명할 것이다.

Python 위키 항목을 읽어보면 Non-CPython implementations에 Jython, IronPython은 GIL이 없고, PyPy는 CPython과 비슷한 GIL을 가지고 있다. 또 Cython에는 CIL이 존재하지만, with 키워드를 이용하여 잠시동안 해제가 가능하다고 한다.

대충 인터프리터가 어떤 의미인지는 알았으니 본론으로 들어가서 GIL에 대해서 알아보자.

GIL

Python 위키를 계속 참고해보면, 이렇게 정의하고 있다.

In CPython, the global interpreter lock, or GIL, is a mutex that protects access to Python objects, preventing multiple threads from executing Python bytecodes at once. The GIL prevents race conditions and ensures thread safety. A nice explanation of how the Python GIL helps in these areas can be found here. In short, this mutex is necessary mainly because CPython's memory management is not thread-safe.

중요한 부분 위주로 해석을 해보면,

GIL은 CPython에서 객체들에 대한 접근을 보호하는 뮤텍스(Mutex)로써, 여러개의 쓰레드가 동시에 파이썬의 바이트코드를 실행하는 것을 방지하는 역할이라는 것이다.

따라서 GIL은 경쟁 상태에 진입하는 것을 막아주고, 쓰레드 안전성을 보장한다.
또 간단하게 말해서, CPython의 메모리 관리가 쓰레드-안전이 아니기 때문에 뮤텍스가 필요하다는 것이다.

더 간단하게 말하면, Python 인터프리터에 대해서 전역적으로 잠금이 걸리기 때문에 한 시점에 오직 하나의 쓰레드만 인터프리터를 실행할 수 있다.

또 이어지는 설명에서 이렇게 설명을 한다.

In hindsight, the GIL is not ideal, since it prevents multithreaded CPython programs from taking full advantage of multiprocessor systems in certain situations.

해석해보자면 돌이켜보았을때 GIL은 멀티쓰레딩 CPython 프로그램이 특정 상황에서 멀티프로세서 시스템의 장점을 다 사용하지 못 하게끔 하기 때문에 GIL은 이상적이지 않다.

여기서 말하는 멀티프로세서 시스템의 장점은 멀티 쓰레딩 동작을 할때 여러 개의 쓰레드가 각각의 프로세서 상에서 병렬적으로 실행됨을 의미한다.

즉, GIL 때문에 CPython에서는 그러한 병렬적인 실행이 불가능하다는 것이다.

GIL의 필요성

괜히 멀티쓰레딩만 방해하고, GIL은 대체 왜 있는걸까? 이것에 대한 해답은 아까 말한 정의에 나와있다.

GIL is ... mutext that protects access to Python Objects.

Python에서 모든 것은 객체로 존재하고, CPython에서 각각의 객체들이 C 구조체를 통해 만들어진다는 것을 생각해보면, 수 많은 객체에 대응되는 수 많은 구조체가 있음을 알 수 있다.

그러면 자연스럽게 메모리 관리를 생각하게 된다.

Python에서 메모리 관리는 참조 횟수(reference count)를 이용해 GC(Garbage Collection)를 수행하는데, 이 참조 횟수가 C 구조체 안에 적혀 있다.

CPython의 소스코드를 확인해보면 이렇게 코드가 나와있다.

https://github.com/python/cpython/blob/main/Include/object.h

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

잘 보면 PyObject 구조체 안에 참조 횟수를 직접 저장하고 있다.

운영체제를 열심히 들으신 분이라면 바로 왜 위에서 언급한 경쟁 상태가 생길수 있는지 아실 것이다.

만약 CPython의 의도와는 정반대로 여러개의 쓰레드가 동시에 Python 인터프리터를 실행한다면,
참조 횟수에 병렬 프로그래밍의 고질적 문제 중 하나인 경쟁 상태가 발생하게 된다.

단순히 여기서 그치는 것이 아니라 아까 Python GC의 원리가 참조 횟수에 기반을 둔다는 점을 다시 생각한다면,
올바르지 않은(비정합적인) 참조 횟수를 기반으로 GC가 일어남으로써 GC가 의도한 바와는 다르게 동작할 수 있다는 것이다.

그렇다고 객체에 대해서 작업을 할때, 좀 더 좁게 말하자면 ob_refcnt에 대한 작업을 수행할때마다 별도의 뮤텍스를 이용해서 Lock을 얻고 해제한다면 비효율적이고, 프로그래머가 일일이 제어하기에는 부담이 가는 작업이다.

그렇기에 CPython에서는 한 쓰레드가 인터프리터를 실행 중일때는 다른 쓰레드가 실행하지 못하도록 인터프리터를 잠궈버렸다.
이렇게 된다면, 객체의 참조 횟수에 대한 경쟁 상태 역시 고려할 필요가 없어진다.

GIL을 선택한 이유에 대해서 조금 더 자세하게 알아보자면, 이 링크와 이 링크를 참조하면 된다.

짧게 얘기하자면, Python을 처음 만들때는 쓰레드라는 개념이 인기 있기 전이였고, 그 후에 쓰레드가 등장했을때 가장 현실적이고 쉬운 방법이 GIL이였다.

첨언하자면, 왜 GIL이 아닌 다른 해결책을 도입하지 않냐고 하자 Python의 개발자인 Guido van Rossum은 이렇게 말했다고 한다.

”단일 쓰레드 프로그램에서(그리고 I/O 바운드 멀티 쓰레드 프로그램) 성능이 저하되지 않는 GIL 해결책을 가지고 오면, 그 해결책을 기쁘게 받아들이겠다.”

이전편 : 가상 메모리

지역성

페이지 교체 알고리즘에 대해 언급하기 전에 먼저 지역성이라는 것에 대해서 알아야 한다.

• 시간 지역성 (Temporal Locality ) : 현재 참조된 메모리가 가까운 미래내에 참조될 가능성이 높음
  • loop,subroutine,stack
• 공간 지역성 (Spatial Locality) : 하나의 메모리가 참조되면 주변의 메모리가 참조될 가능성이 높음
  • Array 순회, 명령어의 순차실행

프로그램의 메모리 참조는 고도의 지역성을 가진다. 임의의 시간 Δt 내에 프로그램의 일부분만을 집중적으로 참조한다는 것이다.
이러한 지역성이 있기 때문에 적절한 페이지 교체 알고리즘이 중요하다.

왜 중요할까?

예를 들어서 주기적으로 두개의 페이지만 참조하는 로직이 있다고 해보자.

만약 그 두개의 페이지를 번갈아가면서 교체를 한다면, 페이지 폴트는 두 개의 페이지에 대해서 접근할때마다 계속 일어날 것이다.

이게 왜 위험하냐면, 불필요한 I/O 작업의 오버헤드도 있고, 그때마다 컨텍스트 스위칭이 계속 일어나기 때문이다.

페이지 교체 알고리즘

페이지 폴트가 났을때, 메모리에 빈공간이 있으면 올리면 되는 일이다. 물론 I/O가 들어가긴 하지만.

근데 만약 모든 메모리가 사용중이라면 교체될 페이지를 골라야하는데, 이걸 잘 고르는게 성능에 큰 영향을 미친다.

그러므로 원하는 것은 가장 낮은 페이지 폴트 확률이다. 모든 예시에서 [1,2,3,4,1,2,5,1,2,3,4,5] 의 순서로 페이지가 필요로 한다고 해보자.

일반적으로 프레임의 개수가 많으면, 페이지 폴트의 빈도도 줄어든다.

다만 정비례 하는것은 아니다. 이는 '벨라디의 모순'과 연관되어 있다.

FIFO

• 단순하게 페이지 교체를 할 때 가장 오래된 페이지를 선택해 교체한다.
  

  

• 근데 프레임이 3개일때와 4개일때를 비교해보면, 프레임이 늘었는데도 오히려 페이지 폴트가 증가했다. → 이것을 '벨라디의 모순'현상이라 한다.
• 즉 투입한 리소스와 효과가 비례하지 않음을 알 수 있고, 적절한 교체 알고리즘을 선택하는것이 중요함을 보인다.

Optimal

• 가장 오랫동안 사용되지 않을 (페이지 교체가 필요한 시점으로부터) 페이지를 선택한다.
  

  

• 가장 이상적인 알고리즘이기 때문에 가장 낮은 페이지 폴트를 보여준다.
• 그렇지만, 다음에 무엇을 사용할지 알 수 없기 때문에 구현이 어렵고 Optimal은 다른 알고리즘과의 성능비교의 기준으로 사용된다.
• 만약, 같은 행동을 반복하는 Bot의 형태고, 메모리 예측을 완벽하게 알 수 있다면 적용할 수 있다.

LRU

LRU는 Least Recently Used의 약자로 페이지 교체를 하는 시점에서
가장 덜 최근에 사용된것, 다시 말해 가장 오래전에 사용한 것 페이지를 선택해 교체하는 알고리즘이다.

• Optimal을 제외하고 굉장히 좋은 성능을 보이는데, 그 이유는 LRU가 Temporal Locality를 전제로 하고 있기 때문이다. 최근에 사용된것은 다시 참조될 가능성이 크니, 반대로 가장 오래전에 사용한것을 지우면서 페이지 교체 자체를 줄이려는 것이다.
  • 그런데 문제점은 LRU를 실제로 구현하는데에 있다.
    • 예를 들어 모든 페이지에 참조된 시간을 적어놓는다면, 페이지 테이블에 추가적인 메모리가 들것이고 (min heap으로 컷해도 될듯) 참조될때마다 이것을 계속 수정하는 오버헤드가 있다.
    • 만약 Linear하게 가장 오래전에 사용된 것을 찾는다고 해보자.
    • 이때의 시간복잡도는 n개의 페이지에 대해서 O(n)인데, 이 N 값이 의미하는 것은 프로세스의 개수이고 보통 너무 크다는데 있다.
  • 그러므로 커널에 구현하기는 시간적/공간적 오버헤드가 너무 크다. 따라서 근사치 모델이 필요하다.

LRU 근사

• 카운터 구현
  • 메모리 참조가 일어날때마다 CPU counter를 올리고, 페이지 A가 참조되면 페이지에 카운터를 덮어씌운다.
  • O(n)의 조회방식, 심지어 그때마다 메모리 액세스가 한번 더 일어남.
• 스택 구현
  • 페이지 번호로 Doubly Linked List 형태로 스택을 구현한다.
  • 페이지 A가 참조되면, A를 헤드로 옮긴다.
    • 이때 6번의 포인터 움직임이 필요하다.
  • 찾는데 드는 오버헤드는 없지만, 매번의 페이지 참조마다 6번의 메모리 액세스가 있다.
  • 교체가 일어나지 않아도 평소 오버헤드가 너무 크다.
• 두번째 기회 (Second Chance)
  • 기본적으로 FIFO다.
  • 페이지를 원형의 큐로 구성한다.
  • 페이지 테이블 내의 모든 페이지의 Ref bit를 초기값 0으로 할당하고, 참조가 되면 1로 바꾼다.
  • 참조비트가 0인 페이지를 찾으면, 그 페이지를 교체한다.
  • 만약 1이라면, 그 페이지는 0으로 바꾸고 한번 더 돈다. 한번의 기회를 더 주는것이다.
  • 한번 더 돌았을때도, 0이면 교환한다.
  • 그런데 모든 bit가 1인 경우를 생각해보면, FIFO의 알고리즘처럼 동작한다.

LFU

• 전제는 많이 사용되는 페이지는 더 많이 사용될 것이라는 전제
• 페이지에 참조된 횟수를 나타내는 카운터를 넣는다.
• 가장 카운터가 적은 페이지를 교체한다.
• 하지만 어떠한 페이지가 집중적으로 참조되다가 그 뒤에도 사용되지 않으면 어느정도까지 계속 머무르는 경향이 일어난다. 즉 전제와 어긋나게 된다.

MFU

• 전제는 카운터가 작은 페이지는 이제 막 들어왔고, 사용되지 않았다는 전제.
• 페이지에 참조된 횟수를 나타내는 카운터를 넣는다.
• 가장 카운터가 큰 페이지를 교체한다.
• Locality가 자주 변하는 시스템에서 유용하다.

프리페이징(Prepaging)

프로세스가 시작될때는 항상 initial page fault가 난다. 아무것도 안올라와 있기 때문에..

이것을 방지하기 위해서, 프로세스가 필요로 하는 페이지의 전부 혹은 일부를 참조되기전에 미리 메모리에 올리는것이다.

물론, 페이지가 사용되지 않으면 낭비가 있다.

Swap의 어떤 이점이 있는가?

• 장점
  • 가상 메모리를 만들고 유지하는데 도움이 된다. 그렇기에 더 많은 프로세스가 구동될 수 있다.
  • 실제 필요한 메모리용량만큼만 디스크에서 메모리로 올릴 수 있게 해주니, 물리메모리보다 더 큰 용량의 프로세스가 구동될 수 있다.
• 단점
  • 디스크에 접근하는 I/O → 디스크가 입출력을 할때 기다리지 않고 컨텍스트 스위칭

난 운영체제가 제일 재밌고 좋다. 최고👍

세마포어와 뮤텍스를 본격적으로 얘기하기에 앞서서 두 방법이 나오게 된 문제상황인 Race Condition과 Critical-Section을 먼저 소개한다.

Race condition

두 개 이상의 프로세스가 공유 데이터에 대해서 동시에 접근하고 조작하려하는 상황을 의미한다. 즉 Race라는 뜻 그대로 하나의 자원을 놓고 서로 경쟁하려는 상태이다.

이 공유된 데이터의 마지막 값은 어느 프로세스가 마지막으로 끝내는지에 따라 달려있다. 만약 interleaved execution(서로 번갈가면서 명령어 수행시) 데이터의 무결성이 침해받는다. → 불확실성

이것을 예방하기 위해서, 동시에 진행되는 프로세스는 반드시 동기화가 되어야 한다.

Critical-Section

이러한 문제를 임계구역(Critical-Section) 문제라고 한다. 임계구역이란 동일한 자원에 대해서 접근하는 영역을 의미한다.
해결하기 위해서는, 한 프로세스가 임계구역에 진입해 작업을 진행할때, 다른 프로세스들은 임계구역에 진입하는 것을 허락하지 않는것이다.

동기화를 해결하는 방법은 세가지 필수적인 조건을 맞춰야 한다.

1. 상호배제(Mutual Exclusion)
   • 어떠한 프로세스 혹은 스레드가 임계구역에서 작업을 진행하면, 다른 프로세스 혹은 스레드는 임계구역에 진입할 수 없다.
2. 진행(Progess)
   • 무기한으로 연기되는것을 막기 위해서 필요하다.
   • 만약, 다른 프로세스가 임계구역에서 작업을 하고 있지 않다면, 다른 진입을 원하는 프로세스의 진입은 지체되어서는 안된다.
3. 한계가 있는 대기 (Bounded Waiting)
   • 과도한 방지를 막기 위해서 필요하다.
   • 프로세스가 임계구역에 들어가기 위해서 요청하고 대기하는 시간은 한정되어 있어야 한다. 즉, 무기한적으로 대기되는것을 막기 위해서 필요하다.

문제에 대한 개괄적인 해결방식

두 개의 프로세스만 있다고 가정했을때, 임계구역에 진입가능했는지 체크하고, 임계구역을 빠져나올때는 진입가능성을 열어준다.
이 때 프로세스들은 동기화를 위한 데이터를 공유해야 한다.

뮤텍스

CS를 가진 스레드 혹은 프로세스들의 실행시간(Running Time)이 서로 겹치지 않고 각각 단독으로 실행될 수 있게끔 하는 기술이다.
일반적으로 한 프로세스에 의해 소유될 수 있는 Key 객체를 기반으로 작동되며, 이 객체를 소유한 스레드 혹은 프로세스만이 공유자원에 접근할 수 있다.

뮤텍스를 구현하는 방식에는 세가지 정도가 있는데, 모두 각각의 장단점이 존재한다.

Swap turn

• 첫번째 해결방식, Swap turn
  • 공유 변수 turn 을 두고, 서로 입장 가능한지 while로 체크한다.
  • 상호배제는 만족하지만, 진행도는 만족하지 못한다.
  • 두 프로세스는 무조건 in-turn 방식(왔다갔다)으로만 진입할 수 있다.
    • 만약 P0→P1 순서대로 들어갔다고 해보자. 이때 P1이 추가적인 진입을 원하더라도 P0의 차례이기 때문에 P1은 진입 할 수 없고, 진행도를 만족하지 못한다.
  • 즉, P1이 CS에 더 자주 접근해야하는 시스템이라고 해보자. 그럴때는 P0에 의존적이다. 두번 연속으로 CS 진입이 불가능하기 때문이다.Dekker's Algorithm
• // P0 **do { while (turn != 0) ; /* My turn? */ critical section turn = 1; /* Now it’s your turn */ remainder section } while (1);** // P1 **do { while (turn != 1) ; /* My turn? */ critical section turn = 0; /* Now it’s your turn */ remainder section } while (1);**
• 두번째 해결방식,데커 알고리즘
  • 만약 flag[i]==true 이면, Pi는 CS에 진입할 수 있다.
  • 첫번째 Swap turn 방식의 문제점인, 연속적인 진입이 불가능한 점을 해결한다.
  • 상호배제는 만족하지만, 진행도는 만족하지 못한다.
  • 만약 flag[i]=true 일때 컨텍스트 스위칭이 일어나면, Pj가 생각하기에 Pi가 들어가있다고 생각할것이다. 실제로는 그렇지 않은데.
    • 그러면 둘다 CS에 진입하지 못하고 기다려야 한다. 다음 컨텍스트 스위칭이 일어날때(선점식일때)까지 기다려야 한다.
    • flag[i]=true 로 바꾸는 저 부분이 유저 코드이기 때문에 중간에 인터럽트의 방해를 받을 수 있는 non-atomic이기 때문이다.Peterson's algorithm
• boolean flag[2] 초기에는 flag[i]=flag[j]=flase // 아무도 CS안에 있지 않다. // Pi do { flag[i] = true; /* Pretend I am in */ while (flag[j]) ; /* Is he also in? then wait*/ critical section flag [i] = false; /* I am out now*/ remainder section } while (1);
• 세번째 해결방식 (피터슨 알고리즘)
  • 1번과 2번의 공유 변수를 조합한 방식이다.
  • flag[j] 변수를 활용해서, swap-turn은 해결했다. 또 turn 문제를 이용해서 무조건 둘 중 하나는 CS에 들어갈 수 있음을 보장한다.
  • 상호배제,진행도,한정된 대기시간이라는 두 프로세스간의 해결책에서의 조건을 모두 만족한다.
  • 여러 프로세스로 확장가능하다. 하지만, while loop에서 CPU는 계속 체크해줘야 하는 busy waiting 문제가 여전히 남아있다. CPU cycle을 낭비하고 있는것이다.
• do { flag [i]= true; /* My intention is to enter …. */ turn = j; /* Set to his turn */ while (flag [j] and turn == j) ; /* wait only if …*/ critical section flag [i] = false; remainder section } while (1);

HW 지원

이렇게 해결책에도 여전히 문제점이 남아있기 때문에, 많은 시스템들은 하드웨어의 지원을 받는다.

• I/O가 없을때 CS 진입 후 선점적인 스케쥴링을 방지.
• 유니프로세서 시스템에선 인터럽트를 꺼버린다. 왜냐면 timeout이 있기 때문에. 하지만 대부분의 멀티프로세서 관점에서는 불리하다.
• 현대의 대부분의 시스템들은 원자적인(atomic) 하드웨어 명령어를 지원받는다.
  • TAS(test and set)
  • 
  • CAS(compare and swap)
    • 원자적으로 두 변수를 바꾼다.
    • 
    • key=true일때 lock이 false면, 진입해버린다. key=true인데 lock이 true면 계속 기다린다.
    • 이때 key는 lock과 달리 지역변수라 컨텍스트스위칭에 안전하다.

세마포어

뮤텍스와 비슷하게 동기화 기법이지만, 뮤텍스는 동시접근을 막으려는 측면이 강하고,
세마포어는 접근 순서 동기화에 조금 더 관련이 있다.

근본적으로 wait() 와 signal() 을 이용해서 제어를 하는 방식으로 세마포어를 여러개를 둠으로써 CS에 접근 가능한 task의 개수를 조절한다.
개수가 1개이면 binary semaphore로 mutex 처럼 작동을 한다.

P(s) // atmoic 해야함
func {
    while S<=0 do nothing;
    S--;
}
V(s) // atomic 해야함
func {
    S++;
}

이렇게 구현하면 세마포어를 이용한 뮤텍스가 된다.물론 busy waiting 문제가 여전히 발생을 한다.
즉, 특정 프로세스가 CS를 많이 차지하면 다른 프로세스는 P에서 계속 기다려야 한다.

이런 방식은 여전히 싱글프로세서 시스템에서 자원의 낭비라는 관점에서 치명적이다.

Block/Wakeup 방식

Block/Wakeup 방식은 busy waiting의 방식처럼 계속 기다리는 것이 아니라,
기다려야 할때만 대기줄에 줄만 세워놓고 block을 당하게 한다. 그 후 자리가 생기면, 즉 순서가 돌아오면 block 당한것들부터 차례로 깨운다.

typedef struct {
int value; /* semaphore */
struct process *L; /*process wait queue*/
} semaphore;

void P(S){
    S.value--;
    if (S.value<0){
        add this into S.L
        block()
    }
}

void V(S){
    S.value++;
    if S.value<=0 {
        remove P from S.L
        wakeup(P)
    }
}

이런식으로 세마포어에 링크드 리스트를 구현해서 세마포어를 완성한다.
process wait queue는 링크드 리스트로 프로세스의 PCB에 대한 정보를 가지고 있다.

• block() : 커널이 현재 프로세스를 중지시키고, 그 프로세스의 PCB를 세마포어 안에 있는 대기 큐에 넣는다.
• wakeup(p) : block되었던 프로세스 P의 작업을 다시 하게 한다.

이 때 S.value 의 절댓값은 현재 block 되어 있는 프로세스의 개수와 동일하다.

이전의 busy waiting과 block wakeup 방식을 비교해보자.

• CS 파트가 작으면
  • 기다리는데 드는 시간보다, block-wakeup하는데 드는 오버헤드가 더 클 수 있음.
• CS 파트가 길면
  • busy waiting이 길어지기 때문에 block-wakeup이 더 좋을수 있다.

임계영역이 유저 공유 데이터에서만 생길까?

1. 인터럽트 핸들러와 커널중간에 인터럽트가 와서 인터럽트 핸들러 내에서 count 값을 올리면, 그 뒤의 count 결과는 보장할 수 없다.
2. count 라는 커널 변수가 있다고 해보자. count 의 값을 올리는 과정은 load하고,increase하고,store를 하는 것인데,
3. 커널이 시스템 콜을 수행중일때, 컨텍스트 스위칭이 일어나면아래와 같은 상황일때 count의 값을 보장 할 수 있는가?이 문제에서 중요한 점은 프로세스간의 데이터 공유가 아니더라도 임계영역문제가 커널 단에서 분명히 발생할 수 있다는 점이다.
4. 유닉스에서는 이를 방지하기 위해서 커널이 작업을 수행하고 있다면(시스템 콜 처리) 선점식 스케쥴링이 일어나지 않는다.
5. 
6. 두 프로세스간은 공유되는 데이터가 없다하더라도, 시스템 콜을 수행할때 커널 데이터는 공유될 수 있다.
7. 멀티프로세서 시스템
   • 만약 두개의 CPU에서 한쪽은 count를 내리고, 한쪽은 카운트를 내린다고 해보자. 어느 값을 저장해야 하는가?
     • 각각의 CPU 이기 때문에 인터럽트로 통제할 수 없다.
   • 이럴때는 커널 자체가 하나의 큰 CS가 된다
     • 커널 자체 접근을 한 CPU만 할 수 있게 하거나
     • 커널내의 공유 변수들을 따로 세마포어로 둔다. 그러면, 큰 CS가 여러개의 나뉘어진 CS가 된다.

이진 세마포어 vs 카운팅 세마포어 비교

• 이진 세마포어
  • 정수값이 0과 1를 오가는 세마포어다. lock과 비슷하게 0은 사용중이고 1은 자유로운 상태이다.
  • 같은 시간 안에 오직 한개의 프로세스나 스레드가 CS에 접근하는 것을 허용한다.
  • CS안에 두개의 프로세스나 스레드가 동시접근이 불가능하기 때문에 상호배제는 만족한다.
  • 단지 정수적인 lock에 불과하니, 제한된 대기를 보장할수는 없다.즉, 기아가 발생할 수 있다.
• 카운팅 세마포어
  • 카운터라는 여러개의 값을 가질 수 있는 세마포어다.
  • 값의 범위는 0에서부터 N까지며, N은 CS로 입장을 허용하는 프로세스 혹은 스레드의 개수이다.
  • 한번에 둘 이상이 CS에 접근가능하기 때문에 상호배제를 보장하지는 않는다.
  • 기아현상을 피하기 위해서 큐를 구성하고 있는데, 이 큐가 있기 때문에 언젠가는 접근할 수 있다. 즉 제한된 대기 상태를 보장한다.
  • 특정하고 1보다 큰 개수의 한정된 자원을 배분할때 사용 될 수 있다.
    • 쓰레드 풀 (Thread Pool)
    • DBCP(Database Connection Pool)의 사례
    • 스프링에서의 사례

세마포어와 뮤텍스 차이점은?

• 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
• 예를 들어 Casting을 한다고 보면 (뮤텍스)세마포어 –> 가능하지만 (세마포어)뮤텍스 –> 불가능하다.
• 세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.
• 뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상을 동기화 할 수 있다. → 즉 임계영역에 접근가능한 수가 원천적으로 1개이냐 , 그 이상이냐의 차이다.

변기가 하나뿐인 화장실에서는
앞의 사람이 볼일을 마치고 나가야 다음 사람이 들어갈 수 있다.
이렇게 한번에 오직 하나만 처리할 수 있는 대상에 사용하는 것이 뮤텍스이다.

변기가 세개인 화장실에서는 동시에 세 사람이 볼일을 볼 수 있고
이 세 사람 중 아무나 한명이 나오면 다음 사람이 볼일을 볼 수 있다.
이렇게 동시에 제한된 수의 여러 처리가 가능하면 세마포어이다.

만약 변기 세개짜리 화장실의 각 변기에 대해 뮤텍스를 사용한다면
대기중인 사람은 각 변기 앞에 줄을 서는 것이고
이렇게 되면 옆 칸이 비어도 들어가지 못하게 된다.

만약 변기 세개를 묶어서 뮤텍스를 사용한다면
변기 수에 관계없이 무조건 한명만 사용할 수 있게 된다.

이 예에서 변기는 동기화 대상, 사람은 그 동기화 대상에 접근하는 쓰레드를 나타낸다.

뮤텍스와 세마포어의 목적은 특정 동기화 대상이 이미 특정 쓰레드에 의해 사용중일 경우
다른 쓰레드가 해당 동기화 대상에 접근하는 것을 제한하는 것으로 동일하지만
관리하는 동기화 대상이 몇개 인가에 따라 차이가 생기게 되는 것이다.

뮤텍스 vs 이진 세마포어

• 뮤텍스
  • 근본적으로 공유하는 자원에 대한 보호의 목적으로 쓰인다.
  • 뮤텍스는 lock을 잠근 task가 보유하는 관점이다.
  • 그렇기에 오직 그 task만이 해제할 수 있다. lock을 보유하지 않은 task가 접근할시 에러가 발생한다.
  • 일반적으로 이진 세마포어보다 더 가볍고 단순하기에 CS에 대한 보호의 용도로 더 많이 사용된다.
• 이진 세마포어
  • 신호를 주는(Signalling) 메커니즘에 더 가깝다. "나는 끝났으니, 이제 너의 작업을 해도 된다"
  • wait를 호출한 프로세스나 스레드가 아니여도 해제할 수 있다.
  • 물론 이것을 이용해서도 공유 자원을 보호하는데 사용할수는 있지만, task의 순서 동기화의 측면이 더 강하다.
  • 일반적으로 뮤텍스에 비해 오버헤드가 크다.

스핀락과 busy waiting의 사용처

do{
    acquire()
    CS
    release()
} while(true)

func acquire(){
    while(!availbale){
        //busy waiting}
    }
    available=false;
}

위의 방식은 available 이라는 변수를 둠으로써 락이 걸려있지 않다면 가져온뒤 CS로 진입하고 그렇지 않으면 계속 시도하는 방식을 쓰고 있다.

이럴때 acquire과 release는 atomic해야한다. 이런 방식의 가장 큰 문제점은 busy waiting을 해야한다는 점이다. 한 프로세스가 CS에 접근하고 다른 프로세스가 acquire 함수를 호출하면, 계속 acquire 안에서 계속적으로 루프를 돌아야 한다. 이런 방식의 구현을 스핀락(spinlock)이라고 하는데 다른 프로레스가 락이 풀리기를 기다리면서 계속 "돌고있기" 때문이다.

이러한 연속적인 루프는 싱글프로세서 시스템에서 명백한 문제인데, busy waiting 방식에서 다른 CPU가 더 잘 사용할 수 있는 자원을 대기하는데만 사용하고 있기 때문이다. 내가 기다리고 있다는 건 다시 말하면 나혼자만 CPU를 할당받고, 다른 프로세스(락을 풀어줄수 있는)는 돌아가고 있지 않기 때문에 기다릴 이유가 없는것이다.

그러면 스핀락을 사용하는 busy-waiting 방식은 전혀 쓸모가 없는것일까?
그렇지 않다.
이에 관해서 Operating System Concepts(공룡책)의 설명을 보자.

Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a
context switch may take considerable time. In certain circumstances on multicore systems, spinlocks are in fact the preferable choice for locking. If a lock is
to be held for a short duration, one thread can “spin” on one processing core while another thread performs its critical section on another core. On modern multicore computing systems, spinlocks are widely used in many operating systems.

야매로 번역을 해보자면,

하지만, 스핀락도 장점이 있다. 락이 빨리 풀릴거라고 예상되는 시스템에서 스핀락은 아주 유용하다.
컨텍스트 스위칭을 하는 비용보다 스핀락으로 busy waiting을 하는게 더 이득일 수 있기 때문이다.
이러한 장점때문에 멀티프로세서 시스템에서 한 쓰레드는 락에 대해서 계속 스핀하고, 다른 쓰레드는 다른 프로세서에서 임계영역에 대한 접근을 할 수 있다.

이게 무슨말이냐면, 원래 락이 빨리 풀리는 시스템에서는, 다른 프로세서에 있는 스레드가 락을 해제한다면, 내 프로세서에서는 컨텍스트 스위칭을 할 필요없이 바로 스핀락 하다가 들어가버리면 되기 때문이다.

만약, 내가 지금 spin 한다고 해서 바로 컨텍스트 스위칭을 해버린다면, 다른 프로세서가 락을 풀어도 내 프로세서는 다시 프로세스로 스케쥴링될때까지 기다리고, 컨텍스트 스위칭을 한 후 접근해야하기 때문이다.
즉, 원래 락이 빨리 풀리는 시스템에선 컨텍스트 스위칭의 비용이 spin lock의 대기시간의 비용보다 더 비쌀수 있기 때문이다.

TCP

신뢰성 있는 데이터 전송을 지원하는 연결 지향형 전송계층 프로토콜로 3 way handshake로 연결을 수립하고 , 4 way handshake로 연결을 해제한다.

• 혼잡 제어, 흐름 제어, 오류 제어등을 통해 신뢰성을 보장하지만 이것때문에 UDP와 비교해서 속도가 느리다.
• 또 SEQ 넘버와 ACK 넘버를 통해서 데이터 흐름 속에서 데이터들의 순서를 파악할 수 있기 때문에 신뢰성이 높아진다.
• 인터넷은 신뢰성을 갖추지 못하기 때문에 종단간의 신뢰성 있는 Byte Stream을 전송하도록 설계되었다.
• 연결을 유지하며 1:1 통신을 한다. 그렇기에 브로드캐스팅과 같은 시스템에선 적합하지 않다.
• 

TCP 연결 과정

TCP는 통신을 시작하기전에 연결 수립이 필수적이다. 이것을 통해서 상대방과의 세션을 수립하여 통신의 정확성을 획득할 수 있다.

클라이언트는 서버에 접속을 요청하고 서버는 요청을 수락하는 ack와 flag가 설정된 패킷을 클라이언트에게 발송한다.

1. 클라이언트가 서버에 접속을 요청하는 SYN(a)이 설정된 패킷을 보낸다. 이때 클라이언트는 SYN_SENT
2. 서버가 클라이언트의 요청인 SYN(a)를 받고 클라이언트에게 요청을 수락한다는 ACK(a+1)과 SYN(b)이 설정된 패킷을 보낸다. 서버는 SYN_RCVD 상태
3. 클라이언트는 서버의 수락 요청에 대한 응답인 ACK(a+1)과 SYN(b) 패킷을 받고, ACK(b+1)을 서버로 보내면 연결이 성립된다. 클라이언트는 ESTABLISHED 상태가 되고, 서버는 ACK을 받으면 ESTABLISHED 상태가 된다.

이 과정에서 SYN이나 ACK가 dropped 된다면, 재전송(retransmission)이 일어난다. 만약 3번 과정에 ACK가 drop된다면 그 다음에 데이터를 보낼때 ACK도 같이 담아서 보내면서(piggy-backing) 연결을 수립한다.

2 way handshake으로 부족한가?

부족하다. TCP는 양방향성 connection이기 때문에, 양쪽의 통신 수립이 필수적이다. 클라이언트와 서버가 있다고 했을때, 클라이언트가 서버에게 SYN을 보내고, 서버가 ACK와 SYN만 보낸다고 하면, 서버 입장에선 제대로 연결되었는지 확인이 불가능하다. 서버의 ACK와 SYN에 대한 클라이언트의 응답인 ACK가 필요하니 3 way handshaking을 해야한다.

💡 초기에 클라이언트에서 보내는 SYN 넘버는 ISN이라는 난수를 생성한다. 그 이유는 이전의 seq와 순차적인 정보를 전송하면, 서버가 판단하기에 이전 연결에서 보내는 정보라고 인식 할 수 있기 때문이다.

💡 SYN flooding attack 이라는 공격이 있는데, 간단히 서버에 대해서 SYN 패킷만 무수히 보내는 것을 의미한다. 이것이 왜 유용하냐면, SYN 패킷을 보내면, 서버는 연결을 수립하는 과정이라고 생각해서 SYN/ACK 패킷을 보내고 ACK를 기다리는 half-open 상태에 돌입한다. 이 상태에서 서버는 클라이언트에 대한 정보를 가지고 있어야 하기때문에, 접속자(혹은 접속을 시도하려는) 사람의 정보를 저장하는 Backlog Queue가 꽉 차게 되고(정상적으로 연결이 수립되면 삭제하지만 그렇지 않으니) Backlog Queue가 꽉 차게 되어서 다른 연결 요청 정보 저장이 불가능해서 정상 Client들이 연결을 수립할 수 없게 된다.

해결 방법으로는 Backlog Queue를 늘리는 것이 있지만 임시적인 해결책이다. 또 한가지 방법 중 하나는 방화벽에서 동일 클라이언트 IP에 대한 SYN 임계치를 설정해두는 방법이다.

TCP 연결 해제 과정

4 way handshake를 통해 TCP는 연결을 해제한다.

1. 클라이언트가 서버에게 연결을 종료하겠다는 FIN 패킷을 보낸다.
2. 서버는 클라이언트의 요청에 대한 응답으로 ACK 패킷을 보낸다.
3. 서버는 자신의 통신이 끝날때까지 기다린다 . CLOSE_WAIT 단계다. → Socket Hang UP 에러 발생가능
4. 처리해야할 통신이 모두 끝났다면 FIN 패킷을 보낸다.
5. 클라이언트가 FIN에 대한 응답으로 ACK 패킷을 보낸다.
6. 클라이언트의 ACK 패킷을 받은 서버는 소켓을 닫는다.
7. 클라이언트가 서버로부터 앚기 받지 않은 데이터가 있을 수 있으니 기다리는 과정을 거친다. TIME_WAIT 단계다.

💡 [에러 발생]
클라이언트에서 FIN 패킷 전송 후 ACK 패킷을 기다리는 FIN_WAIT1과 서버의 ACK 패킷을 받은 후 FIN 패킷을 기다리는 FIN_WAIT2 에러 발생으로 인해 Time out이 되면 스스로 연결을 종료한다.
그러나, CLOSE_WAIT은 Application이 close()를 적절하게 처리하지 못하면 CLOSE_WAIT 상태로 계속 기다리게 되어 Socket Hang Up 에러가 발생할 수 있다.

TCP 상태 다이어그램

• CLOSED, LISTEN, SYN-SENT, SYN-RECEIVED, ESTABLISHED, FIN-WAIT-1, FIN-WAIT-2, TIME-WAIT, CLOSING, CLOSE-WAIT, LAST-ACK 등 상태가 존재한다.
• CLOSED : 연결이 존재하지 않을 때
• LISTEN : 서버에서 SYN이 오는 것을 기다리는 상태.
• SYN-SENT: SYN을 보내고 ACK을 기다리는 상태(클라이언트)
• SYN-RCVD: SYN을 받고 SYN+ACK을 보낸상태(서버)
• ESTABLISHED: ACK을 받게 되면 서버 클라이언트 각각 이 상태로 들어섬
• FIN-WAIT-1: FIN을 클라이언트 쪽에서 보냈을 떄 ACK을 기다리는 상태
• FIN-WAIT-2: 첫번째 FIN에 대한 ACK을 받고 다음 FIN이 날라 올 때까지 기다리는 상태
• CLOSE-WAIT: 첫번째 FIN을 받고 ACK을 보낸 뒤 보낼 데이터들을 보내고 ACK을 받는 상태
• LAST-ACK: 전송이 완료되고 서버쪽에서는 FIN을 보내고 ACK을 기다리는 상태
• TIME-WAIT: FIN이 오고 ACK을 보내준 뒤 일정 시간동안 기다림
• CLOSING: 클라이언트 쪽은 TIME-WAIT이 종료 된 후, 서버쪽은 ACK이 도착한 후 종료된 상태를 의미한다.

TCP의 신뢰성을 위한 방법들

흐름 제어

송신측과 수신측의 데이터 처리 속도 차이를 해결하기 위한 기법이다.

수신측이 너무 지나치게 많은 패킷을 받지 않도록 조절하는것이 목적이고, 기본적인 개념은 수신측이 송신측에게 자신의 상태를 피드백한다는 것이다.

• 수신측이 송신측보다 데이터 속도가 빠르면 문제 없지만, 느릴때 문제가 생김.
• 수신측의 제한된 저장용량를 초과한 이후,즉 버퍼 오버 플로우 후에 도착하는 데이터는 손실될 가능성이 있으며, 손실되면 불필요한 응답과 데이터 전송이 빈번하게 오고감.
• 이를 해결하기 위해서 송신 측의 데이터 전송량을 수신측에 따라서 조절해야한다.
• 해결 방법
  • Stop and Wait : 매번 전송한 패킷에 대해 확인 응답을 받아야만 그 다음 패킷을 전송하는 방법. 그렇기에 비효율적이다.
    • Timeout을 설정하고, 그 Timeout 안에 ACK를 받지 못하면 실패한것으로 간주, 같은 프레임을 재전송한다.
    • 만약 이 Timeout이 너무 짧으면, ACK와 상관없이 계속 다시 보낼것이다.
  • Sliding Window : Stop and wait의 비효율성을 개선한 기법으로, 수신측에서 설정한 window 크기 만큼 송신측에서 확인 응답 없이 세그먼트를 전송할 수 있게하는 방식이다. (윈도우 크기 = 가장 최근 ACK로 응답한 프레임 수 - 이전에 ACK 프레임을 보낸 프레임 수)
    • 3 way handshaking을 할 때 송신측이 수신측의 window size에 맞게 자신의 window size를 조절한다. TCP 헤더안에 있으니..
    • 수신측에서 설정한 윈도우 크기만큼의 세그먼트를 확인 응답없이 보낼 수 있게 하여 동적으로 흐름을 제어하는 방식.
    • 송신측이 ACK 를 수신하지 않았더라도 여러개의 패킷들을 보낼 수 있다. (window size만큼 한번에 보내는방식)
    • 0,1,2,3,4,5,6가 윈도우 사이즈에 맞을때, 0,1을 보내면 윈도우는 2,3,4,5,6 으로 변한다.
    • ACK를 받게 된다면, 0,1이 정상적으로 수신되었음을 알게되고 윈도우는 옆으로 두칸 이동해(slide) 2,3,4,5,6,7,8로 변한다.
    • 

혼잡 제어

송신측의 데이터 전달과 네트워크의 데이터 처리 속도 차이를 해결하기 위한 기법.

• 송신측이 네트워크를 통해서 데이터를 전달할때, 라우터가 만약 데이터가 너무 몰려서(혼잡할때) 모든 데이터를 처리할 수 없게 되고,
• 송신 측은 다시 데이터를 보내고, 혼잡을 가중시켜서 오버플로우나 데이터 손실을 일으키게 된다.
• 그 과정에서 혼잡을 피하기 위해서 강제로 송신측의 데이터 전송속도를 줄이는데, 이것을 혼잡제어라 한다.
• 해결방법
  • AIMD (Additive Increase / Multiplicative Decrease)
    • 처음에는 패킷을 하나씩 보내고, 문제없이 도착하면 window size를 1씩 증가시켜가며(additive increase) 전송하는 방법
    • 만약 패킷 전송에 실패하거나 일정 시간(timeout)을 넘으면, window size를 절반으로 감소시킨다.
    • 이 방식은 fair 한데, 여러 개의 호스트가 네트워크름 공유할때, 처음 보내는 쪽이 1부터 보내기에 불리하지만 나중에는 평형한 상태를 맞추기 때문.
    • 하지만 초기에 1씩 보내기때문에 높은 대역폭을 충분히 사용하지 못하고 , 혼잡상황을 미리 감지 못해 혼잡이 일어나야지만 대역폭을 줄이는 방식.
    • 
  • Slow Start
    • AIMD 방식이 전송 속도를 올리는데 있어서 오래걸리는 단점(1씩 증가하기 때문에)이 있기에 이것을 개선하는 방식.
    • AIMD와 마찬가지로 1개의 패킷을 보내면서 시작하지만, 문제없이 도착하면 window size를 2배로 늘려준다.
    • 혼잡현상이 발생하면, window size를 1로 떨어트림.
    • 처음에는 네트워크에서 혼잡을 유발하는 window size를 알 수 없지만, 한번 혼잡현상이 발생하면 최대 수용량에 대한 유추가 가능해지기에, 그 window size의 절반까지는 이전처럼 2배로 증가하되, 그 이후부터는 완만하게 1씩 증가시키는 방식을 택함.
    • 
    • 임계값(ssthresh)단계에서 부터는 혼잡회피(Congestion Avoidance)를 사용한다.
  • 혼잡 회피 (Congestion Avoidance)
    • window size가 임계값에 도달한 이후부터는 조만간 혼잡이 발생해 데이터 손실 발생 확률이 커지기 때문에 조심스럽게 접근한다.
    • window size를 linear하게 1씩 증가시키는 방법을 사용.
    • 만약 혼잡이 발생했을 경우에, window size를 1로 줄이고, 임계값을 손실 발생했을때의 window size(W)의 절반인 W/2로 줄임.
  • Fast Retransmit (빠른 재전송)
    • 수신측은 순서대로 잘 도착한 마지막 패킷의 다음 번호를 ACK로 보내기 때문에, 중간에 손실이 있을시에는 중복된 ACK를 받게 된다.
    • 이것을 감지하면, 문제가 되는 순번의 패킷을(SR) 재전송 해줄수 있다.(혹은 문제 지점부터 싹 다시보내거나,GBN)
    • 3 ACK Duplicated, 즉 송신 측이 3번 이상 중복된 승인 번호를 받으면 혼잡이라고 인식한다.
    • 이때는 설정된 타임아웃이 지나지 않아도 해당 패킷을 재전송할 수 있다. (GBN or SR)
    • 이 방법으로 설정한 타임아웃 시간이 지나서야 대처하는 기존의 방법보다 낭비되는 시간을 줄일 수 있다.
  • Fast Recovery (빠른 회복)
    • TCP Tahoe : 초기 버전으로 타임아웃이 되거나 3 dup ack가 발생시 W를 1로 줄이고 slow start로 들어간다.
    • TCP Reno : 개선 버전이다. Tahoe가 무조건 W를 1로 줄이기에 대역폭을 온전히 사용 못할 수 있다. 그렇기에 3 Dup ACK는 조금 덜한 혼잡이라고 본다.
      • 3 Dup ACK : 현재 W의 절반으로 W를 줄이고, 1씩 linear하게 증가시킨다. 이때 임계점을 현재 W의 절반으로 설정한다.
      • Timeout : Tahoe와 마찬가지로 W를 1로 줄이고 slow start 한다. 임계점을 수정하지 않는다

오류 제어

기본적으로 TCP는 ARQ(Automatic Repeat Request), 재전송 기반 오류제어를 사용한다. 뭔가 오류가 생기면, 송신측이 수신측에게 해당 데이터를 다시 전송하는 방법이다.

그렇지만 이 재전송이라는 작업 자체가 했던 일을 다시 해야하는 비효율적인 방법이기 때문에, 이 재전송 과정을 최대한 줄일 수 있는 방법을 사용한다.

오류가 발생했다는것은 어떻게 알까?

• NACK(부정 응답) : 더 명확해보이지만, 수신측에서 ACK/NACK를 선택하는 추가적인 과정이 필요하다.
• ACK가 오지 않음 : 수신측이 아예 데이터를 받지 못해 ACK를 못 보내거나, 수신 측이 제대로 응답했지만 ACK가 유실(lose)되는 경우
• 중복된 ACK
  • 송신측이 SEQ 2를 가지는 데이터를 이미 보냈는데도, 수신 측에서 이번엔 2번을 보내달라고 하면 문제가 생겼음을 알 수 있다.
  • 중복된 ACK 한 두번으로는 판단하지 않고, 3번 정도 받았을때 오류로 판단. 그 이유는 TCP가 중복된 ACK를 받앗을때 패킷 로스인지, 세그먼트들의 순서가 reordering 되는건지 명확히 알 수 없기 때문에 3번까지 보는것. 순서가 뒤집히는 이유는 TCP 아래 계층에서 라우팅 하는 단계에서 다른 경로를 택할수도 있기 때문.
  • 

• 해결 방법
  • Stop and wait : 흐름 제어때도 나왔엇지만, 제대로 받았다는 응답이 올때까지 대기하고 그 다음 데이터를 보내는 방식.
    • 아주 기본적으로 오류 제어가 가능하다.
    • 
    • 하지만 흐름 제어에 sliding window 방법을 사용하다면 데이터를 연속적으로 보내기 위함인데, 이런 방식으로 오류 제어를 사용하면, 그 이점을 잃는다.
  • Go Back N (GBN)
    • 데이터를 연속적으로 보내다가, 어느 데이터부터 오류가 발생했는지 검사하는 방식.
    • 
    • 데이터를 연속적으로 보낸 후 한개의 ACK 혹은 NACK(오류 제어에선 설명의 간단함을 위해서 NACK로 사용)만으로 오류 파악이 가능하니, 슬라이딩 윈도우와 찰떡 (sliding window가 네트워크 대역폭의 이용률을 높이기 위해서 다른 프레임을 보내기전에 ACK를 요구하지 않는데 )
    • 만약 4번 데이터에서 에러를 감지하면, 수신측은 4번 데이터 이후 받은 모든 데이터를 폐기후 송신측에 알리는 방식이다.

수신자의 버퍼관리가 간단하다. 결국에 수신자도 상위 계층에 데이터를 전달하는 입장인데, 순서가 잘못 넘어온 데이터에 대해서(n+1만 오고, n은 오지 않음) 버퍼링을 할 필요가 없기 때문이다.

왜 데이터들을 다 폐기할까?

• 송신측은 5번까지 이미 전송을 했지만, 4번 데이터에서 에러가 났다는것을 알았기에 4번으로 되돌아가서(Go Back) 다시 전송해야 한다.
• ACK이 누적적(cumulative)이다.
• SR에 비해서 구현이 간단하지만, GBN의 특성상 같은 데이터가 계속 오갈 수 있으니 대역폭을 효율적으로 사용하지 못한다.
• 또 SR에 비해서 버퍼사이즈를 크게 잡을 수 있는데 시퀀스 넘버가 n비트일때 2^n-1개의 window 사이즈를 가질 수 있다. 왜 1을 빼냐면,
• • Selective Repeat (SR)
    • 오류가 난 데이터만 선택적인 재전송을 의미한다. GBN이 stop and wait에 비하면 효율적이지만, 에러가 발생하면 그 이후 정상적으로 받은 데이터를 모두 폐기처분하니, 재전송해야하는 비효율이 아직 있다.
    • 
    • 문제가 있는 데이터만 재전송하니 효율적이고 만능처럼 보이지만, 버퍼에 데이터들이 연속적이지 않다는 문제점이 있다.
    • 위 예시에서 데이터는 0,1,2,3,5 가 들어있다가 4를 재전송 받게 되면, 0,1,2,3,5,4 의 데이터가 들어있다.
    • 기존의 버퍼 안에서 데이터를 정렬할 수 없으니, 별도의 버퍼를 두어서 그 안에서 재정렬을 해줘야 한다.
    • GBN에 비해서 재전송이 적다는 점에서 효율적이지만, 추가적인 로직이 필요해서 복잡하고, 별도의 버퍼를 관리하는데 드는 비용이 있다.
    • ACK이 각각(individual)이다. (사진상으로는 안그런것처럼 보이지만)
    • 시퀀스 넘버가 n비트 일때 2^(n/2)개 이하의 window size로 제한되어 있다. 만약 2^(n/2)이라고 해보자. 그럼 뒤의 절반이 왔을때, 나머지 앞 절반이 안오면 뒤의 절반을 추가 버퍼에 가지고 있을텐데, 안 온 부분에 대해서

UDP

비연결형 서비스를 지원하는 전송계층 프로토콜이다. 사전에 연결 설정을 하지 않은 데이터그램 방식으로 데이터를 전달한다.
별도의 연결을 수립하지 않고 보내기 때문에, 각각의 패킷은 서로 다른 경로를 통해서 전송될 수 있고 각각은 독립적이고 그렇기에 패킷에 순서를 부여하진 않는다.

실제로 UDP 헤더 부분을 보면 아래와 같이 받는 포트와 보내는 포트 정보, UDP 길이, checksum으로만 구성되어 있는 8Byte 구조이다.

• UDP는 TCP와 달리 흐름제어, 오류제어 , 손상된 세그먼트에 대한 재전송을 하지 않는다.
• 오직 Checksum 필드를 통해서 최소한의 오류만 검출하기 때문에 신뢰성이 TCP에 비해서 낮은 편이지만, 이 때문에 TCP에 비해서 속도가 빠르다.
• 그렇기에 신뢰성 보다는 연속성이 중요한 서비스 , 예를 들어 실시간 서비스에서 자주 사용된다.
• TCP가 소켓을 open해서 통신하는 구조에 반해서 UDP는 오직 IP를 기반으로만 데이터를 전송한다.
• 흐름제어가 없기 때문에, 패킷이 제대로 전송되었는지, 오류가 없는지는 확인할 수 없다.

또 대표적으로 UDP를 사용하는 서비스가 DNS인데(모든 DNS가 UDP만 쓰는것은 아니다.) 아래 이유로 사용된다.

• 3way handshake와 같은 연결 수립 과정이 없기 때문에, 연결 설정에 드는 비용이 없어 빠르다.
• 연결 상태를 유지하는 TCP의 특성상 버퍼에 대한 정보,혼잡제어 정보, seq,ack 번호와 같은 정보를 저장해야하기에 UDP가 더 많은 클라이언트를 수용할 수 있다.
• DNS의 레코드는 일반적으로 작아서 UDP 세그먼트에 어울린다. (50-550 Byte)
• UDP가 신뢰성이 없긴 하지만, DNS가 더 상위계층(application layer)의 프로토콜이니 만약 응답이 오지 않는 경우에서는 다시 전송하도록 지시할 수 있다.

단, DNS의 응답의 크기가 512Byte 보다 크거나, zone transfer(DNS 레코드를 primary에서 secondary로 옮기는 작업)을 할때에는, 데이터의 정합성 검사를 위해서 TCP를 사용한다.

Stack

선형자료구조의 일종으로 LIFO의 특성을 가지고 있다. 가장 처음 들어간 원소가 가장 나중에 접근 가능 하고, 다시 말해서 호출 시에 가장 최근의 원소에 접근 할 수 있다. O(n)의 공간복잡도를 가진다.

링크드 리스트를 이용한 구현과 배열을 이용한(정확히는 Dynamic Array) 두가지 버전이 있다. 링크드 리스트는 일관적인 시간복잡도 O(1)를 보여주는 대신에 추가적인 메모리 사용량(Node 구조를 유지하는데 드는)과 메모리 할당에 추가적인 비용이 들 수 있다.

• 조회 : Top에 있는 원소를 조회할때는 O(1), 하지만 특정한 데이터를 찾고자 할때는 O(n)이다.
• 삽입 : 링크드 리스트를 이용한 구현에서는 단순히 기존의 Top 원소를 새 원소의 next 로 연결시켜주고 head 의 포인터에 새로운 원소를 연결시켜주면 되기 때문에 O(1)이다.
  배열을 이용한 구현에서도 특정 상황(Dynamic array의 팽창)을 제외하고는 O(1)이니 amoritezd\ O(1)이다.
• 삭제 : 링크드 리스트와 배열 모두 O(1)이다.

활용

• Stack Usage : JVM stack, 컴파일러에서 문법 체크(matching parentheses)

💡 프로그램의 함수 호출과 실행 순서는 아래와 같으니

스택프레임에 지역변수,매개변수,복귀주소등의 정보를 저장하고

함수의 실행이 끝나면 stack frame의 top을 pop한 후 복귀 주소로 복귀한다
가장 마지막에 호출된 함수를 가장 먼저 처리하고 복귀하는 후입선출의 구조를 처리하기 위해서 스택을 이용해서 관리한다.

Queue

선형자료구조로 FIFO의 특성을 가지고 있다. 먼저 들어간 원소가 가장 먼저 나오는 구조를 가지고 있다. O(n)의 공간복잡도를 가진다.

배열을 이용해 구현할때는 단순 배열보다 원형 구조 (circular queue)를 이용해서 구현한다. 혹은 링크드 리스트를 이용해서 구현할수 도 있는데 이때는 head 와 tail 에 대한 정보를 기록해야 한다.

• 조회 : 가장 끝에 있는 원소를 조회할때는 O(1).
• 삽입 : 링크드 리스트를 이용한 구현해서는 O(1). 동적 배열을 이용할때는 amoritezd\ O(1)이다. 원형 배열을 이용할때는 O(1).
• 삭제 : 모두 O(1).

스택과 큐 모두 배열을 이용하거나 링크드 리스트를 이용해 구현가능한데, 배열을 사용하는 경우에는 Dynamic array의 팽창을 고려해야하기 때문에 최악의 경우에는 느리지만, 전반적인 성능이 좋다. 반대로 링크드 리스트를 이용한 구현에서는 일관된 성능(O(1))을 보여주지만, 메모리 할당에 들어가는 추가적인 비용 때문에 런타임 성능이 낮을 수 있다.

활용

• Queue Usage : 스케쥴링,키보드 버퍼 → 두 개 모두 데이터 혹은 요청이 입력된 시간 순서대로 처리해야할 필요가 있을 경우에 사용한다.

문제들

• 두 개의 스택으로 큐를 구현하기
  1. in 에 A,B,C를 차례로 push. 그러면 in 에는 [A,B,C] 의 순서대로 데이터가 쌓일 것이다.
  2. 그 후 in 의 데이터를 각각 pop하면 C,B,A의 순서대로 나올것이다. 그 후 out 으로 push해보자. out : [C,B,A]
  3. 이후 out 의 원소들을 순서대로 pop하면 출력은 A,B,C가 나오고 out: []
• 생각보다 엄청 간단하다. 두 개의 스택을 각각 in과 out으로 구분하고, A,B,C 세개의 데이터가 입력으로 주어진다고 해보자. 출력은 A,B,C가 나와야 한다.
• 스택에서 min을 O(1)에 작동하도록 하기삽입
  1. 만약 스택이 비어있다면 x 를 삽입할때, minEle=x 로 할당한다.
  2. 그렇지 않다면, x 와 minEle 의 대소를 비교해야하는데 두가지 경우가 존재한다.
     1. x가 minEle 보다 크거나 같다면, 그냥 삽입한다.
     2. minEle 보다 작다면, 2x-minEle 를 스택에 삽입하고, minEle 를 x 로 초기화해준다.
     삭제
  3. y 가 min 보다 크거나 같으면, y 를 그냥 삭제한다. 여전히 최소값은 minEle 다. 그리고 그 값은 스택이 아닌 minELe 에 있다고 보는것이 맞다.
  4. y 가 minEle 보다 작을 경우에, minEle 를 2*minEle-y 로 변경해준다.minEle 보다 작은 원소가 삽입될때 우리는 2x-minEle 를 삽입하는데, 언제나 그것은 x 보다는 작다는 것이다.
  5. 원리
• 일단 최소 요소를 기록하는 minEle 변수를 stack 내부에 구현한다. 그 후 아래와 같은 사고방식대로 접근한다.

이전편 : 페이징

가상 메모리 (Virtual Memory)

가상 메모리는 논리적 메모리와 물리 메모리를 분리시켜, 프로세스 전체가 메모리내에 올라오지 않아도 실행가능하도록 하는 기법이다.

물론 프로그램이 실행되기 위해서는 메모리에 프로세스가 올라와야 하는것은 맞다. 하지만 특정 부분을 실행할때는 그 부분만 메모리 위에 올라와있어도 구동이 된다.

그렇기 때문에 논리적 주소공간은 실제 물리적 주소공간보다 훨씬 커도 된다. 왜냐면, 어차피 일부만 실행할때 필요하니까..
그럼 가장 핵심적인 기술은 프로세스를 실행할때, 필요한 메모리를 불러오고(swapped in) 필요하지 않은 부분은 내리는(swapped out) 과정이 필요하다.

가상메모리는 요구 페이징(Demand Paging) 이라는 기술로 구현된다.

특정 페이지에 대한 수요가 있을때, 즉 페이지에 대한 참조 요청이 들어왔을때 페이지를 메모리로 불러오는것이다.

다시 말해서 기존의 방법과는 다르게 가상 메모리 방식을 취하면, 시작할때부터 아무 메모리도 올라와있지 않아도 되고 필요할때만 불러오는 방식이다.

프로그램에서 사용되는 일부분만 메모리에 적재하는 가상 메모리를 통해서 아래와 같은것들이 가능하다.

• 시스템 라이브러리가 여러 프로세스 사이에 공유가 가능하다.
  프로세스 입장에서는 자신의 주소공간에 라이브러리가 올라와있다고 생각하지만, 실제로 라이브러리가 들어 있는 물리 메모리는 하나로 모든 프로세스에 공유되는 방식이다.
• 프로세스가 만들어질때 훨씬 더 효율적이다. 왜냐면, 실제로 프로세스를 만들때 필요한 모든 메모리를 할당해주는것이 아니라 필요할때만 주기 때문에 훨씬 가볍고 효율적이다.
  • 예를 들어서 fork 를 해서 프로세스를 생성한다고 해보자.
    이때 메모리를 직접 주는것이 아니라 기존의 메모리를 그대로 사용하게끔만 하고 프로세스는 이것을 독립적인 메모리 공간으로 인식한다.
• 실제 물리 메모리보다 더 큰 메모리를 요구하는 프로세스를 구동시킬 수 있다.
• 더 많은 프로세스가 구동이 가능하다.

요구 페이징 (Demand Paging)

페이지를 메모리에 올릴때 오직 그것이 필요할때만 수행하는것을 요구 페이징이라고 한다.
이것을 Lazy Swapper이라고도 하는것같다.(그 페이지 필요할때까지 절대 페이지를 메모리에 올리지 않는다)

• 적은 I/O : 전체 코드내에서 접근 안되는 주소공간은 가져올 필요가 없으니.
• 적은 메모리 사용량
• 빠른 응답 : 모든 페이지가 올라와있을 필요가 없으니 시작이 빠르다.
• 더 많은 유저 : "논리적 메모리 >> 물리적 메모리 " 이니 더 많은 프로세스를 수용가능하다.

만약에 특정 페이지가 필요하다고 하자. 그럼 그 페이지를 참조해야하는데, 아래와 같은 분기를 가지게 된다.

• 페이지에 대한 잘못된 참조 → 에러
• 메모리에 올라와있지 않음 → 데이터를 메모리에 적재함

그럼 이 올라와있지 않거나 올라와 있는것을 어떻게 구분할까?

논리주소와 물리주소를 변환할때 쓰였던 페이지 테이블을 이용해 페이지 테이블의 엔트리에 valid-bit를 부착해서 구분한다.

만약 valid-bit가

• True면
  • 현재 그 메모리를 가져온다.
• False면
  • Page Fault 발생
  • Page fault에 대한 처리를 하는데 일반적으로 페이지에 해당하는 프레임을 찾아서 로드시킨다.
    

    

    
    위 그림을 보면 B,D,E,F,G,H는 valid-bit가 invalid로 되어있다.
    만약 이때 B나 F와 같은 페이지를 참조하려 하면 Page Fault가 일어나는 것이다.

그럼 페이지 폴트 (Page Fault)가 뭘까?

페이지 폴트 (Page Fault)

페이지 폴트는 valid-bit가 invalid 인 곳에 MMU가 접근을 할때 HW trap을 발생시키면서 생긴다.

valid-bit가 invalid 하다는 것은 현재 메모리안에 내가 원하는 페이지가 존재하지 않음을 의미하므로, 원하는 페이지에 해당하는 프레임을 메모리로 가져온 후 프로그램이 계속 동작되게끔 해야한다.

이것을 페이지 폴트 핸들링이라고 한다.

페이지 폴트 핸들링

페이지 폴트는 결국에 인터럽트이기 때문에 ISR을 수행하는 처리과정을 거친다.

아래는 프로세스가 특정한 페이지를 참조하려고 했을때의 과정에 Page Fault 핸들링하는 과정이 추가된것이다.

1. 프로세스가 논리주소 (p,d) 를 가지고 메모리에 접근하려고 시도한다.
2. TLB를 먼저 확인해서 p에 해당하는 프레임 번호 f가 있는지 확인한다.
   1. TLB Hit,있다면 바로 메모리로 접근해서 (f,d)를 가져온다.
   2. TLB Miss, 없으니 이제 페이지 테이블을 참조해야 한다.
3. (p,d)를 가지고 페이지 테이블에 접근한다.
   1. 페이지 테이블에 p에 해당하는 f가 valid하면, 메모리에 접근해서 로드한다.
      • 이때 TLB 엔트리도 갱신된다.
   2. 만약 valid하지 않다면 현재 메모리에 올라와있지 않다는 것 → Page Fault
4. 운영체제가 메모리 접근할때의 주소를 확인한다.
   1. 잘못된 접근인가? 그러면 중지시켜야 한다.
   2. 아니라면 진행.
5. 물리 메모리에서 적절히 빈공간을 찾는다.
   1. 만약 이때 없다면, 적절하게 다른 프레임을 교체시켜야 한다. 이 교체의 방식이 매우 중요한데, 잘 골라야 다음에 replace가 일어날 확률을 줄인다.
6. 저장소에서 매치되는 페이지를 프레임에 올린다.
   1. 이때 프로세스는 wait 상태인데, 저장소 접근 자체가 I/O 이기 때문이다. 컨텍스트 스위칭 발생.
   2. I/O가 끝나면, 페이지 테이블 엔트리가 업데이트 되고, valid-bit가 valid로 설정된다. 이때도 컨텍스트 스위칭 발생할것같다.
   3. 프로세스는 레디큐로 옮겨진다. 그리고 일반적으로 스케쥴링되는것처럼 기다려야 한다.
7. CPU를 다시 할당받게 되면 페이지 폴트 트랩 처리가 끝난다.
8. 페이지 폴트를 촉발시켰던 명령어부터 다시 수행한다. (PC를 증가시키지 않기 때문에. 만약 PC 증가시키면 그 명령어는 강제로 건너띄는것이다.)

쓰레싱 (Threshing)

스레싱은 멀티프로그래밍 환경에서 페이지 폴트가 많이 일어나서 시스템이 아무런 작업도 하지 못하고 페이지를 메모리에서 가져오고 빼내는 과정만 반복해 CPU 이용률이 급격하게 떨어지는 현상이다.

더 최악인 점은 CPU 이용률이 떨어지니, 레디큐에 프로세스를 올리는 Long-term scheduler가 판단하기를
”CPU 이용률을 높이기 위해 멀티프로그래밍 정도를 올려야 함"이라고 판단하고 레디큐에 더 많은 프로세스를 올리면서 페이지폴트는 더 늘어간다.

• 여기서 멀티프로그래밍 정도가 느는것과 페이지폴트가 무슨상관일까?
  • 새로운 프로세스가 올라오면, Short-term scheduler가 새로운 프로세스에 CPU를 할당할 것이고, 이때는 initial page fault가 생기기 때문이다.

결국 Swap-in,Swap-out만을 하느라 바쁘고, 프로세스는 Block 되며, CPU는 대부분의 상황에서 IDLE 상태다.

I/O 작업만 하니까..

위의 그림처럼 MPD를 계속 올리다보니 스레싱이 발생하고, 그러면 더 MPD를 올리게되고 페이지폴트는 더 자주일어나면서 CPU 이용률은 급감한다.

결국에 자주 접근되는 페이지가 메모리에 올라와있지 않으면 이런 많은 페이지 폴트가 생기는데,
그렇기 때문에 각 프로세스가 필요로 하는 최소 프레임의 개수만큼은 보장을 해주어야 한다.

Array

논리적 저장순서와 물리적 저장순서가 일치한다. 다시 말해서 a[2] 와 다음에 오는 a[3] 는 물리적으로 연결되어 있다.
하지만, 하나의 Array의 크기가 너무 커 하나의 page(혹은 frame) 안에 다 못들어오는 경우에는 virtual adress는 연속적으로 이어져있지만, physical adress에서도 그렇다는 보장은 없다.

💡 하지만 physical adress와 virtual address에 관한 문제는 OS가 처리할 일이고 프로그래머에게 보이지 않는 추상계층이기에 우리가 깊게 생각할 필요는 없다고 생각한다.

또, 한번 사이즈가 정해지면 변할 수 없다. 이를 해결하는 방법이 Dynamic Array다.

• 조회 : 인덱스를 기반으로 한 접근이 가능하다. 인덱스를 알고 있다면 O(1)의 시간 내에 접근이 가능한데 , 이것을 Random Access라고 한다.
• 삽입 : Array의 특정 위치에 삽입을 할때는 원소를 넣고 끝나는 것이 아니라, 기존의 원소들을 shift 해주는 비용이 생기기 때문에 O(n)의 비용이 든다.
• 삭제 : 삽입과 마찬가지로 shift의 비용 때문에 O(n)이 소요된다. 만약 shift를 해주지 않는다면 삭제를 한 곳에 빈 공간이 생기게 될것이고, contiguous한 Array의 특성이 깨진다.

ArrayList

Java 기준으로 primitive만 저장 할 수 있는 Array와는 다르게 Object도 가능하다. ArrayList에 add를 사용하여 primitive한 데이터를 집어넣을때는 Auto-boxing이 사용된다. 또 제네릭이 사용 가능하다.

하지만 가장 큰 차이점은 ArrayList는 Dynamic Array라는 것이다. ArrayList는 내부적으로 Array와 사이즈 정보를 가지고 있다.

Array의 초기 사이즈가 고정되어 있고 늘어나지 않는것에 비해서, ArrayList는 add를 이용해서 원소를 삽입하다가 원소가 가득차게 되면, 내부적인 Array의 크기를 두배 혹은 1.5배 정도로 늘여서 기존의 원소들을 다 옮기게 된다.

이 과정에서의 시간 복잡도를 고민해보면, 기존 원소의 개수가 0개이고 사이즈가 n개라고 해보자.
이때 n번의 add를 할때까지 내부 Array는 가득차지 않고 각각의 삽입연산의 시간복잡도는 O(1)이다.

하지만 한번 더 add를 한다면 내부 Array를 두배로 늘리고 , 기존의 n개의 원소들을 모두 옮겨야 하니 O(n)의 시간이 소요된다.
n+1번의 add에 걸리는 시간복잡도가 O(1)*n+O(n)이니, 평균적인 시간 복잡도는 (O(1)*n+O(n))/(n+1)=O(1)이 되는 것이다.

이것을 분할 상환(Amortized Analysis)라고 한다.

LinkedList

LinkedList는 불연속적인 데이터들의 집합이다. LinkedList는 Node라고 불리는 내부구조들의 chain으로 구성되어 있는데 구조는 아래와 같다.

struct Node {
    Node* next;
    int val;
}

이처럼 Node는 원소와 그 다음 Node를 가리키는 포인터로 구성된다. 각각의 원소들은 오직 자기 다음에 오는 Node의 정보만을 가리키고 있는 것이다.(Singly Linked List 기준). 물론 next 라는 포인터를 하나 더 유지하는 메모리 사용량도 무시할 순 없다.

이것을 이용하여 삽입과 삭제를 O(1)만에 할 수 있다. 삽입을 할때는 단순히 next 만 교체하면 되고, 삭제 역시 마찬가지다.

• 조회 : k번째 원소를 찾기 위해서는 O(k)만큼의 시간이 소요된다.
• 삽입 : 동작 자체만으로는 O(1)이 걸리지만, 원하는 위치를 찾기 위해 LinkedList를 순회해야 하기 때문에 평균적으로 O(n)이 소요된다. 단, 맨 앞에 삽입하는 경우는 O(1)이 소요된다.
• 삭제 : 삽입과 동일. 맨 앞 삭제는 O(1), 맨 뒤 삭제는 tail 에 대한 정보가 있어도 O(n)이 걸리는데 그 이유는 마지막 원소를 가리키는 직전 원소를 찾기 위해 O(n)의 시간이 걸리기 때문이다.

그럼에도 LinkedList가 중요한 이유는 Tree 구조를 이해할때 필수적이기 때문이다.

Doubly Linked List

앞서 살펴본 Linked List는 일반적으로 Singly Linked List를 지칭하는 말이다. Singly Linked List는 아래처럼 다음 원소를 가리키는 next 포인터 하나만을 가지고 있다.

struct Node {
    Node* next;
    int val;
}

이에 반해서 Doubly Linked List는 next 포인터와 그 직전 원소를 가리키는 prev 포인터 역시 가지고 있는 아래와 같은 구조를 띈다.

struct Node {
    Node* next;
    Node* prev;
    int val;
}

또 일반 Singly Linked List와는 다르게 헤드 역시 Node로 이루어져 있다.

• 삽입 : new_node를 삽입하는 과정인데 살펴볼 필요가 있다.

  

  1. new_node의 prev가 before을 가리키게 한다.

  2. new_node의 next가 before의 next를 가리키게 한다.

  3. before의 next의 prev가 new_node를 가리키게 한다.

  4. before의 next가 new_node를 가리키게 한다.

     이 과정에서 순서에 유의해야 하는데, 1번은 언제 일어나도 상관이 없다.
     하지만 2번,3번의 경우 4번보다 먼저 일어나야 하는데, 그렇지 않으면 before의 next가 가리키는 node를 접근 할 방법이 없어지기 때문이다. 또 당연히 첫 순서로 실행되어서는 안된다.

• 삭제 : removed node를 삭제하려는 과정이다. removed의 이중 연결을 해제해주고, removed의 next와 prev를 서로 연결시켜준다.

  

  1. removed의 prev가 removed의 next를 가리키게 한다.

  2. removed의 next가 removed의 prev를 가리키게 한다.

     두 연산은 순서를 바꿔도 상관이 없다.

• 조회 : Doubly Linked List에는 prev 포인터가 있기 때문에, 최악의 경우 O(n)이 소모되었던 Singly Linked List와는 다르게 O(n/2)의 시간 안에 찾을 수 있다. 찾으려는 원소의 인덱스의 범위에 따라 end에서 prev 포인터를 이용해서 돌아가거나, head에서 next 포인터를 이용해 찾는 방법이다. 또, 직전 원소를 찾는 before도 쉽게 구현 할 수 있다.

이런 장점을 이용해서 연속적인 탐색과 접근에 유리하지만 , 구현이 상대적으로 복잡하고 prev 포인터를 유지해야 하기 때문에 메모리 사용량이 2배 정도 증가한다.

하지만 사용성때문에 플레이리스트, 되돌리기와 같은 기능에 사용되는 자료구조다.

Array vs LinkedList

일반론적인 얘기에서 조회는 Random Access를 지원하는 Array가 O(1)의 시간복잡도를 가지고 있어서 LinkedList보다는 빠르다.

삽입과 삭제는 모두 LinkedList가 빠르다고 하지만 이유에 대해서 조금 더 면밀하게 살펴볼 필요가 있다.

빠르다 라고 하는 것은 삽입과 삭제 그 자체에 주목하는 부분이다.
만약 바꿔야 할(삽입 혹은 삭제) 위치를 정확히 아는 상태에서는 Array보다 LinkedList가 항상 빠르다. 단순히 next 포인터만 변경해주면 되기 때문이다.

평균적인 경우에서는 Linkedlist는 O(n/2)개의 원소들을 살펴보아야 하고, Array도 동일한 원소의 개수들을 shift 해줘야하니 비슷하다.

그렇기 때문에 Usage에 따라 두 자료구조를 적절히 아래와 같이 선택해야 한다.

• 삽입과 삭제가 빈번하게 일어나는 경우 → LinkedList
• 데이터에 대한 접근(Access)가 빈번하게 일어나는 경우 → Array

Cache

또 한가지 더 깊게 생각해보자면, 캐싱과 연관이 있다. 정확히 말하면 Spatial Locality.

CPU가 일을 처리할때는 메모리에서 필요한 데이터를 로드하고, 일부를 캐싱한다. 그 캐시 안에 들어있는 요소들을 레지스터로 가져와서 일을 처리하는데, 이 과정에서 차이가 발생한다.

LinkedList는 데이터들의 주솟값들이 서로 연속적이지 않기 때문에, loop를 돌때 (Iterator든 뭐든) 매번 다음 메모리 주소를 찾아야 하고 , CPU가 메모리에 계속적으로 접근해서 로드하는 과정이 생길 수 있다.

불필요한 오버헤드가 생기는 것이다.

반대로 배열은 연결된 데이터 구조를 가지기 때문에, 특정 영역에 존재하는 데이터들을 한번에 로드해와서 bulk들을 캐싱한다.
그렇기에 loop를 돌때도 Array가 매우 크지 않으면 이미 캐시되어 있는 리소스들을 사용할 수 있게 되고 LinkedList와 비교했을 때 상대적으로 적은 메모리 접근이 일어나니 더 빠르다.

운영체제의 핵심 부분인 하나인 메모리 관리에 대해서 적겠다.

대략 3편으로 구성되며 페이징,가상메모리,페이지 교체 알고리즘 순이다.

MMU

CPU는 프로세스를 구동할 때 PC를 참조해서 다음 명령어를 메모리에서 가져온다. 명령어를 참고해 필요한 데이터가 있으면 메모리에서 가져오는데 이때 주소체계가 서로 다르다.

아래의 그림처럼 base와 limit 레지스터 안에 있는 값들을 조합해서 CPU가 사용하는 주소(논리 주소)와 실제 메모리 주소(물리 주소)를 구할 수 있다.

그러면 왜 두 주소를 구분하였을까?

가장 큰 이유는 보안이다. Limit 레지스터를 둠으로써, P1이 P2의 메모리 영역을 참조하는 Memory Illegal Access를 방지하는 Protection의 기능을 수행한다.

MMU는 Memory-Management Unit의 약자로 위에서 말한 논리주소를 물리주소로 대응시켜주는 HW 장치이다.

MMU 방식에서는 relocation 레지스터가 존재하는데, 프로세스가 메모리 주소를 만들때마다 relocation 레지스터 안의 값이 더해지고 이를 통해서 메모리에 접근할 수 있게 된다.

base 레지스터와 역할이 동일하다고 생각하면 된다.

연속적인 할당(Contiguous Allocation)

메모리에 프로그램을 연속적으로 할당하는 방법이다. 간단하게 말해서 아래에서부터 차례차례 채워가는 방식. 메모리를 연속적으로 사용하기 때문에 간단한 MMU만으로 구현할 수 있다.

일반적으로 커널은 낮은 메모리주소에 배치되고, 유저 프로세스는 높아지는 메모리 주소를 가진다.

또 커널을 제외한 메모리 영역을 하나로 보는 방식과 여러개의 파티션으로 보는 방식이 있다.

여러개의 파티션으로 할당하는 방법에서는 다수의 고정된 크기의 파티션으로 나누어져 있고, 2개 이상의 파티션에 할당할때는 합병(merge)해서 할당한다.

그런데 그림에서 마지막 단계를 잘보면 P10과 P2 사이의 빈 공간이 보인다.
이것을 Hole이라고 하는데, 단순히 말해서 할당가능한 메모리의 영역이다.

이 Hole은 크기가 커서 프로세스를 할당받을 정도가 되면 문제가 되지 않지만, 그 크기가 작을때는 파편화 문제가 생길 수 있다.

파편화 (Fragmentation)

파편화 혹은 단편화는 메모리 내에서 할당가능한 영역이 존재하지만, 할당이 불가능한 상태를 의미한다. 두가지 종류가 있다.

• 내부 파편화

  • 할당을 하는 단위가 존재할때 생긴다.

  • 프로그램이 필요한 사이즈보다 더 큰 메모리가 할당되면서 파티션 내부적으로 메모리 공간이 낭비되는 상황

    

• 외부 파편화

  • 남아있는 메모리가 흩어져 있어서 총 메모리 양은 할당할 수 있을 정도인데 실제론 할당할 수 없을때

    

  • 내부 파편화와는 다르게 할당을 하는 단위가 존재해도 생기고, 존재하지 않아도 생길 수 있다.

    • 존재할때는 왜 생길까?
      • B프로세스의 다음 메모리 공간을 보자.
        원래는 프로세스가 들어갈 자리인데도 그 프로세스가 끝나고 D가 끝나지 않았다면 C는 들어가지 못한다.

  • 즉, 사용가능한 메모리 영역은 있는데, 연속적이지 않은것이다.

  • 압축(compaction) 기법을 통해서 해결 할 수 있는데, 오버헤드가 크다. (JVM GC의 mark-and-compaction 생각해보자.)

세그멘테이션 (Segmentation)

페이징 방법에서는 가상 메모리를 서로 같은 크기로 분할했지만, 세그먼테이션 방법에서는 서로 크기가 다른 논리적 단위인 세그먼트로 분할한다.

세그먼트들의 크기가 각각 다르기 때문에(code를 위한것,데이터를 위한것...) 필요할때마다 빈 공간을 찾아서 해결한다.

프로세스가 딱 필요한 만큼만 메모리를 배정해주기 때문에 내부파편화 문제는 없지만, 외부 파편화 문제는 존재한다.

• 아래 그림을 보자. (a)번 상황에서 Segement 1이 빠지고 S7이 들어오면, S7이 더 작기 때문에 공간에는 맞지만 S2와 S7 사이에 빈공간이 생긴다.!
  

  

• 비슷한 상황이 S4가 나가고 S5가 들어오는 상황에서도 생기고 3과 6의 상황에서도 생긴다.
  이런 빈 공간이 생기기 때문에 세그멘테이션은 외부파편화 문제가 여전히 존재한다.

페이징 (Paging)

논리적 메모리 주소 공간이 물리적인 메모리 공간에서 비연속적으로 배치하게끔 허용하는 기법을 의미한다.

물리메모리를 고정된 사이즈의 프레임(Frame) 이라는 크기로 나누고, 동일한 사이즈로 논리메모리를 페이지(Page) 로 나눈다.

즉 , 프로세스가 일정량의 페이지를 요구하면, 같은 양의 충분한 프레임을 찾아서 매치시켜준다. 그렇기 때문에 허용가능한 프레임을 추적해야한다.

또 페이지와 매치되는 프레임을 찾기 위해 페이지 테이블을 관리해야 한다.

하지만 외부 파편화 문제는 해결할 수 있지만(비연속적으로 배치하니) 내부 파편화 문제는 여전히 존재한다.

위의 그림처럼 프로세스의 메모리주소를 같은 크기의 페이지로 나누고 물리 메모리의 프레임과 대응시킨다.

이 대응이라는 것은 논리주소를 단순히 구성할 순 없고, 일반적으로 2^m바이트의 논리 메모리 사이즈와 페이지 사이즈가 2^n바이트일때, 아래와 같이 m 비트를 (m-n)비트,n비트로 구성한다.

페이지 오프셋은 2^n바이트의 페이지 중에서 현재 몇번째 바이트를 지시하는지 알려주고, m-n비트의 페이지 넘버는 페이지 테이블 내에서 몇번째 프레임을 가리키는데 사용된다.

이러한 페이징 방식에서 논리주소 변환은 위의 구조를 가진다.
잘보면 offset인 d는 주소 변환에는 안쓰이고 바로 물리주소에 대응시켜버린다.
반대로 p인 페이지 넘버는 page table내부에서 frame number와 매치시키기 위해서 사용되는데 p→f 의 역할을 하드웨어의 지원을 받아서 수행된다.

페이지 테이블

페이지 번호와 프레임 넘버를 매치시켜주는 구조를 페이지 테이블(Page Table)이라고 하는데 , 메모리 안에 저장된다.

그렇기때문에 실제로 어떠한 메모리에 접근할때는 두 번의 메모리 접근이 필요하다.

1. 메모리에 있는 페이지 테이블 접근
2. 변환된 물리적 주소에 가서 메모리 접근

이 메모리 접근은 꽤 비용이 큰 작업이기 때문에 TLB라는 새로운 하드웨어 캐시가 쓰인다.

TLB

TLB는 Associative Memory라고도 불리는 하드웨어 캐시인데, 논리주소를 물리주소로 변환할때 메모리접근을 줄이기 위해서 사용된다.

페이지테이블과 유사하게 페이지 번호와 프레임 번호가 대응되게 기록되어 있다.
다만, 모든 페이지 번호가 TLB 안에 있는 것은 아니다.

물론 이 레코드들을 다 순차적으로 읽는것은 아니고, 하드웨어의 지원을 받아 병렬적으로 읽기 때문에 매우 빠르다.

이에 관해서 좋은 답변이 있어서 공유한다. How does a TLB lookup compare all keys simultaneously?

요악하자면 단일 CPU 안에서라도 파이프라이닝 기법을 이용해서 병렬적으로 읽는다는 것. (컴퓨터구조 수업을 참고하자.)

TLB가 도입되면서 (p,d)의 논리주소를 물리적 주소로 변환하는 방법이 변했다.

1. TLB를 먼저 확인해서 p에 해당하는 프레임 번호가 있는지 찾는다.
   1. 있다면, 프레임 넘버 f와 오프셋 d를 가지고 바로 메모리에 접근한다.
   2. 없다면 2번으로 간다.
2. 메모리에 있는 페이지 테이블을 확인한다.
3. 페이지 테이블에 적힌 프레임 넘버 f와 오프셋 d를 가지고 메모리에 접근한다.
4. 가장 최근에 사용된 (p,d)→(f,d) 를 TLB에 저장한다.

1,4번 때문에 TLB는 논리적→물리적 주소 변환에서 캐시 역할을 수행한다고 볼 수 있다.

💡 다만 일반적인 CPU 캐시(L1,L2...)와는 목적 자체가 다르다. TLB는 주소 변환 속도 향상을 위한것이어서 MMU에 의한 주소변환시에 생기고 , CPU 캐시는 데이터를 가져올때 메인 메모리 접근을 줄이기 위하여 메인 메모리 접근시점에 참조된다.
물론 둘 다 메인 메모리 접근을 줄이기 위함이라는 점은 비슷하다.

A cache stores a memory location temporarily while a TLB is like a cache that stores address translation (virtual to physical address)

단 이 TLB도 컨텍스트 스위칭이 일어날때 비워진다.

그 이유는 새로운 프로세스가 CPU를 할당받게 되면, 다른 메모리 주소공간을 참조할것이기 때문이다.
이때문에 컨텍스트 스위칭 직후 TLB 미스가 연속적으로 생긴다.

페이지 사이즈

페이지의 크기에 대해서도 얘기해보자.
페이지의 크기를 정하면, 페이지 테이블의 크기도 결정되므로 적절한 페이지 크기 선정이 중요하다.

여기서 말하는 적절한의 기준이 뭘까?

만약 모든 프로세스가 4K만 요구하는데 페이지 사이즈가 8K면?

모든 페이지에 4K만큼의 내부 파편화가 생기는 것이다.

• 만약 페이지 사이즈가 크다면?

  • 페이지 테이블의 크기는 줄어든다.
  • 한 개의 페이지 테이블안에 들어있는 데이터가 많으니 공간 지역성을 잘 만족한다.
  • 한 번에 많은 양의 데이터를 디스크에서 가져오니 I/O 작업이 줄어든다.
  • 내부 파편화 문제가 증가한다.
  • 필요하지 않은 데이터가 메모리에 올라올 수 있다.

• 만약 페이지 사이즈를 작다면?

  • 내부 파편화 문제가 감소한다.
  • 필요한 데이터만 메모리에 가져올 수 있다.
  • 공간 지역성을 지키기 어려워 페이지 폴트 발생 확률이 늘어난다.
  • 페이지 테이블 내의 엔트리가 많아지니 페이지 테이블의 크기가 커진다. 오버헤드가 발생한다.

따라서 여러가지 트레이드 오프를 고려해서 페이지의 크기를 정하는 것이 중요한데,
일반적으로 메모리 크기도 커지고, 프로세스 크기도 커져서 페이지 사이즈의 크기도 커지고 있다.

리눅스 16.04 기준 아래와 같은 명령어로 페이지 사이즈를 알 수 있는데 4096으로 4K다.

$ getconf PAGESIZE
> 4096

Java 7의 JVM

기존의 Permanent 영역에는 아래와 같은 정보들이 저장되었다.

• Class의 메타데이터 (바이트코드 포함)
• Method의 메타데이터
• static 객체, static 상수
• 상수화된 String Object
• Class와 관련된 배열 객체 메타데이터
• JVM 내부적인 객체들과 JIT의 최적화 정보

OOM 문제점

이런 많은것들이 PermG안에 있다보니 , String Constant Pool, static object, Class 메타 데이터들이 쌓여 OOM이 발생하곤 했다. PermG는 시작할때부터 크게 잡지 않는 이상 리사이징이 되지 않아 그런 문제가 발생하곤 했다. 좋은 글

Java 8의 JVM

구체적인 변경점

기존의 PermG 영역에 있던 정보들은 이렇게 변경되었다.

• Class의 메타데이터 (바이트코드 포함) → MetaSpace로 이동
• Method의 메타데이터 → MetaSpace로 이동
• static 객체,static 변수 (class variable) → Heap으로 이동,
• 상수화된 String Object → Heap으로 이동
• Class와 관련된 배열 객체 메타데이터 → Metaspace로 이동
• JVM 내부적인 객체들과 JIT의 최적화 정보 → Metaspace로 이동

위와 같이 변경하면서 , 기존 PermG에 있던 Static Object가 Heap 영역으로 옮겨져서 GC의 대상이 될 수 있게 하였다.

• 장점
  • Native(Metaspace)로 많은 부분을 옮기면서, Native 영역은 JVM에 의해서 크기가 강제되지 않고, 프로세스가 이용할 수 있는 메모리 자원을 최대로 활용할 수 있게 되었다.

💡 Metaspace 영역은 Heap이 아닌 Native 메모리 영역안에 있다. Heap 영역은 JVM이 관리하고 Native 영역은 OS레벨에서 관리해 자동으로 크기를 조절하고, Metaspace가 Native 메모리를 사용함으로써 개발자는 메모리에서의 영역확보의 상한을 크게 인식할 필요가 없게 되었다. 이것이 Java 8에서 Metaspace가 도입된 이유이다.