이번 글에서는 분명 시간 복잡도도 만족하고, 분석도 잘 한 것 같은데 특정 테케에서 아예 오답이 나와 왜일까 고민해본 과정을 적어 내려가보려고 한다.

🔴 첫 번째 시도

function countDifferentBits(target, compare) {
  let t = target.toString(2);
  const c = compare.toString(2);

  t = '0'.repeat(c.length - t.length) + t;

  let count = 0;
  for (let i = 0; i < t.length; i++) {
    if (t[i] !== c[i]) count++;
  }

  return count;
}

function solution(numbers) {
  return numbers.map((number) => {
    for (let i = number + 1; ; i++) {
      const differentCount = countDifferentBits(number, i);
      if (differentCount <= 2) return i;
      else continue;
    }
  });
}

브루트포스 방식으로 일일이 계산해주었다. number에서 숫자를 하나씩 증가시키면서 비트가 다를 때마다 count해주고, 이 개수가 2개 이하이면 return하는 방식. numbers 길이가 최대 100,000개이므로 당연히 시간 초과로 탈락!

🔴 두 번째 시도

시간 초과가 날 것을 알았지만 완탐 밖에 떠오르지 않아서 지피티에게 도움 요청. Bit Masking + Greedy 알고리즘을 제시해주었다.

문제를 분석해보면 비트가 2개 이하로 다르면서 가장 작은 수를 찾는 것이기 때문에, 어떻게 하면 _비트를 2개 이하로 조작_할까 고민해보면 좋을 것 같다.

1. 짝수일 경우

• 짝수는 항상 맨 뒤 비트가 0으로 끝난다. (...0)

• 따라서 +1을 할 경우, 비트가 1개만 변경되면서 가장 작은 값을 만족한다. f(x) = x + 1

  2. 홀수일 경우

• 홀수는 맨 뒤 비트가 1로 끝난다. (...1)

• 홀수의 경우 가장 작은 0을 찾아서 1로 바꾸어준다.

  • 예: 7 (0111) -> 15 (1111)

• 이후, 바꾸어준 자리 바로 오른쪽의 1을 0으로 변경하면 최소 변화 조건을 만족하면서 가장 작은 수가 된다.

  • 예: 7 (0111) -> 15 (1111) - > 11 (1011)

    3. 최종 코드

    function solution(numbers) {
    return numbers.map(x => {
      if (x % 2 === 0) return x + 1;
    
      let bit = 1;
      while ((x & bit) !== 0) bit <<= 1;
    
      return x + bit - (bit >> 1);
    });
    }

    3.1. while ((x & bit) !== 0) bit <<= 1;

• x & bit: x의 특정 비트가 1인지 확인하는 연산

• <<, >>: 비트를 해당 방향(<, >)으로 이동시키는 연산

• <<=, >>=: 비트를 해당 방향(<, >)으로 이동시키고, 이를 비트에 할당한다.

  bit = 1;   // 0001  (1의 자리)
  x & bit = 1  (0이 아님, 계속 이동)
  

bit <<= 1 // 0010 (2의 자리) x & bit = 2 (0이 아님, 계속 이동)

bit <<= 1 // 0100 (3의 자리) x & bit = 4 (0이 아님, 계속 이동)

bit <<= 1 // 1000 (4의 자리) x & bit = 0 (4의 자리 비트가 0임. 종료)

결과적으로 `while ((x & bit) !== 0) bit <<= 1;`는 `bit`를 `0001` → `0010` → `0100` → `1000`으로 이동하면서 `0`을 찾게 된다.
### 3.2. `x + bit - (bit >> 1);`
- `x + bit`는 처음 `0`이 나온 자리를 `1`로 변경한다.
    - `x = 7 (0111)`
    - `bit = 8 (1000)`
    - `x + bit = 1111`
- `bit >> 1`는 처음 `0`이 나온 자리의 바로 오른쪽 비트를 `0`으로 변경한다.
    - `bit >> 1 = 0100`
    - `x + bit - (bit >> 1) = 1111 - 0100 = 1011`
## 4. 그런데..
![](https://velog.velcdn.com/images/jayy_19/post/e142f1bf-1fb9-48db-8d1e-a0958dad7327/image.png)

테케 10, 11에서 계속 오답이 뜨는 나..
시간 복잡도는 해결되었는데 특정 케이스에서 아예 오답이 뜬다고?

![](https://velog.velcdn.com/images/jayy_19/post/14d2e4dd-00e8-46f5-b44a-709d51b624c6/image.jpeg)

원인이 무엇인고.. 고민해보기로 했다.

# 🟢 세 번째 시도
프로그래머스 질문하기 페이지에서 나처럼 테케 10, 11이 틀린 사람들을 살펴봤다.


몇몇 답변으로는 N이 굉장히 큰 수일 때 어쩌고.. 라고 해서 [MDN document](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/Bitwise_AND)를 살펴 보았는데,
![](https://velog.velcdn.com/images/jayy_19/post/af114f89-2ffe-4d7d-b222-c5d3de3c2d36/image.png)

자바스크립트에서는 비트 연산자가 32비트 정수로 자동 변환되기 때문에, `10^15` 같은 큰 숫자를 다룰 때 문제가 발생할 수 있다고 한다. 
즉, **비트 연산(`&`, `|`, `^`, `<<`, `>>`)을 사용하면 32비트 초과 부분이 잘려버릴 수 있다는 것!**

```javascript
console.log(9126805503 | 0);  // 536884607 (잘림)
console.log(8796093022207 | 0);  // -2147483648 (음수가 됨)

이를 해결하기 위해 BigInt를 사용하여 처리했다.

function solution(numbers) {
  return numbers
    .map((x) => {
      x = BigInt(x);

      if (x % 2n === 0n) return x + 1n;

      let bit = 1n;
      while ((x & bit) !== 0n) bit <<= 1n;
      return x + bit - (bit >> 1n);
    })
    .map(Number);
}

BigInt를 사용하면 32비트 제한을 벗어나 큰 숫자도 안전하게 비트 연산이 가능해진다. 연산 후 map(Number)를 활용해 일반 숫자로 변환해주면?

👏🏻👏🏻👏🏻 정답입니다~

사실 비트마스킹 방식 자체가 나에게 익숙하지 않아서, 이번에 비트 연산자를 공부하며 다시 개념을 정리했다.

이외에도 32비트를 초과하는 숫자에서 비트 연산자를 사용할 경우 값이 잘릴 수 있다는 점과, 이를 방지하기 위해 BigInt를 활용하는 방법을 MDN 문서를 통해 직접 확인하며 학습하는 등 여러 새로운 개념을 접하고 적용해 본 문제였기 때문에 이렇게 기록해본다.

I/O(Input/Output)는 컴퓨터나 서버가 파일을 읽거나, 네트워크 통신을 하거나, 데이터베이스에서 데이터를 주고받는 작업을 의미한다. 예를 들어, 네트워크에서 한 컴퓨터가 데이터를 보내고(send), 다른 컴퓨터가 그 데이터를 받는(read) 것을 I/O 작업이라고 한다.

I/O는 User 레벨에서 직접 수행할 수 없고, Kernel에서 수행된다. 유저 프로세스는 커널에 요청만 할 수 있고, 결과과 반환될 때까지 기다리게 된다.

2. Blocking I/O

I/O 작업이 진행되는 동안, 유저 프로세스가 차단되어 기다리는 방식이다.

📌 동작 방식

1. 유저가 커널에 read 작업을 요청하면, 제어권을 커널에 넘겨준다.
2. 데이터가 입력될 때까지 유저는 대기하며, 다른 작업을 할 수 없다.
3. 데이터가 입력되고 나서야 커널이 유저에게 결과를 전달하며, 유저는 제어권을 다시 받아 작업을 재개할 수 있다.

이 방식은 다른 작업을 진행하지 못하기 때문에 자원이 낭비된다는 단점이 있다.

3. Non-blocking I/O

I/O 작업이 진행되는 동안에도 유저 프로세스가 차단되지 않고 다른 작업을 계속 진행할 수 있는 방식이다.

📌 동작 방식

1. 유저가 커널에 read 작업을 요청하면, 바로 결과가 반환된다.
2. 입력된 데이터가 없으면 커널은 EWOULDBLOCK 메세지를 반환하여 데이터가 없다는 것을 알린다.
3. 유저는 제어권을 유지하며 다른 작업을 계속 진행할 수 있다. 데이터가 준비될 때까지 1, 2번 과정을 반복한다.
4. 데이터가 입력되면 커널은 그 데이터를 유저에게 전달해준다.

이 방식은 프로그램이 멈추지 않고 계속 작업을 진행할 수 있다는 장점이 있다.

Reference

• [Network] Blocking I/O 와 Non-Blocking I/O 에 대해서 알아보자
• Boost application performance using asynchronous I/O

동기와 비동기는 작업 완료 여부를 신경 쓰는 방식과 관련이 있다. 즉, 어떤 작업이 시작되면 그 작업의 완료 여부를 기다리는지 또는 바로 다른 작업을 처리할 수 있는지에 따라 동기와 비동기로 나뉜다.

블로킹과 논블로킹은 작업을 요청한 후 해당 작업이 시스템 자원을 차단(blocking)하는지 여부에 대한 관점이다. 즉, 현재 작업이 다른 작업의 진행을 막느냐에 따라 블로킹과 논블로킹으로 나뉜다.

이처럼 두 개념에 대한 의미 차이는 명확하지만, 프로그래밍에서는 종종 혼용되어 사용되기도 한다. 대표적으로 자바스크립트의 setTimeout() 함수를 일반적으로 비동기 함수라고 부르지만 동시에 논블로킹 함수이기도 하다. 즉, 우리가 편의상 부르는 자바스크립트 비동기 함수는 사실 비동기+논블로킹 함수인 것이다. 따라서 이들을 정확하게 구분하고 이해하는 것이 컴퓨터 아키텍쳐를 이해하는 데 있어 중요하다.

1. Synchronous/Asynchronous

1.1. Synchronous

동기(Synchronous)라는 것은 작업을 하나하나 순서대로 처리하는 방식이다. 어떤 작업을 요청했을 때, 그 작업이 끝날 때까지 기다려야 다음 작업을 할 수 있다. 즉, 작업이 순차적으로 처리되는 것이다.

예를 들어, 친구한테 “커피 좀 사다줘”라고 말했을 때, 친구가 돌아올 때까지 기다리고, 그 다음에 다른 일을 할 수 있는 것이다. 완료 여부를 확인하고 나서야 다른 일을 시작하는 방식인 셈이다.

1.2. Asynchronous

비동기(Asynchronous)는 그 반대다. 어떤 작업을 시키더라도 그 결과를 기다리지 않고 바로 다른 일을 할 수 있다. 기다릴 필요 없이 동시에 여러 작업을 처리하는 것처럼 느껴진다.

친구에게 “커피 좀 사다줘”라고 한 후, 커피가 올 때까지 기다리지 않고, 그동안 다른 일을 하면서 보낼 수 있는 것이다. 친구가 커피를 사오면 그때 커피를 받는다.

1.2.1. 비동기의 성능 이점

비동기가 왜 성능이 더 좋을까? 느린 작업을 기다리지 않고 다른 일을 바로 할 수 있기 때문이다.

예를 들어, 웹 애플리케이션이 데이터베이스에서 데이터를 가져와야 하는 상황을 가정해 보자. 동기 방식일 경우, 데이터베이스에서 데이터를 다 가져올 때까지 기다려야 다음 요청을 처리할 수 있다. 그러면 서버가 대기 상태에 빠지고, 많은 사용자가 한꺼번에 접속하면 서버는 느려질 것이다.

하지만 비동기 방식일 경우, 데이터를 가져오는 동안에도 다른 작업을 계속 처리할 수 있다. 데이터베이스 응답이 오면 그때 결과를 처리하고, 그동안은 다른 사용자의 요청도 처리할 수 있는 것이다. 때문에 비동기 방식은 대규모 트래픽에서도 효율적이고, 서버 성능을 더 최적화할 수 있다.

1.2.2. 자바스크립트의 비동기

자바스크립트에서는 비동기 작업을 많이 사용하는데, 예를 들어 setTimeout()라는 함수가 있다. 이는 지정된 시간이 지난 후에 특정 작업을 수행하도록 하는 함수다.

중요한 점은, 시간을 기다리는 동안 다른 코드도 계속 실행된다는 것이다. 자바스크립트는 싱글 스레드로 작동해서 한 번에 하나의 작업만 할 수 있는 것처럼 보이지만, 브라우저에서는 멀티 스레드로 돌아가는 Web API가 있어 비동기 작업을 백드라운드에서 처리하도록 한다.

이런 구조 덕분에 자바스크립트는 한꺼번에 여러 작업을 처리할 수 있는 것처럼 보이고, 서버 성능을 크게 향상시킬 수 있다.

1.3. 동기와 비동기의 작업 순서

동기와 비동기의 가장 큰 차이 중 하나는 작업 순서다.

• 동기에서는 $A→B→C$와 같이 순서대로 작업이 진행된다. 하나가 끝나야 그 다음 작업을 할 수 있다.

  

• 비동기에서는 $A→C→B$와 같이 순서가 보장되지 않는다. 각 작업이 독립적으로 처리되기 때문에, 어떤 작업이 먼저 끝날지 알 수 없다. 때문에 결과가 무작위로 나올 수 있다.

  

2. Blocking/Non-blocking

2.1. Blocking

블로킹은 말 그대로 작업이 끝날 때까지 기다리게 만드는 방식이다.

예를 들어, 친구에게 “커피 좀 사다줘”라고 했을 때, 친구가 돌아올 때까지 아무것도 못하고 문 앞에서 계속 기다리는 상황이다. 다른 일을 할 수가 없고, 친구가 커피를 사오는 작업이 끝날 때까지 대기해야 한다.

2.2. Non-Blocking

반대로 논블로킹은 작업이 끝나지 않았더라도 다른 일을 계속 할 수 있는 방식이다.

커피를 부탁해도 굳이 문 앞에서 기다리지 않고, 집 안에서 다른 일을 하면서 기다리는 것이다. 친구가 커피를 사오면 그때 커피를 받는다. 즉, 다른 작업이 멈추지 않고 동시에 진행되는 것이다.

비동기(Asynchronous)와 논블로킹(Non-Blocking)의 차이

• 비동기는 작업 완료 여부와 관련된 개념이다. 작업을 시켰을 때 결과가 바로 오지 않더라도 다른 작업을 먼저 할 수 있는지 여부를 말한다.
• 논블로킹은 현재 작업이 다른 작업을 막는지 여부를 말한다. 작업이 진행 중이더라도, 다른 작업을 동시에 할 수 있으면 논블로킹이다.

둘 다 결과적으로 동시에 여러 작업을 처리할 수 있다는 점에서 비슷해 보이지만, 비동기는 ‘작업이 끝났냐’를 신경쓰지 않기 때문에 계속 진행하는 것이고, 논블로킹은 ‘작업이 진행되더라도 다른 작업을 멈추지 않고 동시에 처리’하는 것이다.

3. Synchronous/Asynchronous & Blocking/Non-blocking

3.1. 제어권(Control)과 Blocking/Non-Blocking

프로그래밍에서 제어권은 함수나 코드 흐름을 제어할 수 있는 권리를 말한다. 제어권을 누가 가지고 있느냐에 따라 블로킹과 논블로킹을 구분할 수 있다.

3.1.1. Blocking

블로킹 방식은 호출된 함수(B 함수)가 제어권을 가지고, 호출한 함수(A 함수)는 멈춰 있어야 하는 방식이다.

1. A 함수가 B 함수를 호출하면, B에게 제어권이 넘어간다.
2. B 함수가 실행되는 동안, A 함수는 잠시 멈춘다.(Block)
3. B 함수가 끝나면, A 함수에게 제어권을 다시 돌려준다.
4. A 함수는 그제서야 다시 다음 작업을 진행할 수 있다.

쉽게 말하면, A 함수는 B 함수가 끝날 때까지 대기해야 하고, 제어권을 잠시 B 함수에게 양보하는 상태라고 볼 수 있다.

3.1.2. Non-Blocking

논블로킹 방식은 호출된 함수(B 함수)가 실행되지만, 제어권은 여전히 A 함수가 가지고 있는 방식이다.

1. A 함수가 B 함수를 호출하면, B 함수가 실행되지만 제어권은 A 함수에게 계속 남아있다.
2. A 함수는 제어권을 가지고 있기 때문에 B 함수가 끝나지 않더라도 자신의 작업을 계속할 수 있다.
3. B 함수는 백그라운드에서 실행되고, A 함수는 중단되지 않고 코드를 계속 처리한다.

즉, A 함수는 B 함수가 끝나길 기다리지 않고 다른 작업을 바로 진행할 수 있다.

3.2. Sync Blocking(동기+블로킹)

작업을 순서대로 처리하고, 하나의 작업이 끝날 때까지 기다리는 방식이다. 다른 작업이 진행되는 동안 멈추고, 결과가 나올 때까지 대기하는 형태이다.

3.2.1. 실생활 예시

팀장이 사원1에게 A 업무를 시키고, 사원1이 A를 끝낼 때까지 기다린 후에 사원2에게 B 업무를 시키는 상황.

사원의 작업이 끝나기 전까지 팀장은 다른 사원에게 아무 일도 시키지 못한다.

3.2.2. 코드 예시

const data1 = fs.readFileSync('file1.txt', 'utf8'); // A 작업
console.log(data1);

const data2 = fs.readFileSync('file2.txt', 'utf8'); // B 작업
console.log(data2);

이 방식은 코드가 순차적으로 실행된다. 작은 작업에서는 유용할 수 있으나, 시간이 오래 걸리는 작업에서는 비효율적이다.

3.2.3. 적용 프로그램 예시

대표적으로 C나 Java의 코드 실행 후 커맨드에서 입력을 받는 경우가 이에 해당된다. 사용자로부터 입력을 받아야 그 입력값을 가지고 내부 처리를 하여 결과값을 콘솔에 출력해주기 때문에 순차적인 작업이 요구된다.

내부적으로 본다면 실행 코드가 콘솔창을 띄우고 Please enter your name 텍스트를 치고 난 다음 사용자의 리턴값이 필요하기 때문에 제어권을 시스템에서 사용자로 넘겨 사용자가 값을 입력할 때까지 기다리는 것이다.

3.3. Async Blocking(비동기+블로킹)

작업이 시작되면 결과를 기다리지는 않지만, 다른 작업이 완료될 때까지는 막혀있다.

3.3.1. Async Blocking vs Sync Blocking

3.2와 비교했을 때, Async Blocking은 Sync Blocking 수행과 큰 차이가 없어 보인다. 실제로 개념적으로만 차이가 존재할 뿐이지, 성능적으로 큰 차이가 없을 뿐더러 실무에서 마주할 일이 없다.

보통 Async Blocking은 개발자가 비동기 논블로킹으로 처리하려다가 실수하는 경우에 발생하거나, 자기도 모르게 블로킹 작업을 실행하는 의도치 않은 경우에 사용된다. 그래서 이 방식을 안티 패턴(anti-pattern)이라고 치부하기도 한다.

3.3.2. 활용 예시 프로그램

다만 Async Blocking이 실제로 적용된 실무 사례가 있 다. Node.js + MySQL의 조합이 대표적인데, Node.js에서 비동기 방식으로 데이터베이스에 접근하기 때문에 Async지만, MySQL 데이터베이스에 접근하기 위한 MySQL 드라이버가 블로킹 방식으로 작동되기 때문이다.

1. JavaScript는 비동기 방식으로 MySQL에 쿼리를 보낸다. (Async)
2. MySQL은 쿼리를 처리하면서 JavaScript에게 제어권을 넘겨주지 않는다. (Blocking)
3. JavaScript는 다른 작업을 계속 수행할 수는 있지만, MySQL의 결과값을 필요로 하기 때문에 MySQL이 쿼리를 완료할 때까지 기다린다.
4. 결국 Sync Blocking과 차이가 없게 된다.

3.4. Sync Non-Blocking(동기+논블로킹)

결과가 나오기 전에 다른 작업을 할 수 있지만, 작업 순서는 보장돼야 한다. 즉, 순서대로 작업을 해야 하지만, 각 작업이 진행되는 동안 다른 작업을 방해하지 않는다.

3.4.1. 실생활 예시

팀장에게 A, B, C 세 개의 업무가 있는데, A 작업을 끝내야 B 작업을, B 작업을 끝내야 C 작업을 시작할 수 있다. 팀장은 각각의 작업을 시작한 후, 결과가 나올 때까지 동시에 다른 부서와 회의를 하거나 이메일을 처리할 수 있다.

3.4.2. 코드 동작 예시

Thread thread = new Thread(new MyTask());
thread.start(); // 논블로킹 실행

System.out.println("Main thread is running...");

while (thread.isAlive()) {
    System.out.println("Waiting for the thread to finish...");
}

// A가 끝나야 B를 실행
System.out.println("Thread finished!");

System.out.println("Run the next tasks");

스레드를 이용하여 작업을 병렬적으로 처리하도록 지시했지만, while 문을 수행함으로써 요청한 작업의 완료 여부를 계속 확인하고, 결과적으로 순서대로 작업이 수행되는 것을 확인할 수 있다.

자바스크립트의 경우 동기+논블로킹 코드를 구현하기에는 지원하는 메서드에 한계가 있어 완벽히 표현할 수는 없다. 다만 이와 비슷하게 구현하려면 Promise와 async/await를 사용하면 된다.

const fs = require('fs'); 
const { promisify } = require('util'); 
const readFileAsync = promisify(fs.readFile); // fs.readFile 함수를 Promise 객체를 반환하는 함수로 변환

async function readFiles() {
  try {
    // Promise.all() 메소드를 사용하여 여러 개의 비동기 작업을 병렬로 처리한다. (비동기 논블로킹)
    const [data1, data2, data3] = await Promise.all([
      readFileAsync('file.txt', 'utf8'), 
      readFileAsync('file2.txt', 'utf8'), 
      readFileAsync('file3.txt', 'utf8') 
    ]);

    // 파일 읽기가 완료되면 data에 파일 내용이 들어온다.
    console.log(data1); 
    console.log(data2); 
    console.log(data3); 

    // 파일 비교 로직 실행...

  } catch (err) {
    throw err;
  }
}

readFiles(); // async 함수를 호출

• 비동기 논블로킹: Promise.all()을 사용하여 여러 파일을 동시에 읽는 작업을 비동기적으로 실행할 수 있다. 이렇게 하면 작업이 병렬로 진행되어 논블로킹 방식이 된다.
• 동기적 순서 유지: await를 사용하여 파일 읽기 작업이 모두 완료된 후 그 결과를 순차적으로 처리할 수 있다. 즉, 파일을 동시에 읽되, 결과를 동기적으로 처리할 수 있는 방법이다.

async/await은 비동기 작업을 동기적으로 표현해주는 기법처럼 보이지만, 그 이면에서는 비동기 논블로킹으로 작동한다는 점을 기억해야 한다. 자바스크립트의 메인 콜 스택이 모두 비워진 후에 async 함수가 실행되기 때문에, 여전히 비동기적으로 작동하면서 다른 작업을 막지 않는다는 것이다.

3.4.3. 활용 예시 프로그램

게임에서 맵을 이동할 때를 생각해보자. 맵 다운로드는 시간이 걸리는 작업이다. 이 작업은 비동기적으로 백그라운드에서 처리된다. 즉, 게임은 맵 다운로드가 끝날 때까지 기다리지 않고 다른 작업을 계속할 수 있다. 여기서 다른 작업이란 맵 다운로드가 진행되는 동안 게임이 로딩 바를 업데이트하거나 UI를 계속해서 표시하는 것을 의미한다.

⏱️ Sync Blocking vs Sync Non-Blocking

블로킹이든 논블로킹이든, 메인 함수에서 결국 코드를 동기적으로 실행하면 이 둘은 차이가 없어 보인다. 그럼 두 방식은 도긴개긴인 것인가?

성능 차이는 상황에 따라 다르겠으나, 일반적으로 동기+논블로킹이 동기+블로킹보다 효율적일 수 있다. 왜냐하면 동기+논블로킹은 호출하는 함수가 제어권을 가지고 있어 다른 작업을 병렬적으로 수행할 수 있기 때문이다. 반면, 동기+블로킹은 호출하는 함수가 제어권을 잃어서 다른 작업을 수행할 수 없다.

3.5. Async Non-Blocking(비동기+논블로킹)

작업이 끝나기 전에 다른 작업을 처리할 수 있고, 작업 순서에 구애받지 않는다. Node.js같은 환경에서 많이 사용되는 방식이다.

3.5.1. 실생활 예시

팀장이 사원1, 사원2, 사원3에게 동시에 업무를 시키고, 결과가 언제 나오든 나오는 대로 처리하는 방식이다. A, B, C라는 작업을 동시에 시킬 수 있고, 완료되는 순서와 상관없이 결과를 처리할 수 있다.

3.5.2. 코드 예시

fs.readFile('file.txt', 'utf8', (err, data) => {
  console.log(data);
});

fs.readFile('file2.txt', 'utf8', (err, data) => {
  console.log(data);
});

console.log('done'); // 이게 먼저 출력됨

여기서는 파일 읽기가 비동기적으로 처리되고, 순서에 상관없이 논블로킹으로 작업이 진행된다. 비동기 논블로킹 방식은 작업량이 많을 때, 다른 작업을 동시에 처리할 수 있어 성능을 최적화할 수 있다.

fs.readFileSync와 fs.readFile 함수는 둘 다 똑같이 파일을 읽는 함수이지만, 동기냐 비동기냐에 차이가 있다. 즉, fs.readFileSync 함수는 동기적으로 파일을 읽고, fs.readFile 함수는 비동기적으로 파일을 읽는다.

3.5.3. 활용 예시 프로그램

비동기 논블로킹을 활용하는 프로그램은 많다. 그중 예를 들자면, 웹 브라우저의 파일 다운로드가 비동기 논블로킹을 활용하는 예시라고 할 수 있다. 웹 브라우저는 웹 사이트에서 파일을 다운로드할 때, 파일의 전송이 완료될 때까지 다른 작업을 하지 않고 기다리는 것이 아니라, 다른 탭이나 창을 열거나 웹 서핑을 할 수 있다. 이는 웹 브라우저가 파일 다운로드를 비동기적으로 처리하고, 콜백 함수를 통해 다운로드가 완료되면 알려주는 방식으로 구현되어 있기 때문이다.

파일들이 거의 동시에 다운 받아지는 것을 Waterfall 그래프에서 시작적으로 확인할 수 있다.

Reference

• 완벽히 이해하는 동기/비동기 & 블로킹/논블로킹

로드 밸런싱이란 여러 대의 컴퓨터 자원(CPU, 저장장치 등)에 작업을 고르게 분배하여 트래픽을 효율적으로 관리하는 기술이다. 현대의 웹사이트들은 많은 사람들이 동시에 접속하는 경우가 많아, 단일 서버로 모든 트래픽을 처리하기엔 한계가 있다. 이를 해결하기 위한 두 가지 방법이 있다.

• Scale-up: 하드웨어 성능을 향상시키는 방법
• Scale-out: 여러 대의 서버가 트래픽을 나눠서 처리하도록 구성하는 방법

Scale-out은 무중단 서비스 환경을 구성하기 용이하며, 여러 서버에 트래픽을 균등하게 분배하는 것이 바로 로드 밸런싱이다.

2. 원리

로드 밸런싱은 여러 서버에 부하(Load)를 고르게 나누는 분산식 웹 서비스 구조이다. 로드 밸런서는 클라이언트와 서버 사이에 위치하여 트래픽을 분산시켜 서버의 과부하를 방지한다. 서비스 규모에 따라 서버를 증설할 수 있으며, 로드 밸런서를 통해 이러한 서버들을 관리하여 성능을 최적화할 수 있다.

3. 로드 밸런서의 서버 선택 방식

로드 밸런서의 서버 선택 방식에는 다양한 알고리즘이 사용되며, 각 방식은 트래픽의 특성이나 서버의 상태에 따라 효율성을 달리할 수 있다. 대표적인 서버 선택 방식은 아래와 같다.

3.1. 라운드 로빈(Round Robin)

순차적으로 서버를 선택하여 트래픽을 분산하는 방식이다. 서버 목록에서 첫 번째 서버부터 마지막 서버까지 차례대로 요청을 배분하고, 다시 처음으로 돌아가 반복된다. 이 방식은 각 서버의 처리 능력이나 현재 부하를 고려하지 않고 균등하게 분배하는 것이 특징이다.

• 장점: 단순하고 구현이 쉽다. 서버의 부하 상태를 고려하지 않아도 고르게 분산된다.
• 단점: 각 서버의 성능이나 현재 연결된 세션 수를 고려하지 않기 때문에, 성능이 다르거나 세션이 긴 요청이 있는 환경에서는 비효율적일 수 있다.

3.2. Least Connections

현재 연결된 세션 수가 가장 적은 서버에 요청을 분배하는 방식이다. 이 방식은 각 서버의 부하 상태를 실시간으로 고려하며, 세션이 길어지는 트래픽이나 비대칭적인 요청 분포가 발생하는 환경에서 유용하다.

• 장점: 서버 간의 부하를 실시간으로 반영하여 상대적으로 가벼운 서버에 우선적으로 요청을 분배함으로써 효율성을 높인다.
• 단점: 각 서버의 연결 상태를 지속적으로 모니터링해야 하므로 추가적인 오버헤드가 발생할 수 있다. 또한, 세션 수만을 기준으로 삼기 때문에 요청당 리소스가 큰 경우(e.g. 대형 파일 전송)에는 서버 부하를 완전히 반영하지 못할 수 있다.

3.3. Source(IP 해싱)

클라이언트의 IP 주소를 해싱하여 특정 서버에 트래픽을 분배하는 방식이다. 해시 알고리즘을 사용해 사용자의 IP를 기반으로 항상 같은 서버에 연결되도록 보장한다. 이 방식은 사용자 세션 유지가 중요한 환경에서 주로 사용된다.

• 장점: 특정 사용자가 동일한 서버에 항상 연결되므로, 세션 유지가 중요한 경우(e.g. 사용자 로그인 상태, 지속적인 데이터를 처리하는 웹 애플리케이션 등) 유리하다. 세션 유지에 별도의 처리를 할 필요가 없다.
• 단점: 특정 서버에 트래픽이 몰릴 수 있는 위험이 있다. IP 분포가 불균형할 경우 특정 서버에만 많은 부하가 걸릴 수 있으며, 로드 밸런싱의 효과가 떨어질 수 있다.

4. 로드 밸런서의 종류

주로 L4와 L7 로드 밸런서가 많이 사용된다. OSI 7 계층 모델에서 L4는 전송 계층, L7은 애플리케이션 계층을 의미한다. 이 계층에 따라 로드 밸런싱의 정교함이 달라지며, L4부터는 포트 정보를 바탕으로 트래픽 분산이 가능하다.

4.1. L4 로드 밸런서(Layer 4 Load Balancer)

L4 로드 밸런서는 네트워크 계층에서 작동한다. 주로 TCP나 UDP와 같은 전송 계층 프로토콜을 사용해서 클라이언트의 요청을 여러 서버로 분산한다.

4.1.1. 특징

• 작동 방식: 패킷의 소스 IP 주소, 소스 포트, 목적지 IP 주소, 목적지 포트를 기준으로 트래픽을 분산한다. 이 정보는 TCP/UDP 헤더에 포함되어 있으며, 이러한 데이터를 기준으로 요청을 처리한다.
• 트래픽 분산: 트래픽을 직접 분석하지 않고 단순히 네트워크 연결을 기반으로 분배하기 때문에, 세션을 유지하거나 특정 요청의 내용에 따라 트래픽을 분산하는 데에 한계가 있다. 즉, 요청의 데이터(e.g. HTTP 헤더나 콘텐츠)를 분석하지 않고 연결을 처리하는 것이 특징이다.
• 성능: 트래픽 분산을 매우 효율적으로 처리할 수 있다. 애플리케이션 계층에서 일어나는 복잡한 처리 없이 패킷 레벨에서 트래픽을 전달하기 때문에, 대규모 트래픽 처리에 적합하다.

4.1.2. 장점

• 빠르고 간단하다.
  • 애플리케이션 계층까지 도달하지 않기 때문에, 데이터 패킷을 빠르게 분산할 수 있다.
  • 고성능이 요구되는 대규모 네트워크 환경에서 유리하다.
• 프로토콜에 무관하다.
  • HTTP뿐만 아니라 TCP나 UDP를 사용하는 다양한 서비스에 사용할 수 있다.
  • e.g. 데이터베이스나 메일 서버 등 비HTTP 서비스에서 활용 가능

4.1.3. 단점

• 세밀한 제어가 부족하다.
  • 트래픽을 세부적으로 분석하지 않기 때문에 요청의 종류나 사용자의 상태에 따라 적절히 분배하지 못할 수 있다.
  • e.g. 특정 URL을 처리하는 서버가 필요한 경우 적합하지 않다.
• 세션 유지가 어렵다.
  • 사용자의 세션이나 상태를 기반으로 분산하는 기능이 제한적이다.

4.2. L7 로드 밸런서(Layer 7 Load Balancer)

L7 로드 밸런서는 애플리케이션 계층에서 작동한다. HTTP, HTTPS와 같은 애플리케이션 레벨의 프로토콜을 분석하고, 클라이언트의 요청을 보다 정교하게 처리한다.

4.2.1. 특징

• 작동 방식: 요청의 내용(e.g. URL, HTTP 헤더, 쿠키, 메소드 등)을 분석하여 트래픽을 분산한다. 사용자가 요청하는 리소스에 따라 서버를 다르게 지정하거나, 특정 콘텐츠를 처리할 수 있는 서버로 트래픽을 유도할 수 있다.
• 트래픽 분산: HTTP 요청을 이해하고 처리할 수 있으므로 URL 기반, 쿠키 기반, 세션 기반 등 다양한 방식으로 트래픽을 분배할 수 있다. 예를 들어, 특정 URL 패턴에 대한 요청을 특정 서버로 전달하거나, 사용자 데이터를 분석하여 적절한 서버에 할당하는 방식으로 매우 세밀한 로드 밸런싱이 가능하다.
• 성능: 트래픽을 분석하고 처리하는 데 더 많은 리소스를 사용하기 때문에 L4에 비해 성능이 약간 떨어질 수 있다. 하지만 고급 트래픽 제어가 가능하다는 점에서 웹 애플리케이션 환경에서 매우 유용하다.

4.2.2. 장점

• 세밀한 제어가 가능하다.
  • 요청의 내용을 분석하여 더 정교한 트래픽 분배가 가능하다.
  • e.g. 특정 URL로 들어오는 요청만 특정 서버에 전달, 사용자 IP나 쿠키 정보를 바탕으로 분산 조정 가능
• 세션 유지가 용이하다.
  • 특정 사용자가 항상 같은 서버에 연결되도록 보장하는 등, 사용자 상태 기반의 트래픽 관리가 가능하다.
• SSL 종료
  • HTTPS 요청에 대해 SSL/TLS 인증을 처리하고, 암호화를 해제한 후 내부 서버로 전달할 수 있다.
  • 이를 통해 서버는 암호화 부담 없이 요청을 처리할 수 있다.

4.2.3. 단점

• 리소스 소모
  • 애플리케이션 계층에서 요청을 분석하기 때문에 L4보다 더 많은 리소스를 소모하기 때문에, 대규모 트래픽 처리 시 성능 저하가 발생할 수 있다.
• 프로토콜 한정
  • 주로 HTTP/HTTPS 기반의 트래픽에 활용되므로, TCP와 UDP같은 비HTTP 서비스에는 적합하지 않다.

5. 로드 밸런서의 장애 대비

로드 밸런서가 여러 서버로 트래픽을 분산시키는 중요한 역할을 하지만, 그 로드 밸런서 자체가 장애를 겪으면 어떻게 될까?

이러한 문제를 예방하고 서비스의 무중단 가동을 보장하기 위해 로드 밸런서의 이중화가 필요하다.

5.1. 로드 밸런서의 이중화

로드 밸런서 이중화는 동일한 네트워크 내에서 두 개 이상의 로드 밸런서가 함께 동작 하여, 한쪽이 장애를 겪을 때 다른 쪽이 자동으로 그 역할을 대신하는 구조를 의미한다. 이중화된 로드 밸런서들은 서로의 상태를 지속적으로 모니터링하고, 문제가 발생하면 즉시 트래픽을 다른 로드 밸런서로 전환하여 서비스의 중단을 방지한다.

• Active-Passive 방식
  • Active 로드 밸런서: 평상시 모든 트래픽을 처리하는 주 로드 밸런서
  • Passive 로드 밸런서: 대기 상태에서 Active 로드 밸런서를 모니터링한다. Active 로드 밸런서가 장애를 겪으면, Passive 로드 밸런서가 즉시 활성화되어 트래픽을 처리한다.
• Active-Active 방식
  • 두 개 이상의 로드 밸런서가 동시에 활성된 상태에서 트래픽을 분산 처리한다. 각각의 로드 밸런서가 일부 트래픽을 처리하며, 한쪽이 장애를 겪으면 나머지가 자동으로 모든 트래픽을 처리한다.

5.2. Health Check

이중화된 로드 밸런서들이 서로의 상태를 실시간으로 모니터링하기 위해 사용하는 것이 Health Check이다. Health Check는 로드 밸런서가 주기적으로 서로의 상태를 점검하는 기능으로, 정상적인 통신이 이루어지고 있는지 확인한다.

📌 Health Check의 동작 방식

1. 로드 밸런서들은 정기적인 요청을 통해 서로가 정상적으로 작동하고 있는지 확인한다.
2. 만약 응답이 없거나, 이상이 감지되면 장애가 발생한 것으로 간주한다.
3. 이를 통해 트래픽 처리를 맡고 있는 로드 밸런서에 문제가 발생하면, 즉시 다른 로드 밸런서가 그 역할을 대신하게 된다.

5.3. 가상 IP(VIP)와 트래픽 전환

VIP(Virtual IP)는 로드 밸런서의 장애 발생 시 트래픽을 자동으로 다른 로드 밸런서로 전환하는 중요한 역할을 한다. VIP는 실제 물리적 IP가 아니라, 클라이언트가 접속하는 논리적인 IP 주소이다. 즉, 물리적으로 특정 서버에 고정되어 있는 것이 아니라, 여러 장비나 서버 사이에서 동적으로 할당될 수 있는 IP 주소다.

• 주 로드 밸런서가 장애를 겪으면, VIP는 대기 중인 여분의 로드 밸런서로 전환된다.
• 클라이언트는 VIP에 접속하여 서비스에 접근하므로, 클라이언트는 장애 상황을 인식하지 못한 채 서비스를 지속해서 사용할 수 있다.

Reference

• CS-Study/Network/로드밸런싱.md
• Network Load Balancing: Round Robin vs Least Connections

정보를 전달하기 위해서는 머리가 자라는 동안 기다려야 한다는 단점이 있지만, 중요한 정보를 확실히 감추는 데에는 이만한 방법이 없다. 옛날부터 중요한 정보를 안전하게 보내는 것은 매우 중요했다는 것을 알 수 있다.

HTTPS 통신 과정에서도 송신자와 수신자는 주고받을 데이터를 안전하게 보내는 것을 중요시 한다. 이때문에 데이터를 암호화할 대칭키(비밀키)를 타인에게 노출시키지 않고 클라이언트가 서버에게 전송하기 위해 협상을 벌인다.

오늘 다룰 TLS & SSL Handshake는 송신자와 수신자가 암호화된 데이터를 교환하기 위해 벌이는 일련의 협상이다. 협상 과정에서는 TLS 인증서 전달, 대칭키(비밀키) 전달, 암호화 알고리즘 결정, TLS/SSL 프로토콜 결정 등이 포함된다.

위의 파란색 칸은 TCP layer의 3-Way Handshake로 HTTPS가 TCP 기반의 프로토콜이기 때문에 암호화 협상(TLS Handshake)에 앞서 연결을 생성하기 위해 실시하는 과정이고, 아래 노란색 상자의 패킷들이 TLS Handshake이다.

아래 두 가지를 기억하면서 글을 살펴보자.

1. 암호화 알고리즘(Cipher Suite) 결정
2. 데이터를 암호화할 대칭키(비밀키) 전달

1. Client Hello

클라이언트가 서버에 연결을 시도하며 전송하는 패킷이다. 자신이 사용 가능한 Cipher Suite 목록, Session ID, SSL Protocol Version, Random byte 등을 전달한다.

🔼 Client Hello Packet

Cipher Suite는 TLS 통신에서 보안 연결을 설정하는 데 사용되는 알고리즘의 집합이다. 이는 TLS의 프로토콜 버전, 인증서 검증 방식, 데이터 암호화 프로토콜, 해시 알고리즘 등의 정보를 포함한다. 클라이언트는 서버에 자신이 지원하는 Cipher Suite 목록을 제공하고, 서버는 그 중 하나를 선택해 통신에 사용할 암호화 알고리즘을 결정한다. 이렇게 선택된 Cipher Suite에 따라 이후의 데이터가 암호화된다.

🔼 Cipher Suite의 구성

2. Server Hello

서버는 클라이언트가 보낸 Client Hello 패킷에서 제공된 여러 Cipher Suite 중 하나를 선택한다. 서버는 선택한 Cipher Suite와 함께 자신이 사용할 TLS 프로토콜 버전 등의 정보를 포함한 Server Hello 패킷을 클라이언트에 보낸다.

🔼 Server Hello Packet

위 사진을 보면 Client Hello에서 17개였던 Cipher Suite와 달리, 아래에서는 서버가 선택한 한 줄(Cipher Suite: TLS_AES_256_GCM_SHA384)만이 존재하는 것을 알 수 있다. 클라이언트가 보낸 리스트에 있는 Cipher Suite 중 한 개를 선택한 것이다.

서버는 클라이언트가 보낸 Cipher Suite 리스트 중 자신이 지원하는 가장 높은 등급의 Suite를 선택하여 안전한 통신을 시작한다.

3. Certificate

서버가 자신의 TLS 인증서를 클라이언트에게 전달한다. 나의 경우 TLS1.3이기 때문에 key 교환 후 Application Data Protocol을 통해 Certificate이 암호화되어 전송되기 때문에 보이지 않는다. TLS1.2를 사용한 모 블로그의 사진으로 대체하겠다.

🔼 Certificate Packet

이 인증서에는 서버가 발행한 공개키가 포함되어 있으며, 서버는 개인키를 소유한다. 클라이언트는 CA의 공개키를 이용해 인증서를 검증하고, 이 인증서가 유효한지 확인한다.

위 사진을 보면 인증서가 어떤 알고리즘(RSA)으로 암호화되었고, 어떤 Hash 알고리즘(SHA256)으로 서명되었는지 확인 가능하다.

4. Server Key Exchange / Server Hello Done

Server Key Exchange는 서버의 공개키가 TLS 인증서에 포함되지 않았을 때 서버가 직접 공개키를 전달하는 과정이다. 만약 인증서에 공개키가 포함되어 있다면, 클라이언트는 CA의 공개키로 인증서를 복호화해 서버의 공개키를 얻으므로 이 단계가 생략된다.

이 경우 키 교환 알고리즘이 Diffie-Hellman이 사용되어, 서버는 키 교환을 위한 추가 정보를 제공해야 하므로 Server Key Exchange가 발생한다. 이 과정을 통해 최종 세션키가 생성된다.

5. Client Key Exchange

클라이언트는 대칭키를 생성한 후, 서버 인증서에서 추출한 서버의 공개키로 해당 대칭키를 암호화하여 서버로 전달한다. 이 대칭키는 이후 실제 데이터 암호화에 사용되며, TLS Handshake의 가장 중요한 목적 중 하나이다.

위의 사진처럼 Diffie-Hellman과 ECDHE 알고리즘을 사용하면 클라이언트는 대칭키를 직접 보내는 대신, 대칭키를 만들기 위한 재료(키 생성 파라미터)를 서버와 교환한다. 이를 통해 서버와 클라이언트는 각각 교환한 재료를 조합해 같은 대칭키를 생성하게 된다.

반면 RSA 알고이름을 사용할 경우, 클라이언트가 이미 생성한 대칭키를 서버의 공개키로 암호화하여 서버에 전달한다. 최종적으로 이 대칭키를 이용해 실제 데이터가 암호화된다.

6. Change Cipher Spec / Finished

Change Cipher Spec은 클라이언트와 서버가 암호화를 시작하겠다는 신호로, 이 메세지를 주고받은 후 모든 통신이 암호화된다. 즉, 양측이 합의한 암호화 방식을 적용하는 단계이다.

Finished는 Handshake가 끝나고, 성공적으로 암호화 키 교환과 인증이 완료되었음을 확인하는 메세지이다. 이 메세지에는 Handshake 과정 전반의 무결성을 확인하는 해시 값이 포함된다.

📌 TLS Handshake 요약

Client Hello(암호화 알고리즘 나열 및 전달) → Server Hello(암호화 알고리즘 선택) → Server Certificate(인증서 전달) → Client Key Exchange(데이터를 암호화할 대칭키 전달) → Client / Server Hello done(정보 전달 완료) → Finished(TLS Handshake 종료)

위 과정을 통해 클라이언트와 서버는 데이터를 암호화할 동일한 대칭키를 갖게 되며, 서로에게 각자 갖고 있는 동일한 대칭키를 이용하여 데이터를 암호화해 전송하거나 복호화한다. 클라이언트와 서버는 이제 성공적으로 비밀 친구가 된 것이다.

Reference

• HTTPS 통신과정 쉽게 이해하기 #3(SSL Handshake, 협상)
• TLS 핸드셰이크의 원리는 무엇일까요? | SSL 핸드셰이크

2014년, 구글에서는 HTTP를 HTTPS로 바꾸라고 권고한다. 이전까지는 전자상거래가 있는 웹 사이트에서만 다소 번거로운 HTTPS를 사용하고 있었다. HTTPS로의 전환을 장려하기 위해 구글에서는 HTTPS를 사용하는 웹 사이트에 대해 검색 순위 결과에 가산점을 주겠다고 발표했다. 이는 사실상 HTTP를 사용하는 웹 사이트에 벌점을 주는 것과 마찬가지였다.

구글은 어떤 점 때문에 HTTPS로의 전환을 장려했을까? 각각에 대해 알아보자.

1. HTTP란?

HTTP(HyperText Transfer Protocol)란 전 세계 웹 브라우저와 서버 사이에서 데이터를 주고받기 위한 통신 규약이다. HTTP는 클라이언트-서버 모델을 기반으로 작동하는데, 웹 브라우저는 사용자가 URL을 입력하거나 링크를 클릭할 때마다 HTTP 요청을 보내고, 서버는 그 요청을 처리한 후 응답을 반환한다.

이 요청-응답의 반복을 통해 사용자와 서버 간에 데이터를 주고받는 통신이 이루어진다.

1.1. 구조

HTTP는 애플리케이션 레벨의 프로토콜로, TCP/IP 위에서 작동한다. HTTP는 상태 정보를 유지하지 않는 Stateless 프로토콜이며, 클라이언트가 요청을 보낸 후 서버가 응답하는 형태로 이루어진다.

HTTP 메세지는 Method, Path, Version, Headers, Body 등의 구성 요소 이루어져 있다.

• Method: 클라이언트가 서버에 요청하는 방식(GET, POST 등)
• Path: 요청할 리소스의 경로
• Version: HTTP 버전 정보
• Headers: 요청 또는 응답에 대한 부가 정보
• Body: 실제 데이터(필요한 경우)

1.2. 작동 방식

1.2.1. HTTP 요청과 응답

• 클라이언트(보통 웹 브라우저)가 서버에 데이터를 요청하는 방식이다. 클라이언트가 URL을 입력하면 해당 요청이 서버로 전송되고, 서버는 그 요청에 맞는 응답을 클라이언트에 반환한다.
• HTTP는 다양한 상태 코드로 응답 상태를 나타낸다. 예를 들어, 클라이언트가 요청한 작업이 성공했는지, 실패했는지, 잘못된 요청이었는지 숫자 코드로 나타낸다.

1.2.2. 주요 상태 코드

• 200 - OK: 요청이 성공적으로 처리되었음을 의미
• 400 - Bad Request: 요청이 잘못되었거나 서버에서 이해할 수 없는 경우
• 404 - Resource Not Found: 요청한 리소스를 찾을 수 없는 경우

1.3. 문제점

초기의 HTTP는 암호화되지 않은 평문 데이터를 전송하는 방식이었다. 이로 인해 민감한 정보(비밀번호, 주민등록번호 등)를 HTTP로 주고받으면 제3자가 정보를 가로챌 수 있는 문제가 있었다. 이러한 보안 문제를 해결하기 위해 HTTPS가 등장했다.

POST /login HTTP/1.1
Host: example.com
Content-Type: application/x-www-form-urlencoded

username=johndoe&password=12345

2. HTTPS란?

HTTPS(HyperText Transfer Protocol Secure)란 HTTP에 보안 기능을 추가한 확장 버전이다. HTTPS는 SSL/TLS 프로토콜을 사용하여 클라이언트와 서버 간 통신을 암호화한다.

HTTPS의 핵심 기능은 데이터 전송 중에 제3자가 데이터를 가로채거나 볼 수 없도록 보호하는 것이다. 포트 번호는 HTTP와 다르게 443번 포트를 사용한다.

정리하자면, HTTPS는 HTTP에 SSL/TLS가 추가된 프로토콜이다.

2.1. SSL/TLS

SSL(Secure Socket Layer)/TLS(Transport Layer Security)란 웹 서버와 웹 브라우저 간의 암호화 통신을 위해 애플리케이션 계층에서 동작하는 프로토콜이다. 인증, 암호화, 무결성, 지원 프로토콜의 기능을 가진다.

SSL/TLS의 암호화는 세 가지 주요 요소로 구성된다.

1. 비대칭키 암호화(Asymmetric Encryption)
   • SSL/TLS의 Handshake 과정에서 사용된다. (클라이언트-서버 세션 키(대칭키) 교환을 위한 초기 과정)
   • RSA, ECDHE(Elliptic Curve Diffie-Hellman Ephemeral) 알고리즘이 사용된다.
2. 대칭키 암호화(Symmetric Encryption)
   • 비대칭키 암호화 방식이 속도가 느리다는 점 때문에 실제 데이터 전송 과정에서는 대칭키 암호화가 사용된다.
   • 이 대칭키는 Handshake 과정에서 안전하게 교환된 세션 키다.
3. 해시 함수(Hash Function)
   • 데이터의 무결성을 확인하기 위해 사용한다.

2.2. 연결 과정

1. 클라이언트가 서버에 HTTPS 연결 요청
   • 사용자가 브라우저에 HTTPS URL을 입력하면, 브라우저는 서버에 연결을 요청한다.
   • 서버와 SSL/TLS는 연결을 설정하려고 시도한다.
2. 서버가 클라이언트에 SSL/TLS 인증서 전송
   • 서버의 공개키와 SSL 인증서의 유효성에 대한 정보를 포함한다.
3. 클라이언트가 인증서를 검증
   • SSL 인증서의 서명 및 기만 만료 여부 등을 판단하여 유효성을 판단한다.
   • 이 과정에서 문제가 발생하면, 브라우저는 보안 경고를 표시한다. (e.g. 인증서 만료, 유효하지 않음 등)
4. 세션 키 생성 및 교환(Handshake)
   • RSA, ECDHE 방식 중 하나로 세션 키를 안전하게 교환한다.
5. 대칭키 암호화로 데이터 전송
6. 해시 함수를 사용해 데이터 무결성 검증
   • HMAC(Hash-based Message Authentication Code) 등의 해시 함수를 사용한다.
7. 세션 종료 및 키 폐기
   • ECDHE 방식에서는 세션이 종료될 때 임시 키도 폐기되어 순방향 비밀성을 보장한다.

2.3. HTTPS로의 전환의 필요성

2.3.1. 보안

HTTPS는 HTTP와 달리 SSL/TLS 암호화를 사용하여 클라이언트(사용자)와 서버 간에 주고받는 모든 데이터를 암호화한다. 이를 통해 데이터는 기밀성이 보장되고, 무결성이 인증되며, 서버의 신원이 인증된다.

민감한 데이터, 예를 들어 로그인 정보, 신용카드 세부 정보, 개인 식별 정보 등을 안전하게 보호하는 데 필수적이다.

2.3.2. 신뢰성과 사용자 경험

보안 외에도 신뢰성과 사용자 경험을 개선하는 데 중요한 역할을 한다. 특히, 브라우저가 HTTP 사이트와 HTTPS 사이트를 다르게 처리하기 때문에 사용자에게 큰 영향을 미친다.

• 브라우저의 신뢰도 표시: HTTPS가 활성화된 웹 사이트는 브라우저 주소 표시줄에 자물쇠 아이콘이 표시된다. 이 아이콘은 사용자 웹 사이트가 안전하다는 것을 즉각적으로 인식할 수 있게 도움을 준다. 반대로, HTTP 웹 사이트는 ‘안전하지 않음’이라는 경고가 표시되며, 이는 사용자에게 부정적인 경험을 줄 수 있다.

  

• 브라우저 경고 메세지: 2021년 이후 대부분의 브라우저(크롬, 파이어폭스 등)는 HTTP로 연결된 웹 사이트에 대해 경고 메세지를 표시한다. 사용자에게 ‘이 웹 사이트는 안전하지 않습니다.’라는 메세지가 뜨면, 많은 사용자가 즉시 이탈하게 되어 웹 사이트 방문자 수가 급격히 줄어들 수 있다. 이러한 경고는 사용자에게 불안감을 주기 때문에, 신뢰도가 낮아지는 결과를 초래한다.

  

2.3.3. SEO(검색엔진최적화)

구글을 비롯한 주요 검색 엔진들은 웹 사이트의 HTTPS 여부를 순위 결정 신호로 사용하고 있다. 구글은 HTTPS를 웹 사이트의 보안성을 평가하는 중요한 요소로 간주하며, 이를 사용하지 않는 웹 사이트는 검색 결과에서 불리한 위치에 놓이게 된다.

Reference

• HTTP와 HTTPS 차이점
• [CS📖] HTTP와 HTTPS의 차이
• HTTPS란? – HTTP와의 차이점 및 전환의 중요성
• [Web] HTTP와 HTTPS의 개념 및 차이점

암호화는 데이터를 안전하게 전송하고 보관하기 위해 중요한 역할을 한다. 이 과정에서 데이터를 암호화하는 방식에는 대칭키 암호화와 공개키 암호화라는 두 가지 주요 방법이 있다. 이를 이해하려면 암호화의 기본 목적과 각각의 방식이 어떻게 작동하는지 알아볼 필요가 있다.

1. 배경

암호화는 데이터 전송 중에 외부 공격자가 내용을 엿보거나 변조하지 못하게 하기 위해 필요하다. 데이터는 송신자와 수신자 사이에서 주고받는 중에 공격자에게 노출될 수 있기 때문에, 데이터를 보호하기 위해 암호화를 통해 전송 데이터를 암호문으로 바꾸고, 수신자는 다시 이를 복호화해 원본 데이터를 복원한다.

암호화의 목적은 크게 다음과 같다:

1. 기밀성: 오직 허가된 사람만이 데이터를 읽을 수 있도록 함.
2. 무결성: 데이터가 변조되지 않았음을 보장함.
3. 인증: 송신자와 수신자가 서로의 신원을 확인함.
4. 부인 방지: 송신자가 나중에 자신이 보낸 데이터를 부인하지 못하도록 함.

이러한 목적을 달성하기 위해 다양한 암호화 방식이 개발되었고, 크게 대칭키 암호화와 공개키 암호화로 나뉜다.

2. 대칭키 암호화(Symmetric Key Encryption)

대칭키 암호화는 가장 오래된 암호화 방식 중 하나이다. 이 방식에서는 송신자와 수신자가 동일한 키를 사용하여 데이터를 암호화하고 복호화한다. 데이터를 암호화할 때 사용한 키가 데이터 복호화에도 사용되기 때문에, 이를 대칭키라고 부른다.

대칭키 암호화는 매우 빠르고, 대용량 데이터를 처리하는 데 적합하지만 키 교환 문제가 있다. 송신자와 수신자가 서로 안전한 방법으로 이 키를 공유해야 하는데, 네트워크를 통해 키를 교환하는 과정에서 키가 탈취될 위험이 있다. 사용자가 많아질수록 각각의 사용자와 키를 안전하게 관리하기가 어려워지며, 이러한 단점 때문에 주로 소규모 환경이나 안전한 키 교환 방법을 사용할 수 있을 때 사용된다.

2.1. 장점

대칭키 암호화는 암호화 및 복호화 속도가 매우 빠르며, 대용량 데이터를 처리하는 데 적합하다.

2.1.1. 대칭키 암호화의 기본 구조

대칭키 암호화는 단일 키를 사용하여 데이터를 암호화하고 복호화하는데, 이를 블록 단위로 처리하는 경우가 많다. 대칭키 알고리즘에서는 복잡한 수학 연산보다는 효율적인 비트 조작, 순환, 치환, XOR 연산 등이 많이 사용되기 때문에 빠른 속도를 유지할 수 있다.

2.1.2. 처리 방식

대칭키 암호화는 주로 블록 암호나 스트림 암호 방식을 사용한다.

• 블록 암호: 데이터를 일정한 크기의 블록(e.g. 64비트, 128비트)으로 나눈 뒤 각각의 블록에 동일한 연산을 적용한다. 이 방식은 연산 구조가 규칙적이기 때문에 대규모 병렬 처리가 가능해, 대용량 데이터를 빠르게 처리할 수 있다. AES와 DES가 대표적인 블록 암호 알고리즘이다.
• 스트림 암호: 데이터를 연속된 비트 단위로 처리하며, 하나씩 처리하므로 빠르고, 실시간 처리에 적합하다.

대칭키 알고리즘은 상대적으로 적은 연산 자원을 사용하므로, 소규모 장치나 네트워크 환경에서도 성능에 크게 부담을 주지 않는다. 이때문에 대칭키 암호화는 특히 대용량 처리에 적합하다.

2.2. 단점

키 교환 과정이 복잡하며, 사용자가 증가할수록 키 관리가 어려워진다. 키 교환 과정이 복잡하다는 의미는, 이 키가 노출되면 모든 보안이 무너질 수 있다는 것을 의미한다.

2.2.1. 안전한 키 전달의 어려움

대칭키 암호화에서 송신자가 수신자와 동일한 키를 사용하여 데이터를 암호화하고 복호화하기 때문에, 이 키를 사전에 안전하게 교환해야 한다. 문제는 네트워크 상에서 이 키가 탈취되면, 공격자가 데이터를 쉽게 복호화할 수 있다는 것이다.

예를 들어 송신자가 수신자에게 키를 전달하는 과정에서 중간자 공격(Man-in-the-middle attack)이 발생할 수 있다. 공격자가 키 교환 과정을 가로채면, 전송되는 모든 데이터를 복호화할 수 있게 된다.

🔖 신뢰할 수 있는 경로의 필요성

키를 전달하기 위해서는 신뢰할 수 있는 물리적 경로나 암호화된 통신 경로가 필요하다. 하지만 이 경로를 사전에 설정하기 어렵거나 불가능할 때 문제가 발생한다.

2.2.2. 사용자 증가에 따른 관리 복잡성

대칭키 암호화에서는 모든 사용자 간에 각각의 키를 관리해야 한다. 사용자가 2명일 때는 하나의 키만 관리하면 되지만, 사용자가 3명이면 서로 간에 3개의 키가 필요하고, 4명이면 6개의 키, 5명이면 10개의 키가 필요하다.

이를 일반화하면, 사용자 수가 $N$명일 때, $N(N-1)/2$개의 키가 필요하다. 사용자가 많아질수록 관리해야 할 키의 수가 기하급수적으로 증가하기 때문에, 이를 안전하게 관리하는 것이 매우 어려워진다.

2.2.3. 키 합의 프로토콜의 필요성

대칭키 암호화를 안전하게 사용하기 위해 안전하지 않은 네트워크에서도 안전하게 키를 교환할 수 있는 방법을 고안했고, 이를 키 합의 프로토콜이라고 한다. 대표적인 키 합의 프로토콜은 RSA와 Diffie-Hellman 기반의 키 교환이다.

2.3. 대표 알고리즘

AES, DES, 3DES, ChaCha20, SEED, ARIA

2.4. 보장 기능

대칭키 암호화는 데이터를 외부로부터 보호하는 데 탁월하지만, 무결성이나 인증 기능을 제공하지 않는다. 즉, 데이터가 변조되지 않았는지 확인하거나, 송신자의 신원을 보증하는 기능이 부족하다.

3. 공개키 암호화(Asymmetric Key Encryption)

공개키 암호화는 대칭키의 키 관리 문제를 해결하기 위해 등장한 방식이다. 비대칭 키 암호화라고도 불리는 이 방식은 서로 다른 두 개의 키, 즉 공개키와 개인키를 사용한다. 공개키는 누구에게나 공개될 수 있지만, 개인키는 비밀로 유지되어야 한다.

이 방식의 핵심은 한 쪽의 키로 암호화하면, 반대쪽 키로만 복호화할 수 있다는 것이다. 예를 들어, 송신자는 수신자의 공개키로 데이터를 암호화하고, 수신자는 자신의 개인키로 이를 복호화한다. 이를 통해 키 교환 과정에서 발생할 수 있는 보안 문제를 해결할 수 있다.

공개키 암호화는 대칭키 암호화보다 느리지만, 키 관리가 매우 용이하여 다양한 보안 기능을 제공한다. 이를 통해 기밀성뿐만 아니라 인증, 부인 방지 등의 기능도 제공할 수 있다.

3.1. 장점

3.1.1. 키 관리 용이성

대칭키 암호화의 가장 큰 문제점은 키 교환이었다. 송신자와 수신자가 동일한 키를 사용해야 하기 때문에, 이 키를 서로 안전하게 전달해야 한다. 하지만 공개키 암호화 방식에서는 이런 문제를 크게 줄일 수 있다.

• 공개키: 공개키는 누구나 사용할 수 있기 때문에, 키를 미리 교환할 필요가 없다. 이렇게 키가 노출되더라도 개인키가 안전하게 보호되는 한, 보안에는 문제가 없다.
• 개인키: 공개키는 누구에게나 배포할 수 있지만, 개인키는 송신자 혹은 수신자만이 소유하는 비밀 키다. 이 개인키는 절대 다른 사람과 공유되지 않기 때문에, 키 교환 과정에서 발생할 수 있는 공격을 방지할 수 있다.

  즉, 공개키는 네트워크 상에 공개적으로 배포될 수 있고, 악의적인 사용자도 이를 가질 수 있지만, 그 자체로는 보안에 영향을 미치지 않으므로 대규모 환경에서도 키 관리가 쉬워진다. 대칭키 암호화에서는 사용자마다 각각의 키를 관리해야 하는 복잡성이 있지만, 공개키 암호화에서는 사용자별로 하나의 공개키와 개인키만 관리하면 된다. 사용자가 늘어나도 추가적인 키 교환이 필요 없기 때문에 확장성이 뛰어나다.

3.1.2. 다양한 보안 기능

공개키 암호화는 단순한 기밀성뿐만 아니라 인증, 부인 방지 등 다양한 보안 기능을 제공한다. 이들은 모두 암호화의 핵심 보안 요소들이다.

• 기밀성: 송신자는 수신자의 공개키로 데이터를 암호화하고, 수신자는 개인키로 이를 복호화한다. 중간에 공격자가 데이터를 가로채더라도 개인키가 없으면 복호화할 수 없다. 이는 송신된 정보가 비밀로 유지될 수 있음을 의미한다.
• 인증: 공개키 암호화는 자신이 누구인지 증명하는 데 사용할 수 있다. 송신자가 자신의 개인키로 데이터를 암호화하면, 수신자는 그 데이터를 해당 송신자의 공개키로만 복호화할 수 있다. 공개키로 복호화가 가능다하면 그 데이터는 해당 개인키 소유자, 즉 송신자만이 암호화할 수 있다는 것이 보장되기 때문에 송신자가 개인키를 소유한 진짜 사용자임을 인증할 수 있다.
• 부인 방지: 송신자가 데이터를 보낸 후에 이를 부인할 수 없게 만든다. 송신자가 개인키로 서명한 데이터는 해당 개인키에 대응하는 공개키로만 검증할 수 있기 때문에, 송신자가 나중에 “내가 보낸 데이터 아닌데?”라고 주장할 수 없다. 이는 법적 책임을 보장하는 중요한 기능이다.

3.2. 단점

암호화 및 복호화 속도가 느리다. 따라서 대용량 데이터 암호화보다는 소량 데이터 암호화나 대칭키 교환에 사용되는 경우가 많다.

3.2.1. 단방향 연산의 복잡성

공개키 암호화 알고리즘은 대부분 소수 분해, 이산 로그 문제, 타원 곡선 연산 등의 매우 복잡한 수학적 원리를 담은 단방향 함수를 사용한다. 이러한 연산은 계산량이 매우 크고, 컴퓨터에서 처리하는 데 시간이 많이 걸린다.

• RSA 알고리즘:
  • 암호화(쉬운 연산): 두 개의 큰 소수를 곱하여 하나의 큰 수를 만든다.
  • 복호화(어려운 연산): 이 큰 수에서 다시 두 소수로 분해하는 것은 까다롭다. 이 문제는 소인수 분해 문제로 불리며, 현재 컴퓨터 성능으로는 매우 오랜 시간이 걸릴 수 있다.
• ECC(타원 곡선 암호화):
  • 암호화(쉬운 연산): 타원 곡선의 한 점을 기반으로 연산을 수행하여 암호화한다.
  • 복호화(어려운 연산): 타원 곡선의 한 점을 사용하여 다시 원래의 값을 추정하는 것은 이산 로그 문제로, 시간이 많이 소요된다. 이 문제는 현재 알고리즘으로는 효율적인 해법이 없기 때문에 높은 보안성을 제공한다.

3.2.2. 비트 크기

공개키 암호화에서는 높은 보안 수준을 유지하기 위해 긴 비트 크기의 키를 사용한다. 예를 들어, RSA 알고리즘에서는 안전성을 확보하기 위해 최소 2048비트 이상의 키를 사용하는 것이 권장된다. 이와 비교해 대칭키 암호화에서는 128비트, 256비트 정도의 키가 주로 사용된다.

3.3. 사용 사례

3.3.1. 소량 데이터 암호화

공개키 암호화는 대용량 데이터를 처리하는 데는 부적합하지만, 소량의 중요한 정보를 처리하는 데에는 매우 유용하다.

예를 들어, 은행 계좌 정보, 비밀번호, 인증 정보 등 중요한 정보를 안전하게 암호화하는 데 사용된다. 이러한 소량의 데이터를 처리할 때는 공개키 암호화의 속도 저하가 크게 문제되지 않기 때문에, 안전성과 보안성을 우선할 수 있다.

3.3.2. 대칭키 교환

공개키 암호화는 대칭키 교환에 매우 자주 사용된다. 대칭키 암호화는 빠르지만 키 교환 과정에서 보안 문제가 발생할 수 있기 때문에, 공개키 암호화를 사용하여 대칭키(세션 키)를 안전하게 교환한 후, 대칭키로 실제 데이터를 암호화하는 방식이 일반적이다.

이 과정은 다음과 같다.

1. 송신자가 수신자의 공개키로 대칭키를 암호화하여 전송한다.
2. 수신자는 자신의 개인키로 대칭키를 복호화한다.
3. 이렇게 공유된 대칭키를 사용하여, 송신자와 수신자는 빠른 대칭키 암호화 방식을 사용해 대용량 데이터를 암호화하고 주고받는다.

e.g. 웹에서 HTTPS 통신을 할 때 SSL/TLS 프로토콜은 공개키 암호화를 사용하여 대칭키를 안전하게 교환한 후, 그 대칭키로 실제 통신 데이터를 암호화한다. 이를 통해 보안성과 속도 모두를 확보할 수 있다.

3.4. 대표 알고리즘

• RSA: 대표적인 공개키 암호화 방식으로 많이 사용된다.
• Diffie-Hellman: 최초의 공개키 알고리즘이나, 위조에 취약하다.
• ECC: 짧은 키로 높은 보안 강도를 제공하며, 모바일 기기 등에 적합하다.
• DSA: 전자서명 표준 알고리즘

4. 디지털 인증서와 공개키 인프라(PKI)

공개키 암호화는 키 관리가 용이하지만, 한 가지 문제점이 있다. 송신자가 받은 공개키가 정말 수신자의 공개키인지 확신할 방법이 필요하다. 이를 위해 디지털 인증서와 공개키 인프라(PKI)가 사용된다.

디지털 인증서는 신뢰할 수 있는 제3자인 CA(Certificate Authority)가 발급한다. 공개키 교환 절차는 다음과 같다.

1. B는 자신의 공개키를 CA에 제출하여, 그 키가 자신에게 속한다는 인증서를 발급받는다.
2. B의 인증서를 A에게 보낸다. 이 인증서에는 B의 공개키가 포함되어 있다.
3. A는 CA의 공개키로 B의 인증서를 검증하고, 서명이 유효하다면 인증서 안의 B의 공개키를 사용한다.
4. 이제 A는 B의 공개키를 사용해 안전하게 통신을 시작할 수 있다.

5. 기밀성 보장을 위한 노력

앞서 설명한 바와 같이 대칭키를 안전하게 공유할 수 있는 방법에 대한 필요성으로 키 합의 프로토콜이 등장했다. 대표적인 키 합의 프로토콜에 대해 알아보자.

5.1. RSA 키 합의 프로토콜

비대칭키 암호화인 RSA를 사용한 키 합의 프로토콜이다.

앨리스는 앞으로 통신에 사용할 세션키를 만들어서 이를 밥의 공개키로 암호화한 다음 밥에게 전송한다. 밥은 자신의 개인키로 암호화된 세션키를 복호화해 사용한다.

문제점은 이 방식에서는 순방향 비밀성이 보장되지 않는다는 것이다.

순방향 비밀성(Forward Secrecy)이란, 미래에 개인키가 유출되더라도, 과거의 세션 내용은 복호화할 수 없도록 보장하는 것이다. 하지만 RSA 방식에서는 만약 공격자가 이후에 밥의 개인키를 탈취하면, 이전 통신에서 사용한 세션키를 복호화하여 모든 과거의 통신 내용을 해독할 수 있게 된다.

5.2. Diffie-Hellman 키 합의 프로토콜

디피-헬만 키 교환은 순방향 비밀성을 제공하는 대표적 키 합의 프로토콜이다. 이 프로토콜은 암호화되지 않은 공용 채널에서도 안전하게 대칭키를 생성하고 교환할 수 있도록 설계되었다.

1. 기저키 선택: 앨리스와 밥은 서로 통신에 사용할 기저키(공용 값)를 공개적으로 선택한다. 이 기저키는 노출되어도 상관 없다.
2. 개인키 설정: 앨리스와 밥은 각각 자신만 아는 비밀키를 정한다.
3. 공유 정보 생성: 앨리스와 밥은 각자의 비밀키와 기저키를 조합하여 중간 값을 계산하고, 그 값을 서로에게 전송한다.
4. 최종 키 계산: 앨리스는 밥의 중간 값에 자신의 비밀키를 추가로 조합하여 최종 공유 키를 계산하고, 밥도 마찬가지로 앨리스의 중간 값에 자신의 비밀키를 추가하여 같은 최종 공유 키를 계산한다.
5. 비밀키 삭제: 세션이 끝나면 앨리스와 밥은 각자의 비밀키를 즉시 폐기한다.

설사 나중에 공격자가 밥의 개인키를 탈취하더라도, 그로부터 얻을 수 있는 정보는 세션키를 만들기 위한 단서(힌트) 정도일 뿐, 실제 세션키나 과거의 통신키 내용을 복호화할 수는 없다.

6. 무결성 보장을 위한 노력

무결성을 보장하기 위해서는 데이터가 전송 중에 손상되거나 변경되었는지를 확인할 수 있어야 한다. 이를 위해 주로 해시 함수와 메세지 인증 코드(MAC)가 사용된다.

6.1. 해시 함수(Hash Function)

해시 함수는 임의의 길이를 가진 데이터를 일정한 길이의 고정된 값으로 변환하는 함수이다. 이 고정된 값이 바로 해시 값 또는 해시라고 불린다.

6.1.1. 암호학적 해시 함수의 특징

암호학적으로 안전한 해시 함수는 다음과 같은 특성을 가져야 한다.

1. 단방향성: 해시 값만 보고 원래 입력 데이터를 알아내는 것이 불가능하거나 매우 어렵다.
2. 충돌 회피: 동일한 해시 값을 가지는 서로 다른 데이터(충돌)를 찾는 것이 매우 어렵다.
3. 민감도: 입력 데이터에서 단 1비트라도 변경되면 완전히 다른 해시 값이 출력된다.

e.g. SHA-256: 매우 널리 사용되는 암호학적 해시 함수이다. 256비트(32바이트)의 해시 값을 생성하며, 블록 체인 기술에서도 많이 사용된다.

6.1.2. 해시 함수의 역할

데이터를 송신할 때, 데이터의 해시 값을 함께 전송하여 수신자가 이를 검증할 수 있게 한다. 수신자가 데이터의 해시 값을 재계산하고 송신자가 보낸 해시 값과 비교하여 데이터가 변조되었는지 확인할 수 있다.

만약 두 해시 값이 다르면 데이터가 전송 중에 손상되었거나 변경된 것이다.

6.1.3. 문제점

해시 함수는 데이터가 변경되었는지 여부를 판단할 수는 있지만, 누가 데이터를 변경했는지 확인할 수는 없다. 즉, 악의적인 공격자가 데이터를 변경한 후 새로운 해시 값을 생성하여 위조할 수 있다.

따라서 해시 함수만으로는 완전한 무결성을 보장하기 어렵다. 이를 보완하기 위해 사용하는 것이 키가 포함된 해시 함수, 즉 메세지 인증 코드(MAC)이다.

6.2. 메세지 인증 코드(MAC: Message Authentication Code)

메세지 인증 코드는 대칭키 암호화와 해시 함수를 결합한 방식으로, 메세지의 무결성과 인증을 동시에 제공한다. MAC은 송신자가 데이터를 변조하지 않도록 보호하고, 수신자는 해당 데이터가 변조되지 않았는지, 그리고 인증된 송신자로부터 온 것인지 확인할 수 있다.

MAC은 단순 해시 함수와 달리, 송신자와 수신자가 미리 공유한 대칭키를 사용하여 생성한다. 대칭키는 송신자와 수신자만이 알고있기 때문에, 제3자가 이 키를 모르면 MAC 값을 생성하거나 변조할 수 없다.

6.2.1. 인증 과정

1. 키 공유: 송신자 앨리스와 수신자 밥은 미리 공유된 대칭키를 가지고 있다.
2. MAC 값 생성: 송신자 앨리스는 메세지와 대칭키를 결합하여 MAC 값을 계산한다. 이를 해시 값과 비슷하게 생각할 수 있다.
3. 메세지 전송: 앨리스는 메세지와 함께 MAC 값을 수신자 밥에게 전송한다.
4. MAC 검증: 밥은 메세지와 미리 공유된 대칭키를 사용하여 MAC 값을 재계산한 후, 앨리스가 보낸 MAC 값과 비교한다.
5. 무결성 및 인증 확인: 두 MAC 값이 같다면 데이터가 변조되지 않았고, 해당 데이터가 앨리스로부터 온 것임을 확인할 수 있다.

6.2.2. 장점

• 무결성 보장: 메세지가 전송 중 변경되었을 경우, 수신자가 이를 쉽게 알아낼 수 있다.
• 인증 기능: 송신자와 수신자가 사전에 공유된 키를 사용하기 때문에, 수신자는 이 메세지가 진짜 송신자로부터 온 것임을 확인할 수 있다.
• 안전성: MAC 값은 대칭키를 사용하여 계산되므로, 공격자가 대칭키를 알지 못하면 MAC 값을 위조할 수 없다.

Reference

• 대칭키 vs 공개키(비대칭키)

1.1. IP(Internet Protocol)의 한계

IP는 인터넷에서 Host to Host 간의 데이터를 전달하는 기본적인 프로토콜이다. 여기서 중요한 점은, IP는 데이터가 목적지에 도착할 때까지의 경로를 책임지는 역할은 하지만, 그 이후에 수많은 프로그램들이 어떻게 통신할지에 대한 정보는 제공하지 않는다는 것이다.

즉, IP는 장비 간의 통신만을 지원할 뿐, 그 장비 내부에서 어떤 애플리케이션이 데이터를 받을지에 대한 처리를 할 수 없다.

🚨 ICMP(Internet Control Message Protocol)와 IP의 오류 처리

IP가 제공하는 통신 과정에서 오류가 발생할 때는 ICMP가 오류를 알려준다. 예를 들어, 목적지에 데이터가 도착하지 못했거나, 라우터에서 문제가 발생하면 ICMP는 송신 측에 오류 메세지를 보내 네트워크 문제를 감지하게 한다.

하지만, ICMP는 그저 오류를 알리는 역할만 할 뿐, 문제를 해결하거나 데이터를 재전송하는 등의 대처는 하지 못한다.

1.2. 포트 번호와 상위 프로토콜의 등장

1.2.1. 포트 번호(Port Number)

여러 애플리케이션이 한 장비 안에서 동시에 통신하는 상황을 해결하기 위해 등장한 개념이 포트 번호다.

IP는 장치 간의 통신만 해결할 수 있기 때문에, 장비 내부에서 어떤 애플리케이션이 데이터를 받을지 식별하기 위해 포트 번호가 필요하다. 이를 통해 같은 장치 내에서 여러 프로그램이 동시에 네트워크 통신을 할 수 있게 되었다.

1.2.2. TCP와 UDP

TCP와 UDP는 IP 위에서 동작하는 전송 계층 프로토콜이다. 이 프로토콜들이 등장한 이유는 오류 처리와 프로그램 간의 데이터 통신을 좀 더 효율적으로 하기 위해서다.

• TCP(Transmission Control Protocol): 신뢰성 있는 데이터 전송을 보장한다. 데이터 분실, 중복, 순서 뒤바뀜 등을 해결해 송신 측에서 수신 측으로 정확하게 데이터를 전달할 수 있도록 한다. 이를 위해 연결 설정(3-Way Handshake), 재전송, 흐름 제어, 혼잡 제어와 같은 복잡한 메커니즘을 사용한다.
• UDP(User Datagram Protocol): 간단한 IP 상위 계층 프로토콜로, TCP와 달리 에러 처리나 재전송을 하지 않는다. 즉, UDP는 데이터 전송 시 오류가 발생할 수 있고, 순서가 뒤바뀔 수 있으며, 신뢰성이 보장되지 않지만 그만큼 빠르고 간단하게 데이터를 전송할 수 있다.

2. UDP(User Datagram Protocol)

TCP와 UDP의 등장 배경을 살펴봤으니, 오늘은 UDP에 대해 알아보자.

UDP는 TCP와 함께 OSI 모델 4계층인 전송 계층에 포함되는 프로토콜이다. IP를 사용하는 네트워크 내에서 컴퓨터 간 메시지들이 교환될 때 제한된 서비스만 제공하는 프로토콜이다.

UDP는 데이터를 전송할 때 IP 프로토콜을 통해 데이터그램이라는 단위로 데이터를 전송한다. TCP와 달리 메시지를 데이터그램으로 나누고, 반대편에서 재조립, 순서 조정 등의 서비스는 하지 않는다.

UDP는 IP 계층에서 제공하지 않는 서비스도 제공하는데, IP 내 사용자 구분을 위한 포트 번호 부여와 데이터 손상 여부 확인에 쓰이는 체크섬 서비스다.

2.1. 특징

• 비연결형(Connectionless): TCP처럼 연결을 설정하지 않고, 데이터를 보내기 전에 세션을 확립하지 않는다. 송신자는 데이터를 바로 전송하고, 수신자는 받는 즉시 처리한다.
• 빠른 속도: 연결 설정이나 오류 제어 같은 추가 작업이 없기 때문에 데이터 전송 속도가 빠르다. 실시간 응답이 필요한 애플리케이션에서 많이 사용된다.
• 신뢰성 없음: TCP와 달리 데이터 전송의 신뢰성을 보장하지 않는다. 즉, 패킷이 손실되거나, 순서가 바뀌거나, 중복되더라도 UDP는 이를 감지하지도, 처리하지도 않는다. 오류 처리는 애플리케이션이 직접 해야한다.
• 작은 오버헤드: TCP보다 헤더가 간단해서 네트워크에 부하를 덜 주고, 자원 소모가 적다.

2.2. UDP를 사용하는 이유

2.2.1. 데이터의 신속성

UDP의 가장 큰 장점은 데이터 전송의 신속성이다. TCP는 연결 설정과 확인 응답, 흐름 제어 등의 과정을 거쳐야 하기 때문에 전송 속도가 느리지만, UDP는 이런 과정 없이 데이터를 바로 전송하므로 빠르게 데이터를 주고받을 수 있다.

이로 인해 실시간 통신이 중요한 상황(e.g. 실시간 스트리밍, 온라인 게임 등)에서 UDP가 많이 사용된다.

2.2.2. DNS에서의 UDP

DNS(Domain Name System)는 도메인 이름을 IP 주소로 변환하는 작업을 하는데, 이때 UDP를 사용한다.

DNS 쿼리와 응답은 대부분 짧은 데이터이지만, 매우 많은 요청이 들어온다. UDP는 TCP와 달리 오버헤드가 적고, 데이터를 전송하기 위한 세션 확립 과정이 없기 때문에, 빠르게 요청과 응답을 처리하고 네트워크 리소스를 절약할 수 있다.

하지만, 512바이트를 넘는 데이터를 전송하거나 DNS 서버 간의 영역 전송(Zone Transfer) 같은 작업을 할 때는 TCP를 사용한다. TCP는 더 큰 데이터 전송이나 신뢰성이 중요한 작업에 적합하다.

2.3. 헤더 구조

UDP는 간단한 프로토콜이기 때문에 헤더도 매우 단순하다. 헤더는 총 8바이트로, 아래와 같이 구성된다.

• Source Port(2바이트): 송신 측의 포트 번호
• Destination Port(2바이트): 수신 측의 포트 번호
• Length(2바이트): 전체 UDP 패킷의 길이(헤더와 데이터 포함)
• Checksum(2바이트): 오류 검출을 위한 값(필수는 아님)

Reference

• 그림으로 쉽게 보는 TCP

이 기능들 덕분에 네트워크에서 발생할 수 있는 문제를 TCP가 알아서 처리해주기 때문에 상위 레이어, 즉 애플리케이션 개발자는 복잡한 네트워크 상황을 신경 쓸 필요가 없다.

1. 흐름 제어(Flow Control)

흐름 제어는 송신 측과 수신 측의 데이터 처리 속도를 맞추기 위한 장치이다. 송신 측이 데이터를 너무 빨리 보내면 수신 측의 버퍼가 꽉 차서 데이터를 제대로 처리하지 못할 수 있다. 이때 발생하는 문제가 오버플로우(Overflow)다. 이를 막기 위해 TCP는 윈도우 크기(Window Size)를 통해 송신 측이 보낼 수 있는 데이터 양을 조절한다.

윈도우 크기는 수신 측이 자신의 버퍼에서 처리할 수 있는 데이터의 양을 송신 측에 전달하는 정보다. 그래서 송신 측은 이 정보를 바탕으로 한 번에 얼마나 데이터를 보낼지 결정한다.

1.1. Stop and wait 방식

가장 단순한 흐름 제어 방식은 Stop-and-Wait 방식이다. 송신 측이 데이터를 보낸 후, 수신 측의 응답(ACK)를 기다렸다가 다음 데이터를 전송하는 방식이다.

기본적인 ARQ(Automatic Repeat Request)를 구현한다고 생각해 보면, 수신 측의 윈도우 크기를 1 byte로 설정하고 처리 가능 = 1, 처리 불가능 = 0과 같은 식으로 대충 구현해도 돌아가기는 한다.

이 방식은 매우 간단한 만큼 비효율적이다. 송신 측이 자신의 데이터를 직접 보내봐야 이 데이터를 수신 측이 처리할 수 있는지 알 수 있기 때문이다.

이때문에 Stop and Wait 방식을 사용해 흐름 제어를 할 경우에는, 이런 비효율성을 커버하기 위해 이런 단순한 구현이 아닌 여러 가지 오류 제어 방식을 함께 도입해 사용한다.

1.2. Sliding Window 방식

그렇기에 더 효율적인 방식인 Sliding Window가 등장한다. Sliding Window는 수신 측이 자신이 한 번에 받을 수 있는 데이터 양(윈도우 크기)을 송신 측에 알려주고, 송신 측은 그 범위 안에서 여러 개의 데이터를 한 번에 보낼 수 있다.

e.g. 수신 측이 한 번에 5개의 패킷을 처리할 수 있다면 송신 측은 응답을 기다리지 않고 5개의 패킷을 연달아 보낸다.

윈도우 안에 들어있는 프레임은 수신 측의 응답이 없어도 연속으로 보낼 수 있다.

송신 측의 윈도우 크기는 맨 처음 TCP의 연결을 생성하는 과정인 3-Way Handshake 때 결정된다. 이때 송신 측과 수신 측은 자신의 현재 버퍼 크기를 서로에게 알려주게 되고, 송신 측은 수신 측이 보내준 버퍼 크기를 사용해 자신의 윈도우 크기를 정하게 된다.

localhost.initiator > localhost.receiver: Flags [S], seq 1487079775, win 65535
localhost.receiver > localhost.initiator: Flags [S.], seq 3886578796, ack 1487079776, win 65535
localhost.initiator > localhost.receiver: Flags [.], ack 1, win 6379

tcpdump를 통해 3-Way Handshake를 관찰해 보자. 처음 SYN과 SYN+ACK 패킷에는 각자 자신의 버퍼를 알려준 후 마지막 ACK 패킷 때 송신 측이 자신이 정한 윈도우 사이즈를 수신 측에 통보한다.

이때 송신, 수신 측 모두 자신의 버퍼 크기를 65535라고 했지만 최종적으로 송신 측이 정한 윈도우 크기는 6379이다. 왜 송신 측은 수신 측 버퍼 크기의 10분의 1로 자신의 윈도우 크기를 정한 것일까?

송신 측의 윈도우 크기는 수신 측의 버퍼 크기로만 정하는 것이 아니라 다른 여러 가지 요인들을 함께 고려해 결정되기 때문이다. 네트워크 상태에 따라, 예를 들어 패킷 왕복 시간(Round Trop Time, RTT)이 길어지거나 네트워크가 혼잡하다고 판단되면, 송신 측은 윈도우 크기를 줄여서 네트워크에 부담을 덜 주도록 조절할 수 있다.

이때 정해진 윈도우 크기는 통신을 하는 과정 중간에도 계속해서 네트워크의 혼잡 환경과 수신 측이 보내주는 윈도우 크기를 통해 동적으로 변경될 수 있다.

🪟 이름이 왜 Sliding Window인가?

먼저, 송신 측이 0~6번의 시퀀스 번호를 가진 데이터를 상대방에게 전송하고 싶어하는 상황을 생각해 보자. 이때 송신 측의 버퍼에는 전송해야 할 데이터들이 아래와 같이 담겨져 있을 것이다.

이때 송신 측은 수신 측에게 받은 윈도우 크기와 현재 네트워크 상황을 고려하여 윈도우 크기를 3으로 잡았고, 윈도우 안에 있는 데이터를 순차적으로 전송한다.

송신 측이 데이터를 전송했을 때, 그 데이터가 수신 측에 도착했는지, 혹은 수신 측이 잘 처리했는지 여부는 아직 모르는 상태이다. 이 상황에서 송신 측의 윈도우에는 이미 전송한 데이터들이 남아있지만, 응답(ACK)을 받기 전까지는 여전히 확인되지 않은 상태인 것이다.

이처럼 윈도우 안에 있는 데이터들은 모두 전송이 끝났지만, 아직 수신 측이 응답을 보내지 않았기 때문에 “불확실한” 상태로 남아있다. 이 점이 슬라이딩 윈도우의 중요한 포인트 중 하나다. 즉, 송신 측은 항상 여러 개의 데이터를 보내면서도 그 데이터들이 실제로 전송이 완료되었는지 여부는 나중에 확인해야 한다.

이제 수신 측이 데이터를 처리한 후, 응답(ACK)을 보내면서 “나 윈도우 크기 1만큼 남았어”라는 메세지를 보낸다고 가정해 보자. 이때 송신 측은 그 메세지를 받고 나서, 윈도우를 한 칸 오른쪽으로 밀어서 새롭게 들어온 데이터를 보낼 준비를 한다.

이 과정이 슬라이딩 윈도우에서 중요한 “슬라이딩” 동작이다. 윈도우가 한 칸씩 옆으로 밀리면서 새로운 데이터를 전송한다. 예를 들어, 송신 측은 이제 3번 데이터를 윈도우에 넣고 전송할 수 있게 된다.

단, 이 경우 송신 측의 윈도우 크기가 3이기 때문에 수신 측이 4를 보냈다고 해서 4칸을 밀지는 않고, 자신의 윈도우 크기인 3만큼만 밀 수 있다. 그러나 이 경우에는 송신 측이 수신 측의 퍼포먼스가 더 좋아졌다는 것을 알았으니 자신의 윈도우 크기를 늘리는 방법으로 대처할 수 있을 것이다.

즉, 슬라이딩 윈도우 방식은 보내고→응답 받고→윈도우 밀고를 반복하면서, 현재 자신이 보낼 수 있는 데이터를 최대한 연속적으로 보내는 방법이라고 할 수 있다.

2. 오류 제어(Error Control)

TCP는 데이터가 손상되거나 유실되는 것을 허용하지 않는다. 네트워크 통신에서 오류가 발생하면, 이를 감지하고 다시 데이터를 전송하는 방식으로 오류를 처리한다. 이를 재전송 기반 오류제어, ARQ(Automatic Repeat Request)라고 부른다.

패킷 기반 전송을 하는 TCP의 특성 상 각 패킷의 도착 순서가 무조건 보장되는 것이 아니기에, 중복된 ACK를 보통은 3회 정도 받았을 때 에러라고 판별한다.

즉, 데이터를 제대로 받지 못했으면 그 데이터를 다시 보내달라고 요청하는 방식이다. 이 방식이 TCP가 신뢰성을 제공하는 핵심 이유이다.

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

🚨 오류가 발생했다는 걸 확인하는 방법

TCP를 사용하는 송수신 측이 오류를 파악하는 방법은 크게 두 가지로 나누어진다.

수신 측이 송신 측에게 명시적으로 NACK(부정응답)을 보내는 방법, 그리고 송신 측에게 ACK(긍정응답)가 오지 않거나, 중복된 ACK가 계속해서 오면 오류가 발생했다고 추정하는 방법이다.

간단히 생각해 보면 NACK을 사용하는 게 훨씬 명확하고 간단할 것 같지만, NACK을 사용하게 되면 수신 측이 상대방에게 ACK을 보낼지 NACK을 보낼지 선택해야 하는 로직이 추가적으로 필요하기 때문에, 일반적으로는 ACK만을 사용해 오류를 추정한다.

2.1. Stop and Wait

가장 기본적인 오류 제어 방식이다. 송신 측은 데이터를 하나 보낸 뒤, ACK를 기다린다. 만약 일정 시간 안에 ACK가 오지 않으면, 송신 측은 해당 데이터를 다시 보낸다.

흐름 제어의 Stop and Wait 때 한 번 살펴본 방식인데, 이 방식만으로 흐름 제어와 오류 제어가 동시에 가능하다. 그러나 위에서 살펴본 슬라이딩 윈도우를 사용하여 흐름 제어를 하는 경우에는 윈도우 안에 있는 데이터를 연속적으로 보내야 하기 때문에, 오류 제어에 Stop and Wait를 사용해 버리면 슬라이딩 윈도우를 사용하는 이점을 잃어버린다.

그런 이유로 일반적으로 이런 단순한 방법보다 조금 더 효율적이도 똑똑한 ARQ를 사용한다.

2.2. Go Back N

더 발전된 방식이 Go Back N ARQ이다. 송신 측은 여러 데이터를 연속적으로 보낼 수 있는데, 만약 중간에 하나의 패킷이 손실되면 그 이후에 보낸 모든 데이터를 다시 보내는 방식이다.

e.g. 1, 2, 3, 4번 데이터를 보냈는데, 4번 데이터가 손실되었다면, 4번부터 그 이후 모든 데이터를 재전송한다.

이미 성공적으로 전송된 데이터까지 다시 보내기 때문에 조금 비효율적이긴 하다.

2.3. Selective Repeat

그래서 나온 방식이 Selective Repeat ARQ이다. Go Back N과 달리 손실된 데이터만 다시 보내는 방식이다.

e.g. 1, 2, 3, 4번 중 3번 데이터만 손실되었다면, 3번 데이터만 다시 보내면 된다.

하지만 이 방식은 수신 측에서 데이터를 정렬할 별도의 버퍼가 필요하고, 데이터가 순차적으로 오지 않을 수 있기 때문에 약간의 복잡성이 추가된다.

3. 혼잡 제어(Congestion Control)

혼잡 제어는 네트워크에서 혼잡 상태를 파악하고 이를 해결하기 위해 데이터 전송을 조절하는 기법이다. 네트워크는 워낙 광대하고 블랙박스 같은 특성을 갖고 있어서, 어디에서 어떤 이유로 전송이 느려지는지 정확하게 파악하기 어렵다.

하지만 데이터 전송이 느려지는 현상 자체는 송신 측에서 쉽게 감지할 수 있다. 예를 들어, 데이터를 보냈는데 상대방으로부터 응답이 늦게 오거나 아예 안 오면 문제가 발생했다는 걸 알 수 있듯 말이다.

이때 흐름 제어나 오류 제어 기법만 사용하면 재전송이 계속 반복될 수밖에 없다. 한두 번의 재전송은 큰 문제가 아니겠지만, 네트워크가 여러 사람들이 함께 사용하는 공간이기 때문에, 이런 재전송이 여러 곳에서 발생하면 네트워크가 심각하게 혼잡해질 수 있다. 이것을 혼잡 붕괴라고 한다.

따라서 네트워크의 혼잡이 감지되면 최악의 상황을 피하기 위해 송신 측은 혼잡 윈도우(CWND)의 크기를 줄여 데이터를 덜 보내는 방식으로 대응한다. 이 과정이 바로 혼잡 제어다.

🪟 혼잡 윈도우(Congestion Window, CWND)

혼잡 제어에서 중요한 개념인 혼잡 윈도우는 송신 측이 네트워크의 혼잡 상태를 고려해 정하는 윈도우 크기를 의미한다. 송신 측은 데이터를 보낼 때 수신 측에서 보내준 수신 윈도우(RWND)와 자신이 결정한 혼잡 윈도우 중 더 작은 값을 사용한다. 즉, 송신 윈도우 크기가 이 두 값에 의해 결정된다.

혼잡 윈도우는 네트워크 상황을 반영해 계속 변화하는데, 여기서 조정하는 건 송신 윈도우가 아니라 송신 측의 혼잡 윈도우다.

3.1. 혼잡 회피 방법

TCP 혼잡 제어 정책들은 혼잡 상태를 감지하는 방법과 혼잡 윈도우 크기를 조절하는 방식을 점차 발전시켜 왔다. 그 기본은 AIMD와 Slow Start라는 두 가지 기법을 상황에 맞게 조합해 사용하는 방식이다.

3.1.1. AIMD(Additive Increase/Multiplicative Decrease)

AIMD는 패킷을 처음 보낼 때 하나씩 보내고, 문제가 발생하지 않으면 전송 속도를 서서히 증가시키는 방식이다. 전송 속도는 1씩 추가적으로 늘어나고(Additive Increase), 만약 패킷 전송에 실패하면 전송 속도를 절반으로 줄인다.(Multiplicative Decrease) 이렇게 하면 전송 속도가 네트워크 상태에 따라 서서히 안정되는 균형점에 도달한다.

이 방식은 아주 간단해 보이지만, 네트워크 자원을 공평하게 분배하는 데 효과적이다.

예를 들어, 여러 사용자가 이미 네트워크를 이용하고 있는 상황에서 새로 들어온 사용자가 있다면, 기존 사용자의 윈도우 크기가 더 클 것이다. 하지만 혼잡이 발생하면 윈도우 크기가 큰 사용자부터 데이터를 더 많이 보내게 되므로 손실 확률도 높아진다.

이런 상황이라면 네트워크에 일찍 참여해 이미 혼잡 윈도우가 큰 사람이 자신의 윈도우 크기를 줄여서 혼잡 상황을 해결하려 할 것이고, 이때 남은 대역폭을 활용하여 나중에 들어온 사람들이 자신의 혼잡 윈도우 크기를 키울 수 있는 것이다. 그런 이유로 시간이 흐르면 네트워크에 참여한 순서와 관계 없이 모든 호스트들의 윈도우 크기가 평행 상태로 수렴하게 된다.

그러나 AIMD의 문제점은 네트워크 대역이 펑펑 남아도는 상황에도 윈도우 크기를 너무 조금씩 늘리면서 접근한다는 것이다. 때문에 AIMD 방식은 네트워크의 모든 대역을 활용하여 제대로 된 속도로 통신하기까지 시간이 걸린다.

3.1.2. Slow Start(느린 시작)

Slow Start는 AIMD의 단점을 보완한 방식이다. AIMD는 전송 속도를 1씩 천천히 올리는 반면, Slow Start는 처음에 패킷을 하나 보내고, ACK를 받을 때마다 윈도우 크기를 지수적으로(2배씩) 늘려나간다. 혼잡이 감지되면 윈도우 크기를 1로 다시 줄이고, 그 후에는 혼잡이 발생할 때까지 빠르게 늘리다가 일정 부분에서부터는 천천히 1씩 증가시킨다.

이 방식 덕분에 네트워크 용량에 대한 정보를 빠르게 파악할 수 있고, 어느 정도 네트워크 수용량을 예측한 후 혼잡이 발생하기 전까지는 전송 속도를 계속해서 빠르게 늘릴 수 있다.

3.2. 혼잡 제어 정책

TCP에서 혼잡 제어는 네트워크의 혼잡 상태를 감지하고 그에 맞춰 데이터 전송을 조절하는 방법이다. 주요 기법으로는 Tahoe와 Reno가 있으며, 이 두 가지 기법은 기본적으로 네트워크가 혼잡하다고 느껴졌을 때 윈도우 크기를 줄이거나, 증가를 멈추고 혼잡을 회피하는 방식으로 동작한다.

🚨 혼잡 감지 기준

• Timeout: 송신 측이 데이터를 보내고 나서 응답을 받지 못할 때 혼잡 상태라고 간주한다.
• 3 ACK Duplicated: 수신 측이 정상적으로 데이터를 받지 못해 같은 승인 번호(ACK)를 세 번 이상 보낼 경우, 송신 측은 네트워크에 문제가 있다고 판단한다.
  이 두 가지 상황이 발생하면 송신 측은 혼잡이 발생했다고 보고 윈도우 크기를 줄인다.

3.2.1. Tahoe

Slow Start로 시작해 윈도우 크기를 지수적으로 빠르게 증가시킨다.

혼잡 상황이 발생하면, 윈도우 크기를 1로 줄이고 다시 Slow Start를 시작한다. 이때 ssthresh(Slow Start Threshold) 값을 윈도우 크기의 절반으로 설정하고, 이후 혼잡 제어는 AIMD 방식으로 진행된다.

이는 혼잡이 발생했을 때 윈도우 크기를 1로 줄이는 과정이 비효율적일 수 있다.

3.2.2. Reno

Reno는 Tahoe의 문제점을 개선한 방식으로, Slow Start로 시작하여 임계점(ssthresh)을 넘으면 AIMD 방식으로 전환된다.

• 3 ACK Duplicated 발생 시: Tahoe와 달리, 윈도우 크기를 1로 줄이지 않고 반으로만 줄이고 다시 합 증가 방식으로 윈도우 크기를 늘린다. 이를 통해 빠른 회복(Fast Recovery)가 가능하다.
• Timeout 발생 시: Tahoe처럼 윈도우 크기를 1로 줄이고 Slow Start로 다시 시작한다.

즉, Reno는 ACK 중복과 타임아웃을 구분하여 더 유연하게 대처한다. ACK 중복은 비교적 작은 혼잡 상황으로 간주해 회복 과정을 빠르게 처리하고, 타임아웃은 더 심각한 문제로 보고 더 강하게 대처하는 것이다.

Reference

• 패킷의 흐름과 오류를 제어하는 TCP
• 사이 좋게 네트워크를 나눠 쓰는 방법, TCP의 혼잡 제어

TCP의 3 & 4 Way Handshake에 대해 알아보기 전에, 우선 아래의 내용을 살펴보자.

1.1. Transport Layer

OSI 7계층에서 Transport Layer에는 양 끝단(End to End)의 사용자들이 신뢰성 있는 데이터를 주고 받을 수 있도록 해주어, 상위 계층들이 데이터 전달의 유효성이나 효율성을 생각하지 않도록 해준다.

전송 계층은 인터넷의 기반인 TCP/IP 모델과 일반적인 네트워크 모델인 개방형 시스템 간 상호 접속(Open Systems Interconnection, OSI) 모두 포함하고 있다.

전송 프로토콜 중 잘 알려진 것이 바로 TCP와 UDP이다.

• Transport Layer: Application 프로세스들 간의 논리적인 통신을 제공한다. 즉, 서로 다른 컴퓨터에서 실행되는 애플리케이션 프로세스들이 데이터를 주고받을 수 있도록 지원한다.
• Network Layer: 호스트 간의 논리적인 통신을 제공한다. 네트워크 계층은 패킷을 목적지까지 전송하는 역할을 하며, 이를 위해 IP 주소를 사용해 데이터를 올바른 경로로 전달한다. 네트워크 계층은 각 호스트(컴퓨터 또는 장치) 간의 통신 경로를 결정하고, 패킷이 목적지까지 도달할 수 있도록 라우팅을 처리한다.

1.2. TCP & UDP

TCP에서는 Transport Layer에서 주고 받는 데이터 단위를 세그먼트(Segment)라고 한다. 반면, UDP에서는 데이터를 데이터그램(Datagram)이라고 부른다. 데이터그램은 비연결형 서비스에서 사용되는 용어로, UDP가 데이터를 패킷으로 처리하는 방식을 설명하는 데 사용된다.

🙋🏻‍♀️ 왜 굳이 두 단어를 구분해야 하죠?

TCP는 연결 지향적이며, 데이터의 ‘정확한 전송’을 보장하기 위한 여러 제어 기능이 포함되어 있다. 이러한 특징을 반영하기 위해 각 세그먼트에는 데이터 외에도 제어 정보가 포함된다.

반면 데이터그램은 독립적이고 신뢰성 없이 전송되는 데이터 단위를 가리킨다. 이때문에 데이터그램에는 데이터 전송을 간단하고 빠르게 처리하기 위해 필수적인 최소한의 제어 정보만 포함시킨다.

즉, TCP와 UDP 모두 패킷에 정보가 담긴다는 점은 동일하지만, 헤더의 구조와 내용이 다르기 때문에 다른 단어를 사용하는 것이다.

1.2.1. TCP(Transmission Control Protocol)

TCP는 인터넷 상에서 데이터를 안전하게 전달하기 위해 IP와 함께 사용하는 프로토콜이다. TCP는 다음과 같은 특징을 가지고 있다.

• 연결지향적(Connected-Oriented): 데이터를 보내기 전에 3-Way Handshake를 통해 연결을 설정하고, 이후 데이터를 주고받는다. 데이터를 주고받는 동안에도 지속적으로 연결 상태를 유지하며, 데이터 전송이 끝난 후에는 4-Way Handshake를 통해 연결을 종료한다.
• 신뢰성 보장: TCP는 데이터를 신뢰성 있게 전송하는 것을 보장한다. 데이터가 손실되거나 손상되면 재전송하고, 데이터가 올바른 순서로 도착하도록 관리한다. 수신된 데이터의 확인(ACK) 응답을 통해 데이터 전송이 제대로 이루어졌는지 확인한다.
• 흐름 제어(Flow Control): 송신자와 수신자가 서로 다른 속도로 데이터를 처리할 수 있는 상황을 대비하여, 송신자가 데이터를 너무 빠르게 보내는 것을 방지한다. 이를 통해 수신자의 버퍼가 넘치지 않도록 조절한다.
• 혼잡 제어(Congestion Control): 네트워크의 혼잡 상태를 감지하고, 데이터 전송 속도를 동적으로 조절하여 네트워크 트래픽을 관리한다. 이를 통해 네트워크 혼잡 시 성능 저하를 방지한다.
• 속도: TCP는 여러 보조 기능을 통해 신뢰성을 보장하기 때문에 UDP보다 속도가 느릴 수 있다. 하지만 이 속도 차이는 매우 미세하기 때문에 대부분의 사용자가 체감하기 어렵다.
• 파일 전송, 웹 브라우징, 이메일, 데이터베이스 통신 등 신뢰성이 중요한 상황에서 주로 사용된다.

1.2.2. UDP(User Datagram Protocol)

UDP는 비연결형 프로토콜로, 데이터 전송 전에 연결을 설정하지 않고 빠르게 데이터를 전송하는 데 중점을 둔다. UDP는 다음과 같은 특징을 가지고 있다.

• 비연결형(Connectionless): UDP는 데이터를 전송하기 전에 연결 설정을 하지 않으며, 데이터를 송신하면 수신자가 받는지 여부를 확인하지 않는다. 이는 TCP의 3-Way Handshake와 같은 과정이 없다는 것을 의미한다.
• 독립적인 패킷 전송: 각 패킷은 독립적으로 전송되며, 서로 다른 경로로 전송될 수 있다. 따라서 UDP는 데이터의 순서 보장을 하지 않으며, 손실된 패킷에 대한 재전송도 이루어지지 않는다.
• 빠른 전송 속도: UDP는 연결 설정 및 확인 과정이 없기 때문에 빠른 전송 속도를 제공한다. 또한, 흐름 제어와 혼잡 제어가 없어 네트워크 부하가 적다.
• 스트리밍, 실시간 비디오/음성 통화, 온라인 게임 등 연속성이 중요하고 약간의 데이터 손실이 큰 문제가 되지 않는 경우에 주로 사용된다.

TCP와 UDP는 각각 별도의 포트 주소 공간을 관리하므로, 같은 포트 번호를 사용해도 서로 독립적인 포트로 동작한다.

또한 클라이언트 프로그램이 동시에 여러 서버와 연결을 맺을 때, 같은 프로토콜을 사용하는 경우라도 각 연결마다 다른 포트 번호를 사용하여 여러 연결을 처리한다.

1.3. 포트(Port) 상태 정보

• CLOSED: 포트가 닫혀 있는 상태로, 어떤 연결 요청도 받지 않는다.
• LISTEN: 서버의 포트가 열린 상태로 연결 요청을 기다리는 상태이다. 이때 서버는 클라이언트로부터 들어오는 연결 요청을 받을 준비가 된 상태이다.
• SYN_RCV: 서버가 클라이언트의 SYN 요청을 받고, 이에 대한 응답으로 SYN-ACK 패킷을 보낸 상태이다. 즉, 서버는 클라이언트로부터 받은 연결 요청에 대해 응답을 보내고, 연결이 완료되기를 기다리고 있다.
• ESTABLISHED: 클라이언트와 서버 간에 연결이 성립된 상태. 이 상태에서는 데이터를 주고받을 수 있으며, 연결이 정상적으로 작동하고 있는 상태이다.

1.4. 플래그 정보

TCP 헤더에는 6개의 CONTROL BIT(플래그 비트)가 있으며, 각 비트는 특정 기능을 수행하는 패킷임을 나타낸다. 플래그 비트는 1bit의 정보를 가지며, 1이면 해당 기능을 수행하는 패킷이다.

📌 Sequence Number

TCP에서는 각 패킷이 전송될 때마다 Sequence Number(시퀀스 번호)가 부여된다. 이 번호는 패킷이 전송된 순서를 나타내고, 데이터가 손실 없이, 정확한 순서로 도착하도록 관리된다.

1.4.1. SYN(Synchronize Sequence Number) / 000010

• SYN 플래그는 연결 설정에 사용된다. 클라이언트가 서버에 연결 요청을 보낼 때 사용되며, 초기 Sequence Number를 설정하여 세션을 시작한다.
• 주로 3-Way Handshake의 첫 번째 단계에서 사용되며, 클라이언트와 서버 간에 초기 연결을 설정하는 역할을 한다.

1.4.2. ACK(Acknowledgement) / 010000

• ACK 플래그는 응답 확인을 나타낸다. 클라이언트나 서버가 패킷을 정상적으로 수신했음을 확인하고, 이에 대한 응답을 보낼 때 사용된다.
• ACK Number 필드는 수신자가 다음에 받고자 하는 데이터의 Sequence Number를 의미한다.
  • e.g. 클라이언트 → 서버로 Sequence Number가 1000인 데이터 패킷을 보낸다.
  • 서버가 이 패킷을 받으면, “Sequence Number 1000에서 시작하는 데이터를 잘 받았다.”는 의미로 ACK Number를 1001로 설정하여 클라이언트에게 응답한다.
  • ACK Number 1001은 “이제 1001번부터 시작하는 데이터를 보내달라”는 의미이다.
  • 클라이언트는 ACK Number를 보고, 그다음 데이터를 1001번 시퀀스 번호부터 전송한다.
• 연결이 설정된 후 모든 패킷에 이 ACK 플래그가 설정된다. 데이터 전송 과정에서 거의 모든 패킷에 사용된다고 볼 수 있다.

1.4.3. FIN(Finish) / 000001

• FIN 플래그는 연결을 종료할 때 사용된다. 더 이상 전송할 데이터가 없다는 것을 알리기 위해 클라이언트 또는 서버가 FIN 패킷을 전송한다.
• 주로 4-Way Handshake 과정에서 연결 종료 요청을 나타내며, 양측 모두 이 플래그를 사용하여 연결을 종료한다.

2. 3-Way Handshake

3-Way Handshake는 TCP 연결을 설정하는 과정으로, 클라이언트와 서버가 데이터를 주고받기 전에 신뢰성 있는 연결을 설정하는 데 사용된다. 이 과정은 양방향 통신이 가능하도록 준비하기 위해 수행되며, 다음 세 단계로 이루어진다.

2.1. 클라이언트 → 서버 : SYN

• 클라이언트가 서버에 SYN 패킷을 보내 연결을 요청한다.
• 이때 SYN 플래그가 설정된 패킷이 전송되며, 이 패킷에는 랜덤한 초기 Sequence Number가 포함되어 있다.
• 클라이언트는 서버에게 “너랑 연결을 맺고 싶다”라는 의사를 전한다.
• 이 상태에서 서버는 LISTEN 상태에 있을 수 있다. 즉, 서버는 클라이언트와의 연결 요청에 귀기울이고 있는 상태이다.

2.2. 서버 → 클라이언트 : SYN-ACK

• 서버는 클라이언트의 연결 요청을 수락하고, SYN-ACK 패킷을 클라이언트로 보낸다.
• 서버는 클라이언트가 보낸 SYN 패킷을 확인하고, 자신도 연결할 준비가 되었음을 나타내기 위해 SYN 플래그와 함께 ACK 플래그를 설정한 패킷을 보낸다.
• ACK Number는 클라이언트가 보낸 Sequence Number + 1이다. 이는 클라이언트가 보낸 요청을 받았음을 확인하는 숫자이다.
• 이 시점에서 서버는 SYN_RCV 상태이다.

2.3. 클라이언트 → 서버 : ACK

• 클라이언트는 서버가 보낸 SYN-ACK 패킷을 받으면, 다시 서버에게 ACK 패킷을 보낸다.
• 이때 ACK 플래그만 설정된 패킷을 보내며, 이는 연결이 성립되었음을 확인하는 응답이다.
• 클라이언트와 서버가 모두 ESTABLISHED 상태로 전환되며, 이제 양측은 데이터를 주고받을 준비가 완료된 상태이다.

이 3단계 과정을 통해 양방향에서 데이터를 전송할 준비가 완료된 Full-duplex 통신이 형성된다. Full-duplex 통신은 양방향으로 동시에 데이터를 전송할 수 있는 상태를 의미한다.

3. 4-Way Handshake

4-Way Handshake는 TCP 연결을 종료하는 절차로, 클라이언트와 서버가 각각의 데이터 전송이 끝났음을 명확히 확인하는 과정을 거친다. 이때 양쪽 모두 FIN 플래그를 사용해 더 이상 보낼 데이터가 없음을 알리고, 마지막으로 ACK 패킷을 주고받아 연결을 종료한다.

3.1. 클라이언트 → 서버 : FIN(+ACK)

• 클라이언트가 더 이상 보낼 데이터가 없을 때, 연결을 종료하려고 FIN 플래그가 설정된 패킷을 서버에 보낸다.
• 이때 클라이언트는 FIN_WAIT_1 상태로 들어가며, 서버로부터 ACK 응답을 기다린다.
• 여기서 중요한 점은, FIN 패킷은 데이터를 보내는 일방적인 요청이지만, 연결 자체를 완전히 종료하지는 않는다. 아직 서버가 데이터를 전송할 수도 있기 때문이다.

3.2. 서버 → 클라이언트 : ACK

• 서버는 클라이언트가 보낸 FIN 패킷을 받으면, 확인 응답(ACK 패킷)을 클라이언트에 보낸다.
• 서버는 CLOSE_WAIT 상태로 전환되며, 아직 처리 중인 데이터가 있다면 이를 처리하고 나서 연결을 완전히 종료할 준비를 한다.
• 클라이언트는 서버로부터 ACK 패킷을 받으면 FIN_WAIT_2 상태로 전환되며, 서버가 종료할 때까지 기다린다.

3.3. 서버 → 클라이언트 : FIN

• 서버가 남은 데이터를 모두 전송하고 나면, 연결을 종료하기 위해 FIN 패킷을 클라이언트에게 보낸다.
• 서버는 이때 LAST_ACK 상태로 들어가며, 클라이언트로부터 최종 ACK를 받기 전까지 기다린다.

3.4. 클라이언트 → 서버 : ACK

• 클라이언트는 서버로부터 FIN 패킷을 받은 후, 마지막 ACK 패킷을 서버에 보내 서버의 종료 요청을 확인한다.
• 클라이언트는 이때 TIME_WAIT 상태로 돌아가며, 네트워크 상에 남아있을지 모르는 패킷(e.g. 마지막 ACK 패킷이 손실된 경우)을 처리하기 위해 일정 시간 대기한다.
• 서버는 클라이언트로부터 ACK를 받으면 완전히 연결을 종료하고 CLOSED 상태로 전환된다.

⏱️ TIME_WAIT 상태

• 클라이언트는 TIME_WAIT 상태에서 남아있을 수 있는 잘못된 패킷을 처리하기 위해 잠시 대기한다. 네트워크에 혹여나 남아있을 수 있는 지연된 패킷을 처리하고, 만약 서버가 FIN 패킷을 다시 보내는 경우를 처리하기 위함이다.
• TIME_WAIT 시간이 끝나면 클라이언트도 CLOSED 상태로 전환되고, 연결이 완전히 종료된다.

🔎 Termination 종류

• Graceful Connection Release(정상적인 연결 해제)
  • 양쪽 모두가 연결을 안전하게 닫기 위해 서로 FIN과 ACK를 주고받으며 연결을 종료하는 방식이다. 4-Way Handshake가 바로 이 정상적인 연결 해제에 해당된다.
  • 양쪽이 서로 연결 종료를 동의하며, 모든 데이터 전송이 끝날 때까지 연결을 유지한다.
• Abrupt Connection Release(갑작스러운 연결 해제)
  • 갑자기 한쪽이 연결을 강제로 종료하는 방식이다.
  • 이때는 RST(Reset) 세그먼트를 사용해 연결을 즉시 끊는다.
  • e.g. 비정상적인 상황(리소스 부족, 비정상적인 패킷 수신 등)에서 한쪽이 연결을 강제로 닫고 싶을 때 RST 패킷을 보내 연결을 종료한다.

🔎 Half-Close 기법

Half-Close는 한쪽에서 먼저 연결을 닫았지만, 다른 쪽은 계속해서 데이터를 전송할 수 있는 상태를 말한다.

• 예를 들어 클라이언트가 먼저 FIN 패킷을 보내면서 자신의 데이터를 모두 보냈음을 알리지만, 서버는 남은 데이터를 전송할 수 있는 상태를 유지한다.
• FIN 패킷에 ACK가 포함되어 있는 이유는 “일단 데이터를 보내는 건 끝났지만, 서버가 보낼 데이터는 계속 받을 준비가 되어있다.”는 의미이다.
• 서버가 데이터를 모두 전송하고 나면, 다시 FIN 패킷을 보내 연결을 완전히 종료한다.

Reference

• [네트워크] TCP/UDP와 3 -Way Handshake & 4 -Way Handshake

1.1. OSI(Open Systems Interconnection) 7계층 모델

OSI(Open Systems Interconnection) 7계층 모델은 네트워크 통신에서 발생하는 복잡한 작업을 일곱 개의 독립적인 계층으로 나누어 설명하는 개념적 모델이다. 이는 네트워크 통신을 계층화해서 쉽게 이해하고, 각 계층 간의 상호작용을 설명하는 데 중점을 둔다. 주로 이론적 교육용 모델로 사용된다.

그런데 잠깐, 우리가 실제로 배우는 네트워크 모델은 5개 계층 밖에 되지 않는데, 왜 7계층일까?

1.2. TCP/IP 모델

그 이유는 오늘날 네트워크 통신에서 OSI 7계층 모델보다 TCP/IP 모델이 더 널리 사용되기 때문이다.

TCP/IP 모델은 실제 구현된 인터넷 프로토콜을 바탕으로 한 네트워크 모델이다. OSI 7계층과 다르게 5개의 계층으로 구성되어 있고, 이는 실제로 인터넷과 대부분의 네트워크 시스템에서 사용되는 모델이다.

TCP/IP 모델은 OSI 모델의 세션(Session)과 표현(Presentation) 계층을 응용 계층(Application Layer)에 통합하여, 계층 수가 5개로 줄어들었다. 이는 실제로 네트워크 통신에서 세션 관리나 데이터 변환 등의 기능이 주로 응용 계층에서 처리되기 때문이다.

또한 TCP/IP 모델은 네트워크에서 실제로 구현되는 프로토콜을 기반으로 만들어졌기 때문에, 효율적이고 실용적인 구조로 설계되었다. 7계층 구조가 이론적으로는 유용하지만, 네트워크 프로토콜의 구현에서는 과도한 복잡성을 피하기 위해 5계층으로 단순화된 것이다.

정리하자면, OSI 모델은 이론적으로는 우수하나 실제로 적용하기에는 복잡하고 표준화 속도가 느렸던 반면, TCP/IP 모델은 실용적이고 빠르게 구현되었기 때문에 인터넷과 네트워크의 실제 표준으로 자리 잡게 된 것이다.

그럼 이제 TCP/IP 모델의 각 계층에 대해 자세히 살펴 보자.

2. Physical Layer

컴퓨터가 데이터를 주고 받기 위해서는 어떻게 해야할까? 모든 파일과 프로그램은 결국 0과 1로 이루어진 데이터의 나열이다. 그렇다면, 두 대의 컴퓨터가 서로 0과 1만 주고받을 수 있다면 모든 데이터를 주고 받을 수 있을 것이다.

2.1. 데이터 전송의 기초: 0과 1의 전송

두 대의 컴퓨터를 전선으로 직접 연결한다고 가정해보자.

• 1을 보낼 때: +5V의 전기 신호를 보낸다.
• 0을 보낼 때: -5V의 전기 신호를 보낸다.

이 방식을 이용하면 이진 데이터, 즉 0과 1의 나열을 주고 받을 수 있다. 두 컴퓨터가 데이터를 교환할 수 있는 기본적인 환경이 마련된 것처럼 보인다.

2.2. 현실적인 문제: 신호 왜곡

하지만 이 간단한 방식은 실제로는 잘 동작하지 않는다. 그 이유는 전기 신호가 이상적인 조건에서만 전송되지 않기 때문이다.

파동은 왼쪽처럼 이상적인 sin파로만 전송되지 않는다. 전송되는 환경에 따라 오른쪽과 같이 왜곡되거나 변형된다.

예를 들어, 어떤 전선이 5-8Hz의 전자기파만 통과시킬 수 있다면, 1Hz에서 10Hz 사이의 다양한 주파수 성분을 가진 신호는 제대로 전달되지 못하고 일부 성분만 통과하게 된다. 결과적으로 도착하는 데이터는 엉뚱한 값이 될 가능성이 높아진다.

왜 이런 문제가 발생할까?

전자기파에는 다양한 주파수 성분이 포함되어 있다. 특히 수직선과 수평선으로 급격하게 변하는 신호(이진 데이터)의 경우 매우 넓은 주파수 대역(0~무한대)을 필요로 한다. 현실에서는 무한대의 주파수 범위를 전달할 수 있는 전선은 존재하지 않기 때문에, 이러한 신호를 그대로 보내는 것은 불가능하다.

2.3. 해결책: 아날로그 신호로 변환

따라서 실제 통신에서는 0과 1을 직접 전송하는 대신, 아날로그 신호로 변환하여 데이터를 전송한다. sin파나 cos파 같은 아날로그 신호는 전선에서 발생하는 주파수 제한 문제를 완화할 수 있다.

• 인코딩(Encoding): 0과 1의 이진 데이터를 아날로그 신호로 변환하여 전송한다.
• 디코딩(Decoding): 전송된 아날로그 신호를 다시 0과 1로 변환하여 데이터를 복원한다.

2.4. Physical Layer란?

이러한 과정을 담당하는 것이 바로 네트워크 1계층, 물리 계층(Physical Layer)이다. 물리 계층은 0과 1의 나열을 아날로그 신호로 변환하여 전선이나 기타 물리적인 매체를 통해 전달하고, 다시 아날로그 신호를 0과 1로 변환하여 데이터 통신을 가능하게 하는 모듈(module)이다.

물리 계층은 컴퓨터가 전기 신호를 통해 데이터를 전송하고 수신하는 기본적인 통신 방법을 제공하며, 네트워크의 가장 기초적인 부분을 담당한다.

물리 계층 기술은 PHY 칩이라고 불리는 하드웨어 장치에 의해 구현된다. 이 칩은 전기 신호의 인코딩과 디코딩을 처리하며, 주로 네트워크 장비나 컴퓨터의 네트워크 인터페이스 카드(NIC)에 내장되어 있다. 중요한 점은 물리 계층의 기능이 하드웨어적으로 구현된다는 것이다. 즉, 물리 계층은 우리가 프로그래밍 언어로 작성한 함수가 아니라 회로로 구성되어 동작한다.

3. Data-Link Layer

컴퓨터가 서로 데이터를 주고 받기 위해서는 단순히 물리적으로 연결되는 것만으로는 충분치 않다. 여러 대의 컴퓨터가 동시에 하나의 전선을 통해 통신하기 위해서는 추가적인 기술이 필요하다.

3.1. 여러 대의 컴퓨터와 통신하기

A와 B가 하나의 전선으로 통신하고 있다고 가정해 보자. 그런데 A가 C와도 통신하고 싶다면 어떻게 해야할까?

방법은 간단하다. A와 C 사이에도 전선을 하나 더 연결하면 된다.

그러나 이 방식은 컴퓨터 수가 늘어날 때마다 전선을 계속 추가해야 하는 비효율적인 방식이다. 새로운 컴퓨터와 통신할 때마다 새로운 전선과 연결 포트가 필요하기 때문이다.

이러한 비효율성을 해결하기 위해 전선 하나를 여러 대의 컴퓨터가 공유하면서도, 동시에 충돌 없이 통신할 수 있는 방법이 필요하다. 위의 그림처럼 전선 하나에 여러 대의 컴퓨터를 연결한 상황을 생각해 보자. 가운데 전선을 구겨서 상자에 넣으면 오른쪽과 같은 그림이 되는데, 이를 스위치(Switch)라고 한다.

위 그림과 같이 서로 다른 네트워크가 스위치와 스위치로 연결되어 서로 다른 네트워크에 속한 컴퓨터끼리 통신이 가능하게 해주는 장비를 라우터(Router)라고 한다. (엄밀히 해당 상자는 스위치+라우터로 구성된 L3스위치이지만, 뭉뚱그려 라우터라고 하자.)

이렇게 전 세계의 컴퓨터들이 계층구조로 연결되어 있는 것을 인터넷이라고 한다.

3.2. Framing

여러 대의 컴퓨터가 어떻게 통신할 수 있는지는 알겠다. 아래 그림과 같은 상황을 생각해 보자.

A에게 B, C, D가 거의 동시에 각각의 정보를 보내면, A는 010111110001이라는 데이터를 받게 된다.

A는 송신된 데이터의 시작과 끝을 명확히 알지 않으면 데이터가 꼬이게 된다. 이를 위해 프레이밍(Framing)이라는 작업이 필요하다. 송신자는 데이터를 끊어서 전송하기 위해 특정한 비트열을 데이터 앞뒤에 붙인다. 이 비트열은 데이터를 주고받는 컴퓨터들이 데이터의 구분을 명확하게 할 수 있도록 도와준다.

3.3. Data-Link Layer란?

Data-Link Layer는 물리적으로 같은 네트워크에 연결된 여러 대의 컴퓨터들이 데이터를 원활하게 주고받을 수 있도록 도와준다. 이 계층에서는 데이터를 전송할 때 어디에서 시작되고 끝나는지 구분해야 하며, 데이터를 여러 부분으로 나눠서 전송하거나, 데이터 전송 중 오류가 발생하지 않도록 관리하는 역할을 한다.

Data-Link Layer의 기술은 네트워크 인터페이스 카드(NIC), 흔히 랜카드라고 불리는 장치에 구현된다. 이는 1계층의 물리적인 신호 처리를 담당하는 부분과 함께 하드웨어적으로 구현되어 있다.

3.4. Data-Link Layer와 Physical Layer의 차이점

1계층인 Physical Layer는 단순히 전기 신호를 매개체로 하여 데이터를 전송하는 기능을 담당한다. 이 계층에서는 데이터가 어떻게 전송되는지에 대한 규칙은 없고, 그저 신호를 주고 받기만 한다.

반면 Data-Link Layer는 단순히 신호를 주고 받는 것을 넘어서, 데이터를 프레임 단위로 나누고 이를 통제하여 충돌이나 오류 없이 전송할 수 있도록 관리한다. 즉, 물리적인 전송이 가능한 환경에서 안정적으로 데이터를 주고 받는 과정을 처리하는 것이다.

4. Network Layer

컴퓨터들이 서로 통신을 하기 위해서는 IP 주소를 알아야 한다. IP 주소는 컴퓨터가 가지는 고유한 주소로, 네트워크 상에서 데이터를 주고 받기 위해서는 상대방 컴퓨터의 IP 주소가 필수적이다.

예를 들어, 우리가 웹 브라우저에 www.naver.com을 입력하면, 이 주소는 실제 IP 주소로 변환되어 사용된다. 결국 우리는 웹사이트에 접속할 때 이미 그 사이트의 IP 주소를 사용하고 있는 셈이다.

4.1. 패킷(Packet)

네트워크 상에서 데이터는 패킷이라는 단위로 전송된다. 패킷은 단순히 데이터를 담는 그릇이 아니라, 상대방의 IP 주소와 데이터를 함께 담은 것을 의미한다. 따라서 A가 B에게 데이터를 보내려면 B의 IP 주소를 알고 있어야 하며, 그 IP 주소에 데이터를 전송하는 것이 패킷을 보내는 과정이다.

위 그림에서 A에서 B로 패킷을 보내는 과정을 생각해 보자.

패킷은 여러 라우터를 거쳐 이동해야 한다. 라우터는 네트워크 상에서 중간중간 위치하며, 패킷이 최종 목적지로 갈 수 있도록 경로를 찾아주는 역할을 한다.

예를 들어 A가 B에게 패킷을 보내기 위해 가 라우터를 통해야 하고, 그 다음 마 라우터를 거친다고 가정해 보자. 인간인 우리는 딱 그림을 보면 바 라우터로 가야한다는 것을 알 수 있다. 하지만 라우터는 스스로 패킷이 어디로 가야 할지 알고 있는 것이 아니라, 경로를 찾아주는 과정을 거쳐야 한다. 이 과정이 바로 라우팅(Routing)이다.

• 라우팅(Routing): 목적지 컴퓨터의 IP 주소를 바탕으로 경로를 찾는 과정. 라우터는 자신과 연결된 네트워크를 분석하고, 목적지까지 최적 경로를 계산하여 패킷을 어느 방향으로 보낼지 결정한다.
• 포워딩(Forwarding): 라우팅을 통해 결정된 경로를 바탕으로, 다음 라우터로 패킷을 실제로 전달하는 과정. 라우터는 패킷을 받아 다음 목적지로 넘기는 역할을 수행한다.

4.2. Network Layer란?

Network Layer는 네트워크 상에서 IP 주소를 사용하여 경로를 찾고, 그 경로를 따라 데이터를 목적지까지 전달하는 역할을 담당한다. 이는 네트워크의 복잡성과 관계없이 패킷이 목적지까지 도달할 수 있도록 해주는 중요한 계층이다.

네트워크 계층의 기능은 소프트웨어적으로 구현되어 있으며, 이는 운영체제의 커널에서 처리된다.

5. Transport Layer

이제 네트워크 레이어 덕분에 인터넷 상의 모든 컴퓨터가 서로 통신할 수 있게 되었다. 하지만 네트워크를 통해 데이터를 전송받는 컴퓨터는 여러 프로그램(프로세스)이 동시에 실행되고 있을 수 있다.

예를 들어, 한 컴퓨터에서 카카오톡과 크롬이 동시에 실행 중일 수 있다. 이때 컴퓨터는 어떤 데이터를 어떤 프로그램에 보내야 할지 어떻게 알 수 있을까?

5.1. 포트 번호(Port Number)

컴퓨터에서 실행 중인 여러 프로그램들이 네트워크 상에서 데이터를 주고 받기 위해서는, 각 프로그램이 고유한 포트 번호를 가져야 한다. 포트 번호는 각 프로세스가 데이터를 구분하여 받을 수 있도록 컴퓨터 내에서 서로 구별되는 정수값이다. 이를 통해 컴퓨터는 어떤 데이터가 어떤 프로세스로 가야하는지 정확히 알 수 있다.

이를 통해 송신자는 데이터를 보낼 때 수신자의 IP 주소뿐만 아니라, 수신자 프로그램의 포트 번호도 함께 붙여서 보내야 한다는 것을 알 수 있다. 이렇게 하면 수신자 컴퓨터는 데이터를 받은 후, 이 데이터를 정확히 어느 프로그램에 전달해야 할지 알 수 있다.

우리가 웹사이트에 접속할 때도 포트 번호가 사용된다. 예를 들어, 웹 브라우저에서 www.naver.com을 입력할 때, 실제로는 포트 번호 80이 생략되어 있다. 이 포트 번호는 HTTP 프로토콜에서 기본적으로 사용되는 포트 번호이다. 즉, 우리는 인지하고 있지 못하고 있었지만 네이버의 포트 번호를 알고 있는 것이나 마찬가지인 셈이다.

5.2. Transport Layer란?

Transport Layer는 네트워크 상에서 데이터를 전송할 때 IP 주소와 포트 번호를 사용하여, 데이터를 정확한 프로세스(즉, 실행 중인 프로그램)에 전달하는 역할을 한다.

이 계층에서는 두 가지 주요 프로토콜이 많이 사용된다.

• TCP(Transmission Control Protocol): 데이터 전송의 신뢰성과 순서를 보장하는 프로토콜. 데이터를 보내는 도중 손실되면 재전송하고, 순서가 뒤바뀌지 않도록 관리한다.
• UDP(User Datagram Protocol): 상대적으로 빠르게 데이터를 전송하지만 신뢰성을 보장하지는 않는 프로토콜. 실시간 스트리밍이나 게임 등에서 많이 사용된다.

전송 계층은 운영체제의 커널에서 소프트웨어적으로 구현되어 있다. 운영체제는 네트워크를 통해 들어온 데이터를 포트 번호를 기준으로 적절한 프로그램에 분배한다. 이를 통해 컴퓨터는 동시에 여러 프로그램이 실행 중이더라도, 각각의 프로그램이 자신에게 할당된 데이터를 문제없이 수신할 수 있게 된다.

6. Application Layer

6.1. Application Layer란?

Application Layer는 네트워크 통신의 최종 도착지인 프로세스 간의 데이터 교환을 다룬다. 이 계층에서는 다양한 애플리케이션 프로토콜들이 사용된다. 가장 대표적인 것이 HTTP, FTP, SMTP와 같은 프로토콜이다.

애플리케이션 계층에서도 다른 계층과 마찬가지로 인코딩과 디코딩 과정이 이루어진다. 예를 들어, HTTP는 웹 브라우저가 웹 서버와 데이터를 주고받을 때 사용하는 프로토콜로, 인코딩과 디코딩을 통해 요청과 응답을 주고 받는다.

6.2. TCP/IP 소켓 프로그래밍

TCP/IP 소켓 프로그래밍은 네트워크 프로그램을 작성할 때 Transport Layer에서 제공하는 API를 활용하여 프로그램 간 통신을 가능하게 한다. 이 소켓 프로그래밍을 통해 클라이언트와 서버 프로그램을 만들고, 데이터를 주고 받을 수 있다.

소켓 프로그래밍은 Transport Layer에서 네트워크 연결을 설정하고 데이터 전송을 담당하는 반면, Application Layer는 이 소켓을 이용해 실제로 주고 받을 데이터를 다루는 계층이다.

즉, 소켓 프로그래밍 자체는 Transport Layer에 속하지만, 이 소켓을 통해 주고 받는 데이터의 내용은 Application Layer에서 처리가 된다.

Reference

• [10분 테코톡] 🔮 히히의 OSI 7 Layer

하드 디스크에는 파일 시스템(File System)이 존재하며, 이 파일 시스템은 계층 구조로 이루어져 있다. 예를 들어, 윈도우의 루트 디렉토리 아래에 여러 폴더와 파일이 위치하는 것처럼 말이다.

파일이 하드 디스크에 어떻게 할당되는지 알아보자.

하드 디스크는 다음과 같이 구성되어 있다.

• 플래터(Platter): 하드 디스크의 데이터를 저장하는 원형의 디스크로, 데이터를 실제로 저장하는 물리적인 공간이다. 하드 디스크에는 여러 개의 플래터가 쌓여 있으며, 각 플래터는 양면에 데이터를 기록할 수 있다. 플래터는 자성 물질로 코딩되어 있어, 디스크 헤드가 자성을 읽거나 변경함으로써 데이터를 기록하거나 읽어온다.
• 트랙(Track): 플래터의 표면에 기록된 원형 경로로, 데이터를 저장하는 단위이다. 플래터는 수많은 동심원 모양의 트랙으로 나뉘어져 있다. 하드 디스크의 디스크 헤드가 특정 트랙 위에서 데이터를 읽거나 쓴다.
• 실린더(Cylinder): 여러 개의 플래터가 쌓여있을 때, 같은 위치에 있는 트랙들을 묶어 실린더라고 부른다. 즉, 상하로 쌓인 여러 플래터의 동일 위치에 있는 트랙들이 모여 하나의 실린더를 형성한다. 데이터를 읽어올 때, 디스크 헤드는 트랙의 위치에 맞춰 실린더 단위로 데이터를 읽어들인다.
• 섹터(Sector): 트랙은 여러 개의 작은 구획으로 나누어져 있는데, 이 각각의 구획을 섹터라고 한다. 섹터는 하드 디스크에서 데이터를 저장하고 읽어내는 최소 단위이다. 일반적으로 한 섹터는 512bytes 또는 4KB 크기의 데이터를 저장할 수 있다.

섹터는 몇 개가 모여 블록(Block)을 이룬다. 하드 디스크는 블록 단위로 데이터를 읽고 쓰며, 이때문에 하드 디스크는 블록 디바이스(Block Device)라고도 불린다.

cf) 캐릭터 디바이스(Character Device): 글자 단위로 자료가 이동된다. (e.g. 키보드)

예시로 test.txt라는 파일에 ‘a’라는 글자를 저장한다고 가정해 보자. ‘a’는 1byte의 크기를 가지지만, 하드 디스크는 블록 단위로 데이터를 처리하기 때문에, 이 작은 파일을 저장할 때에도 최소 한 블록(일반적으로 4KB)이 할당된다. 결과적으로 1byte의 파일을 위해 4KB의 디스크 공간이 사용되며, 남은 공간은 비어있지만 사용할 수 없는 상태가 된다.

이 예시를 통해 디스크가 블록 단위로 데이터를 읽고 쓴다는 것을 알 수 있다. 블록 크기는 파일 시스템에 의해 결정되며, 작은 파일도 최소 블록 크기만큼의 공간을 차지한다.

디스크는 pool of free blocks로 구성되어 있으며, 이들은 각 파일에 할당된다. 각각의 파일에 대해 free blocks를 어떻게 할당하고, 어떻게 관리할지 알아보자.

1. 파일 할당

위 그림은 pool of free blocks를 논리적인 그림으로 나타낸 모습이다. 블록마다 인덱스 번호가 설정되어 있다.

파일에 블록을 할당하는 방식은 크게 연속 할당, 연결 할당, 색인 할당 세 가지로 나누어 볼 수 있다.

1.1. 연속 할당(Contiguous Allocation)

각 파일에 대해 디스크 상에 연속된 블록을 할당하는 방식이다.

예를 들어 f1이라는 파일이 5KB를 필요로 한다면, 디스크에서 5KB 크기의 연속된 블록을 할당해준다.

1.1.1. 특징

연속 할당 방식은 파일을 읽을 때 디스크 헤드를 한 번만 움직이면 연속적으로 파일을 읽을 수 있어 속도가 빠르다. 옛날 60-70년대의 IBM에서 많이 사용됐던 방법이며, 동영상, 음악, VOD와 같이 연속적으로 재생하는 용량이 큰 파일에 적합하다.

또한 이 방식은 파일을 순서대로 읽는 순차 접근(Sequential Access)과 특정 부분을 바로 읽을 수 있는 직접 접근(Direct Access) 모두 가능하다.

🔎 디렉토리(Directory)

디렉토리는 파일에 대한 메타데이터를 저장하는 파일 시스템의 테이블 역할을 한다.

디렉토리에는 파일의 이름, 크기, 생성 시간, 소유자와 같은 정보뿐만 아니라 시작 블록 번호와 파일의 크기도 저장된다. 연속 할당에서는 디렉토리에 파일의 시작 블록 번호와 연속된 블록의 크기만 있으면 해당 파일에 directly access할 수 있다.

file name: f1
file size: 5 bytes
...
-----------------
block number: 0

1.1.2. 단점

이 방식은 현재 거의 사용되지 않는데, 외부 단편화가 큰 문제로 작용하기 때문이다. 파일이 삭제되면 그 공간은 hole로 남게 되고, 다양한 크기의 파일들이 생성되고 삭제되면서 빈 공간이 조각난다. 이로 인해 충분한 연속된 공간을 찾기 어려워지고, 파일을 저장하지 못하는 상황이 발생한다. 이를 해결하기 위해 compaction을 통해 빈 공간을 모으는 작업이 필요한데, 이 작업은 매우 비효율적이고 시간이 많이 소요된다. (80년대 MS-DOS에서는 이를 해결하기 위해 compaction 프로그램을 따로 돌렸었다.)

또한 파일 크기 예측의 어려움도 큰 단점이다. 파일이 생성될 때, 파일의 최종 크기는 미리 알 수 없다. 파일이 예상보다 커지면 기존에 할당된 공간을 넘어 확장해야 하는데, 연속된 공간이 부족하면 확장이 불가능해 파일을 다른 곳으로 옮겨야 하는 상황이 발생한다. 특히 로그 파일과 같이 크기가 계속 증가하는 파일의 경우, 초기 할당 크기를 예측하기 매우 어렵다.

연속 할당 방식은 이렇듯 빠른 데이터 접근을 제공하지만, 치명적인 단점들로 인해 현대의 파일 시스템에서는 거의 사용되지 않는다.

1.2. 연결 할당(Linked Allocation)

파일을 연속적으로 할당하지 않고, 임의의 블록에 할당하면서 각 블록에 다음 블록을 가리키는 포인터를 저장하는 방식이다. 이는 자료구조의 연결 리스트(Linked List)와 유사한 방식이다. (cf. 연속 할당은 배열처럼 파일을 저장한다.)

이러한 파일을 linked list of data blocks라고 한다.

예를 들어, 파일의 첫 번째 블록을 6번 블록에 저장했다면, 6번 블록의 마지막에 다음 블록의 주소를 가리키는 포인터를 둔다. 디렉토리는 파일의 첫 번째 블록을 가리키는 주소를 저장한다.

file name: f1
file size: 5 bytes
...
-----------------
block number: 6

1.2.1. 특징

외부 단편화가 발생하지 않는다. 파일이 연속적인 블록에 저장될 필요가 없기 때문에, 디스크의 빈 블록을 효율적으로 사용할 수 있다.

또한 파일이 커질 경우에도 쉽게 확장할 수 있다. 추가적인 블록을 할당하고 포인터를 연결해 주기만 하면 된다.

1.2.2. 단점

가장 큰 단점은 직접 접근이 불가능하다는 점이다. 예를 들어, 파일 f1의 세 번째 블록에 바로 접근할 수 없다. 포인터를 통해 첫 번째 블록에서 순차적으로 접근해야만 세 번째 블록의 위치를 알 수 있다. 즉, 순차 접근만 가능하다는 뜻이다.

또한, 각 블록마다 포인터를 저장해야 하므로 추가적인 저장 공간 손실이 발생한다. 포인터 저장을 위해 약 4bytes 정도가 사용된다.

신뢰성 문제도 있는데, 만약 디스크의 특정 블록에 오류가 발생하면 해당 블록의 포인터를 읽지 못해 그 이후의 블록들도 모두 접근할 수 없게 된다.

이뿐만 아니라 파일이 여러 블록에 분산되어 있으므로 디스크 헤더가 자주 이동해야 하며, 이로 인해 성능 저하가 발생할 수 있다.

연결 할당은 연속 할당의 단점을 해결하지만, 나름의 문제점도 있다. 그럼에도 중요한 점은 외부 단편화가 발생하지 않아 디스크 공간 낭비가 없다는 것이다.

📁 FAT(File Allocation Table) 파일 시스템

MS-DOS의 개발 당시, MS는 연결 할당의 장점을 살리면서도 효율적인 파일 시스템을 만들기 위해 FAT 파일 시스템을 고안했다. FAT는 연결 할당의 변종으로, 포인터들을 각 블록에 저장하는 대신, 이 포인터들을 테이블로 따로 모아 디스크 블록 중 하나에 저장하는 방식이다. 이 테이블을 FAT라고 부른다.

FAT 시스템에서 각 블록은 FAT 테이블에 기록된 포인터를 통해 다음 블록을 가리킨다. 예를 들어, 6번 블록이 다음 블록으로 2번을 가리키고 있다고 할 때, 이 정보는 6번 블록에 있는 것이 아니라 FAT 테이블에 기록된다. 파일의 끝을 표시할 때는 -1을 사용한다.

이 방식의 장점은 직접 접근이 가능해진다는 것이다. 포인터를 일일이 따라갈 필요 없이 FAT 테이블을 읽어 원하는 데이터 블록으로 바로 이동할 수 있다. FAT 테이블은 부팅 시 메모리로 로드되기 때문에 테이블을 읽는 속도가 빠르다. 또한, 연결 할당의 단점 중 하나인 포인터가 깨지면 파일 전체를 읽을 수 없는 문제도 해결된다. 만약 테이블이 손상될 경우를 대비해 FAT 테이블의 복사본이 저장된다.

FAT에는 테이블을 위한 비트 할당 크기에 따라 여러 종류가 있다. FAT16, FAT32 같은 이름은 할당되는 비트 크기를 나타내며, 비트가 커질수록 저장 가능한 파일의 크기와 수가 늘어난다.

FAT는 주로 USB 메모리와 같은 이동식 디스크에서 많이 사용되며, 이 시스템은 MS-DOS, OS/2, Windows 등에서 널리 사용되고 있다.

1.3. 색인 할당(Index Allocation)

파일의 각 블록을 가리키는 포인터들을 인덱스 테이블에 저장하는 방식이다.

디렉토리는 해당 파일의 인덱스 블록의 위치를 저장한다. 즉, 인덱스 블록은 해당 파일의 데이터 블록들을 가리키는 포인터들의 집합이라고 볼 수 있다.

file name: f1
file size: 5 bytes
...
-----------------
index block number: 11

1.3.1. 특징

이 방식은 순차 접근과 직접 접근이 모두 가능하다.

또한 파일이 연속적으로 저장될 필요가 없어 외부 단편화 문제도 해결된다.

1.3.2. 단점

하지만 인덱스 테이블을 위한 별도의 블록이 필요하기 때문에 저장 공간의 낭비가 발생한다. 예를 들어, 1byte의 작은 파일, 영어 한 글자를 저장하기 위해 데이터 블록 하나와 인덱스 블록 하나가 사용되며, 이는 상당한 비효율이다.

FAT 파일 시스템의 경우 앞의 몇 블록 정도만을 테이블로 사용하였는데, 색인 할당 방식은 하나의 파일 당 한 블럭이 사용되므로 조금 더 손실이 크다고 볼 수 있다.

파일이 커질 경우, 하나의 인덱스 블록만으로 충분하지 않을 수 있다. 예를 들어, 한 블록이 512bytes라고 가정하고, 4bytes 정수형 포인터를 사용하면 한 인덱스 블록에 $512/4=128$개의 포인터를 저장할 수 있다. 즉, 128개의 블록을 가리킬 수 있으며, 이는 $128*512=64KB$의 파일 크기에 해당한다. 파일 크기가 64KB를 초과할 경우, 하나의 인덱스 블록만으로는 모든 파일 블록을 가리킬 수 없다.

이 문제를 해결하기 위해 다양한 확장 방식이 있다.

1. Linked 인덱스 방식: 하나의 인덱스 블록이 부족할 경우, 다른 인덱스 블록과 연결하여 파일의 모든 블록을 가리킬 수 있다.

   

2. 다중 레벨 인덱스(Multilevel Index): 여러 단계의 인덱스 테이블을 사용하여 대용량 파일을 처리할 수 있다. 예를 들어, 2단계 인덱스를 사용하면 첫 번째 인덱스 블록은 두 번째 인덱스 블록을 가리키고, 그 블록이 실제 데이터 블록을 가리킨다.

   

3. 혼합 방식(Combined Scheme): 첫 번째 인덱스 블록의 앞 부분은 실제 데이터 블록을 가리키고, 뒤쪽은 다른 인덱스 블록을 가리키는 방식이다. 이 방식은 대용량 파일을 처리하면서도 인덱스 테이블의 효율성을 높일 수 있다.

Reference

• KOCW 양희재 운영체제
• [운영체제(OS)] 18. 파일 할당

보조기억장치(e.g. 하드 드라이브, SSD)에는 운영체제와 다양한 실행 파일들이 저장되어 있다. 컴퓨터의 전원을 켜면, 운영체제는 보조기억장치에서 메인 메모리(RAM)로 로드된다.

운영체제의 중요한 역할 중 하나는 프로세스를 관리하는 것이다. 즉, 운영체제는 CPU 자원을 효율적으로 관리하며, 여러 프로세스가 원활하게 실행될 수 있도록 조정합니다. 이를 프로세스 관리(Process Management)라고 한다.

또 다른 중요한 역할은 메인 메모리(RAM)를 효과적으로 관리하는 것이다. 운영체제는 메모리의 사용을 추적하고, 프로세스가 필요한 메모리를 할당하거나 해제하며, 메모리 자원을 최적화한다. 이를 메모리 관리(Memory Management)라고 한다.

메인 메모리 관리에 대해 자세히 알아보자.

1.1. 메모리의 역사

현재 우리는 메모리를 생각하면 반도체 집적 회로를 떠올린다. 하지만 과거에는 반도체 기술이 지금처럼 발달하지 않았다. 예전에는 반도체 안의 소자, 특히 트랜지스터가 손톱 크기 정도였고, 1비트를 저장하는 데에도 상당한 어려움이 있었다.

트랜지스터 메모리는 1960-1970년대에 사용되었으며, 그 이전에는 진공관 메모리가 있었다. 진공관은 트랜지스터 보다 훨씬 크고 비효율적이었으며, 손가락 서너 개 크기의 진공관이 1비트를 저장할 수 있는 정도였다.

또 다른 초기 메모리 기술로 Core Memory가 있다. 이는 반지 모양의 철심에 자성 물질을 바르고 전기를 흘려 플레밍의 오른손 법칙에 따라 자장이 형성되도록 했다. 전기를 흘려 자석을 만드는 방식을 통해 메모리를 구성했다.

이런 과거의 기술적 한계를 고려할 때, 1비트를 저장하는 데에 굉장히 큰 비용이 들었을 것으로 예상할 수 있다.

1.2. 메모리 용량

메모리 용량은 시간이 지나면서 급격히 증가했다.

• 1970년대: 8-bit PC 64KB
• 1980년대: 16-bit IBM-PC 640KB → 1MB → 4MB
• 1990년대: 수 MB → 수십 MB
• 2000년~: 수백 MB → 수 GB

우리가 배우는 운영체제는 언제 만들어졌을까? 운영체제의 기본 개념은 1960년대에 만들어졌다. (e.g. 리눅스는 1969년에 개발되었다.)

그 시절에는 메모리가 매우 부족했기 때문에, 프로세스 관리도 중요했지만 메모리 관리가 무엇보다도 중요했다. 사람들은 어떻게 하면 작은 메모리를 알차게 사용할 수 있을지 고민하며 다양한 기술을 개발했다.

하지만 지금은 메모리 용량이 매우 커졌다. 그럼 이제 메모리 관리는 중요치 않은 걸까?

그렇지 않다. 메모리는 언제나 부족하다.

1.3. 언제나 부족한 메모리

초등학생 때는 용돈 만 원으로 살고, 중학생 때는 용돈 5만원으로 살고, 고등학생 때는 용돈 10만 원으로도 충분히 살았는데 이제는 그 돈으로는 턱없이 부족하다. 생활 반경이 넓어지고 씀씀이가 커지면서 필요한 돈도 함께 늘어나기 때문이다.

메모리도 마찬가지다. 메모리 용량이 매우 커졌음에도 불구하고, 여전히 메모리는 늘 부족하다.

1950-1960년대에는 프로그램을 작성할 때 주로 기계어, 어셈블리어로 작성했다. 1970년대에는 C 언어와 같은 고급 언어로 작성되기 시작했다. 이후 자바와 같은 객체지향 언어가 등장하면서 프로그램의 규모는 더욱 커졌다. 예전에는 숫자나 문자를 처리하던 프로그램이 지금은 그림, 소리, 비디오 등 다양한 멀티미디어 자료를 처리하게 되면서 데이터의 크기가 기하급수적으로 증가했다.

때문에 현대에도 메모리는 여전히 부족하다. 메모리 관리에 대한 연구는 오랜 연구 분야지만, 그 필요성은 지금도 존재한다.

메모리 관리에서 우리가 배우고자 하는 것은, 이렇게 늘 부족한 메모리를 어떻게 하면 낭비 없이 효율적으로 사용할 수 있을까 하는 것이다.

1.4. 메모리에 프로그램 올리기

1.4.1. 메모리 구조

메모리 구조는 기본적으로 주소(Address)와 데이터(Data)로 이루어져 있다. CPU가 특정 주소를 읽으려고 하면, 해당 주소를 메모리에 보내고 메모리는 그 주소에 해당하는 데이터를 CPU로 돌려준다.

1.4.2. 프로그램 개발

프로그램을 빌드하면 컴파일 과정을 거치면서 원천 파일(Source file), 목적 파일(Object file), 실행 파일(Executable file)이 생성된다.

원천 파일(e.g. main.c)은 고수준 언어나 어셈블리 언어로 작성된 코드가 포함되어 있다. 이 원천 파일을 컴파일하면 목적 파일(e.g. main.o)이 생성된다. 목적 파일은 기계어로 번역된 파일로, 컴파일 과정에서 생성되는 결과물이다. 이 목적 파일은 프로그램 실행에 필요한 코드의 일부만 포함하고 있으며, 나중에 다른 코드들과 연결(Link)되어 최종 실행 파일(e.g. main.exe)이 된다.

1.4.3. 프로그램 실행

실행 파일은 크게 세 가지 주요 세그먼트로 구성된다.

• 코드(Code): 실제 기계어 코드가 저장된 부분
• 데이터(Data): 프로그램이 사용하는 변수들이 저장되는 부분
• 스택(Stack): 함수 호출 시 돌아오는 주소와 지역 변수가 저장되는 부분

1.4.4. 메모리에 실행 파일 올리기

이렇게 만들어진 실행 파일을 메모리에 올려보자. 이걸 메모리의 몇 번지에 올려야 할지 우리는 고민할 필요가 없다. 운영체제가 이 문제를 해결해 주기 때문이다. 운영체제의 메모리 관리 부서에서 Loader가 이 역할을 담당한다.

다중 프로그래밍 환경에서는 여러 프로세스가 메모리에 동시에 올라가 있다. 예를 들어, 오늘은 워드 프로세서를 메모리의 500번지에 올렸다. 내일 해당 주소에 다시 워드 프로세서를 올릴 수 있다는 보장이 있을까? 내일은 해당 주소가 다른 프로세스에 의해 사용될 수 있어 동일한 주소를 보장받을 수 없다.

이 문제를 해결하는 데 중요한 역할을 하는 것이 MMU(Memory Management Unit)이다.

1.4.5 MMU(Memory Management Unit)

MMU는 CPU와 메모리 사이에 위치하며, base 레지스터와 limit 레지스터, 그리고 재배치 레지스터(Relocation Register)를 포함하고 있다.

MMU 덕분에 우리는 실행 파일을 메인 메모리의 어느 곳에나 배치하여 실행할 수 있다.

예를 들어, CPU는 main.exe가 항상 메모리의 0번지에서 실행된다고 가정하지만, 실제로는 500번지에 위치할 수 있다. 이때 MMU가 500번지를 매핑해줌으로써 CPU는 0번지에서 실행된다고 생각하지만 실제로는 500번지에서 실행된다. 만약 다음 날 1000번지에서 실행된다면, MMU는 1000번지를 매핑해준다.

운영체제는 이 재배치 레지스터를 조정하여, 실제 메모리의 어느 위치에 프로그램이 있든지 상관없이 동일하게 실행되도록 한다. 따라서 프로그램이 메모리의 어느 번지에 위치하는지는 중요치 않게 된다.

정리하자면, MMU는 주소 변환(Address Translation)을 수행하여 논리적 주소(CPU가 내는 주소)를 물리적 주소(실제 메모리 주소)로 변환한다. CPU는 항상 동일한 주소를 사용하고 있다고 생각하지만, 실제로 물리적 주소는 매번 다를 수 있다. 이렇게 해서 컴퓨터 내에는 두 가지 주소(논리적 주소, 물리적 주소)가 존재하게 된다.

2. 메모리 낭비 방지

운영체제의 주된 목적은 컴퓨터를 쉽게 사용할 수 있도록 하고, 시스템의 효율성을 극대화하는 것이다. 이 과정에서 중요한 요소 중 하나는 메모리 낭비를 최소화하는 것이다. 메모리 낭비를 줄이기 위해 어떤 요소들이 문제로 작용하며, 이를 어떻게 해결할 수 있을지 알아보자.

2.1. 동적 적재(Dynamic Loading)

예를 들어, 오류 처리를 위한 코드가 있다고 생각해보자. 이는 파일이 정상적으로 열리지 않는 경우에만 실행될 텐데, 실제로 대부분의 경우 파일은 정상적으로 열린다. 이처럼 거의 사용되지 않는 오류 처리 루틴을 메모리에 항상 올려놓는 것은 메모리 낭비다.

동적 적재는 이러한 낭비를 방지하기 위한 방법이다. 동적 적재는 프로그램 실행 시 반드시 필요한 루틴이나 데이터만 메모리에 적재하고, 필요 시에만 추가로 적재한다. 모든 오류 처리, 모든 데이터(e.g. 배열)을 필요할 때에만 메모리에 올리는 것이 동적 적재의 예다.

현재 사용하는 윈도우, 리눅스는 동적 적재를 채택해 메모리 사용의 효율성을 높이고 있다.

cf) 정적 적재(Static Loading): 프로그램의 모든 루틴과 데이터를 미리 메모리에 올리는 방식

2.2. 동적 연결(Dynamic Linking)

여러 프로그램이 공통적으로 사용하는 라이브러리 코드가 있다면, 이를 메모리에 중복해서 올리는 것은 큰 낭비이다. 예를 들어, p1.exe와 p2.exe가 printf와 같은 라이브러리 코드를 사용하는 경우, 이 라이브러리를 각각의 프로그램이 중복해서 메모리에 올린다면 메모리 자원의 낭비가 발생한다.

동적 연결은 이러한 낭비를 방지하는 방법이다. 공통적으로 사용되는 라이브러리 코드를 하나만 메모리에 적재하고, 여러 프로그램이 이를 공유하는 방식이다. 동적 연결은 프로그램이 실행 파일을 우선 만든 뒤 필요에 따라 하드 디스크에서 이를 링크하는 방식으로, 실행 파일을 만들기 전에 링크가 이루어지는 정적 연결(Static Linking)과 대조된다.

리눅스에서는 이러한 공통 라이브러리를 공유 라이브러리(Shared Library)라고 하며, 윈도우에서는 동적 연결 라이브러리(DLL: Dynamic Linking Library)라고 한다.

2.3. Swapping

Swapping은 메모리에 적재되어 있지만 현재 사용되지 않는 프로세스를 메모리에서 하드 디스크로 이동시키는 방법이다.

hwp 프로그램을 사용하던 중에 전화가 와서 잠시 자리를 비운 상황을 생각해 보자. 내가 자리를 비우더라도 프로그램은 여전히 메모리에 올라가서 실행 중에 있고, 이는 명백한 메모리 자원의 낭비이다. 이때 운영체제는 메모리에서 이 프로그램을 하드 디스크로 이동시키고, 다른 프로세스를 위해 메모리를 확보한다.

하드 디스크에 저장된 hwp.exe 파일에는 기본적으로 code와 data가 포함되어 있다. 이 파일이 메모리에 올라가면 code, data, stack으로 구성된다. 하드 디스크에 있는 hwp.exe와 메모리에 적재된 hwp.exe는 동일한 코드 파일을 가질지 몰라도, data와 stack은 메모리에 로드된 후의 상태에 따라 다르게 관리된다.

따라서, 프로세스를 swap-out할 때 단순히 하드 디스크에 있는 원본 파일로 대체할 수는 없다. Swap-out은 하드 디스크의 특정 영역(Backing Store)에 현재까지 실행 중이던 프로세스의 상태(code, data, stack)를 저장하는 것을 의미한다. 이렇게 swap되어 확보된 메모리 공간은 다른 프로세스가 사용하게 되어 메모리 낭비를 방지한다.

하드 디스크는 크게 파일 시스템(File System)과 Backing Store(=Swap Device)로 구분할 수 있다. Backing Store는 swap-out된 프로세스의 이미지를 저장하는 공간이다. 서버나 대형 컴퓨터의 경우, 파일 시스템과 Backing Store를 위한 별도의 하드 디스크를 두기도 한다. 그러나 일반적인 PC나 스마트폰은 하나의 하드 디스크를 나누어 이 기능을 수행한다.

Backing Store의 크기는 대개 메인 메모리 크기와 비슷하게 설정된다. 예를 들어, 메인 메모리가 1GB인 경우, 최대 1GB의 프로세스가 swap-out될 수 있으므로 Backing Store의 크기도 이와 비슷한 크기로 설정된다. 사실 메인 메모리에는 운영체제 영역도 있기 때문에 실제 필요한 크기는 더 작아도 된다. Backing Store의 크기는 시스템에 따라 기본적으로 설정되지만, 사용자가 직접 설정할 수도 있다.

전화를 마치고 돌아와 hwp.exe를 다시 실행하려고 할 때, hwp.exe가 사용 중이던 주소를 다른 프로세스가 사용하고 있다면 hwp.exe는 다른 메모리 영역으로 이동해야 한다. 이때 재배치 레지스터(Relocation Register) 값을 조정하면 문제없이 프로그램 실행이 가능하다.

Swapping 자체는 성능에 부담을 줄 수 있다. 프로세스의 상태를 Backing Store에 기록하는 작업은 하드 디스크의 속도에 의존하기 때문에 느릴 수 있다. 그럼에도 Swapping 덕분에 전체 메모리 활용도는 크게 향상된다. 일부 슈퍼 컴퓨터의 경우, Backing Store를 위해 속도가 느린 별도의 저장 장치를 사용하여 메모리 효율을 극대화하기도 한다.

3. 연속 메모리 할당

최초의 컴퓨터는 OS가 없었기 때문에 메모리에 프로세스 하나만 올라갔다. 시간이 지나면서 메모리에는 운영체제와 프로세스 하나가 올라간다. (e.g. 도스) 이후 메모리에 단일 프로세스와 함께 여러 프로세스가 돌아가는, 다중 프로그래밍 환경이 생성되었다.

3.1. 외부 단편화(External Fragmentation)

부팅 직후의 메모리 상태는 OS와 big single hole로 구성되어 있다. 이후 프로세스가 생성되고 종료되는 것이 반복되며 scattered holes가 생성된다. 즉, 메모리가 쪼개져 있게 되는데, 이를 메모리 단편화(Memory Fragmentation)라고 한다.

Holes의 크기를 100KB, 50KB, 80KB라고 해보자. 새로운 130KB짜리 프로세스를 메인 메모리에 올리고 싶은데, holes가 불연속적으로 흩어져 있어 올릴 수 없다. 이를 외부 단편화라고 한다. 비어 있는 메모리 공간을 합치면 충분히 들어갈 수 있는데 떨어져 있기 때문에 이를 사용할 수 없는 상황을 말한다.

3.2. 연속 메모리 할당 방식

외부 단편화를 어떻게 하면 최소화할 수 있을까? 우선 연속 메모리 할당 방식부터 살펴보자.

• First-fit(최초 적합): 메모리를 순차적으로 돌면서 해당 프로세스가 올라갈 수 있는 곳을 찾으면 즉시 올린다.
• Best-fit(최적 적합): 프로세스의 크기와 가장 밀접한 메모리 공간에 올린다.
  • e.g. 60KB의 프로세스는 100KB가 아니라 80KB에 올린다.
• Worst-fit(최악 적합): 프로세스와 가장 밀접하지 않은 메모리 공간에 올린다. 더 작은 메모리 공간에는 올릴 수 없다.

메모리를 순차적으로 돌면서 알맞은 공간이면 바로 프로세스를 올린다는 점에서 속도 측면으로는 first-fit이 가장 우수하다. 메모리가 가장 효율적으로 활용되는 방식은 의외로 best-fit과 first-fit이 비슷하다. Best-fit 방식이 가장 우수할 것이라고 예상되지만, 여러 케이스를 돌려본 결과 두 방식이 유사하다고 한다. Worst-fit은 언제나 가장 비효율적이다.

그러나 어떤 방식을 사용하든 외부 단편화 문제를 완벽히 해결할 수는 없다. 실제로 이로 인한 메모리 낭비는 $1/3$ 수준에 달한다.

운영체제가 메모리 공간을 지켜보다가, 프로세스를 새로 돌리려고 할 때 실행 중인 프로세스들 또는 holes를 한 곳으로 모으는 것을 Compaction이라고 한다. 이는 외부 단편화를 해결할 수는 있겠으나 부담이 크고, 어떤 프로세스를 어디로 모으는 게 효율적일지 계산하는 최적 알고리즘이랄 게 없다.

4. 가상 메모리

가상 메모리는 물리적 메모리 크기의 한계를 극복하기 위해 개발된 기술이다. 메인 메모리가 100MB밖에 없는데 200MB 크기의 프로그램을 실행하고 싶은 상황을 생각해 보자.

200MB의 프로그램을 실행할 때, 반드시 모든 프로세스 이미지를 메모리에 올려야 할까? 그렇지 않다. 우리는 동적 적재에서 보았듯, 오류 처리 코드와 같이 반드시 필요하지 않은 루틴은 실행 중에 올릴 필요가 없다. 예를 들어, 오류 처리 루틴이 50MB라면 이를 제외하고 150MB만 메모리에 올리면 된다.

그래도 메모리가 부족하다면 사용하지 않을 루틴을 더 제외할 수 있다. 예를 들어, 한글 작업을 하는 동안 정렬 또는 표 만들기 기능을 사용하지 않을 예정이라면, 이들을 메모리에 올리지 않고 당장 사용하는 부분만 올려 실행한다.

결국 가상 메모리의 핵심은, 우리가 프로그램의 모든 코드를 메모리에 올려야 한다고 생각할 필요가 없다는 것이다. 필요한 부분만 메모리에 올려 프로그램을 실행할 수 있다는 개념이 가상 메모리의 본질이다.

4.1. 요구 페이징(Demand Paging)

요구 페이징은 프로세스를 페이지 단위로 나누어, 현재 필요한 페이지만 메모리에 올리는 방식이다. 필요한 페이지가 메모리에 없으면 하드 디스크에서 해당 페이지를 가져오고, 현재 요구되지 않는 페이지는 Backing Store에 저장한다.

페이지 테이블에는 각 페이지 상태를 기록하는 유효 비트(Valid Bit)가 있다. 이 비트를 통해 메모리에 올라와 있는 페이지와 그렇지 않은 페이지(invalid)를 구분할 수 있다. CPU가 요청한 주소가 페이지 테이블에 없으면, MMU는 CPU에 인터럽트를 걸어 OS가 해당 페이지를 하드 디스크에서 메모리로 가져오도록 처리한다.

가상 메모리를 만드는 방법은 대표적으로 두 가지가 있으나, 요구 페이징이 가장 일반적으로 사용되어 두 용어를 동일하게 간주하는 경우가 많다.

4.1.1. Pure Demanding Paging

진짜 필요한 페이지만 메모리에 가져오는 방식이다. 프로그램이 처음 실행될 때 어떤 페이지가 필요한지 예측하지 않고, 처음에는 아무 페이지도 메모리에 올리지 않는다.

처음 프로그램이 실행될 때 페이지 부재가 많이 발생하여 속도가 느려질 수 있으나, 메모리 절약에는 도움이 된다.

4.1.2. Prepaging

앞으로 필요할 것으로 예상되는 페이지를 미리 가져오는 방식이다.

페이지 부재를 줄이고 프로그램 실행 속도를 높일 수 있지만, 미리 가져온 페이지가 실제로 사용되지 않으면 메모리 낭비가 발생할 수 있다.

4.1.3. Swapping vs Demanding Paging

Swapping은 프로세스 전체를 메모리에서 하드 디스크로 내보내고, 필요할 때 전체를 다시 가져오는 방식이다. 반면, Demanding Paging은 필요한 페이지만을 메모리로 가져오는 방식이다.

둘 다 메모리와 Backing Store를 오가는 방식이지만, Swapping은 프로세스 단위로, Demanding Paging은 페이지 단위로 작업이 이루어진다.

4.2. 페이지 부재(Page Fault)

CPU가 요청한 페이지가 메모리에 없을 때 발생하는 상황이다. 페이지 부재가 발생하면 CPU는 하던 일을 멈추고, OS가 해당 페이지를 하드 디스크에서 메모리로 가져오도록 처리한다.

과정은 다음과 같다.

1. CPU가 특정 주소를 요청한다.
2. 해당 주소가 포함된 페이지가 메모리에 없는 경우, MMU가 페이지 부재를 감지하고 CPU에 신호를 보낸다.
3. OS가 하드 디스크를 돌면서 요구 페이지를 찾는다.
4. 요구 페이지를 메인 메모리로 가져온다.
5. 페이지 테이블을 갱신한다.
6. 해당 페이지를 읽어 명령을 마저 수행한다.

4.2.1. 유효 접근 시간(Effective Access Time)

CPU가 메모리에 접근하는 시간은 페이지 부재 발생 여부에 따라 달라진다. 페이지 부재가 발생하지 않으면 메모리에서 데이터를 즉시 가져올 수 있지만, 페이지 부재가 발생하면 하드 디스크에서 데이터를 가져와야 하므로 시간이 더 오래 걸린다.

유효 접근 시간이란 페이지 부재 확률($p$)와 페이지 부재 처리 시간($T_p$), 메모리 접근 시간($T_m$)을 조합한 평균 접근 시간을 의미한다. ($T_{eff}=(1-p)T_m+pT_p$)

아래 예제를 살펴 보자.

• $T_m=200ns$ (DRAM)
• $T_p=8ms$
• $T_{eff} = (1-p)200 + p 8,000,000 = 200 + 7,999,800p$

여기서 페이지 부재 확률의 계수가 매우 커 $p$가 높아질수록 유효 접근 시간 $T_{eff}$가 크게 증가하는 것을 확인할 수 있다.

예를 들어 $p=1/1,000$일 경우, $T_{eff}=8.2μs$으로 $T_m$보다 40배는 느리다. $p = 1/399,990$일 경우 $T_{eff}=220ns$으로 $T_m$보다 10% 느리다.

⏱️ 페이지 부재 처리 시간 $T_p$은 Seek Time, Rotational Delay, Transfer Time으로 구성되어 있다.

하드 디스크의 구조는 원판(플래터)에 자성 물질이 코팅되어 있고, 그 위에 디스크 헤드가 위치하여 데이터를 읽고 쓴다. 디스크 헤드는 전기 코일로 이루어져 있으며, 이 코일에 전류가 흐르면 자성이 발생하고, 자성 물질에 기록된 데이터를 읽을 수 있다. 원판이 고속으로 회전하면서 디스크 헤드가 자성 물질의 변화에 따라 유도된 전기 신호를 감지하여 데이터를 읽어낸다.

하드 디스크에서 데이터를 읽어내는 과정은 다음과 같다.

1. Seek Time: 디스크 헤드를 원하는 트랙(원판의 특정 위치)으로 이동시키는 데 걸리는 시간. 트랙은 원판의 원형 경로를 의미하며, 헤드가 물리적으로 해당 트랙으로 이동해야 한다. 이 과정은 전체 디스크 접근 시간 중 가장 오래 소요되는 부분이다.
2. Rotational Delay: 트랙에 도달한 후, 원판이 회전하여 디스크 헤드 아래로 원하는 데이터가 위치할 때까지의 대기 시간. 원판이 회전하는 속도에 따라 달라지며, 데이터가 헤드 아래에 도착할 때까지의 시간이다.
3. Transfer Time: 디스크 헤드가 데이터를 읽어내는 실제 시간. 원판이 회전하면서 자성 물질의 변화를 감지해 데이터를 읽어들이며, 전기가 유도되는 과정에서 정보가 전송된다.
   이 세 가지 시간을 모두 합한 것이 하드 디스크에서 데이터를 읽는 데 걸리는 총 시간이다. 일반적으로 이들 중 가장 오래 걸리는 시간은 Seek Time이다. Seek Time은 헤드가 물리적으로 움직여야 하기 때문이다.
   이를 거꾸로 생각해 보면, Backing Store를 하드 디스크로 쓰지 않고 SSD, 느린 저가 DRAM을 사용하는 방법을 활용해 유효 접근 시간을 낮출 수 있다.

4.2.2. 지역성의 원리(Principal of Locality)

CPU가 특정 주소를 참조할 때, 그 근처의 주소를 자주 참조하게 된다(Locality of Reference)는 특성을 말한다.

• 시간적 지역성(Time Locality): 최근에 접근한 데이터를 다시 접근할 가능성이 높다.
  • e.g. 보통 컴퓨터 프로그램은 반복문이 많아 방금 읽은 코드를 다시 읽을 가능성이 높다.
• 공간적 지역성(Spatial Locality): 근처 주소를 연속적으로 접근할 가능성이 높다.
  • e.g. 한 명령어 길이가 4byte면, 주소 1000번지에서 시작된 명령어를 읽고 곧바로 1004, 1008, … 등 그 인접 주소의 명령어들도 읽히게 된다.

이 원리 덕분에, 페이지 부재가 발생하면 그 인근의 데이터를 블록 단위로 미리 가져옴으로써 페이지 부재 확률을 줄일 수 있다.

Reference

• [운영체제(OS)] 12. 주기억장치관리
• [운영체제(OS)] 15. 가상메모리
• (56) Swapping
• KOCW 양희재 운영체제

처음 부팅했을 때에는 메모리가 비워져 있다가, 프로그램 실행에 따라 요구되는 페이지들을 backing store에서 가져와 메모리에 올린다. 이를 반복하다 보면 언젠가는 메모리가 가득 차게 된다.

메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고(page-out) 빈 자리에 페이지를 가져온다.(page-in)

1.1. Victim Page

이렇게 빈 자리를 위해 쫓아내는 페이지를 희생양 페이지(Victim Page)라고 한다.

Backing store로 페이지를 몰아낼 때, 즉 하드 디스크로 페이지를 보낼 때 해당 내용을 하드 디스크에 다시 써줘야 할까? 사실 페이지가 단순히 읽기 작업만 수행한 것이라면, 이미 하드 디스크에 있던 내용일 것이다. 그러나 만일 CPU에서 해당 페이지의 내용을 수정했다면 이를 하드 디스크에 다시 저장해야 한다.

하드 디스크는 일반적으로 속도가 느리기 때문에, 데이터를 쓰는 데 시간이 오래 걸린다. 따라서 가능한 한 수정되지 않은 페이지(victim)를 선택해 내보내는 것이 좋다. 수정 여부를 알기 위해 페이지 테이블에 Modified Bit(=Dirty Bit)를 추가하여 검사한다.

위의 그림은 Modified Bit를 추가한 페이지 테이블이다. 그런데 수정되지 않은 페이지는 0, 2, 3으로 복수 개가 존재한다. 어떤 페이지를 victim으로 설정해야 할까?

Random으로 설정하여 가장 간단하지만 성능 또한 제멋대로인 방법도 있을 거고, FIFO를 사용하여 가장 먼저 메모리에 올라온 페이지를 쫓아내는 방법도 있을 것이다.

이처럼 victim page를 어떤 기준으로 선정할 것인지 판단하는 알고리즘을 페이지 교체 알고리즘(Page Replacement Algorithms)이라고 한다.

2. 페이지 교체 알고리즘

페이징에서는 byte보다 페이지 단위가 중요하다. CPU가 낸 주소를 페이지 넘버와 $d$로 나눌 수 있는데, 이 페이지 넘버를 통해 내가 읽으려는 페이지가 메인 메모리의 어느 주소에 위치하는지 알 수 있기 때문이다.

CPU 주소 = 100 101 102 432 612 103 104 611 612
Page No. = 1 1 1 4 6 1 1 6 6

위의 예시에서 Page size = 100byte일 경우 페이지 번호는 1, 1, 1, 4, 6, 1, … 이 된다. (offset은 0, 1, 2, 32, 12, 3, …)

1번 페이지가 Page Fault가 나서 하드 디스크에서 이를 가져온다. 이 뒤에 바로 1번 페이지를 읽으면 절대 Page Fault가 나지 않는다. 이처럼 페이지 번호 중에서 바로 이어지는 번호는 스킵하고 읽는 것을 페이지 참조열(Page Reference String)이라고 한다.

Page Reference String = 1 4 6 1 6

2.1. FIFO(First-In First-Out)

FIFO(First-In, First-Out) 페이지 교체 알고리즘은 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 방식으로 동작한다. 매우 간단한 방식이며, 페이지가 메모리에 올라온 순서를 그대로 유지하여 오래된 페이지를 우선적으로 교체한다.

해당 알고리즘의 아이디어는 가장 처음 메모리에 올라온 페이지는 주로 프로그램 초기화와 관련된 코드나 데이터를 담고 있을 가능성이 높다는 가정이었다.

e.g. 자바와 같은 언어에서는 객체가 생성될 때 생성자 메서드가 실행되며, 이는 한 번만 실행된다.

이처럼 초기화 코드는 대개 프로그램 초기에 한 번만 사용되고, 이후에는 재사용될 필요가 적다. 따라서 메모리에 가장 먼저 올라온 페이지는 초기화에 필요한 코드나 데이터를 담고 있을 가능성이 크다고 판단해 가장 처음 메모리에 올라온 페이지를 교체 대상으로 선택하는 것이 합리적이라 생각되어 고안된 것이다.

2.1.1. 예제

페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 0 1
# of frames = 3

최종적으로 Page Fault는 15번 발생한다.

예제를 보면 알 수 있듯, 직전에 내보낸 페이지가 다시 필요한 경우가 있다. 단순히 처음 들어온 페이지를 Page-out하는 구조이기 때문에 이와 같은 경우 비효율적이라는 것을 알 수 있다.

2.1.2. Belady’s Anomaly

일반적으로 메인 메모리의 용량이 작을수록 Page Fault가 더 자주 발생할 가능성이 크다. 메모리에 적재할 수 있는 페이지의 수가 제한적이기에 필요한 페이지를 자주 교체해야 하기 때문이다.

그러나 FIFO(First-In, First-Out)를 사용할 때, 메모리의 프레임 수가 증가함에 따라 페이지 폴트 횟수가 오히려 증가하는 현상이 발생할 수 있다. 이 현상을 Belady's Anomaly라고 한다.

Belady's Anomaly는 FIFO 알고리즘의 특성상 발생하는데, 이는 페이지 참조열이 특정한 패턴을 가질 때 주로 나타난다.

e.g. 페이지 참조열이 순환적이거나 일정한 패턴을 반복하는 경우, FIFO는 초기의 오래된 페이지를 반복적으로 교체하며 더 많은 프레임을 할당받았음에도 불구하고 PF가 증가한다.

이러한 이유로 FIFO는 단순한 알고리즘이지만, 모든 상황에서 최적의 성능을 보장하지는 않는다.

2.2. Optimal(OPT)

위에서 언급한 FIFO의 문제점들을 해결하기 위해, 앞으로 가장 오랫동안 사용되지 않을 페이지를 victim으로 선택하는 방법이 있다. 이 방식을 사용하면 동일한 페이지 참조열과 동일한 프레임 개수에서 Page Fault가 9번 발생하게 된다.

그러나 이 방식은 unrealistic하다. 실제 컴퓨터가 실행될 때, 앞으로 어떤 페이지가 사용되지 않을지 미래를 알 수 없기 때문이다. 따라서 알고리즘으로는 설명할 수 있으나 현실에서 적용하기는 어렵다.

cf) CPU 스케줄링의 Shortest Job First(SJF) 알고리즘

이를 통해 우리는 앞으로 사용되지 않을 페이지를 예측하는 것이 중요하다는 것을 알 수 있다. 해당 아이디어를 가져가면서 realistic한 방법은 없을까?

2.3. Least-Recently-Used(LRU)

미래를 정확히 예측할 수는 없지만 과거를 보면 대략 짐작할 수는 있다. 과거에 시험을 잘 본 사람은 앞으로의 시험을 잘 볼 확률이 높듯 말이다.

LRU는 최근에 가장 오랫동안 사용되지 않은 페이지를 victim으로 설정하는 방식이다. 아이디어는 최근에 사용되지 않았으면 앞으로도 사용될 일이 적을 것이라는 가정이다. 단, ‘최근’의 일이어야만 영향을 미친다고 본다. 유치원 때 공부를 잘했다고 성인이 되어서도 반드시 공부를 잘하는 것은 아닌 것과 비슷하다.

이 방식을 사용하면 동일한 페이지 참조열과 동일한 프레임 개수에서 Page Fault가 12번 발생하게 된다. OPT보다는 많고, FIFO 보다는 적다. OPT는 가장 이상적인 방법이나 적용이 어렵고, FIFO는 가장 간단하나 성능이 좋지 않고 메모리가 증가헀음에도 PF가 증가하는 기현상이 있어 대부분의 컴퓨터는 LRU를 채택한다.

2.4. 교체 방식

2.4.1. Global replacement

메모리 상의 모든 프로세스를 대상으로 하여 victim을 선택하는 방법이다. 모든 프로세스의 메모리 자원을 공유하는 방식으로, 특정 프로세스의 페이지 폴트가 발생할 때 다른 프로세스의 페이지를 희생양으로 선택할 수 있다.

2.4.2. Local Replacement

특정 프로세스의 메모리 공간에서만 victim을 선택하는 방법이다. 각 프로세스가 할당받은 메모리 내에서만 페이지 교체가 이루어지도록 제한한다.

e.g. $P_1$의 5번 페이지에서 Page Fault가 발생했을 때, $P_1$의 페이지들에 한정하여 FIFO, LRU 등과 같은 알고리즘을 적용해 victim을 선택한다.

💡 Global vs Local Replacement

• Global replacement가 대개 더 효율적이다. 이는 모든 프로세스의 페이지를 대상으로 선택할 수 있기 때문에, 시스템 전체적으로 최적의 victim을 선택할 가능성이 높아지기 때문이다.

• 반면, Local replacement는 특정 프로세스의 페이지에만 제한되기 때문에, 선택의 폭이 좁아져 전체 시스템 성능이 저하될 수 있다.
  정리하자면, Global replacement는 시스템 자원의 전반적인 효율성을 높이는 반면, Local replacement는 각 프로세스의 독립성을 보장하는데 더 유리하다.

Reference

• KOCW 양희재 운영체제
• [운영체제(OS)] 15. 가상메모리
• What is Belady's Anomaly in Operating System

코끼리를 냉장고에 넣으려면 어떻게 해야할까? (잔인하지만) 코끼리를 잘라서 냉장고에 넣으면 된다.

우리는 이전까지 프로세스는 메모리 공간에 연속적으로 존재해야 한다고 생각했다. 하지만 꼭 연속적으로 존재해야 할까? 페이징은 이런 발상의 전환으로부터 등장했다.

프로세스를 일정한 크기(=페이지)로 잘라서 메모리에 올리는 것을 페이징이라고 한다.

그런데 프로세스가 잘라져 있어도 실행될 수 있을까? CPU가 프로세스가 연속적으로 존재한다고 착각하게 만들면 된다. MMU의 재배치 레지스터를 여러 개 사용해 아래 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이런 목적으로 사용되는 MMU는 재배치 레지스터가 테이블과 같은 형태로 배치되어 페이지 테이블(Page Table)이라고 한다.

프로세스를 자른 단위를 페이지, 메모리를 자른 단위를 프레임이라고 한다.

위의 그림에서는 프로세스 $P_1$을 5개의 페이지로 나누고, 이를 메인 메모리 5곳에 나누어 할당하였다. CPU는 논리 주소를 사용해 연속적인 주소값으로 명령을 내리지만, 메모리에 접근하기 전에 각 페이지의 실제 물리 주소를 찾아야 한다. 이를 위해 페이지 테이블이 사용되며, 이는 논리 주소를 해당 페이지의 물리 주소로 변환하는 역할을 한다.

1.1. 주소 변환(Address Translation)

CPU가 내는 주소를 논리 주소(Logical Address)라고 한다. 이 논리 주소를 메모리로 가는 물리 주소(Physical Address)로 바꿔줘야 한다.

앞서 언급한 바와 같이, CPU가 메모리의 여러 곳에 흩어진 페이지에 접근하기 위해서는 페이지의 물리 주소가 필요하다. 이를 어떻게 변환하는지 알아보자.

1.1.1. 논리 주소(Logical Address)

논리 주소는 2진수로 표현된다.전체 비트를 $m$이라고 했을 때, 하위 $n$비트는 오프셋(offset) 또는 변위(displacement)라고 한다. 상위 $m-n$비트는 페이지 번호다.$(n=d, m-n=p)$

1.1.2. 물리 주소(Physical Address)

물리 주소는 프레임 번호($f$)와 변위($d$)로 구성된다. 페이지 번호($p$)는 페이지 테이블의 인덱스 값이고, 변위는 변하지 않는다.

1.1.3. 예제

Page size = 4bytes, Page Table: 5 6 1 2일 때, 논리 주소 13번지는 물리 주소 몇 번지인가?

$13=1101_2$이고, $4=2^2$이므로 $d=2$이다. 따라서 뒤의 두 칸이 $d$를 가리키고, $p$는 $d$를 제외한 나머지 크기이다.

13 = 1101
p = 11
d = 01

$p=11_2=3$이므로 페이지 번호 3번을 가리킨다. 페이지 3번에 해당하는 프레임 번호는 2번이므로, 물리 주소를 구성하는 $f$값은 2가 된다.

f = 10
d = 01
물리 주소 = 1001

이처럼 프로세스를 흩어지게 함으로써 더이상 외부 단편화는 발생하지 않게 되나, 내부 단편화라는 문제가 생긴다.

1.2. 내부 단편화(Internal Fragment)

페이지 사이즈가 4byte이고, 프로세스 크기는 15byte라고 하면 페이지는 4개가 필요하다. 마지막 페이지는 크기를 다 채우지 못하고 1byte가 남게 된다.

프로세스 크기가 페이지 크기의 배수가 아닐 때 마지막 페이지가 한 프레임을 다 채울 수 없는 것을 내부 단편화라고 한다. 공간이 남는다는 것은 곧 메모리 낭비를 의미한다.

하지만 내부 단편화로 낭비되는 메모리의 최대 크기는 (page size - 1)byte쯤 된다. 이는 매우 미미한 수준이어서 크게 문제가 되지 않는다.

1.3. 페이지 테이블 만들기

CPU와 메모리 사이에는 페이지 테이블이 있는데, 이를 만드는 방법은 여러 가지가 있다.

1.3.1. CPU 레지스터

MMU를 CPU 안에 넣는 방법이다. 페이지 테이블은 프레임 넘버를 기억하기 때문에 일종의 기억장치이다. 따라서 CPU 안의 기억장치인 레지스터로 페이지 테이블을 만들 수 있다.

CPU 안에 있기 때문에 주소 변환이 매우 빠르다는 장점이 있으나, 많이 넣을 수는 없다는 단점이 있다.

1.3.2. 메모리

MMU를 메인 메모리 안에 넣는 방법이다. 메모리는 용량이 매우 크므로 페이지 테이블의 엔트리 개수가 아무리 많아도 넣기 용이하다.

하지만 주소 변환 속도가 느리다는 단점이 있다. CPU가 주소를 내면 그 주소는 OS 영역 안에서 페이지 테이블을 한 번 읽고, 읽고 나서 나온 프레임 넘버에 따라 물리 주소로 가야하기 때문이다.

1.3.3. TLB(Translation Look-aside Buffer)

MMU를 캐시 메모리로 만드는 방법으로, 실제로 가장 많이 사용된다. 별도의 high speed SRAM 칩을 만들어 주소 변환만을 위해 이용하는 걸 TLB라고 부르며, 원리는 캐시 메모리와 동일하다.

이 방식은 CPU 레지스터로 만드는 방법이나 메모리로 만드는 방법과 테이블 엔트리 개수, 변환 속도 측면에서 성능을 비교할 수 있다.

e.g. TLB 사용 시 유효 메모리 접근 시간(Effective Memory Access Time) 구하기

메모리를 읽는 데 걸리는 시간 $T_m=100ns$, TLB를 읽는 시간 $T_b=20ns$, 어떤 주소가 페이지 테이블 엔트리에 있을 확률 hit ratio = 80%

$T_e=h(T_b+T_m)+$$(1-h)(T_b+T_m+T_m)$$=0.8120+0.2220=140ns$

이는 $T_m=100ns$보다 40% 느려진 시간이나, 실제로는 hit ratio가 95% 이상에 달하기 때문에 외부 단편화 해결을 위해 감수해야 하는 부분이라고 할 수 있다.

1.4. 보호와 공유

1.4.1. 보호(Protection)

운영체제가 해야하는 중요한 일 중 하나가 보호이다. CPU가 내는 모든 주소는 페이지 테이블을 경유하므로 해당 페이지에 대한 접근 제어가 가능하다.

페이지 테이블은 엔트리마다 r(read), w(write), x(execute) 비트를 두어 해당 비트의 값에 따라 수행 여부를 결정한다.

e.g. 2번 엔트리에 읽기 비트가 꺼져있는데 읽기 작업을 시도하면 CPU에 인터럽트가 발생하여 ISR에서 강제로 해당 프로세스를 종료시킨다.

1.4.2. 공유(Sharing)

하나의 프로그램이 실행될 때 code, stack, data가 필요하다. 같은 프로그램을 사용하는 복수 개의 프로세스 $P_A, P_B, P_C$가 있다고 해보자. 이들은 각각 독립적인 프로세스이기 때문에 data가 다르고, stack과 같이 실행 시점에 따라 달라지는 지역 변수 등도 다를 것이다.

하지만 같은 프로그램이기 때문에 code 영역은 동일하다. 동일한 값을 중복되게 메모리에 띄우는 것은 명백한 낭비이다. 따라서 같은 프로그램을 쓰는 프로세스가 있다면 code 영역을 공유하여 컨텍스트 스위치가 될 때마다 같은 곳을 가리키게 한다.

단, 코드가 실행되는 동안 스스로 내용을 바꾸지 않는다는 전제가 있어야 한다. 이는 non-self-modifying code = reentrant code(재진입가능 코드) = pure code라고 한다.

2. 세그멘테이션(Segmentation)

코끼리를 냉장고에 넣을 때 그냥 일정 크기로 자르는 방법도 있고, 부위별로 자르는 방법이 있다.

앞서 우리는 프로세스를 일정한 크기에 따라 잘랐다. 세그멘테이션은 프로세스를 논리적 내용, 세그먼트 단위로 잘라 메모리에 올리는 것을 말한다. 이때문에 세그먼트의 크기는 일정하지 않다.

2.1. 주소 변환(Address Translation)

세그멘테이션을 위한 테이블을 세그먼트 테이블이라고 한다. 세그먼트 테이블은 세그먼트 번호, base, limit으로 구성되어 있다.

세그먼트 번호($s$)는 세그먼트 테이블 인덱스 값을 의미한다. Base는 시작 번지, 즉 해당 세그먼트가 메모리 몇 번지에 있는지를 의미한다. Limit은 세그먼트 크기를 의미한다.

세그먼트의 주소 변환 역시 페이징 주소 변환과 유사하나, 세그먼트의 크기는 일정하지 않기 때문에 테이블에 limit 정보가 주어진다. CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해 해당 프로세스를 강제로 종료시킨다.

위 그림은 세그먼트 테이블과 프로세스가 할당된 메모리의 모습이다. 페이징 주소 변환과 동일하게 $d$는 논리 주소와 물리 주소가 동일하다. 물리 주소는 $base[s]+d$로 계산된다.

e.g.

• 논리 주소 (2, 100) ⇒ 물리 주소 4400번지
• 논리 주소 (1, 500) ⇒ 인터럽트로 인해 프로세스 강제 종료(잘못된 세그먼트 violation)

2.2. 보호와 공유

세그멘테이션은 보호와 공유 측면에서 페이징보다 더 나은 방법이다. 핵심은 세그멘테이션은 프로세스를 기능 단위로 자른다는 점이다.

2.2.1. 보호(Protection)

모든 주소는 세그먼트 테이블을 경유하므로 세그먼트 테이블 엔트리마다 r, w, x 비트를 두어 해당 세그먼트에 대한 접근을 제어한다.

프로세스를 자를 때에 페이징은 그저 일정 크기로 자르기 때문에 예를 들어 어떤 페이지에는 code가 있고, 다음 페이지에는 data+code가 있고, 다음 페이지에는 code+stack이 있다.

반면 세그멘테이션은 기능별로 자르기 때문에 섞일 일이 없다. Data는 읽고 쓰되 실행은 하면 안 될 것이고, 어떤 것은 읽기만 하고 실행과 쓰기를 하면 안 된다. 그런데 페이징처럼 어중간하게 잘리면 r, w, x 비트를 어떻게 설정할지 곤란해진다.

따라서 보호의 측면에서 프로세스를 논리적으로 의미가 있는 구분으로 자르는 것이 더 나은 방식이다.

2.2.2. 공유(Sharing)

같은 프로그램을 돌리는 복수의 프로세스가 있을 때, 세그먼트 테이블의 code 영역이 같은 곳을 가리키게 하면 된다. 세그먼트는 확실하게 code 영역을 자르기 때문에, 페이징과 다르게 code 영역이 확실히 분리된다. 이때문에 공유의 측면에서도 세그멘테이션은 페이징보다 우월하다.

그럼에도 대부분의 운영체제는 페이징을 사용한다. 왜 그런 것일까?

2.3. 외부 단편화(External Fragment)

1.1에서 설명한 것과 같이, 다중 프로그래밍에서는 프로세스가 실행되고 종료됨에 따라 메모리에 hole이 생긴다. 이때문에 남는 메모리 공간 자체는 충분함에도 프로세스를 할당하지 못하는 외부 단편화 문제가 발생한다.

세그멘테이션에서도 똑같은 문제가 발생하는데, 이는 세그먼트가 논리적인 단위로 나누어져 크기가 상이하기 때문이다. 이로 인해 다양한 크기의 hole이 발생해 외부 단편화 문제가 또다시 나타난다.

3. 세그멘테이션과 페이징

이러한 문제 때문에 세그먼트를 페이징하는 방식이 나타났다.

프로세스를 자를 때 처음에는 세그먼트로 자른다. 그런데 이를 바로 메인 메모리에 올리면 외부 단편화 문제가 발생할 수 있기 때문에 세그먼트를 다시 일정 간격, 즉 페이지 단위로 자른다. 이를 Paged Segmentation이라고 한다.

이를 통해 우리는 두 가지 방식의 장점을 둘 다 가져갈 수 있게 되었다. 그런데 이는 주소 변환에 있어 시간적 부담이 늘어난다는 단점이 있다. 처음 주소가 세그먼트 테이블로 가고, 그 다음 페이징 테이블로 가서 단계가 하나 늘어났기 때문이다.

Paged Segmentation으로 보호와 공유 측면, 외부 단편화 문제에서도 더 뛰어난 성능을 가져갈 수 있게 되었으나, 이러한 이점에는 시간이 더 오래 걸린다는 trade-off가 따른다.

Reference

• KOCW 양희재 운영체제
• [운영체제(OS)] 13. 페이징

1. 동기화 도구

1.1. 세마포어(Semaphore)

n. (철도의) 까치발 신호기, 시그널; U (군대의) 수기 신호 OS에서의 세마포어란, 동기화 문제를 해결하기 위한 소프트웨어 툴로, 역사가 굉장히 오래되었다.

세마포어는 정수형 변수와 두 개의 동작(P, V)으로 구성되어 있다. P는 Proberen(test), 정수 값을 테스트한다는 의미이고 acquire()로 사용한다. V는 Verhogen(increment), 정수 값을 증가시킨다는 의미이고 release()로 사용한다.

class Semaphore {
    int value; // number of permits

    Semaphore(int value) {
        ...
    }

    void acquire() {
        value--;
        if (value < 0) {
            add this process/thread to list;
            block;
    }

    void release() {
        value++;
        if (value <= 0) {
            remove a process P from list;
            wakeup P;
    }
}

Stack에 push, pop 동작이 있듯, 세마포어에는 acquire, release 동작이 있다.

acquire는 정수 값을 1만큼 감소시키고, 이 값이 0보다 작으면 이 acquire를 호출한 프로세스(혹은 스레드)를 세마포어의 큐에 집어 넣는다. 이 프로세스는 누가 꺼내주기 전까지 block 상태이다.

release는 정수 값을 1만큼 증가시키고, 이 값이 0보다 작거나 크면 세마포어 큐 안에 어떤 프로세스가 갇혀 있는 것을 의미한다. 따라서 해당 프로세스를 wakeup하여 세마포어 큐에서 해방시킨다.

세마포어의 일반적 사용에 대한 예시를 보며 이해해 보자.

1.1.1. Mutual exclusion

한 프로세스가 임계구역으로 들어가면 다른 프로세스는 들어가지 못한다.

세마포어의 초기값이 1이라고 해보자. 이 세마포어에 대해 acquire를 호출하면 value는 0이 되고, 해당 프로세스는 임계구역으로 진입한다.

이후 컨텍스트 스위치가 일어나 다른 프로세스가 acquire를 호출했다고 해보자. value는 0보다 작기 때문에 이 프로세스는 세마포어의 큐에 갇힌다. 즉, 임계구역으로 진입하지 못한다.

// Parent

sem.acquire();
/////////////////////////
int temp = balance + n;
System.out.print("+");
balance = temp;
/////////////////////////
sem.release();

// Child

sem.acquire();
/////////////////////////
int temp = balance - n;
System.out.print("-");
balance = temp;
/////////////////////////
sem.release();

여러 자원이 동시에 사용 가능한 경우는 어떨까?

세마포어 값은 1 이상이 될 수 있으며, 이때는 여러 프로세스가 동시에 자원에 접근할 수 있다. 이런 상황에서는 자원 간 경합이나 데이터 불일치 문제가 발생할 수 있기 때문에, Strict Mutual Exclusion(엄격한 상호 배제)이 요구되는 경우에는 세마포어만으로는 해결이 어렵다.

1.1.2. Ordering

세마포어의 초기값이 0이라고 해보자.

$P_1→P_2$의 순서로 프로세스를 실행시키고 싶다. $P_1$부터 실행시키면 우리가 원하는 대로 될 것이고, 공교롭게도 CPU가 $P_2$를 먼저 돌린다고 하더라도 acquire을 호출하여 $P_2$는 세마포어 큐에 갇히게 된다. 그렇게 되면 $S_2$로 넘어가지 못하고 컨텍스트 스위치가 일어나 $P_1$이 실행된다. 이후 $P_1$이 release를 호출해 value를 증가시키고 $P_2$가 깨어나게 된다.

세마포어를 따로 두고 하나가 풀리면 하나를 가두는 것을 반복하면 두 프로세스를 교대로 실행할 수 있다.

1.1.3. 특징

이처럼 세마포어는 여러 프로세스가 동시에 자원에 접근하는 것을 제어하기 위해 사용된다. 예를 들어, 동시에 n개의 자원을 사용할 수 있는 환경에서는 세마포어가 유용하다. 또한 세마포어는 프로세스의 실행 순서를 제어하거나, 교대 작업을 수행할 때 유용하게 사용된다.

하지만 세마포어는 여러 자원을 관리할 수 있다는 점에서 유연했지만, 앞서 언급했듯 Strict Mutual Exclusion을 완벽히 보장하지는 못하는 한계가 있었다. 즉, 특정 자원에 오직 하나의 프로세스만 접근해야 할 경우를 안전하게 처리하기에는 부족했다. 이로 인해 더 엄격한 동기화가 필요하다는 요구가 생겨났고, 그 결과 뮤텍스가 등장하게 된다.

1.2. 뮤텍스(Mutex)

뮤텍스는 이진 잠금 장치로, 단 하나의 프로세스 또는 스레드만이 임계구역에 접근할 수 있도록 보장한다. 이 방식은 자원에 대해 엄격한 배타적 접근을 요구하는 경우에 적합하다.

1.2.1. 동작 과정

• Lock: 임계구역에 들어가기 전에 잠금을 설정하여 다른 프로세스가 접근하지 못하도록 한다.
• Unlock: 임계구역을 벗어나면 잠금을 해제하여 다른 프로세스가 자원에 접근할 수 있도록 한다.

class Mutex {
    boolean isLocked = false;

    void lock() {
        while (isLocked) {
            wait;  // 잠겨 있으면 대기
        }
        isLocked = true;  // 잠금 설정
    }

    void unlock() {
        isLocked = false;  // 잠금 해제
        notify();  // 기다리는 스레드를 깨움
    }
}

뮤텍스는 자원을 소유한 프로세스만이 unlock()을 호출할 수 있다는 점에서, 세마포어와 구분된다. 세마포어는 누가 release()를 호출해도 세마포어 값을 증가시킬 수 있지만, 뮤텍스는 자원을 점유한 프로세스만이 잠금을 해제할 수 있는 소유권 개념이 있다.

1.2.2. 특징

뮤텍스는 CPU 자원을 절약할 수 있는 장점이 있다. 자원이 사용 중일 때 스레드가 뮤텍스 큐에 들어가 대기 상태로 전환되기 때문에, CPU 사이클을 소모하지 않는다. 이는 특히 멀티 코어 시스템에서 스레드가 자주 대기해야 하는 상황에서 유리하다.

반면 스레드를 대기 상태로 전환하고 다시 실행 상태로 전환할 때, 컨텍스트 스위치가 발생하며 이 과정에서 성능 오버헤드가 발생할 수 있다는 단점이 있다.

❓ 뮤텍스 큐에서 임계구역이 해제되면, 순서가 된 프로세스가 CPU 점유권을 즉시 갖게 될까?

일반적으로 뮤텍스 큐에서 임계구역이 해제되면 그 큐에서 대기 중이던 프로세스 또는 스레드는 즉시 실행 상태(ready state)로 전환된다. 하지만 실행 상태로 전환된다고 해서 바로 CPU 점유권을 강제로 가져가지는 않는다. CPU를 실제로 점유하기 되는지 여부는 스케줄러에 의해 결정된다.

선점형 스케줄링의 경우 프로세스가 높은 우선순위를 갖고 있다면, 현재 CPU에서 실행 중인 스레드를 선점하고 CPU를 획득한다. 비선점형 스케줄링의 경우 임계구역이 해제되어도 즉시 CPU를 획득하지 못하고, 현재 CPU를 점유하고 있는 프로세스의 작업이 끝날 때까지 대기하게 된다.

만약 매번 뮤텍스 해제로 인해 강제로 CPU가 선점된다면, 컨텍스트 스위칭이 너무 자주 발생하여 성능 문제가 생길 수 있다. 이를 방지하기 위해 운영체제는 우선순위 기반 스케줄링, 타임 슬라이스 제어 등 다양한 기법을 사용해 효율적인 CPU 점유를 보장한다.

⇒ 정리하자면, 뮤텍스 해제 시 순서가 된 프로세스가 반드시 CPU를 강제로 점유하지는 않으며, 스케줄러가 적절한 시점에 프로세스를 실행하게 된다. 이로써 불필요한 컨텍스트 스위칭을 줄이면서도 효율적인 자원 할당이 이루어진다.

1.2.3. 스핀락 vs 뮤텍스

스핀락(Spinlock)은 뮤텍스와 유사하게 임계구역을 보호하기 위한 락이지만, 자원을 점유하고 있는 스레드가 해제될 때까지 계속해서 반복적으로 확인(스핀)한다. 즉, 자원이 사용 중일 때 자원을 기다리는 스레드는 대기 상태로 전환되지 않고, 그 자원이 풀릴 때까지 CPU 사이클을 소모하며 자원을 획득하려는 시도를 계속 반복한다. 이를 바쁜 대기(busy waiting)라고 부르기도 한다.

스핀락은 자원을 기다리는 동안 CPU 자원을 계속 소모하지만, 락을 짧은 시간 내에 해제할 수 있는 경우에는 뮤텍스보다 성능이 좋을 수 있다. 스핀락은 짧은 임계구역이나 컨텍스트 스위치가 비용이 큰 환경에서 효과적이다.

Reference

• KOCW 양희재 운영체제

현대 운영체제에서는 보통 스위칭이 스레드 단위로 일어나기 때문에 정확히는 Thread synchronization이라고 할 수 있다.

프로세스는 일반적으로 두 부류로 나눌 수 있는데 하나는 Independent 프로세스이다. 프로세스 간에 아무런 관계가 없다면 independent하다고 볼 수 있다. 반면 어떤 형태로든 두 프로세스가 영향을 주고 받는다면 Cooperating 프로세스이다.

대부분의 프로세스는 사실 협력 관계에 해당되는데, 예를 들어 명절 기차표 예약, 수강신청을 생각해 보면 여러 사용자가 같은 데이터에 접근을 해 서로 간에 영향을 준다.

이처럼 공유된 데이터에 동시 접근이 발생할 때, 데이터에는 inconsistency가 야기될 수 있는데, 이를 경쟁 상태(Race Condition)라고 한다. 프로세스 동기화는 협력 관계에 놓인 프로세스에 순서를 정해 실행하여, 데이터 consistency를 유지하는 것이다.

1.1. BankAccount Problem

부모님이 은행 계좌에 입금을 하고, 자녀는 출금하는 상황을 생각해 보자. 입금(deposit)과 출금(withdraw)은 독립적으로 일어난다.

class BankAccount {
    int balance;

    void deposit(int amount) {
        balance += amount;
    }

    void withdraw(int amount) {
        balance -= amount;
    }

    int getBalance() {
        return balance;
    }
}

class Parent extends Thread {
    BankAccount b;

    Parent(BankAccount b) {
        this.b = b;
    }

    public void run() {
        for (int i = 0; i < 100; i++) {
            b.deposit(1000);
        }
    }
}

class Child extends Thread {
    BankAccount b;

    Child(BankAccount b) {
        this.b = b;
    }

    public void run() {
        for (int i = 0; i < 100; i++) {
            b.withdraw(1000);
        }
    }
}

class Test {
    public static void main(String[] args) 
        throws InterruptedException {
        BankAccount b = new BankAccount();
        Parent p = new Parent(b);
        Child c = new Child(b);
        p.start();
        c.start();
        p.join();
        c.join();
        System.out.println("Balance = " + b.getBalance());
    }
}

위의 파일을 실행해 보면 balance는 0원으로 출력이 된다.

Balance = 0

여기에 시간 지연을 주면 어떻게 될까?

class BankAccount {
    int balance;

    void deposit(int amount) {
        int temp = balance + amount;
        System.out.println("+");
        balance = temp;
    }

    void withdraw(int amount) {
        int temp = balance - amount;
        System.out.println("-");
        balance = amount;
    }

    int getBalance() {
        return balance;
    }
}

deposit, withdraw 함수에 temp 변수를 따로 선언하여 balance 값을 업데이트 하도록 하고, “+”, “-”를 출력하도록 하여 입출금 동작에 시간 지연을 추가했다.

++--+++++++++++++++++++++++++-------------------------++++++++++-----++
-------+++++++-----------------++++++++--------------------------+-----
...
...Balance = 1000000

실행 결과는 실행할 때마다 다르다. 0원보다 많게 나올 때도 있고, 0원보다 적게 나올 때도 있다. 상식적으로는 똑같이 1000원을 100번 입금하고, 100번 출금했는데 왜 0원이 나오지 않을까?

우리는 balance라는 공통 변수를 이용하는데 이를 동시에 업데이트 하려고 해서 문제가 생긴 것이다. High level language로는 한 줄이지만 low level language로는 여러 줄인데, 공통 변수가 업데이트되는 도중에 스위칭이 일어난 것이다.

LDR r0, [balance]
LDR r1, [amount]
ADD r0, r0, r1
STR r0, [balance]

이를 해결하기 위해서는 위 네 개의 명령이 atomic하게, 즉 분해되지 않고 한 번에 처리되어야 한다. 만약 3번째의 ADD 명령어를 수행하다가 문맥 전환이 일어나서 balance의 값이 원래 값과 달라지면 위에서 설명한 상황처럼 데이터의 일관성이 깨지게 된다.

이처럼 둘 이상의 스레드가 동시에 접근해서는 안 되는 공유 자원(예제에서는 balance)을 접근하는 코드의 일부를 임계구역이라고 한다.

2. 임계구역 문제(The Critical-Section Problem)

의미 그대로는 이 구간에서 무언가 치명적인(critical) 오류가 일어날 수 있다는 의미이다.

여러 개의 스레드로 이루어진 시스템에서, 각각의 스레드는 어떤 코드의 영역을 가지고 있는데 이를 critical section이라고 한다. 이 안에서 여러 스레드들은 공통 변수, 테이블, 파일을 수정한다. 1.1의 예시에서는 balance라는 공통 변수를 업데이트하는 부분을 임계구역이라고 한다.

우리가 만들어야 하는 임계구역 문제의 해결은 아래 세 가지가 전부 만족되어야 한다.

• Mutual exclusion(상호배타): 공통 변수에 대한 업데이트는 상호배타적이어야 한다.
  • e.g. Parent가 critical section 안에 들어가면, 즉 balance라는 공통 변수를 업데이트하면 Child는 이를 업데이트해서는 안 된다. 그 반대도 마찬가지다.
• Progress(진행): 임계구역에 어떤 스레드가 먼저 들어갈 것인지 결정하는 것은 유한 시간 내에 결정되어야 한다.
• Bounded waiting(유한대기): 어느 스레드라도 기다리고 다른 스레드가 기다리고 있다면 그 스레드는 유한 시간 내에 임계구역에 들어갈 수 있다.

Reference

• KOCW 양희재 운영체제

1. 교착상태(Deadlock)

프로세스는 실행을 위해 여러 자원을 필요로 한다. (e.g. CPU, 메모리, 파일, 프린터, …) 그러나 프로세스가 필요로 하는 자원은 보통 하나이고, 프로세스들은 공통된 자원을 나누어 써야 하는 상황인 것이다. 이때 운영체제가 이 프로세스들에게 자원을 제대로 나누어 주지 못하면 교착상태(Deadlock)에 빠지게 된다.

e.g. 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때(e.g. 다른 프로세스가 사용 중) 대기해야 할 때 교착상태에 빠지게 된다.

교착상태에 빠진다는 것은 다음의 네 가지 필요 조건을 모두 만족해야 일어날 수 있다.

• Mutual exclusion(상호배타): 하나의 프로세스가 자원을 점유 중일 때, 다른 프로세스는 해당 자원을 점유하지 못하는 것
• Hold and wait(보유 및 대기): 본인이 다른 자원을 보유하고 있으면서 다른 자원이 올 떄까지 대기하는 것
• No Preemption(비선점): 다른 프로세스가 점유하고 있는 자원을 빼앗지 못하는 것
• Circular wait(환형대기): 프로세스들이 자원을 기다리는 관계가 원형으로 연결된 상태
  • 프로세스 A → 프로세스 B가 점유한 자원 대기, 프로세스 B → 프로세스 C가 점유한 자원 대기, 프로세스 C → 프로세스 A가 점유한 자원 대기

정리하자면 교착상태는 결국 하드웨어 자원이 한정적으로 존재하기 때문에 발생한다고 볼 수 있다.

2. 자원(Resources)

프로세스가 자원을 사용하기 위해서는 OS에 요청(request)을 한다. OS는 요청이 올바를 경우 프로세스가 이를 사용(use)하게 한다. 자원을 다 쓰고 나면 OS에 해당 자원을 반납(release)한다.

2.1. 자원 할당도(Resource Allocation Graph)

자원 할당도는 컴퓨터에 어떤 자원이 있고 그 자원이 어떤 프로세스에 할당되었는지, 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는지 시각적으로 표현하는 도구이다. 이를 통해 교착상태의 발생 여부를 판단할 수 있다.

동일 자원이 여러 개 있을 수 있다. 각각을 instance라고 한다.

자원은 사각형, 프로세스는 원, 할당은 화살표로 표시한다.

• 환형대기 x, 교착상태 x

• 식사하는 철학자 문제. 환형대기 o, 교착상태 가능성 o

3. 교착상태 처리

교착상태는 위에서 언급한 필요 조건들을 전부 만족했을 때 일어날 ‘수’ 있다. 즉, 컴퓨터에서 교착상태는 잘 일어나지 않는다. 하지만 그럼에도 발생하는 경우에는 어떻게 처리해야 할까?

3.1. 교착상태 방지(Deadlock Prevention)

교착상태는 필요 조건 4가지를 만족해야 일어날 가능성이 있다고 했다. 그렇다면 교착상태를 방지하기 위해서는 4가지 조건 중 한 가지 이상을 불만족하도록 만들면 된다.

3.1.1. 상호배타(Mutual exclusion)

위의 그림에서 자원은 2개의 instance를 가지고 있고, 각각 $P_1$, $P_2$에 할당되어 있다. 이때 $P_3$는 해당 자원을 가지지 못한다.

이를 해결하기 위해서는 해당 자원을 공유 가능하게 만드는 방법이 있다. 하지만 이는 원천적으로 불가능한 이야기이다. 식사하는 철학자 문제에서도 같은 오른쪽 젓가락을 두 명의 철학자가 동시에 사용하는 것이 불가능한 것을 생각해볼 수 있다.

3.1.2. 보유 및 대기(Hold & Wait)

보유 및 대기 조건을 불만족하기 위해서는 자원을 가지고 있으면서 다른 자원을 기다리지 않게 하면 된다. 예를 들어 일부 자원만이 사용 가능할 경우에는 보유하는 자원을 모두 놓아준다. 즉, 자원을 보유하지 않은 상태에서 필요한 모든 자원을 대기한다.

이는 starvation을 야기하고 자원 활용률이 저하되나, 3.1.1과 비교했을 때 현실적으로 사용할 수 있는 방법이다.

3.1.3. 비선점(No preemption)

다른 프로세스가 사용 중인 자원을 선점 가능하도록 하면 교착상태에 빠지지 않을 수 있다. 하지만 이 방법 또한 원천적으로 불가능하다. 예를 들어 다른 프로세스가 프린터를 사용 중인데 이를 강제로 빼앗아 사용하면 자료가 꼬일 수 있다.

CPU에서는 컨텍스트 스위칭을 강제로 하는 등 일부 가능은 하겠으나, 대부분의 경우 빼앗아 오는 것은 일반적으로 불가능하다.

3.1.4. 환형대기(Circular wait)

일반적으로 환형대기를 깨는 방법은 자원에 번호를 부여하고, 번호 오름차순으로 자원을 요청하는 것이다.

이는 대부분의 상황에 적용이 가능은 하겠으나, 실제 자원이 매우 많은 컴퓨터에 적용을 해보았을 때 자원 활용률이 굉장히 떨어지게 된다.

실제로 사용 가능한 방법은 3.1.2, 3.1.4 정도가 되겠다. 컴퓨터의 경우 교착상태가 발생하면 재부팅을 시도해볼 수 있지만, 항공선의 경우 재부팅 자체가 불가하다. 따라서 부득이하게 자원 활용률 및 기타 단점을 감수하고서라도 교착상태를 방지해야 하는 상황이 발생할 수 있다.

3.2. 교착상태 회피(Deadlock Avoidance)

데드락 발생 이유를 자원 요청에 대한 잘못된 승인이라고 생각한다. 아래 예제를 살펴 보자.

12개의 magnetic tape와 3개의 프로세스가 있다.

Current needs에 따라 자원을 나누어 주면 $12-(5+2+2)=3$이 된다. 이때 $P_0$는 Max needs에 따라 $5$만큼을 더 필요로 하지만 자원이 없어 실행되지 못한다. $P_2$는 $2$만큼을 더 필요로 하여 자원을 가져간 뒤, 프로세스를 종료하여 $4$만큼을 반납한다. ($3-2+4=5$)

$P_0$이 필요한 자원 $5$를 만족하게 되어 $P_0$는 $5$만큼 가져다가 쓰고 프로세스를 종료하고 $10$을 반납한다. ($5-5+10=10$) $P_2$역시 $7$만큼 가져다가 쓰고 프로세스를 종료하고 $9$를 반납한다.($10-7+9=12$)

이처럼 자원이 적절히 배분되어 프로세스가 전체적으로 돌아갈 수 있도록 자원 요청을 승인하는 것을 안전한 할당(safe allocation)이라고 한다. 여기서 $P_2$의 current needs가 $2$에서 $3$으로만 바뀌어도 교착상태에 빠지게 되며, 이를 불안전한 할당(Unsafe allocation)이라고 한다.

불안전한 할당은 곧 교착상태로 이어지기 때문에, OS는 자원을 요청받을 때 데드락이 일어나지 않도록 승인을 잘 해주어야 한다. 이는 마치 대출 전문 은행과 유사하다고 하여, Banker’s Algorithm이라고 한다.

3.3. 교착상태 검출 및 복구(Deadlock Detection & Recovery)

데드락이 일어나는 것을 허용은 하되, 이를 복구하도록 하는 방법이다.

운영체제가 처음부터 데드락이 일어나지 않도록 신경 쓰는 게 아니라, 프로세스가 필요한 대로 자원을 전부 나누어 준다. 이렇게 막 나누어 주다 보면 어쩌다 한 번 데드락이 일어날 수 있다.

이를 감지하기 위해 OS는 주기적으로 검사를 실행한다. 검사를 자주 실행해 혹시 모를 데드락을 대비하는 것도 좋겠으나, 검사를 위한 오버헤드가 크다는 문제가 있다.

데드락을 한 번 발견했다면, 복구를 위해 주기적으로 현재 상태를 기억해 두어야 한다. 데드락이 발생하기 이전 상태로 상황을 되돌려야 하기 때문이다. 이 방법이 불가능할 때에는 한 프로세스를 강제로 종료시키거나, 자원을 강제로 빼앗아(선점) 일부 프로세스에 할당한다.

3.4. 교착상태 무시(Don’t Care)

교착상태는 실제로 잘 일어나지 않는다. 앞서 언급한 바와 같이 4가지 필요 조건을 모두 만족하더라도 일어나지 않을 수 있다. 공연히 일어나지도 않을 일 때문에 detection하는 등의 방법은 오히려 컴퓨터 성능을 떨어뜨린다. 따라서 교착상태가 일어나도 아무런 조치를 하지 않는 것도 하나의 방법이라 할 수 있겠다.

Reference

• KOCW 양희재 운영체제
• 11: 교착 상태: Deadlock

1. Preemptive vs Non-preemptive

병원에서 환자가 진료를 기다리고 있는 상황을 생각해 보자.

대기실(Ready Queue)에서 환자(Process)가 진료(CPU)를 기다린다.

앞의 환자가 진료가 끝날 때까지 환자들은 대기실에서 기다린다. 이는 Non-preemptive 스케줄링이라고 한다.

반면, 응급 환자가 나타나면 앞의 환자의 진료가 끝나지 않아도 진료를 시작한다. 이를 Preemptive 스케줄링이라고 한다.

1.1. Preemptive

프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다. 즉, 프로세스가 정상적으로 수행 중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.

1.2. Non-preemptive

한 프로세스가 한 번 CPU를 점유했다면, I/O 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못한다.

2. Scheduling criteria

하나의 프로세스가 종료되면 큐에 올려져 있는 다음 프로세스를 실행하는 것이 가장 일반적이고 자연스러울 것이다. 하지만 필요에 따라 여러 방법을 이용할 수 있고, 이때 어떤 방법이 가장 적합할지 비교하기 위한 척도가 필요하다.

• CPU Utilization(CPU 이용률): CPU가 얼마나 놀지 않고 부지런히 일하는가
  • e.g. $P_1$→$P_2$→$P_3$로 실행하니 CPU가 100%로 사용되는데, $P_2$→$P_1$→$P_3$로 실행하니 CPU가 80%는 일하고 20%는 놀더라
• Throughput(처리율): 단위 시간당 몇 개의 작업을 처리하는가
• Turnaround time(반환시간): 어떤 작업이 메인 메모리로 들어가 작업을 끝내고 나올 때까지 걸리는 시간이 얼마나 걸리는가
• Waiting time(대기시간): CPU의 서비스를 받기 위해 Ready Queue에서 얼마나 기다리는가
• Response time(응답시간): 명령을 내리고 첫 응답을 받을 때까지 시간이 얼마나 걸리는가, 주로 interactive system에서 중요한 척도로 사용.

3. CPU Scheduling Algorithms

3.1. First-Come, First-Served(FCFS)

먼저 온 것을 먼저 서비스 해준다. 가장 간단하고 공평한 방법이나, 반드시 좋은 성능을 나타내진 않는다. 아래 Gantt Chart의 Average Waiting Time을 구해보자.

![](https://velog.velcdn.com/images/jayy_19/post/1f8e3648-f08c-4d3a-ac4f-5660e6b49a7d/image.png)

단순히 $P_1$이 먼저 도착했다고 해서 먼저 처리할 경우 AWT는 17ms가 된다.

2. $P_3$→$P_2$→$P_1$

   

   반면 짧게 걸리는 $P_2$, $P_3$를 먼저 처리할 경우 AWT는 3ms가 된다.

⇒ 평균 대기 시간 측면으로 보았을 때 FCFS가 반드시 좋은 방법은 아니란 것을 알 수 있다.

위의 예시처럼 CPU 점유 시간이 긴 프로세스($P_1$)를 CPU 점유 시간이 짧은 프로세스들($P_2$, $P_3$)이 뒤에서 오랫동안 기다리며 시중처럼 따라다니는 것 같은 모습을 Convoy Effect(호위효과)라고 한다.

정리하자면 FCFS에는 호위효과라는 단점이 나타날 수 있고, 이 방식은 Non-preemptive 스케줄링이다.

3.2. Shortest-Job-First(SJF)

가장 짧은 실행 시간이 걸리는 작업부터 먼저 처리한다. 이는 Provably optimal, 즉 수학적으로 증명은 생략하겠으나 가장 이상적인 방법이라고 할 수 있다. 아래 예시를 보자.

SJF 방식을 이용하여 AWT를 구한 결과 7ms가 나온다.

앞서 배운 FCFS 방식을 이용해 구한 AWT는 10.25ms로 역시나 SJF이 가장 효율적인 걸 알 수 있다.

그럼 항상 SJF를 사용하면 최고의 효율을 뽑을 수 있는 거 아닐까?

SJF 방식은 Not realistic하다. 실제 돌아가는 프로세스들은 CPU 점유 시간이 얼마나 걸릴지는 알 수 없기에 prediction이 필요하다. 하지만 프로세스의 예상 점유 시간을 구하기 위해 과거 실행 시간을 기억하고 계산하면 되려 오버헤드가 커진다. 따라서 현실적으로 적용하기 어려운 방법이라고 할 수 있다.

SJF는 Preemptive, Non-preemptive 두 가지 방식으로 만들 수 있다.

![](https://velog.velcdn.com/images/jayy_19/post/4811ff01-9cd8-4707-ad33-0013466182ac/image.png)

레디 큐에 올라와 있는 프로세스 중 가장 짧은 점유 시간을 가진 프로세스가 우선적으로 실행된다. 한 프로세스가 실행 중에 있을 때 점유 시간이 더 짧은 프로세스가 들어온다 하더라도 실행되는 프로세스가 바뀌지 않는다.

• Preemptive

  

  한 프로세스가 실행 중에 있더라도, 남아 있는 시간이 짧은 순서대로 점유하는 프로세스가 달라진다. Shortest-Remaining-Time-First(최소잔여시간 우선)이라고도 한다.

3.3. Priority Scheduling

우선순위가 더 높은 프로세스를 먼저 서비스해준다.

우선순위는 보통 컴퓨터에서 정수값으로 표기되고, 대부분의 운영체제(Unix/Linux)에서는 숫자가 작은 게 더 높은 우선순위를 나타낸다. 아래 예시를 보자.

그럼 우선순위는 어떻게 정해질까? 내부적, 외부적 요인에 따라 결정된다.

• Internal: time limit, memory requirement, I/O to CPU burst, …
• External: amount of funds being paid, political factors, …

실제로 컴퓨터가 돌아갈 때 외부에서 계속해서 새로운 프로세스가 들어온다. 이때 우선순위가 낮은 프로세스의 경우, 아무리 오래 기다려도 해당 프로세스보다 우선순위가 높은 작업이 들어오면 계속해서 대기하게 된다. 이렇게 아무리 기다려도 CPU 시간을 차지하지 못하는 상황을 starvation이라고 한다.

이를 해결하기 위해 Ready Queue에서 오래 기다린 프로세스일수록 점진적으로 우선순위를 높여주는 방법을 aging이라고 한다.

3.4. Round-Robin

뿅망치로 머리를 때리면 머리 위에 빙빙 도는 새처럼 빙빙 돌며 스케줄링하는 방식이며, Time-sharing system(시분할/시공유 시스템)에서 많이 사용되는 방법이다.

시간축을 길게 늘여뜨려 놓고 보았을 때, 일정 간격으로 시간축을 나눈다. 이를 Time Quantum 혹은 Time Slice라고 한다. 기호로는 델타(Δ)를 사용한다.

이 방식은 Time Quantum이 지나면 자동으로 다음 프로세스가 CPU를 점유하기 때문에 Preemptive 스케줄링에 해당된다. 아래 예제를 살펴보자.

Δ = 4ms일 때 AWT를 구하면 아래와 같다.

이 방식은 Time Quantum의 size에 의존적이다.

만약 위의 예제에서 $∆→∞$일 경우 점유 중인 프로세스가 실행이 끝날 때까지 switching이 일어나지 않는다. 즉, FCFS와 동일한 방법이 된다. $∆→0$인 경우 switching이 빈번하게 일어나 여러 프로세스들이 거의 동시에 일어나는, Processor sharing과 동일하게 본다. 하지만 이 경우 context switching overhead가 커져 결코 좋은 방법으로 볼 수는 없다.

아래 예제에서 Average turnaround time을 구해보자.

Δ = 1ms일 때

Δ = 5ms일 때

이처럼 델타에 따라 turnaround time이 상이하게 나타나는 것을 알 수 있다. 즉, Δ를 얼마로 잡을 것이냐가 성능에 중요한 포인트가 된다.

3.5. Multilevel Queue Scheduling

먼저 프로세스 그룹에 대해 살펴보자. 프로세스는 기준에 따라 몇 가지 그룹으로 나눌 수 있다.

• System processes: OS 커널 수준의 프로세스
  • e.g. 가상 메모리 매핑, 파일 읽기, 통신 등
• Interactive processes: 유저 수준의 대화형 프로세스
  • e.g. 게임
• Interactive editing processes
  • e.g. 워드 프로세서
• Batch processes: 대화형이 아닌 프로세스, 일괄적으로 컴퓨터가 알아서 처리
  • e.g. 컴파일러
• Student processes

Interactive editing 프로세스는 컴퓨터 앞에 직접 앉아서 작업을 하는데 응답이 없으면 답답하다. 반면 Batch 프로세스는 돌려놓고 집에 가도 되기 때문에 조금 느리게 처리되어도 크게 문제가 없다.

이렇게 다양한 성격의 프로세스를 동일한 Ready Queue에 두는 것은 비효율적이게 보인다. 즉, Queue를 여러 개 두고 서비스하는 것이 더 효율적이다. 이를 Multilevel Queue Scheduling이라고 한다.

이 방식의 경우 각각의 Queue에 절대적 우선순위가 존재하거나 CPU time을 각 Queue에 차등 배분한다. 또한 각 Queue는 독립된 scheduling 정책을 사용한다.

3.6. Multilevel Feedback Queue Scheduling

3.5와 마찬가지로 복수 개의 Queue를 두고 프로세스는 하나의 입구로 진입한다.

해당 Queue의 스케줄링 방식대로 처리가 되다가, 일정 시간이 지나도 Queue가 줄지 않으면, 즉 너무 많은 CPU time을 사용하면 해당 스케줄링 방식이 맞지 않는다고 판단(feedback)하고 다른 Queue로 넘긴다.

또한 기아 상태 우려 시 우선순위가 높은 Queue로 프로세스를 옮긴다.

Reference

• KOCW 양희재 운영체제

• 프로세스는 각자의 주소 공간을 가지고 수행된다.
• 원칙적으로 하나의 프로세스는 다른 프로세스 수행에 영향을 미치지 못한다.

2. 협력 프로세스(Cooperating Process)

• 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있다.

3. IPC: Interprocess Communication

프로세스 간에 정보를 주고 받을 수 있는 방법

• 메세지를 전달하는 방법
  • Message Passing
• 주소 공간을 공유하는 방법
  • Shared Memory
  • Thread

3.1. Message Passing

공유 메모리와 대조적으로, 공유 변수 없이 메세지를 통해 데이터를 전달한다는 점에서 차별화된다. 메세지 전달은 일반적으로 커널을 통해 이루어지며, 직접 또는 간접적으로 프로세스 간의 통신을 지원한다.

3.1.1. Communication 방식

• Direct Communication: 통신하려는 프로세스의 이름을 명시적으로 표시

  

  인터페이스 측면에서 메세지를 전달하는 프로세스가 메세지를 전달 받을 프로세스를 명시

• Indirect Communication: mailbox(또는 port)를 통해 메세지를 간접 전달

  

  경우에 따라 메세지를 집어 넣으면서 문어발 식으로 아무나 꺼내가라 할 수도 있음.

3.1.2. 동기화(Synchronization)

• 동기적 통신(Synchronous Communication)
  • 메세지를 보내는 프로세스는 수신 프로세스가 메세지를 받을 때까지 기다린다. 즉, 송신과 수신이 동시에 이루어져야 한다.
  • 통신의 신뢰성이 높으나, 송신 프로세스가 수신 프로세스의 응답을 기다려야 하므로 시스템 효율 저하를 일으킨다.
• 비동기적 통신(Asynchronous Communication)
  • 메세지를 보내는 프로세스는 메세지를 보낸 후 바로 다음 작업을 수행할 수 있으며, 수신 프로세스는 나중에 메세지를 수신한다.
  • 수신 프로세스는 언제든지 메세지를 수신할 수 있으며, 송신 프로세스는 수신 여부에 관계없이 계속 작업 수행이 가능하다.
  • 시스템의 효율성을 높일 수 있으나, 메세지 손실 가능성이 있다.

3.2. Pipe(익명 파이프 & Named 파이프)

프로세스 간에 데이터를 바이트 스트림 형태로 전달하며, 주로 부모-자식 프로세스 간의 통신에 사용된다. 파이프는 단방향 또는 양방향 통신을 지원하며, 익명 파이프와 Named 파이프 두 가지 주요 유형으로 나뉜다.

• 기본적으로 반이중 통신(단방향 통신)만 가능하기 때문에, 양방향 통신이 필요하면 두 개의 파이프를 만들어야 한다.
• 파이프는 단순한 데이터 흐름을 처리하는 데 적합하며, 두 프로세스가 연속적으로 데이터를 송수신하는 구조다.
• 유형
  • 익명 파이프: 부모-자식 관계와 같이 밀접한 관계에 있는 프로세스 간에 사용된다.
  • Named 파이프(FIFO): 전혀 모르는 상태의 프로세스 사이에서도 사용될 수 있다.

3.3. Shared Memory

두 개 이상의 프로세스가 동일한 메모리 공간을 공유하여 데이터를 주고받을 수 있게 해주는 메커니즘이다. 빠른 데이터 교환을 가능하게 하지만, 동기화 문제를 적절히 처리하지 않으면 데이터 경합이나 일관성 문제가 발생할 수 있다.

Share Memory에서 프로세스 A, B는 따로 주소 공간을 가지고 있으나 물리적으로 매핑될 때 일부 공간이 공유된다.

• 여러 프로세스가 동일한 메모리 영역을 동시에 접근할 수 있기 때문에, 데이터의 일관성을 유지하려면 동기화가 필요하다.
• 세마포어, 뮤텍스 같은 동기화 메커니즘을 사용하여 공유 메모리 접근을 제어해야 한다. 그렇지 않으면 여러 프로세스가 동시에 데이터를 수정할 때 충돌이나 데이터 손실이 발생할 수 있다.

3.4. Thread

• 스레드는 사실상 하나의 프로세스이므로 프로세스 간 협력으로 보기에는 어렵다.
• 하지만 동일한 프로세스를 구성하는 스레드 간에는 주소 공간을 공유하므로 협력이 가능하다.

Reference

• 이화여자대학교 운영체제-반효경 강의