이제 단일 프로세스가 아니다...

• 초기 시스템의 경우, 간단하게 운영체제는 메모리에 상주하는 라이브러리의 집합. 물리 메모리에 하나의 프로세스가 존재, 나머지 메모리를 사용하였지만...

멀티 프로세스

• 여러 프로세스가 실행 준비 상태에 있고, 운영체제는 이를 전환하며 실행.
• CPU 이용률 증가, 효율성 개선 필요.

시분할 시스템

• 일괄처리방식 컴퓨팅의 한계.
• 많은 사용자가 동시에 컴퓨터 사용.
• 구현 방법 :
  • 하나의 프로세스를 짧은 시간 동안 실행시키는 것.
  • 해당 기간 동안 프로세스에 모든 메모리를 접근할 권한이 주어짐.
  • 프로세스 중단, 중단 시점의 모든 상태를 디스크에 저장.
  • 다른 프로세스의 상태를 탑재.
  • 다시 짧은 시간 동안 실행. 무한반복...
• 위와 같은 구현의 문제점 :
  • 메모리 내용을 디스크에 저장하여 너무 느림;
• 시분할로 인한 OS 새로운 요구사항 :
  • 여러 프로그램이 메모리에 동시에 존재하려면 보호 필요.

주소 공간에 대한 고민 필요

주소 공간의 구조

• 실행 프로그램의 모든 메모리 상태 가짐.
• 프로그램의 코드(명령어)
  • 프로그램이 실행되며 추가 메모리를 필요로 하지 않기 때문에 주소 공간 상단에 배치.
• 스택 : 현재 실행 함수 위치, 지역 변수, 함수 인자, 반환 값 등 저장.
  • 하단에 존재. (예를 들어 프로시저 호출 시) 위로 확장 가능.
• 힙 : 동적 할당 메모리.
  • 상단에 존재. (예를 들어 malloc 시) 아래로 확장 가능.
• 배치는 정해진 것이 아니며 다른 방식으로 배치 가능.

메모리 가상화 필요

• 프로세스는 특정 주소의 메모리에 탑재되고, 매우 큰 전용 주소 공간을 가지는 것처럼 구현.
• 프로세스가 가상 주소 0에서 연산을 수행할 때, 운영체제는 하드웨어의 지원을 통해 물리 주소0이 아닌 실제 프로세스가 탐재된 메모리 부분 n을 읽도록 보장해야 한다.

메모리 가상화의 목표는

멋지게 가상화 하기

투명성

• 운영체제는 프로세스가 가상 메모리의 존재를 인지하지 못하게 구현해야.
• 프로세스는 전용 물리 메모리를 이용하는 것처럼 행동하게 해야.

효율성

• 운영체제는 가상화가 시간/공간 측면에서 효율적이게 구현해야.
• 시간적 : 프로세스가 너무 느리면 안 됨.
• 공간적 : 가상화 구현을 위해 너무 많은 메모리를 사용해선 안 됨.
• TLB 등 하드웨어 기능이 지원.

보호

• 운영체제/프로세스들은 서로 고립되어 보호받아야.
• 프로세스가 탑재, 저장, 명령어 등을 실행할 때 다른 프로세스/운영체제의 메모리에 접근하거나 영향을 줘서는 안 됨.

Memory API

메모리 공간의 종류

스택

• 할당과 반환이 컴파일러에 의해 암묵적으로 이루어지는 '자동 메모리'.
• 함수를 작성하고 일반 변수를 선언하면:
  • 컴파일러가 알아서 함수 호출 시 스택에 공간을 확보.
  • 함수에서 리턴하면 컴파일러가 메모리를 반환.

힙

• 모든 할당과 반환이 프로그래머에 의해 명시적으로 처리.
• malloc을 호출
  • 변수를 위한 공간을 힙으로부터 요구.
  • 반환된 변수의 주소가 스택에 저장되어 사용 됨.

malloc() 함수

• 호출 :
  • 힙에 요청할 공간의 크기를 넘겨줌.
  • 성공 시, 새로 할당된 공간에 대한 포인터를 반환.
  • 실패 시, NULL 반환.
• void 타입에 대한 포인터를 반환.
  • 주소만 넘겨주고 어떤 타입을 저장할지는 개발자가 결정하게 하는 방식.

free() 함수

• 할당된 힙 메모리를 해제.
• malloc()에 의해 반환된 포인터를 인자로 받아 해제.

(malloc, free 사용 시) 흔한 오류

자동 메모리 관리

• 대부분 새로운 언어들은 자동 메모리 관리를 제공.
• 이러한 조~흔 언어들은 할당을 위해서는 특정 루틴을 호출하지만, 해제를 위해서는 호출하지 않는다.
• garbage collector가 실행되어 참조되지 않는 메모리는 자동으로 해제된다.

메모리 할당 잊어버리기

많은 루틴들은 호출 전에 필요한 메모리가 이미 할당되었다고 가정한다. ex) 할당하지 않은 채 strcpy()하면 쥬금...

메모리를 부족하게 할당받기

버퍼 오버플로우 : 할당된 공간 이상의 범위를 접근하는 경우에 발생.

할당받은 메모리 초기화하지 않기

malloc을 호출했으나 실수로 초기화하지 않은 경우, 해당 영역에 접근하면 버그 발생.

메모리 해제하지 않기

메모리 누수 : free로 메모리 해제를 잊었을 때 발생.

• 메모리가 정리되지 못하고 천천히 누수되다가 메모리 부족으로 쥬금...

메모리 사용이 끝나기 전에 메모리 해제하기

dangling pointer : 해제한 메모리 영역에 접근하면 쥬금...

반복적으로 메모리 해제하기

double free : 이미 해제한 메모리를 한 번 더 해제하는 경우 발생. 쥬금...

free() 잘못 호출하기

invalid free : malloc으로 할당받은 포인터가 아닌 이외의 값을 해제 시도.

회사에서 다 겪어본 것들이군...

운영체제의 지원

malloc/free

• 시스템 콜이 아닌 라이브러리 함수.
• 라이브러리 자체는 더 많은 메모리를 요구하고 반환하는 시스템 콜 기반으로 구축.

brk

• 프로그램 break 위치를 변경하는 데 사용.
  • break : 힙의 마지막 위치를 나타냄.
• 새로운 break 주소를 인자로 전달받아 현재 break보다 큰지/작은지에 따라 힙의 크기 증가/감소.
• 직접 호출하면 안 되고 메모리 할당 라이브러리에 의해 사용.

mmap

• 운영체제로부터 메모리를 얻을 수 있음.
• 프로그램에 anonymous 메모리 영역 생성.
  • anonymous 영역 : 특정 파일과 연결되어 있지 않고 스왑 공간과 연결. 힙처럼 취급.

기타 함수들

calloc : 메모리 할당 영역을 0으로 채워 반환. realloc : 이미 할당된 공간을 확장.

address Translation

주소 변환의 원리

가상화 제공과 함께

• 효율성 추구
  • 하드웨어 지원을 활용. 레지스터 및 TLB, 페이지 테이블 등 하드웨어 활용.
• 제어
  • 프로세스가 자신의 메모리 이외의 다른 메모리에 접근하지 못하는 것을 보장.
• 유연성
  • 개발자 마음대로 주소 공간 사용, 개발하기 쉬운 시스템.

하드웨어 기반 주소 변환

• 제한적 직접 실행 방식에 부가적으로 사용되는 기능.
• 주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등 가상 주소를 실제 물리 주소로 변환.
• 프로세스의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위해 하드웨어가 주소 변환.
• 정확한 변환을 위해 하드웨어 및 운영체제의 도움이 필요.
  • 운영체제는 메모리 빈 공간과 사용 중인 공간을 알고 있어야 하고, 메모리 사용을 제어 및 관리.
• 목표 : 프로세스가 각자 자신의 전용 메모리를 소유하고 그 안에 자신의 코드/데이터가 있다는 환상을 갖게 하는 것.

사례

주소 변환 구현을 위해 어떤 것이 왜 필요한지?

• 프로세스 관점에서 주소 공간은 0부터 시작하여 n까지. 모든 메모리 참조는 0~n 이내에 있어야 함.
• 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0이 아닌 다른 곳에 위치시킴.
• 이때 어떻게 프로세스 모르게 다른 위치에 메모리를 재배치하느냐가 관건.
• 즉, 실제로는 다른 물리 주소에서 시작하는데, 프로세스는 주소 0부터 시작한다고 느낌.

동적 (하드웨어 기반) 재배치

동적 재배치

• 하드웨어 기반 주소 변환의 아주 간단한 사례로, 베이스와 바운드라고도 함.
• 각 CPU마다 2개의 하드웨어 레지스터가 필요.
  • base 레지스터 : 프로세스가 탑재될 물리 메모리 시작 위치.
  • bound(limit) 레지스터 : 보호 지원. 메모리 참조가 합법적인가를 판단하기 위해 가상 주소가 바운드(범위) 안에 있는지 확인. base와 마찬가지로 주소 공간의 크기를 저장하거나 마지막 물리 주소를 저장.
• 레지스터 쌍으로 원하는 위치에 주소 공간을 배치 및 프로세스가 해당 주소 공간에만 접근할 수 있게 한다.
• 운영체제는 프로세스가 탐재될 물리 메모리 위치를 정하고, 베이스 레지르터를 지정.
• 프로세스에 의해 생성되는 모든 주소가 프로세서에 의해 physical address = virtual address + base로 변환.
• 즉, base 레지스터 + 가상 메모리 주소를 이용해 물리 메모리 주소에 접근함으로써 가상 메모리 주소는 0부터 시작하는 것처럼 사용된다.
• 이러한 주소의 재배치는 실행 시 발생하고 실행 이후에도 주소 공간을 이동할 수 있기 때문에 동적 재배치라고 한다.

하드웨어 지원: 요약

두 가지 CPU 모드가 필요.

• 커널(특권) 모드 : 운영체제가 커널 모드로 실행되며 컴퓨터 전체의 접근 권한을 가짐.
• 사용자 모드 : 응용 프로그램은 제한된 권한을 가짐.

프로세스서 상태 워드 : 한 비트가 CPU의 현재 실행 모드를 나타냄. 시스템 콜 또는 인터럽트 등으로 인해 CPU는 모드를 전환.

베이스/바운드 레지스터 : 가상 주소에 값을 더해 실제 물리 주소로 변환 가능.

• 하드웨어는 이 레지스터 값을 변경하는 명령어 제공.
• 커널 모드에서 레지스터 변경 가능.

예외 핸들러

• CPU는 사용자 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근을 시도하려는 상황에서 예외를 발생시킬 수 있어야 함.
• 프로세스의 실행을 중지하고, 운영체제의 예외 핸들러가 실행되도록 조치.

운영체제 이슈

하드웨어 지원 + 운영체제 관리 == 간단한 가상 메모리 구현

베이스/바운드 방식의 가상 메모리 구현을 위한 운영체제 개입 시점

• 프로세스가 생성될 때, 주소 공간이 저장될 메모리 공간을 찾아 조치 취해야 함.
  • 새로운 주소 공간 할당에 필요한 영역을 찾기 위해 빈 공간 리스트 검색.
• 프로세스가 종료될 때, 메모리를 회수하여 다른 프로세스에서 사용할 수 있게 해야 함.
  • 종료된 프로세스의 메모리를 다시 빈 공간 리스트에 넣고 연관된 자료 구조를 모두 정리.
• 문맥 교환이 일어날 때, 프로세스 전환 시 베이스/바운드 쌍을 저장/복원 해야 한다.
  • 운영체제가 실행 중인 프로세스를 중단시키기로 하면, 운영체제는 메모리에 존재하는 프로세스 별 자료 구조 안에 베이스/바운드 레지스터 값을 저장.
  • 이 자료구조를 프로세스 제어 블럭이라고 함.
  • 프로세스가 중단되면, 운영체제는 메모리 현 위치에서 다른 위치로 주소 공간을 쉽게 옮길 수 있음. (주소 공간 복사 및 베이스 레지스터 갱신을 통해) 이때 프로세스는 다른 위치로 옮겨진 것을 인식하지 못함.
• 예외 핸들러 또는 호출된 함수를 제공해야 함.
  • 운영체지는 부팅할 때 특권 명령어로 핸들러 설치.
  • 예를 들어 프로세스가 바운드 밖의 메모리에 접근하려는 경우, CPU는 예외를 발생시키고, 운영체제는 이에 대한 조치를 취해야 함.
  • 운영체제가 개입하여 프로세스를 종료시키고 메모리 해제, 프로세스 테이블에서 항목 정리.

Segmentation

내부 단편화

• 동적 재배치는 비효율적.
• 예를 들어 프로세스 스택과 힙이 아주 크지 않을 때, 둘 사이의 공간이 낭비.
• 즉, 할당 영역의 내부 공간이 사용되지 않아 단편화가 발생되어 낭비 됨.
• 물리 메모리의 사용률을 높이고 내부 단편화 방지를 위해 base-and-bound 일반화 즉, 세그멘테이션 기법을 사용.

세그멘테이션: base/bound의 일반화

세그멘테이션

• MMU 안에 하나의 베이스/바운드 쌍만 존재하는 것이 아니라, 주소 공간의 논리적인 segment마다 베이스/바운드 쌍이 존재한다.
• 이때의 세그멘트는 특정 길이를 가지는 연속적인 주소 공간.
• 세그멘테이션을 이용해 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지.

세그멘트의 종류

하드웨어는 가상 주소가 어느 세그멘트를 참조하는지, 오프셋은 얼마인지 어떻게 앎?

• 일반적인 접근법 : 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그멘트로 나누기.
  • 예를 들어 최상위 2비트가 00이면 가상 주소가 코드 세그멘트를 가리킨다고 가정하고, 코드 세그멘트의 베이스/바운드 쌍을 사용하여 주소를 물리 메모리에 재배치.
  • 최상의 2비트는 세그멘트의 종류, 하위 12비트는 세그멘트 내의 오피셋.
  • 오프셋을 이용해 바운드보다 작은지 여부를 검사 가능.
  • 세그멘트 종류를 나타내는 데 2비트를 쓰고, 종류는 코드/힙/스택 세 가지이므로 주소 공간의1/4는 사용 불가능.
  • 이를 해결하기 위해 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하는 식으로 세그멘트 종류 구별에 1비트만 사용.
• 묵시적 접근 방식 : 주소가 어떻게 형성되었나를 관찰해 세그멘트를 결정.
  • PC에서 생성되었다면 코드 세그멘트, 스택/베이스 포인터에 기반을 둔다면 스택 세그멘트, 이외는 힙...

스택

스택의 큰 차이점 : 다른 세그멘트들과는 반대 방향으로 확장

스택의 변환 방법

• 간단한 하드웨어가 추가로 필요.
  • 하드웨어는 세그멘트가 어느 방향으로 확장하는지도 알아야 함.
  • 예를 들어 1비트를 사용하여 1이면 커지는 쪽으로 확장, 0이면 작아지는 쪽으로 확장.

공유 지원

세그멘트 공유

• 메모리를 절약하기 위해 주소 공간 사이에 특정 메모리 세그멘트를 공유. 특히 코드 공유.
• protection bit
  • 공유 지원을 위해 세그멘트마다 비트 추가.
  • 세그멘트를 읽거나 쓸 수 있는지, 세그멘트의 코드를 실행시킬 수 있는지를 나타냄.
  • 코드 세그멘트를 읽기 전용으로 설정하면, 주소 공간의 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유할 수 있음.

소단위 대 대단위 세그멘테이션

대단위 세그멘테이션

• 코드/스택/힙으로 소수의 세그멘트만 지원하는 경우, 비교적 큰 단위로 분할하는 대단위 세그멘테이션.

소단위 세그멘테이션

• 일부 초기 시스템의 경우, 주소 공간을 작은 크기의 공간으로 분할하는 것이 허용.
• 많은 수의 세그멘트를 지원하기 위해서 여러 세그멘트 정보를 메모리에 저장할 세그멘트 테이블이 필요.

운영체제의 지원

세그멘테이션이 제기하는 문제

• 문맥 교환 시 운영체제는 세그멘트 레지스터의 저장과 복원을 해야 함.
• 미사용 중인 물리 메모리 공간의 관리.
  • 새로운 주소 공간이 생성되면 운영체제는 세그멘트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 함.
• 외부 단편화.
  • 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워짐.
  • 이 공간들은 세그멘트에 할당/확장하기 어려운 단편화 된 공간.

해결책

• 기존의 세그멘트를 정리하여 물리 메모리를 압축.

      현재 실행 중인 프로세스 중단, 데이터를 하나의 연속된 공간에 복사, 세그멘트 레지스터가 새로운 물리 메모리 위치를 가리키게 함.
      but 세그멘트 복사는 메모리 부하가 크고, 많은 프로세서 시간을 사용하므로 비용이 높음.

• 빈 공간 리스트 관리 알고리즘 사용.

      할당 가능한 메모리 영역들을 리스트 형태로 유지하여 최적 적합/최초 적합/버디 알고리즘 등을 이용해 할당.

Free Space Management

저수준 기법들

분할과 병합

분할

• 1020은 사용 중이지만, 010과 20~30(주소 20, 길이 10)이 빈 공간 리스트인 경우, 일반적으로 10바이트를 초과하는 요청은 실패.
• 만약 1바이트의 메모리를 요청했을 때, 할당기는 분할 수행.
• 요청을 만족시킬 수 있는 청크를 찾아 둘로 분할.
• 첫 청크는 호출자에게 반환, 두 번째 청크는 리스트에 남음.
• 만약 주소 20에 해당하는 주소를 반환하기로 하였으면, 빈 공간 리스트는 010, 2130(주소 21, 길이 9)이 남게 됨.
• 이렇게 요청이 특정 빈 청크의 크기보다 작은 경우, 분할 기법 사용.

병합

• 프로세스가 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환하면 주소 10/길이 10, 주소0/길이10, 주소 20/길이 10이 빈 공간 리스트에 존재.
• 힙 전체가 비어있지만, 10바이트 길이의 청크 3개로 나눠져 있게 됨.
• 이때 사용자가 20바이트를 요청하면 단순한 리스트 탐색의 경우, 빈 20짜리 청크를 발견하지 못하고 반환 실채.
• 메모리 청크가 반환될 때 빈 공간들을 병합 필요.
• 해제되는 청크의 주소와 인접한 빈 청크의 주소가 있는지 확인하여 인접해있다면 하나의 청크로 병합.

할당된 공간의 크기 파악

헤더

• 대부분의 할당기는 추가 정보를 헤더 블럭에 저장.
• 헤더 블럭은 메모리에 유지되며, 해제된 청크 바로 직전에 위치.
• 할당된 공간의 크기, 해제 속도를 향상시키기 위한 추가의 포인터, 무결성 검사를 제공하기 위한 매직 넘버, 기타 정보들을 저장.
• 헤더를 가리키는 포인터를 얻으면 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전성 검사 실시, 해제된 영역의 크기를 계산.

힙의 확장

힙 공간이 부족한 경우

• 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진 시 운영체제로부터 더 많은 메모리를 요청.
• 할당기는 힙 확장을 위해 특정 시스템 콜을 호출, 확장도니 영역에서 새로운 청크를 할당.
• 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환.

기본 전략

이상적인 할당기는 속도가 빠르고 단편화를 최소화.

최적 적합

• 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾음.
• 그룹 중 가장 작은 크기의 청크 반환.
• 빈 공간을 한 번 순회하여 반환할 블럭 찾음.
• 공간의 낭비를 줄일 수 있으나, 항상 전체를 검색해야하므로 성능 저하.

최악 적합

• 최적 적합의 반대.
• 가장 큰 빈 청크를 찾아 요청된 크기 만큼 반환.
• 성능 저하 + 단편화 발생.

최초 적합

• 요청에 부합하는 첫 블럭을 찾아 요청 만큼 반환.
• 전체를 탐색할 필요가 없어 속도가 빠름.
• 할당기가 빈 공간 리스트의 순서를 주소-기반 정렬 등으로 관리하면 병합이 쉽고 단편화 감소.

다음 적합

• 처음부터가 아니라 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 두어 해당 위치부터 탐색.
• 빈 공간 탐색을 리스트 전체에 균등하게 분산시켜 리스트 첫 부분에만 단편이 발생하는 것을 방지.

다른 접근법

개별 리스트

• 특정 프로세스가 자주 요청하는 크기가 있다면, 해당 크기의 객체를 관리하기 위한 리스트를 별도로 유지.
• 특정 크기의 요청에 대한 메모리 청크를 유지하여 단편화 가능성 줄임.
• 복잡한 리스트 검색이 필요 없으며 할당과 해제 요청이 빠름.
• But... 지정된 크기의 메모리 플과 일반 풀에 얼마씩 메모리를 할당해야?
  • 슬랩 할당기 : 특수 목적 할당기로 위 문제 해결.
    • 커널 부팅 시, 커널 객체를 위한 여러 객체(락, 아이노드 등) 캐시가 할당.
    • 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트로, 메모리 할당 및 해제 요청 속도 증진.
    • 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩 요청, 참조 횟수가 0이 되면 상위 메모리 할당기가 슬랩을 회수.
    • 슬랩 할당 방식은 빈 객체들을 사전에 초기화 된 상태로 리스트에 유지하여 개별 리스트 방식보다 개선.
    • 즉, 객체 당 잦은 초기화와 반납 작업을 피할 수 있어 오버헤드 감소.

버디 할당

이진 버디 할당기

• 빈 공간의 합병은 할당기의 중요 기능.
• 빈 메모리는 처음에는 크기 2^n인 하나의 큰 공간으로 생각되며, 메모리 요청 발생 시 충분한 공간이 발견될 때까지 빈 공간을 2개로 분할하여 반환.
• 2의 거듭제곱 크기 만큼의 블럭만 할당 가능하므로 내부 단편화가 대량 발생 가능.
• 블럭이 해제될 때, 빈 공간 리스트에 반환하면 할당기는 그 크기의 "버디" (2개로 쪼개졌던 반대쪽)가 비어있는지 확인.
• 비어있다면 두 블럭을 병합하여 하나의 블럭으로 만듦.
• 그 뒤에 합쳐진 블럭 크기의 버디가 있는지 확인, 합병을 반복.
• 재귀 합병 과정이 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이란게 확인 될때까지 반복.

기타 아이디어

확장성

• 위 접근 방식들에는 확장성 문제가 있음.
• 빈 공간 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있음.
• 정교한 할당기는 균형 이진 트리, 스플레이 트리, 부분 정렬 트리 등 복잡한 자료 구조를 사용하여 비용을 줄이고 성능 향상.
• glibc의 할당기?

Paging

세그멘테이션의 문제점

• 세그멘테이션 : 메모리 공간을 가변 크기의 논리 세그멘트 조각으로 분할하는 것.
• 다양한 크기의 청크로 분할할 때, 공간이 단편화 됨.

페이징

• 메모리 공간을 동일 크기의 조각으로 분할하는 것.
• 페이지 : 고정 크기의 단위.
• 페이지 프레임 : 물리 메모리의 고정 크기 슬롯 배열.
• 프레임 당 하나의 가상 메모리 페이지 저장.

개요

페이징의 구성

• 물리 메모리는 고정 크기의 슬롯들로 구성.
• 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치.
• 프로세스가 생성한 가상 주소의 변환을 위해, 우선 가상 주소를 가상 페이지 번호와 페이지 내의 오프셋 2개의 구성 요소로 분할.
• 프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환.
• 예를들어 가상 주소가 21(010101)이면, 이 가상 주소를 검사하고 가상 페이지 번호와 오프셋으로 나눈다. 가상 페이지 01의 0101(5)번째 바이트다.
• 가상 페이지 번호(VPN)를 갖고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다.
• 물리 프레임 번호(PFN)/물리 페이지 번호(PPN) : VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있음.

페이징의 장점

• 유연성
  • 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념 지원. 힙/스택이 어느 방향으로 커지는가, 어떻게 사용되는 가 신경 X.
• 빈 공간 관리의 단순함.
  • 비어있는 페이지 빈 공간 리스트를 유지하고 요청 받은 공간 만큼 선택하여 반환.
  • 각 가상 페이지의 물리 메모리 위치 기록을 위해 운영체제는 프로세스마다 페이지 테이블 자료 구조를 유지.
  • 페이지 테이블 : 프로세스마다 존재하며, 주소 공간의 가상 페이지 주소 변환 정보를 저장. 각 페이지가 저장된 물리 메모리 위치가 어디인지 알려줌.

페이지 테이블은 어디에 저장되는가?

• 페이지 테이블은 실행 중인 프로세스와 할당 메모리에 따라 매우 커지기 때문에, 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지 않음.
• 대신, 각 프로세스의 페이지 테이블을 메모리에 상주.
• 페이지 테이블은 운영체제 가상 메모리에 저장할 수도 있고 디스크에 스왑될 수도 있음.

페이지 테이블에는 실제 무엇이 있는가?

선형 페이지 테이블

• 가장 단순한 배열 형태.
• 물리 프레임 번호를 찾기 위해 가상 페이지 번호로 배열 항목에 접근, 항목의 페이지 테이블 항목을 검색.
• 각 페이지 테이블 항목에는 여러 비트들이 존재.
  • Valid bit : 특정 변환의 유효 여부. 할당되지 않은 주소 공간 표현.
  • protection bit : 페이지를 읽을 수/쓸 수/실행될 수 있는지를 표시.
  • Present bit : 페이지가 물리 메모리에 있는지, 디스크에 있는지(스왑 아웃 되었는지).
  • dirty bit : 메모리에 반입된 후 페이지가 변경되었는지.
  • reference bit : 페이지가 접근되었는지 추적.

페이징 : 너무 느림

페이지 테이블 크기로 인해 처리 속도가 저하될 수 있음.

• 하드웨어에서 주소 변환 시, 페이지 테이블에서 적절한 페이지 테이블 항목을 가져오고, 변환 수행 뒤에 물리 메모리에 데이터를 탑재.
• 이를 위해 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야 함.
• 페이지 테이블 베이스 레지스터를 이용해 메모리에서 PTE 반입, PFN 추출 및 가상 주소의 오프셋과 연결하여 원하는 물리 주소를 만듦.
• 하드웨어는 메모리에서 원하는 데이터를 가져와 eax 레지스터에 탑재.

위와 같이 많은 메모리 참조 작업이 필요. 메모리 참조는 비용이 높고 프로세스가 느려짐.

메모리 트레이스

프로세스의 메모리 참조

• 프로세스가 실행되면, 각 명령어의 반입 시 메모리가 두 번 참조.
  • 명령어 위치 파악하기 위한 페이지 테이블 접근.
  • 명령어 자체.
  • mov 명령어는 메모리 참조를 한 번 함. (페이지 테이블 접근, 배열 자체 접근)
• 전체 트레이스에서 루프 당 10번의 메모리 접근이 존재. 네 번의 명령어 반입, 한 번의 메모리 갱신, 이 주소 변환을 위한 총 다섯 번의 페이지 테이블 접근.

Translation Lookaside Buffers

페이징: 더 빠른 변환 (TLB)

페이징

• 프로세스 주소 공간을 작은 고정 크기로 나누고, 각 페이지의 실제 위치를 메모리에 저장.
• 매핑 정보 저장을 위해 큰 메모리 공간을 요구.
• 페이지 테이블 접근을 위한 메모리 읽기 작업은 성능 저하 유발.

변환-색인 버퍼 (TLB)

• 주소 변환을 빠르게 하기 위해 사용.
• 자주 참조되는 가상 주소-실 주소 변환 정보를 저장하는 하드웨어 캐시.
• 가상 메모리 참조 시, TLB에 먼저 변환 정보가 있는지 확인. 있다면 페이지 테이블을 통하지 않고 빠르게 변환 가능.

TLB 기본 알고리즘

가상 주소 변환... 이제 TLB를 곁들인

• 선형 페이지 테이블과 하드웨어로 관리되는 TLB로 구성.
• 가상 주소에서 가상 페이지 번호를 추출, 해당 VPN의 TLB 존재 여부를 검사.
• 존재한다면 TLB 히트. TLB가 변환 값을 갖고 있다는 것.
• TLB 항목에서 페이지 프레임 번호를 추출 가능.
• 해당 페이지에 대한 접근 권한 검사가 성공하면, 정보를 원래 가상 주소의 오프셋과 합쳐 원하는 물리 주소를 구성, 메모리 접근 가능.
• 만약 TLB에 변환 정보가 존재하지 않는다면, 페이지 테이블 접근, 가상 메모리 참조가 유효하고 접근 가능하다면 해당 변환 정보를 TLB로 읽어와야 함. (시간이 많~이 걸림)
• TLB 미스가 발생하면 메모리 참조가 많이 추가되며 페이징 비용이 커짐.

배열 접근

자세한 TLB 작동 과정

• 예를들어 배열의 0, 1, 2번이 하나의 페이지에, 3, 4, 5, 6이 하나의 페이지에, 7, 8, 9가 하나의 페이지에 들어있다고 가정.
• 배열들을 돌며 읽을 때, TLB가 초기화 되어있는 경우, 처음으로 접근하는 페이지에 대해서는 TLB 미스가 발생하며 TLB 갱신이 일어난다. 두 번째로 접근할떄는 TLB 히트가 발생.
• 0~9까지 읽어올 때 미스, 히트, 히트, 미스, 히트, 히트, 히트, 미스, 히드, 히트가 발생.
• 공간 지역성 : 배열이 처음 접근되었지만, TLB는 공간 지역성으로 인해 성능 개선 가능. 배열들이 페이지 내에서 인접해있기 때문에 페이지의 첫 항목을 접근할 때만 TLB 미스 발생.
• 페이지 크기는 TLB의 효용성에 매우 중요한 역할. 페이지 크기가 두 배가 되면 TLB 미스 횟수가 훨씬 줄어들을 것.
• 시간 지역성 : 루프 종료 후에도 배열을 사용한다면 모든 주소 변환 정보가 TLB에 탑재되어 있기 때문에 성능은 더욱 개선.

TLB 미스는 누가 처리?

TLB 미스 처리

• 하드웨어 (CISC)
  • 하드웨어가 페이지 테이블에 대한 명확한 정보를 갖고 있어야 함. 메모리 상 위치와 정확한 형식을 알아야.
  • 미스 발생 시, 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고, 필요한 변환 정보를 추출하여, TLB 갱신 후, TLB 미스 발생 명령어를 재실행.
• 소프트웨어 관리 TLB (RISC)
  • TLB 미스 발생 시, 하드웨어는 예외 시그널 발생.
  • 예외 시그널을 받은 운영체제는 명령어 실행 중지, 실행 모드를 커널 모드로 변경, 트랩 핸들러 실행. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드.
  • 트랩 핸들러는 페이지 테이블을 검색해 변환 정보를 찾고, TLB 접근이 가능한 특권 명령어를 사용해 TLB 갱신 후 리턴.
  • 리턴되면 하드웨어가 명령어 재실행.

TLB의 구성

하드웨어 TLB

• 32, 64 또는 128 개의 엔트리를 가지며, 완전 연관 방식.
• 완전 연관 방식 : 변환 정보는 TLB 어디든 위치 가능. 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행.
• 변환 정보 저장 위치에 제약이 없도록 각 항목마다 VPN, PFN이 있음.

TLB의 문제: 문맥 교환

• TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 탑재시킨 프로세스에서만 유효.
• 문맥 교환으로 인해 프로세스가 변환되었을때, 어떤 프로세스를 위한 항목인지 알 수 없음.
• 즉, TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해 추가적 기능이 필요.

문맥 교환 시 기존 TLB 내용 비우기

• 모든 valid bit를 0으로 설정하여 지움.
• 문맥 교환할때마다 TLB를 비우면, 잘못된 변환 정보를 사용하는 것을 방지가능.
• But, 문맥 교체 발생 시마다 페이지 접근으로 인한 TLB 미스가 발생하며 성능에 부담을 가져올 수 있다.

TLB 내용 보존

• 위 문제를 개선하기 위해 몇 시스템에서는 문맥 교환 시 TLB 내용을 보존할 수 있는 하드웨어 기능 추가.
• TLB에 주소 공간 식별자 필드(ASID)를 추가. 프로세스 식별자와 유사하며, 좀 더 적은 비트를 갖고 있음.
• ASID 정보를 추가하면 프로세스 별로 TLB 변환 정보를 구분할 수 있음.
• 문맥 전환 시, 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재.

이슈: 교체 정책

캐시 교체 정책

• TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 어떤 것을 교체 대상을 해야 할지?
• 흔한 방법 : 최저 사용 빈도
  • 오랫동안 사용되지 않은 항목을 교체.
• 랜덤 정책
  • 무작위. 구현이 간단하고 예외 상황의 발생을 피함.

Advanced Page Tables

페이징: 더 작은 테이블

• 페이지 테이블이 크면 많은 메모리 공간을 차지한다는 문제점.

간단한 해법: 더 큰 페이지

• 페이지 크기를 증가시켜 페이지 테이블의 크기를 줄일 수 있음.
• 페이지 내부의 낭비 공간이 증가하는 내부 단편화 문제가 발생.

하이브리드 접근 방법: 페이징과 세그멘트

하이브리드

• 두 방식을 조합하여 장점을 취함.
• 프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 논리 세그멘트마다 따로 페이지 테이블을 둔다.
• 세그멘테이션에서는 세그멘트 물리 주소 시작 위치를 나타내는 base, 크기를 나타내는 bound 레지스터가 있음.
• MMU에 비슷한 구조를 사용. 베이스는 세그멘트 시작 주소가 아니라 세그멘트의 페이지 테이블의 시작 주소를 가짐. 바운드는 페이지 테이블의 끝을 나타내기 위해 사용.
• 문맥 교환 시, 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치값으로 변경.
• TLB 미스가 발생하면 하드웨어는 세그멘트 비트를 이용해 어떤 베이스/바운드 쌍을 사용할지 결정.
• 선형 페이지 테이블의 동작과 유사하되, 하나의 페이지 테이블 베이스 레지스터가 아니라 셋 중 하나의 세그멘트 베이스 레지스터를 사용하는 점이 다르다.
• 이를 통해 선형 페이지 테이블에 비해 메모리 사용을 개선시킬 수 있음. 스택/힙 사이의 할당되지 않은 페이지들은 페이지 테이블 상에 더 이상 공간을 차지하지 않음.
• But 문제점
  • 여전히 세그멘테이션을 사용. 세그멘테이션은 주소 공간에 패턴을 가정하기 때문에 유연성이 떨어짐. 드문드문 사용되는 힙의 경우에는 여전히 페이지 테이블 낭비가 존재.
  • 외부 단편화 유발.

멀티 레벨 페이지 테이블

멀티 레벨 페이지 테이블

• 선형 페이지 테이블을 트리 구조로 표현.
• 페이지 테이블을 페이지 크기의 단위로 나눔. 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않음.
• 페이지 디렉터리 자료 구조를 사용하여 페이지 테이블의 각 페이지의 할당 여부와 위치 파악.
• 페이지 디렉터리
  • 페이지 디렉터리 항목들로 구성. 유효 비트, 페이지 프레임 번호를 갖고 있음.
• 장점
  • 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간 할당. 보다 작은 크기의 페이지 테이블로 주소 공간 표현 가능.
  • 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 용이. 각 페이지들이 물리 메모리에 산재해있어도 페이지 디렉터리를 이용해 위치를 파악 가능하여 공간 할당이 매우 유연.
• 단점
  • 추가 비용 발생. TLB 미스 시, 주소 변환을 위해 두 번의 메모리 로드 발생. 페이지 테이블 크기는 줄였으나 메모리 접근 시간이 증가. TLB 히트 시에 성능은 같지만, 미스 시에는 두 배의 시간 소요.
  • 복잡도. 페이지 테이블 검색의 구현이 복잡함.

2단계 이상 사용

트리의 단계를 더 증가시킬 수 있다.

• 페이지 디렉터리가 너무 커지면 멀티 레벨 페이지 테이블의 목적이 훼손.
• 페이지 디렉터리 자체를 멀티 페이지들로 나눠 트리의 단계를 늘릴 수 있음.
• 페이지들을 가리킬 수 있도록 그 위에 새로운 페이지 디렉터리를 추가.
• 가상 주소의 최상위 비트들을 사용하여 상위 단계의 페이지 디렉터리에서 엔트리를 찾고, 유효하다면 상위의 물리 주소와 두 번째 단계의 페이지 디렉터리 인덱스를 결합해 물리 페이지를 구함.
• 유효할 경우, PTE 주소는 두 번째 단계의 페이지 디렉터리 항목에서 얻은 물리 주소와 페이지 테이블 인덱스를 결합하여 구함.

역 페이지 테이블

• 여러 개의 페이지 테이블 대신 시스템에 하나의 페이지 테이블만 둔다.
• 페이지 테이블은 물리 페이지를 가상 주소 페이지로 변환.
• 역 페이지 테이블의 각 항목은 해당 물리 페이지를 사용 중인 프로세스 번호 가상 페이지 번호를 갖고 있음.
• 주소 변환을 위해 전체 테이블을 검색해 가상 주소 페이지 항목을 찾아야 하므로 순차 탐색은 느림. 탐색 속도 향상을 위해 주로 해시 테이블 사용.

페이지 테이블을 디스크로 스와핑

• 여전히 모든 페이지 테이블을 메모리에 상주시키기에는 양이 너무 클 수 있음.
• 페이지 테이블을 커널 가상 메모리에 존재시키거나 디스크로 스왑.

wapping: Mechanisms

물리 메모리 크기의 극복: 메커니즘

• 메모리 계층에 레이어를 추가하고 큰 주소 공간을 제공하면 더 많은 걱정이 사라진다.

스왑 공간

• 디스크에 페이지들을 저장할 수 있는 일정 공간.
• 입출력 단위는 페이지.
• 운영체제는 스왑 공간의 모든 페이지들의 디스크 주소를 기억해야 함.
• 시스템이 사용할 수 있는 메모리 페이지의 최대 수를 결정하기 때문에 크기가 매우 중요.

Present Bit

일반적인 메모리 참조 과정

• 메모리가 참조될 때, 프로세스가 가상 메모리 참조를 생성. 하드웨어는 메모리에서 원하는 데이터를 가져오기 전에 가상 주소를 물리 주소로 변환.
• 하드웨어는 먼저 가상 주소에서 VPN을 추출한 후에 TLB에 해당 정보가 있는지 검사.
• TLB에서 찾을 수 없다면, 하드웨어는 페이지 테이블의 메모리 주소를 파악하고 VPN을 인덱스로 하여 PTE 추출, PTE에서 PFN 추출 및 TLB에 탑재, 명령어 재실행.

Present Bit

• 페이지가 디스크로 스왑되는 것을 가능하게 하려면, 하드웨어가 PTE에서 해당 페이지가 물리 메모리에 존재하지 않는다는 것을 표현해야 함.
• present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는지를 표현.
• 만약 비트가 0으로 설정되어 있다면 메모리에 해당 페이지가 존재하지 않고 디스크 어딘가에 있음을 나타냄.
• 만약 물리 메모리에 존재하지 않는 페이지를 접근하면 페이지 폴트 발생.

페이지 폴트

• 페이지 폴트 발생 시, 운영체제의 페이지 폴트 핸들러가 처리 메커니즘을 규정.
• 만약 요청된 페이지가 메모리에 없고 디스크로 스왑되었다면, 운영체제는 해당 페이지를 메모리로 스왑해옴.
• 원하는 페이지의 스왑 공간상에서의 위치를 보통 페이지 테이블에 저장.
• 페이지 폴트 발생 시, 운영체제는 페이지 테이블의 항목에서 해당 페이지의 디스크 상 위치를 파악하여 메모리로 탑재.
• 디스크 I/O가 완료되면 운영체제는 해당 PTE의 PFN 값을 탑재된 페이지의 메모리 위치로 갱신.
• 위 작업 완료 시, 페이지 폴트를 발생시킨 명령어 재실행.
• 재실행에서 TLB 미스 발생 가능. 미스 처리 과정에서 TLB 값 갱신.
• 마지막 재실행 시 TLB에서 주소 변환 정보를 찾게 되고, 물리 주소에서 원하는 데이터를 가져옴.

메모리에 빈 공간이 없으면?

페이지 교체 정책

• 메모리에 여유 공간이 없을 때, 새로운 페이지 탑재를 위해 페이지들을 먼저 페이지 아웃 해야 할 수 있음.
• 교체할 페이지를 선택하는 것을 페이지 교체 정책.

페이지 폴트의 처리

TLB 미스 발생 시, 세 가지 경우.

• 페이지가 존재하며 유효한 경우. TLB 미스 핸들러가 PTE에서 PFN을 가져와서 명령어를 재시도.
• 페이지가 유효하지만 존재하지 않는 경우. 페이지 폴트 핸들러가 반드시 실행되어야 함.
• 페이지가 유효하지 않는 경우. 버그 등으로 잘못된 주소를 접근하는 경우이며, 운영체제의 트랩 핸들러에 의해 처리되도록 해야 함.

페이지 폴트 처리 과정

• 운영체제는 탑재할 페이지를 위한 물리 프레임 확보.
• 여유 프레임이 없다면, 교체 알고리즘을 실행해 메모리에서 페이지를 내보내고 여유 공간 확보.
• 물리 프레임 확보 후, I/O 요청을 통해 스왑 영역에서 페이지를 읽어옴.
• 운영체제는 페이지 테이블을 갱신, 명령어 재시도.
• TLB 미스가 발생, 다시 한 번 재시도하면 TLB 히트 및 접근 가능.

교체는 실제 언제 발생하는가

• 메모리에 항상 여유 공간을 비워두기 위해 대부분 운영체제들은 여유 공간 최댓값/최솟값을 설정해 교체 알고리즘 작동에 활용.

여유 공간 비워두기

• 운영체제가 여유 공간의 크기가 최솟값보다 작아지면 여유 공간을 확보하는 스왑 데몬(페이지 데몬) 스레드가 실행.
• 스레드는 여유 공간의 크기가 최댓값에 이를 때까지 페이지 제거.
• 다수의 페이지들을 클러스터/그룹으로 묶어 한 번에 스왑 파티션에 저장함으로써 디스크 효율 개선. 클러스터링은 디스크의 탐색과 회전 지연에 대한 오버헤드를 경감시킴.

Swapping: Policies

물리 메모리 크기의 극복: 정책

• 빈 메모리 공간이 거의 없으면 운영체제는 메모리 압박 해소를 위해 다른 페이지들을 강제적으로 페이징 아웃.
• 내보낼 페이지의 선택은 운영체제의 교체 정책에 의해 정해짐.

캐시 관리

• 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수 최소화. 즉, 디스크로부터 페이지를 가져오는 횟수 최소화. (== 캐시 히트 횟수 최대화)
• 캐시 히트/미스 횟수를 안다면 프로그램의 평균 메모리 접근 시간을 계산 가능.
• 현대 시스템에서는 디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 줌.
• 디스크 속도 수준으로 느리게 실행되는 것을 방지하기 위해서는 적절한 정책을 만들고 미스를 최대한 줄여야 함.

최적 교체 정책

• 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킴.
• 현재 탑재되어 있는 각 페이지들의 미래를 살펴보아, 가장 먼 미래에 접근 될 페이지를 내보냄.
• 일반적으로 미래의 접근을 미리 알 수 없으므로 구현이 불가.

간단한 정책: FIFO

• 단순하게 큐의 마지막에 있는, 가장 먼저 들어온 페이지를 내보냄.
• 구현하기 매우 쉬우며, 성능은 떨어짐.

또 다른 간단한 정책: 무작위 선택

• 구현하기 쉬우며 평균적으로 FIFO보다는 약간 더 좋은 성능을 보임.

과거 정보의 사용: LRU

• 과거 사용 이력을 활용하여, 가까운 과거에 한 페이지에 접근했다면 가까운 미래에 그 페이지를 다시 접근할 것이라고 추측할 수 있음.
• 활용 가능한 과거 정보는 빈도 수, 최근성이 있음. 이는 지역성의 원칙에 기반을 둠.
• LFU 정책 : 가장 적은 빈도로 사용된 페이지를 교체.
• LRU : 가장 오래 전에 사용했던 페이지를 교체.

워크로드에 따른 성능 비교

지역성이 없는 경우

• 접근되는 페이지들의 집합에서 페이지가 무작위적으로 참조되는 경우.
• 어느 정책을 사용하든 큰 상관이 없음. LRU, FIFO, 무작위 선택 모두 동일한 성능을 보이며, 히트율은 캐시의 크기에 의해 결정 됨.
• 캐시가 충분히 크면 어느 정책을 사용하든 상관 없음.

80 대 20의 경우

• 20%의 페이지에서 80%의 참조 발생, 나머지 80%의 페이지에서 20%의 참조만 발생하는 경우.
• 인기있는 페이지들을 캐시에 오래 두는 LRU가 가장 좋은 성능. FIFO와 랜덤 정책도 나쁘지 않은 성능.

순차 반복의 경우

• 순서대로 모든 페이지를 반복하여 참조하는 경우.
• LRU와 FIFO에서 가장 안 좋은 성능을 보임.
• 랜덤의 경우 훨씬 좋은 성능을 보임.

과거 이력 기반 알고리즘 구현

LRU의 경우

• 완벽히 구현하기 위해서는 각 페이지 접근마다 해당 페이지가 리스트 가장 앞으로 이동하도록 자료 구조를 갱신해야 함.
• 어떤 페이지가 언제 사용되었는지 관리하기 위해 모든 메모리 참조 정보를 기록해야 함.
• 이를 효율적으로 하기 위해 하드웨어의 지원을 받을 수 있다. 예를 들어 페이지 접근이 있을때마다 메모리 시간 필드를 갱신.

LRU 정책에 근사하기

• 연산량을 고려했을 때, 완벽한 LRU를 만들기보다 LRU에 근사하는 식으로 만들면 훨씬 쉬움.
• use bit
  • 시스템의 페이지마다 하나의 use bit를 둠.
  • 페이지가 참조될 때마다 하드웨어에 의해 use bit가 1로 설정.
  • 시계 알고리즘에 의해 주기적으로 use bit를 지워가며 교체 대상을 찾는 방식.

갱신된 페이지 고려

• 만약 어떤 페이지가 변경된 경우, 그 페이지를 내보내기 위해 비용(I/O) 지불 필요. 만약 변경되지 않았다면 내보낼 때 추가 비용이 없이 다른 용도로 재사용될 수 있음.
• 따라서 dirty 페이지보다 깨끗한 패이지를 내보내는 것을 선호.
• modified bit를 이용해 교체 대상을 선택.
  • 페이지가 변경될 때마다 비트가 1로 설정.
  • 시계 알고리즘에 의해 교체 대상을 선택할 때 사용되지 않고 깨끗한 페이지를 먼저 찾도록.

다른 VM 정책들

페이지 선택

• 언제 페이지를 메모리로 불러들일지도 결정해야 함.
• 대부분 요구 페이징 정책 사용.
  • 요청된 후 즉시 해당 페이지를 메모리로 읽어들임.
• 어떤 페이지가 곧 사용될지 예상하면 미리 메모리로 읽어들이느 선반입 가능.
  • 성공 확률이 높을 때에만 해야 함.

클러스터링

• 변경된 페이지를 디스크에 반영하는 방식에 관한 정책.
• 디스크 드라이브는 여러 개의 작은 크기의 쓰기 요청보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있으므로 보통 모아서 한 번에 효율적으로 기록.

Thrashing

쓰래싱

• 메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 어떻게 해야?
• 끊임없이 페이징 하게 되는 상황을 쓰래싱이라고 함.
• 발견과 해결 기법
  • 진입 제어 : 다수의 프로세스가 존재할 때, 일부 프로세스의 실행 중지.
  • out-of-memory killer : 메모리 요구가 초과되면 많은 메모리를 요구하는 프로세스를 골라 죽임.

과도한 페이징에 대한 최적의 해결책 : 더 많은 메모리를 구입해라!!

Case Study: VAX

VAX/VMS 가상 메모리 시스템 배경

VMS

• 컴퓨터의 구조적 결함을 소프트웨어로 보완한 사례.

메모리 관리 하드웨어

VAX-11

• 하이브리드 구조. 주소 공간 절반은 프로세스 공간, 각 프로세스마다 다르게 할당.
• VAX 하드웨어의 페이지 크기가 512바이트로 매우 작음. 선형 페이지 테이블 크기가 지나치게 커짐. -> VMS가 페이지 테이블 저장을 위해 메모리를 소진하는 것을 막아야.
  • 사용자 주소 공간을 두 개의 세그멘트로 나눠 프로세스마다 각 영역을 위한 페이지 테이블을 갖게 함. 스택과 힙 사이 사용되지 않는 주소 영역을 위한 페이지 테이블 공간이 필요 없게 됨.
  • 사용자 페이지 테이블들을 커널의 가상 메모리에 배치하여 메모리 압박을 줄임. 페이지 테이블을 할당하거나 크기를 키울 때, 가상 메모리, 세그멘트 내에 공간을 할당. 메모리 고갈 시, 페이지 테이블의 페이지들을 디스크로 스왑하여 물리 메모리를 다른 용도로 사용할 수 있게 함.

페이지 교체

VAX 페이지 테이블 항목이 갖고있는 비트

• 유효 비트, 보호 필드, 변경 비트, 운영체제 예약 필드, 물리 메모리 페이지 위치를 저장하기 위한 물리 프레임 번호.
• reference bit가 없음. 어떤 페이지가 자주 사용 중인지를 하드웨어 지원 없이 판단해야 함.
• 메모리를 너무 많이 사용하는 프로그램에 대한 대비책이 없음.

세그멘트된 FIFO 교체 정책

• 각 프로세스들은 상주 집합 크기라는 메모리 유지할 수 있는 최대 페이지 개수를 지정.
• 각 페이지들은 FIFO 리스트에 보관. 페이지 개수가 RSS보다 커지만 제일 먼저 들어왔던 페이지가 방출.
• 추가적으로 전역 클린-페이지 프리 리스트와 더티-페이지 리스트라고 하는 두 개의 second-chance list를 도입.
  • 메모리에서 제거되기 전에 페이지가 보관.
  • 다른 프로세스에서 빈 페이지가 필요하면 전역 클린 리스트에서 첫 프리 페이지를 꺼냄.
  • 원래의 프로세스가 해당 페이지가 회수되기 전에 폴트를 발생시키면, 프리 리스트에서 페이지를 가져와 다시 사용하는 식으로 디스크 접근을 피함.
• 전역 second-chance list 크기가 클수록 세그멘트된 FIFO 알고리즘은 LRU와 유사하게 동작.

페이지 클러스터링

• VMS의 작은 페이지 크기 극복
• 페이지의 크기가 작을수록 스왑할 때 디스크 I/O가 비효율적.
• 클러스터링 기법을 써서 전역 더티 리스트의 페이지들을 작업 묶음으로 만들어 한 번에 디스크로 보내서 성능 향상.

그 외의 VM 기법들

demand zeroing

• 페이지가 주소 공간에 추가되는 시점에, 페이지 테이블에 접근 불가능 페이지라고 표기하고 항목 추가.
• 프로세스가 추가된 페이지를 읽거나 쓸때 트랩 발생.
• 트랩을 처리하며 물리 페이지를 0으로 채우고, 프로세스의 주소 공간으로 매핑하는 등 필요한 작업을 함.
• 프로세스가 해당 페이지를 전혀 접근하지 않는다면 이 작업들을 피할 수 있다는 장점.

copy-on-write

• 운영체제가 한 주소 공간에서 다른 공간으로 페이지를 복사할 필요가 있을 때, 복사하지 않고 해당 페이지를 대상 주소 공간으로 매핑, 해당 페이지 테이블 엔트리를 양쪽 주소 공간에서 읽기 전용으로 표시.
• 만약 양쪽 주소 공간이 읽기만 하면 더 이상 처리 필요 없이 빠른 복사 가능.
• 둘 중 하나가 페이지 쓰기를 시도하면 운영체제 트랩 발생.
• 운영체제는 해당 페이지가 COW 페이지인 것을 파악, 새로운 페이지 할당, 데이터 복사, 주소 공간에 매핑.

CPU, 메모리, 디스크 등 시스템의 자원을 호율적으로 관리하는 것이 운영체제의 역할이다.

한 마디로 자원 관리자.

가상화?

OS가 한정된 자원(CPU, 메모리 등)을 효율적으로 사용하기 위해, 그리고 안전하게 격리하여 사용하기 위해 가상화 하여 사용한다.

CPU 가상화

• 소규모의 CPU 집합을 여러 개의 CPU가 존재하는 것처럼 변환하여 동시에 많은 수의 프로그램을 실행시키는 것을 CPU 가상화라고 한다.

메모리 가상화

• 각 프로세스는 자신만의 가상 주로 공간을 갖고, 운영체제는 이 가상 주소 공간을 물리 메모리에 매핑한다.
• 실제 물리 메모리는 공유 자원이고, 운영체제에 의해 가상화 되어 관리된다.

그런데 문제가 있당??

병행성

• 프로그램이 한 번에 많은 일을 동시에 하려고 할 때 발생하는 것이 병행성 문제이다.
• 각 명령어는 원자적으로 실행되지 않기 때문에 운영체제, 또는 멀티스레드에서 병행성 문제가 생길 수 있다.

영속성

• DRAM 같은 장치들은 데이터를 휘발성 있게 저장히기 때문에 데이터 손실을 막기 위해 영속적으로 저장 가능한 하드웨어/소프트웨어 저장장치가 필요하다.
• 또한, 쓰기 중의 다양한 문제에 대비하여 저널링, Copy-On-Write 등을 사용하고, 효율적인 디스크 작업을 위해 B-Tree 등 다양한 종류의 자료 구조를 활용한다.

OS를 어떻게 설계하는 것이 바람직한지?

• 운영체제는 위와 같이 CPU, 메모리, 디스크와 같은 물리 자원을 가상화 하고, 병행성과 같은 문제를 처리하고, 파일을 영속적으로 저장한다.
• 운영체제 설계에 있어 가장 중요한 목표는 오버헤드를 최소화 하는 것, 즉 성능이다.
• 또한, 프로그램 간의 보호를 위한 isolation이 필요하다.
• 계속해서 문제 없이 실행되어야 하는 신뢰성, 에너지-효율성, 보안, 이동성 등이 운영체제의 목표이다.

운영체제의 역사

• 단순 라이브러리 : 초창기에는 단순히 자주 사용되는 함수들을 모아놓은 라이브러리 형태.
• 보호 : 운영체제 코드는 장치를 제어하기 때문에 기존의 라이브러리 형태가 아닌 시스템 콜 형태로 구현.
• 시스템 콜 : 제어를 운영체제에 넘길 때 하드웨어 특권 수준을 상향 조정한다. 일반적인 user mode가 아니라 trap handler를 이용해 kernel mode로 격상시킨다. 따라서 운영체제는 시스템의 하드웨어를 자유롭게 접근하며 작업할 수 있게 된다.
• 멀티프로그래밍 : 한 번에 하나의 프로그램만 실행시키는 것이 아니라, 여러 작업을 메모리에 담아 빠르게 번갈아가며 실행하여 CPU 사용률을 향상. 한 번에 여러가지 작업을 하게 됨으로써 메모리 보호와 병행성 문제에 대한 관리가 중요해졌다.
• 현대 : 다양한 OS의 출범 및 PC 보급.

프로세스

프로세스라 함은... 그거지 그거

실행 중인 프로그램.

(프로세스 입장에서) 하드웨어 구성 요소

• 메모리 : 명령어 및 데이터가 저장. 프로세스가 접근 가능한 메모리 주소 공간 제공.
• 레지스터 : 명령어들이 직접 읽거나 갱신.
  • 프로그램 카운터 : 현재 어느 명령어가 실행 중인지.
  • 스택 포인터 : 함수의 변수 스택 관리.
  • 프레임 포인터 : 리턴 주소를 저장하는 스택을 관리.

하나의 OS에 여러 개의 프로세스가 떠있을 텐데?

• 자원을 여러 프로세스가 돌아가며 사용하게 함으로써, 원하는 수 만큼 프로세스를 동시에 실행하는 시분할 기법.
• CPU를 공유하기 때문에 각 프로세스의 성능이 낮아짐.
• 모든 현대 운영체제들이 채택 중.

프로세스 API

운영체제는 프로세스에 대한 기본 기능을 제공.

• Create : 새로운 프로세스를 생성할 수 있는 방법 제공.
• Destroy : 프로세스를 강제로 제거할 수 있는 방법 제공.
• Wait : 프로세스의 대기 인터페이스 제공.
• 각종 제어 : 일시정지, 재시작 등의 기능 제공.
• Status : 프로세스 상태 정보를 얻어내는 기능.

프로세스 생성

• 프로그램 실행 시, 운영체제는 디스크에 저장되어있는 프로그램 코드와 정적 데이터를 메모리, 프로세스의 주소 공간에 load한다.
• stack 메모리 영역을 할당한다. 스택은 지역 변수, 함수 인자, 리턴 주소 등을 저장하기 위해 사용된다. heap 메모리 영역을 할당한다. 힙은 동적으로 할당된 데이터(연결 리스트, 해시 테이블, 트리 등)를 저장하기 위해 사용된다.
• 입출력과 관계된 초기화 작업을 수행한다. Unix에서는 프로세스들이 STDIN, STDOUT, STDERR에 해당하는 파일 디스크립터를 갖는다.
• 프로그램 실행 준비를 마치면, 프로그램의 시작 지점에서부터 실행을 시작한다. 운영체제는 CPU를 새로 생성된 프로세스에게 넘기게 되고, 프로그램 실행이 시작된다.

프로세스 상태

간단하게 세 상태 중 하나로 존재한다.

• Running : 실행 상태. 명령어를 실행 중이다.
• Ready : 준비 상태. 실행할 준비가 되어있지만, 운영체제가 다른 프로세스를 실행하고 있는 등의 이유로 대기 중이다.
• Blocked : 수행 중단 중. 프로세스가 다른 사건(디스크 입출력 완료 등) 완료까지 기다리는 상태이다.
• 그 외에도
• initial : 프로세스가 생성되는 중인 초기 상태.
• zombie / final : 프로세스는 종료되었지만, 메모리에 남아있는 상태. 보통 내가 회사 장비에서 실수했을때 많이 보임

자료 구조

프로세스 리스트

• 프로세스 상태를 파악하기 위해 준비 상태의 프로세스들에 대한 자료 구조.

레지스터 문맥

• 프로세스가 중단되었을 때, 해당 프로세스의 레지스터 값들을 저장.
• 이후에 복원하여 운영체제가 프로세스 실행을 재개할 수 있다. (문맥 교환)

Process API

Unix는 프로세스 생성을 위해 for()와 exec() 시스템 콜을 사용하며, wait() 시스템 콜을 사용하여 프로세스를 종료한다.

fork()

• 프로세스를 생성한다.
• 호출하면 부모(메인) 프로세스의 복사본 프로세스가 생성된다. 이를 자식 프로세스라고 한다.
• 자식 프로세스는 자신만의 주소 공간, 레지스터, PC 값, PID 값 등을 갖는다는 점에서 부모 프로세스와는 다른 프로세스이다.
• fork()로부터 부모 프로세스는 생성된 자식 프로세스의 PID를 반환 받고, 자식 프로세스는 0을 반환받는다. 이러한 값의 차이로 인해 부모와 자식 프로세스가 서로 다른 코드를 실행하도록 만들 수 있다.

wait()

• 부모 프로세스가 자식 프로세스의 종료를 대기한다.
• 호출한 위치에서 자식 프로세스의 종료 시점까지 자신의 실행을 중지시킨다.

exec()

• 자기 자신이 아닌 다른 프로그램을 실행해야 할 때 사용한다.
• 실행 파일의 이름과 인자를 받아, 해당 실행 파일의 코드와 정적 데이터를 읽어 현재 실행 중인 프로세스의 코드 segment와 정적 데이터 부분을 덮어 씌운다.
• 힙과 스택, 주소 공간들은 새로운 프로그램의 실행을 위해 초기화 된다.
• 프로세스의 argv와 같은 인자를 전달하여 프로그램을 실행시킨다.
• 새로운 프로세스를 생성하는 것이 아니라, 현재 실행 중인 프로그램을 다른 실행 중인 프로그램으로 대체하는 것.

API는 왜 쓸까용?

쉘 구현을 위해 fork와 exec 분리가 필요

• 쉘은 명령어 실행을 위해 fork()로 새로운 자식 프로세스를 만든다.
• 그리고 exec()의 변형으로 프로그램을 실행시키고, wait()으로 명령어가 끝나기를 기다린다.
• 자식 프로세스가 종료되면 wait()으로부터 return하고 다음 명령어를 기다린다.
• 이 과정에서 fork()와 exec()가 분리됨으로써 쉘은 명령어 입출력을 재지정 처리하기 쉬워진다.
• Unix의 pipe가 유사한 방식으로 구현되었다.

암튼 fork()와 exec() 조합이 프로세스 생성/조작에 있어 강력한 방법이다~

Direct Execution

기본적으로 CPU 가상화를 위해서는 물리적인 CPU를 여러 프로세스에서 잠깐씩 돌아가며 실행시켜 CPU 시간을 나누어 씀으로써 구현 가능하다. 즉, CPU 가상화를 구현하기 위한 핵심적인 저수준 기법. 그러나 이는 성능 저하, 제어 문제가 있다.

Limited Direct Execution

제한적 직접 실행

• 직접 실행 : 프로그램을 CPU 상에서 그냥 직접 실행시키는 것.
• 직접 실행 문제점 : 운영체제가 원치 않는 일을 하지 않는다는 것 보장 어려움. 프로세스 실행 시, 운영체제가 어떻게 프로그램 실행을 중단/다른 프로세스로 전환하는지.

issue 1 : 제한된 연산

직접 실행의 장점 : 빠르게 실행되는 것.

• 프로그램이 하드웨어 CPU에서만 실행도기 때문이다.
• 단, 그렇기 때문에 디스크 입출력 요청이나 CPU/메모리 등 자원에 대한 추가 할당 요청 수행 시의 문제가 있다.

만약 프로세스가 원하는대로 하도록 방치하면?

• 바람직하지 않음.

user/kernel mode 도입

• user mode에서 실행되는 코드는 할 수 있는 일이 제한된다.
  • 입출력 요청 X. (예외 발생 및 프로세스 제거)
  • 자원 접근 권한 일부 제한.
• kernel mode에서는 특수한 명령어를 포함해 모든 작업 수행 가능하다.
  • 입출력 요청 및 자원 접근 가능.

사용자 프로세스가 디스크 입출력 실행을 해야 한다면?

• 시스템 콜 사용.
  • 파일 시스템 접근, 프로세스 생성/제거, 다른 프로세스와의 통신, 메모리 할당 등 가능.
  • 실행을 위해 trap 명령어 실행 :
    • 하드웨어는 호출한 프로세스의 필요 레지스터들을 각 프로세스의 kernel stack에 저장.
    • 커널 안으로 분기 및 특권 수준을 kernel mode로 상향.
    • 완료 시, return-from-trap을 호출하여 다시 user mode로 하향, 호출한 사용자 프로그램으로 return. 이때, 레지스터 값들을 스택에서 pop하여 user mode 프로그램의 실행을 다시 시작.

trap table

• 커널이 임의의 코드를 실행하기 위해서는 접근 권한 검사가 끝난 뒤 분기 필요. 즉, trap이 코드 어디를 실행해야하는지 모른다.
• 그래서 커널은 부팅 시(kernel mode로 동작하기에 원하는대로 제어 가능)에 트랩 테이블을 만들고 이를 이용해 시스템을 통제.
• 명령어를 이용해 하드웨어에 trap handler 위치를 알려준다. 하드웨어는 해당 위치를 기억하고 있다가 시스템 콜과 같은 사건이 발생했을때 어느 코드로 분기하여 실행해야 할지 알 수 있다.

간단히 하자면

1. 부팅 시, 커널은 트랩 테이블 초기화, CPU는 나중에 사용을 위해 테이블 위치 기억.
2. 프로세스 실행 시, return-from-trap을 이용해 새로운 프로세스를 위한 노드를 할당하여 프로세스 리스트에 삽입, 메모리 할당 등 작업 후, CPU를 user mode로 전환하고 프로세스 실행.
3. 프로세스가 시스템 콜 호출 시, 운영체제로 다시 trap.
4. 운영체제가 시스템 콜 처리.
5. return-from-trap을 이용해 다시 제어를 프로세스에 넘김.
6. 프로세스는 자기 할 일 하고 main()에서 return. 일반적으로 스텁 코드로 리턴하고, 스텁 코드가 프로그램 종료시킴.
7. 종료 시, exit() 호출, 운영체제로 트랩.
8. 운영체제가 정리 작업을 하고 종료. (안 간단함)

issue 2: 프로세스 간 전환

간단히 프로세스 간 전환이 가능해야 한다. CPU에서 프로세스가 실행 중이라는 것은, 운영체제가 실행 중이지 않다는 것이기 때문에 프로세스 간 전환이 안 된다.

협조 방식 : 시스템 콜 기다리기

옛날 방식. 너무 오랫동안 실행될 가능성이 있는 프로세스는 운영체제 구동을 위해 주기적으로 CPU를 포기할 것이라고 가정.

yield 시스템 콜 : 운영체제에게 제어를 넘겨 운영체제가 다른 프로세스를 실행할 수 있게 한다.

또 다른 경우로는... 프로그램이 비정상적인 행위를 하게 되면 운영체제로 제어가 넘어간다.(트랩)

비협조 방식 : 운영체제가 전권을 행사

프로세스의 협조가 없는 상황에서 CPU의 제어를 획득하는 방식이다.

타이머 인터럽트

• 수 밀리 초마다 인터럽트를 발생시킨다.
• 인터럽트가 발생하면 수행 중이던 프로세스는 중단되고, 운영체제의 인터럽트 핸들러가 실행된다.
• 운영체제는 하드웨어에게 타이머 인터럽트 발생 시 실행할 코드를 미리 알려줘야 한다.
• 인터럽트 발생 시, 하드웨어는 프로세스 상태를 저장해 나중에 return-from-trap으로 프로그램을 다시 시작할 수 있게 한다. (시스템 콜이 호출되었을 때와 마찬가지)

문맥의 저장과 복원

협조/비협조적인 경우 모두 운영체제가 제어권을 다시 획득했을때 프로세스를 계속 실행할건지, 다른 프로세스로 전환할 것인지가 스케줄러에 의해 결정된다.

문맥 교환

• 운영체제가 실행 중인 프로세스의 범용 레지스터 값, PC, 현재 커널 스택 포인터를 커널 스택에 저장.
• 실행될 프로세스의 범용 레지스터 값, PC,를 복원하고, 커널 스택을 해당 프로세스의 커널 스택으로 전환.
• 이를 통해 운영체제는 인터럽트된 프로세스 문맥에서 전환 코드를 호출, 실행될 프로세스 문맥으로 return 가능.
• return-from-trap을 실행하면 실행 예정이던 프로세스가 실행 중이 된다.

총 두 번의 레지스터 저장/복원이 일어난다. 첫 번째 : 타이머 인터럽트 발생 시.

• 실행 중인 프로세스의 레지스터 값이 저장, 저장 장소는 해당 프로세스의 커널 스택.

두 번째 : 운영체제가 프로세스 전환 결정 시.

• 커널 레지스터는 운영체제에 의해 해당 프로세스의 프로세스 구조체에 저장. (실행 예정인 프로세스로부터 커널로 트랩 된 것처럼 만듦)

병행성 걱정

시스템 콜 처리 중에 타이머 인터럽트가 발생하면 병행성 문제가 생길 수 있다.

간단한 처리 방법 : 인터럽트 불능화

• 하나의 인터럽트 처리 중에는 다른 인터럽트는 CPU에 전달되지 않게 한다.
• 단, 이 방식은 너무 오래 불능화하면 인터럽트를 놓치는 묹제점.

lock 기법

• 내부 자료 구조에 동시에 접근하는 것을 방지하여, 커널 안에서 동시에 다수의 활동이 진행될 수 있게 허용.

CPU Scheduling

워크로드에 대한 가정

워크로드 : 일련의 프로세스들이 실행하는 상황.

• 이를 결정하여 정교하게 스케줄링 정책을 손질해야 한다.

스케줄링 평가 항목

스케줄링 평가 항목 : 워크로드에 대한 가정 외에도 스케줄링 정책의 비교를 위해 결정해야 함.

다양한 평가 기준이 존재.

• 반환 시간 : 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간. 성능 측면에서의 평가 기준.
• 공정성 : 예를들어 Jain's Fairness Index에 따라 측정.
• 반환 시간과 공정성은 스케줄링에서 서로 상충되는 목표.

선입선출

FIFO : 선입선출

• 단순하고 구현하기 쉽다.
• convoy effect : 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상.

FCFS : 선도착선처리

최단 작업 우선

SJF : 최단 작업 우선.

• FIFO의 convoy effect 문제 완화. 작업 실행 시간이 다른 경우.
• 이미 실행시간이 긴 작업이 먼저 도착하여 실행되고 있고, 이후에 짧은 작업들이 도착 시, SJF라도 긴 작업 먼저 이미 작업하고 그 후에 짧은 작업들이 작업 되는 문제.

최소 잔여시간 우선

STCF : 최단 잔여시간 우선

• SJF와 같은 문제 발생 시에, 긴 작업을 중지하고 짧은 작업이 도착했을때 그 작업들을 먼저 실행하기로 할 수 있다.
• SJF에 선점 기능 추가.
• 새로운 작업이 들어오면, 남아있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고, 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.

반환 시간이 전부인가?

새로운 평가 기준 -> 응답 시간 응답 시간 : 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간.

라운드 로빈

Round-Robin : 하나의 작업을 일정 시간(타임 슬라이스/스케줄링 퀀텀) 동안 실행한 후, 실행 큐의 다음 작업으로 전환하는 방식.

• 응답 시간 문제를 해결.
  • 타임 슬라이스의 길이가 짧을수록, 응답 시간 기준으로 성능이 좋아짐.
  • 너무 짧으면 문맥 교환 비용이 전체 성능에 영향을 미침.
  • 즉, 타임 슬라이스의 길이는 문맥 교환 비용을 상쇄할 수 있을 만큼 길어야 하지만, 응답 시간이 너무 길어지면 안 된다.
  • 문맥 교환 비용 : 레지스터 저장/복원 작업, CPU 캐시, TLB, 분기 예측 등. 작업이 전환되면 갱신되어야 하므로 매우 큰 성능 비용 유발.
• 응답 시간이 평가 기준이면 RR이 좋고, 반환 시간이 측정 기준이면 최악.
• 작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 공정한 정책.

입출력 연산의 고려

프로세스가 입출력 작업하는 동안 실행될 다른 작업을 스케줄 해야 한다. 입출력 완료 시에도 인터럽트 하여 어떤 작업을 올릴지 결정. 하나의 프로세스가 입출력 작업을 하는 동안, 다른 프로세스가 CPU를 사용하게 할 수 있다. (연산의 중첩)

But

각 작업의 실행 시간을 알고 있다면 스케줄링에 큰 도움이 되겠지만, 범용 운영체제에서 작업의 길이에 대해 알 수 있는 길은 없다. 아무것도... 없었다.

Multi-Level Feedback

멀티 레벨 피드백 큐 : CTSS에 사용된느 가장 유명한 스케줄링 기법.

• 해결하려고 하는 문제 :
  • 짧은 작업을 먼저 실행시켜 반환 시간 최적화.
  • 응답 시간 최적화.
• 작업 실행 시간 등과 같은 프로세스에 대한 정보가 없을 때 어떻게 적절히 스케줄링 할 수 있을까?

MLFQ : 기본 규칙

MLFQ 기본 알고리즘

• 여러 개의 큐로 구성되어 있으며, 각각 다른 우선순위가 배정된다. 실행 준비 된 프로세스는 이중 하나의 큐에 존재.
• 높은 우선순위 큐에 존재하는 작업이 선택 된다.
• 큐에 여러 작업이 있을 수 있는데, 이는 같은 우선순위를 가진다. 이 작업들 내에서는 Round-Robin 스케줄링 사용.
• 우선순위 정하는 방식 :
  • 각 작업의 특성에 따라 동적으로 우선순위 부여.
  • 입출력을 기다리며 반복적으로 CPU를 양보하는 경우, 우선순위 높게 유지.
  • 긴 시간 동안 CPU를 집중적으로 사용하는 경우, 우선선위 낮춤.

시도 1: 우선순위의 변경

예 1: 한 개의 긴 실행 시간을 가진 작업

• 타임 슬라이스 1이 지나면 작업의 우선순위를 한 단계 낮춤.
• 타임 슬라이스 2가 지나면 가장 낮은 순위를 가지게 되고, 계속 머무름.

예 2: 짧은 작업과 함께

• 긴 작업이 낮은 우선순위 큐에서 계속 실행되고 있고, 짧은 작업이 들어왔을 때, 짧은 작업이 가장 낮은 우선순위 큐에 놓여져 빠르게 실행되게 된다.
• 이 짧은 작업 또한 타임 슬라이스 경과에 따라 우선순위가 낮아지지만, 기존의 긴 작업과 같은 우선순위에 놓이기 전에 종료된다.
• 스케줄러는 짧은/긴 작업인지는 알 수 없기 때문에 일단 짧은 작업이라 가정하여 높은 우선순위로 동작시키다가, 진짜 짧은 작업이면 빨리 동작이 끝나고 종료, 긴 작업이라면 천천히 우선순위가 낮아진다.

예 3: 입출력 작업에 대해서는?

• 프로세스가 타임 슬라이스 소진 전에 프로세서를 양도하면 같은 우선순위를 유지하게 된다.
• 자주 입출력을 수행하면 타임 슬라이스 소진 전에 CPU를 양도하게 된다. 그런 경우에 우선순위를 유지한다. (대화형 작업을 빨리 실행)

현재 MLFQ의 문제점

1. 기아 상태 발생 가능 :
   • 시스템에 너무 많은 대화형 작업이 존재하면 모든 CPU 자원을 소모.
   • 긴 실행 시간 작업은 CPU 시간을 할당받지 못하고 굶어죽ㅜ
2. 스케줄러를 자신에게 유리하게 동작하도록 프로그램 작성 가능 (어뷰징;;) :
   • 예를 들면 타임 슬라이스가 끝나기 전에 아무 파일이나 입출력 하게 하여 CPU 양도.
   • 그러면 같은 큐에 머무르며 더 높은 CPU 시간을 얻게 된다.
3. 프로그램은 시간 흐름에 따라 특성이 변할 수 있음 :
   • CPU 위주 작업이 대화형 작업으로 변할 수 있음.
   • 다른 대화형 작업과 비슷하게 처리됨.

시도 2: 우선순위의 상향 조정

1, 3 문제 해결.

우선순위 상향 조정 : cpu 위주 작업을 조금이라도 진행하도록 보장하여 기아 문제를 방지해야 한다.

• 일정 시간이 지나면 시스템의 모든 작업을 최상위 큐로 이동.
  • 프로세스는 굶비 않는다는 것을 보장.
  • CPU 위주의 작업이 대화형 작업으로 특성이 변할 경우, 우선순위 상향 받을 수 있음.
• 부두 상수 : 여기서의 일정 시간을 의미. 정확하게 결정하기 위해선 흑마술이 필요;
  • 너무 크면 긴 실행 시간을 가진 작업은 굶음. 너무 작으면 대화형 작업이 적절하게 CPU 시간 활용 못 함.

시도 3: 더 나은 시간 측정

2 문제 해결.

주어진 단계에서 시간 할당량을 소진하면 우선순위가 낮아지게 한다.

• 각 단계에서 CPU 총 사용량을 측정하여 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순의 큐로 강등한다.
• 즉, 타임 슬라이스가 끝나기 직전에 입출력 명령을 내려 CPU 시간 독점하는 것을 막는다.

MLFQ 조정과 다른 쟁점들.

대부분의 MLFQ 기법은 큐 별로 타임 슬라이스 변경이 가능하다.

• 우선순위가 높은 큐는 짧은 타임 슬라이스를 주어, 대화형 작업으로 구성하고 빠르게 교제하게 할 수 있다.
• 낮은 우선순위는 CPU 중심의 오래 실행되는 작업을 포함하여 오래 실행되도록 한다.

Lottery Scheduling

비례 배분 스케줄러

• 반환 시간/응답 시간을 최적화하기보다 각 작업에 CPU의 일정 비율을 보장하는게 목적.
• 좋은 예 중 하나 : 추첨 스케줄링.

기본 개념 : 추첨권이 당신의 몫을 나타낸다

추첨권 : 프로세스가 받아야 할 자원의 몫.

• 각 프로세스가 일정 비율만큼 추첨권을 갖고 있고, 타임 슬라이스가 끝날 때마다 스케줄러가 추첨권을 선택하여 선택된 프로세스에 할당.
• 할당 결과가 원하는 비율(추첨권 비율)을 정확히 보장하지는 않지만, 작업이 진행될수록 원하는 비율에 가까워진다.

무작위 방법이 의외로 좋은 이유;

• 특이 사항 대응이 된다. ex) 최악의 경우가 발생하지 않는다.
• 관리해야 할 상태 정보가 적어 매우 가볍다.
• 매우 빠르다;;;;

추첨 기법

추첨권 화폐

• 사용자가 작업들에 개인의 화폐 가치로 추첨권을 자유롭게 할당.
• 시스템이 자동적으로 화폐 가치를 변환.

추첨권 양도

• 양도를 통해 일시적으로 다른 프로세스에게 추첨권을 넘겨줄 수 있다.
• client 프로세스가 server에게 작업 요청 및 빠른 작업을 위해 추첨권을 양도할 수 있다.
• 요청 완수 시, server는 다시 client에게 추첨권을 반환.

추첨권 팽창

• 프로세스가 일시적으로 자신이 소유한 추첨권을 늘이거나 줄일 수 있다.
• 프로세스들이 서로 신뢰할 때 유용하며, 많은 CPU 시간이 필요로 하는 프로세스가 시스템에 이를 알리고 혼자 추첨권의 가치를 상향 조정한다.

구현

추첨 스케줄링의 구현

• 난수 발생기, 프로세스 집합 자료 구조, 추첨권의 개수만으로 단순하게 구현 가능하다.
• 난수로 추첨권 선택 후, 리스트를 순회하며 카운터 값을 이용해 당첨자를 찾는다.

불공정 지표

• 두 작업을 거의 동시에 종료시키고 싶을 때, 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업보다 먼저 종료될 수 있다.
• 이때 이 차이를 불공정 지표라고 한다.
• 작업이 충분한 기간 동안 실행되어야 불공정이 낮아진다, 즉 원하는 결과에 가까워진다.

추첨권 배분 방식

추첨권 할당 방식에 따라 시스템 동작이 크게 달라지는데, 이는 기본적으로 사용자가 가장 잘 알고 있다고 가정한다. 즉, 사용자에게 추첨권을 나눠준 뒤, 사용자가 알아서 작업에 배분하도록. 이는 해결책이 아니다. 주어진 작업 집합에 대한 추첨권 할당 문제는 미해결 떡밥ㅡㅡ

왜 결정론적 방법을 사용하지 않는가?

보폭 스케줄링

• 무작위성을 이용하면 단순하지만 짧은 기간 실행될때 정확한 비율 보장이 어렵다.
• 결정론적 공정 배분 스케줄러인 보폭 스케줄링을 고안.
• 시스템의 각 작업은 보폭(stride)을 갖고 있음. 보폭은 임의의 큰 값을 추첨권 개수로 나눠 계산.
• 프로세스가 실행될 때마다 pass 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지를 추적.
• 보폭과 pass 값을 사용해 어느 프로세스를 실행시킬지 결정.
  • 가장 작은 pass 값을 가진 프로세스를 선택.
• 각 스케줄링 주기마다 정확한 비율로 CPU 배분이 가능.

근데 왜 추첨 스케줄링 씀?

• 추첨은 상태 정보가 필요 없다.
• 보폭에서는 새로운 작업이 들어왔을때 pass가 0이 되어 CPU 독점하는 등의 문제 발생 가능.
• 추첨에서는 그러한 문제가 없고 CPU 사용 현황, pass 값 등 유지가 필요 없음.
• 추첨에서는 새 프로세스 쉽게 추가 가능.

Multi-CPU Scheduling

배경 : 멀티프로세서 구조

하드웨어 캐시

• 메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하여 프로그램을 빠르게 실행.
• 캐시는 지역성에 기반.

    - 시간 지역성 : 데이터가 한 번 접근되면 나중에 다시 접근되기 쉽다.
    - 공간 지역성 : 접근된 데이터의 주변 데이터는 접근되기 쉽다.

• 이를 통해 무엇을 캐시에 저장할지 추측하여 동작.

캐시 일관성 문제

• CPU1에서 작업하다가 캐시에서만 특정 데이터를 변경했는데, 이후 CPU2로 이동하면 당연히 CPU1의 캐시가 아닌 메모리에서 데이터를 가져오게 된다. 즉, 변경 결과 미반영.
• 하드웨어에 의한 기본적인 해결책 : 여러 프로세스들이 하나의 메모리에 갱신할때 항상 공유하게.
  • 버스 스누핑 : 캐시는 자신-메모리 버스의 통신 상황을 계속 모니터링. 캐시 변경 발생 시, 자신의 캐시에서 삭제(무효화)하거나, 갱신.

동기화 이슈슈슈

CPU들이 동일한 데이터에 접근할 때, 올바른 연산 결과를 보장하기 위해 락과 같은 상호 배제를 보장하는 동기화 기법들이 사용된다. 여러 CPU가 하나의 데이터에 접근하여 작업할 때, lock을 이용하여 올바르게 동작하게 해야 한다.

하지만...

• 성능 측면에서 문제가 있다.
• CPU가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느려진다.

마지막 문제점: 캐시 친화성

캐시 친화성

• CPU에서 프로세스가 실행될 때, 캐시와 TLB에 상태 정보를 올려놓게 된다.
• 다음 번 프로세스 실행 시, 동일한 CPU에서 실행되는 것이 당연히 좋다.
• 매번 다른 CPU에서 실행 시, 필요한 정보를 다시 탑재해야 한다.
• 멀티 프로세서 스케줄러는 스케줄링 결정 시, 가능한 한 프로세스를 동일한 CPU에서 실행하도록 해야 한다.

단일 큐 스케줄링

SQMS (단일 큐 멀티프로세스 스케줄링)

• 단순하게 모든 작업을 단일 큐에 넣는다.
• 확장성 결여 : lock은 SQMS 코드가 단일 큐에 접근할 때 올바른 결과가 나오게 하지만, CPU 개수가 증가할수록 성능을 크게 저하시킬 수 있다.
• 캐시 친화성 : 각 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨다니며 캐시 친화적이지 못하게 진행된다.

멀티 큐 스케줄링

MQMS (멀티 큐 멀티프로세스 스케줄링)

• CPU마다 큐를 하나씩 둔다.
• 작업이 시스템에 들어오면 하나의 스케줄링 큐에 배치된다.
• 각각 독립적으로 스케줄 되기 때문에 단일 큐 방식의 정보의 공유 및 동기화 문제를 피한다.
• SQMS보다 확장성이 좋다.
  • CPU 개수가 증가할수록 큐의 개수도 증가하므로 lock과 cache 경합은 문제되지 않는다.
  • 캐시 친화적이다.
• 그러나 워크로드의 불균형이 발생한다.
  • 작업의 개수/양이 불균형할때 한 쪽 CPU가 작업을 끝마치고 유휴 상태가 될 수 있다.
• 작업을 다른 CPU로 이주시켜 개선할 수 있다.
• 이주의 필요 여부는 어떻게 결정?
  • 작업 훔치기 : 작업의 개수가 낮은 큐가 다른 큐에 많은 작업이 있는지 확인. 워크로드 균형을 맞추기 위해 작업을 가져온다.
    • but 큐를 너무 자주 검사하면 높은 오버헤드로 확장성 문제.

Linux 멀티프로세서 스케줄러

O(1) 스케줄러

• 멀티 큐
• 우선순위 기반. 시간에 따라 우선순위를 변경하여 가장 높은 작업을 선택.
• 상호작용을 가장 우선시.

CFS

• 멀티 큐
• 결정론적 비례배분 방식.
• CFS는 Completely Fair Scheduler라는 뜻으로, CPU 시간을 최대한 공정하게 배분.

BFS

• 단일 큐
• 비례배분 방식.
• EEVDF라는 방식에 기반을 둠.
• BFS는 뜻이 브레인...뻑...

  진짜요?

OS

OSTEP과 함께 가상화에 대해 알아보자 (1)

TCP에는 전송 데이터 양을 조절하는 흐름 제어, 데이터 유실/잘못 수신 시 대처하는 오류 제어, 네트워크 혼잡에 대처하는 혼잡 제어가 존재한다.

흐름 제어

송수신 측의 데이터 처리 속도가 다를 때(특히 송신 측의 속도가 빠른 경우), 버퍼가 흘러넘치는 오버플로우 문제가 발생할 수 있다. 수신 측의 버퍼 용량을 초과한 이후에 도착하는 패킷은 손실될 수 있으며, 불필요한 추가 패킷 전송이 발생한다.

이렇게 송수신측의 TCP 버퍼 크기 차이로 인한 문제를 방지하기 위해 송수신 측의 데이터 전송량(속도)을 조절하는 것이 흐름 제어다.

Stop & Wait

데이터를 전송한 후, 받았다는 응답이 돌아올 때까지 기다렸다가 ACK를 받으면 다음 패킷을 전송하는 방식이다. (보냄 -> ACK -> 보냄 -> ACK...) 상대방이 응답을 하면 다음 데이터를 보내는 형식이기 떄문에 간단하지만 비효율적이다.

Sliding Window

현재 TCP는 대부분 슬라이딩 윈도우 방식으로 동작한다.

수신 측이 한 번에 처리 가능한 데이터를 정해두고, 수신 측의 데이터 처리 상황을 송신 측에 알려서 데이터 흐름을 제어하는 방식이다. 통신 초기에 Window Size를 교섭하기 때문에 송신 측이 수신 측이 처리 가능한 데이터의 양을 알고 있다. 따라서 수신 측에서는 굳이 처리 가능이라는 답을 날리지 않아도 송신 측에서 처리 가능 여부를 어느 정도 예측할 수 있다.

윈도우 크기 : 3-way handshake를 통해 수신 측 윈도우 크기로 설정되며, 버퍼에 남아있는 공간에 따라 변한다. 수신 측이 송신 측으로 ACK을 보낼 때 TCP header의 WIndow Size에 포함시켜 보낸다.

동작 방식

• 예를들어 송신 측이 0~6까지의 데이터를 전송하고자 할때.
• 송신 측은 수신 측에게서 받은 윈도우 크기와 네트워크 상황을 고려하여 Window Size를 측정한다.
• 3으로 잡은 경우, 우선 윈도우 3 내에 있는 0, 1, 2의 데이터를 전송한다.
• 수신 측에서 데이터를 받아 자신의 처리 속도대로 처리한 후, 응답으로 남아있는 버퍼 크기를 송신한다. 예를들어 하나 처리하여 남아있는 공간이 하나 생겼을 경우, Windoe Size: 1을 전송.
• 해당 ACK를 받은 송신 측은 수신 측이 데이터 하나를 처리했으며 1 만큼 더 받을 수 있음을 알고, 윈도우를 옆으로 Sliding하듯 움직여, 윈도우 3 내의 값을 1, 2, 3으로 바꾼다.
• 송신 측은 자신의 윈도우 내에 새로 들어온 3번 데이터를 수신 측에 전송한다.

즉, 슬라이딩 윈도우란 Window Size 만큼 데이터를 전송하고, 응답 받고, 응답받은 Window 크기 만큼 윈도우를 밀고, 윈도우 내의 데이터를 전송하고의 반복이다.

송신 측에서 일정 시간 동안 ACK를 받지 못하면 패킷을 재전송 하게 되는데, 만약 재전송했는데 패킷이 소실된 경우가 아니라 수신 측의 버퍼에 남은 공간이 없는 경우라면 문제가 발생한다. 이를 해결하기 위해 송신 측은 ACK을 보내며 남은 Window Size도 함께 보낸다.

하나씩 전송하고 응답받는 Stop & Wait보다는 훨씬 빠르며, 윈도우 크기를 송수신 측 간에 유연하게 조절할 수 있으므로 TCP의 기본적인 흐름 제어 기법으로 사용되고 있다.

혼잡 제어

네트워크 내의 패킷 수가 증가하면 오버플로우가 발생하는 등 장애가 발생할 수 있다. 송신 측의 전송 속도를 조절하여 이를 방지하는 것을 혼잡 제어라고 한다.

AIMD

Additive Increse/Multicative Decrease 즉, 합 증가/곱 감소라는 뜻이다.

처음에는 패킷을 하나씩 보내며 문제 없이 도착한다면 윈도우 크기를 1씩 증가시켜가며, 즉 합 증가 방식으로 전송한다. 만약 전송 실패하는 시점이 온다면, 윈도우 크기를 절반으로 줄인다. 즉, 곱 감소시킨다.

처음에 윈도우 크기를 너무 조금씩 늘리기 때문에 제대로 네트워크의 대역폭을 활용하여 전송하기까지의 시간이 오래 걸린다는 단점이 있다.

Slow Start

느리게 증가하는 AIMD 방식을 보완하였다.

Slow Start는 Window Size를 1, 2, 4, 8... 과 같이 지수적으로 증가시키다가 혼잡이 감지되면 윈도우 크기를 1로 줄인다.

처음에는 Window Size가 천천히 증가하지만, 시간이 갈수록 빠르게 증가하게 된다.

Fast Retransmit

TCP는 일반적으로 받은 데이터 중 연속되는 패킷의 마지막 번호 이후를 ACK 패킷에 실어 보낸다. 따라서 0, 1, 2(소실), 3, 4를 보내더라도 수신 측은 ACK 2를 중복하여 보내게 된다. 이때 timeout 발생 전이라도 송신 측은 손실된 것으로 보이는 2번 패킷을 재전송한다.

송신 측이 3번 이상 중복된 ACK를 보내는 3-ACK Duplicated가 발생하면 혼잡한 상황이라고 판단하고 Window Size를 줄이는 것이 Fast Retransmit이다.

Fast Recovery

혼잡한 상태가 되면, Window Size를 1로 줄이는 것이 아니라 절반으로 줄이고 선형 증가시키는 방법이다. 즉, 혼잡을 겪은 후, AIMD 방식으로 교체되는 것이다.

혼잡 제어 정책

위 혼잡 제어 기법들을 조합하여 실제로 어떤 상황에 어떤 기법을 사용해 혼잡을 제어할지 정의한 것이다.

혼잡 제어 정책들은 혼잡이 발생하면 윈도우 크기를 줄이거나, 증가시키지 않으며 혼잡을 회피한다는 공통 전제가 있다.

Tahoe와 Reno 둘 다 처음에는 Slow Start 방식을 사용하다가 혼잡이 감지되었을때에는 AIMD 방식으로 전환하는 방법이다.

Taboe : 처음에는 Slow Start로 Window Size를 지수적으로 증가시키다가 임계치에 도달하면 이후부터는 AIMD를 사용하여 선형적으로 Window Size를 증가시킨다. 3 ACK Duplicated나 Timeout 발생 시, 혼잡으로 판단하여 임계치와 Window Size를 1로 줄이도록 조정한다.

Reno : 처음에는 Slow Start로 시작하여 임계점을 도달하면 이후부터는 AIMD를 사용한다. 3 ACK Duplicate 발생 시, Window Size를 1이 아니라 AIMD처럼 절반으로 줄이고, 임계치를 줄어든 Window 값으로 정한다. (Fast Recovery) Timeout에 의해 데이터 손실 시, Window Size를 바로 1로 줄이고 Slow Start 한다.

오류 제어

TCP에서는 통신 중에 오류가 발생하면 해당 데이터를 재전송하는 재전송 기반 오류 제어 ARQ를 제공한다.

기본적으로 송신 측이 ACK를 받지 못하거나, 중복된 ACK를 받거나, NACK를 받았을 때 오류가 발생했음을 알게 된다.

Stop & Wait

흐름 제어의 맥락에서도 쓰이지만, 오류 제어의 맥락에서도 사용된다.

ACK를 받고 나서 다음 데이터를 보내는 방식이므로, 일정 시간이 지나 ACK이 돌아오지 않은 채 timeout이 발생하면 이전 데이터를 재전송한다.

Go Back N

연속적으로 데이터를 전송하다가, 오류가 발생하면 해당 지점부터 재전송한다.

예를들어 1, 2, 3, 4, 5를 전송했는데 3번에서 오류가 발생한다면 3번 이후의 모든 데이터를 삭제하고 3번부터 재전송을 요청한다. 따라서 이후의 성공적으로 전송한 데이터까지 모두 재전송하기 때문에 비효율적이다.

Selective Repeat

오류가 발생한 데이터만 재전송하는 방식이다.

단점은 버퍼의 데이터가 순차적이지 않기 때문에 정렬 과정이 추가로 필요하고, 별도의 버퍼가 필요하다는 것이다.

Q. TCP/IP에서 흐름 제어 기법이 왜 사용되는지? A. 송수신 측의 TCP 버퍼 크기 차이로 인해 데이터 손실, 재전송 등의 데이터 처리 속도 차이 문제가 발생하는 것을 막기 위해서다.

Q. TCP/IP 흐름 제어 기법은 무엇이 있는지? A. Stop & Wait와 Sliding Window 기법이 있다. Stop & Wait는 전송한 패킷에 대한 ACK를 받아야만 다음 패킷을 전송하는 기법이다. Sliding Window는 수신 측에서 설정한 윈도우 크기 만큼 송신 측에서 ACK 없이도 전송할 수 있게 하며, 데이터 전송 흐름을 동적으로 조절하는 기법이다.

Q. TCP/IP 혼잡 제어 기법이 왜 사용되는지? A. 송신 측에서 보내는 데이터 양이 중간 기기에서 처리 가능한 양을 초과하면 데이터가 처리되지 못해 송신 측에서 손실로 인식하게 되므로, 송신 측은 계속 재전송하여 네트워크를 혼잡하게 만들 수 있다. 이를 방지하기 위해 네트워크의 혼잡도에 맞춰 송신 측의 전송 속도를 적절히 조절하는 것이다.

TCP Socket State는 TCP 연결의 생명주기에서 각 TCP 종단점이 현재 어떤 단계에 있는지를 나타낸다.

TCP 연결은 크게 연결 설정, 데이터 전송, 연결 해제의 단계로 분류되며, 이벤트와 패킷 송수신에 따라 각 종단점의 상태 전이가 일어난다.

리눅스에서는 netstat 또는 ss 명령어로 소켓의 상태를 출력할 수 있다.

외워야 될...까?

• ESTABLISHED : TCP 연결이 성립된 상태. 양방향 데이터 송수신이 가능한 데이터 전송 상태.
• SYN_SENT : 로컬에서 SYN을 보낸 후, 상대방의 SYN 또는 SYN + ACK를 기다리는 상태.
• SYN_RECV : 상대방의 SYN을 받고 SYN, ACK를 보낸 뒤, 최종 ACK를 기다리는 상태.
• FIN_WAIT1 : 로컬 FIN을 보낸 뒤, ACK 또는 상대 FIN을 기다리는 상태.
• FIN_WAIT2 : 로컬 FIN에 대한 ACK를 받고, 상대 FIN을 기다리는 상태.
• TIME_WAIT : closed 이후 socket이 여전히 네트워크에 남아있는 패킷을 처리하기 위해 대기하는 상태. 일정시간 지난 후, CLOSED로 변하는 상태.
• CLOSED : socket이 사용 중이지 않은 상태. (TCP 연결이 존재하지 않는 상태)
• CLOSE_WAIT : 상대 FIN을 받고 ACK하였으며, 로컬 애플리케이션이 close하기를 기다리는 상태.
• LAST_ACK : 로컬도 FIN을 보냈고, 그 FIN에 대한 최종 ACK를 기대리는 상태.
• LISTEN : socket이 연결 요청을 기다리는 상태.
• CLOSING : 양쪽 모두 socket이 닫혔지만(거의 동시에 FIN 송신), 로컬 FIN이 아직 ACK 되지 않은 상태에서 상대방의 FIN도 받은 상태.
• UNKNOWN : socket의 상태를 알 수 없는 상태. (표준 아님)

연결 설정 (3-way handshake) 시 소켓 상태

(클라이언트 상태 - <패킷 송신> - 서버 상태 : 설명)

() - - - (LISTEN) : Server가 해당 소켓에 대해 연결을 기다리고 있는 상태. (SYN-SENT) -> SYN -> (SYN-RECV) : client에서 SYN 신호를 보내 Server에서 SYN 신호를 받음. (ESTABLISHED) <- SYN, ACK <- (SYN-RECV) : server에서 ACK 신호를 client에 보냄. (ESTABLISHED) -> ACK -> (ESTABLISHED) : client에서 ACK 신호를 server에 보냄. 이후부터 상호간에 데이터 송수신.

데이터 송수신

연결 완료 후, 양측이 ESTABLISHED된 상태에서 데이터를 송수신 받는다. ^^b

연결 종료 (4-way handshake) 시 소켓 상태

(여기서의 클라이언트는 먼저 소켓을 close 요청한 쪽으로 전제한다. 통신에서는 client쪽에서든 server쪽에서든 종료를 요청할 수 있다.)

(FIN-WAIT-1) -> FIN, ACK -> (CLOSE-WAIT) : socket이 종료를 요청 중인 상태. server의 응답은 받을 수 있음. (FIN-WAIT-2) <- ACK <- (CLOSE-WAIT) : server에서 ACK을 보내 client가 받은 상태. (TIME-WAIT) <- FIN, ACK <- (LAST-ACK) : server에서 ACK 신호를 client에 보냄. (TIME-WAIT) -> ACK -> (CLOSED) : client에서 종료 ACK를 보냄. (CLOSED) : 연결 종료.

셋 모두 네트워크 통신의 대상을 식별하거나 연결을 표현하는 개념이다.

IP 주소 : 어느 기기의 어느 NIC인지?
Port 번호 : 어느 네트워크 서비스인지?
Socket : 운영체제가 실제 네트워크 통신을 처리하기 위해 만든 통신 객체.

IP 주소

네트워크에서 호스트까지, 또는 NIC을 식별하기 위한 주소. 하나의 기기에 여러 개의 IP 주소를 가질 수도 있다.

패킷의 목적지 IP를 보고 라우터가 어디로 전송할지 결정한다.

Port 번호

한 호스트 안에서 어느 애플리케이션/서비스를 대상으로 하는지 구분하는 번호.

IP만 있으면 어느 컴퓨터로 접근해야 하는지는 찾을 수 있지만, 그 컴퓨터의 어느 프로그램에 데이터를 전달해야 하는지 알 수 없다. 따라서 어떤 서비스에 전달해야하는지를 Port 번호를 이용해 찾을 수 있다.

Socket

애플리케이션이 운영체제의 네트워크 기능을 사용하기 위한 통신 종단점 객체.

프로그램은 패킷을 직접 LAN카드에 쓰는 것이 아니라 일반적으로 소켓 API를 이용한다. 소켓은 운영체제 내부에서 통신 상태와 버퍼 등을 관리하는 실제 객체다. 프로세스는 이러한 소켓을 통해 네트워크로 메시지를 주고 받는다. 하나의 프로세스는 같은 Protocol, 같은 IP, 같은 Port 번호를 갖는 여러 개의 소켓을 가질 수 있다.

소켓에는 IP 주소, 전송 프로토콜, 로컬 IP/Port, 원격 IP/Port, 연결 상태, 송수신 버퍼 등의 정보가 연결된다. 출발지 IP/Port, 목적지 IP/Port, 전송 프로토콜을 5-tuple이라고 하며, 이것을 통해 서로 다른 TCP 연결임을 구분할 수 있다.

IP + Port는 소켓 주소이며, Socket은 그 주소와 프로토콜, 상태, 버퍼 등을 가진 운영체제 통신 객체다.

Socket State라는 상태 흐름도 있는데...더보기

Domain Name System은 도메인(호스트) 이름을 IP 주소로 변환하는 네트워크 시스템이다. 그 외에도 도메인 이름에 연결된 메일 서버, 네임서버 등의 정보를 저장하고 조회할 수 있도록 구성된 분산형 계층적 시스템이다.

일반적으로 우리가 웹페이지에 접근할 때에는 기억하고 쓰기 편한 test.com 등의 도메인 이름을 입력하여 접근한다. 그러나 실제로 인터넷 상에서 서버를 찾아가기 위해서는 IP 주소가 필요하다. 이때, DNS는 도메인 이름을 IP 주소로 변환한다.

여러 개의 DNS 서버로 구성 된 분산 시스템이다. 통신에 일반적으로 UDP 53번 포트를 사용한다. 512Byte를 초과할 시, DNS Header Flags에서 Truncated를 세팅하고 TCP 53번 포트를 사용한다.

DNS 서버 요소

일반적인 웹페이지 도메인 이름의 DNS 변환 과정을 살펴보기 위해 관련된 서버들을 알아두어야 한다.

Recursive DNS Resolver
: 웹 브라우저 등의 애플리케이션을 통해 클라이언트로부터 최초로 쿼리를 받는 서버. 클라이언트의 DNS 쿼리를 처리하기 위해(IP 주소를 알아내기 위해) 재귀적으로 DNS 쿼리를 진행한다.

Root DNS Server
: 호스트 이름을 IP 주소로 변환할 때 처음으로 거치게 되는 루트 서버다. 다음 네임 서버(TLD DNS Server)의 IP 주소를 제공한다.

TLD DNS Server
: TLD(최상위 도메인) 서버로, 호스트 이름 마지막 부분을 호스팅한다. 즉, test.com에서 .com에 해당하는 최상위 도메인 영역을 관리하며, 해당 TLD 아래에 위임된 네임 서버(전체 도메인 네임을 지닌 DNS Server)의 IP 주소를 제공한다.

(Authoritative) DNS Server
: 재귀적인 서버 쿼리의 종착점이다. 해당 이름이 속한 DNS Zone에 대해 권한이 있다면, 요청한 호스트 이름의 IP 주소를 최초 요청자인 Recursive DNS로 보낸다. test.com DNS 서버일 경우, own.test.com처럼 test.com의 서브 도메인들에 대한 IP 주소도 모두 관리한다. 다만 일부 서브 도메인이 별도의 Zone으로 위임된 경우에는 직접 관리하지 않는다.

하나의 DNS 서버가 모든 정보를 갖고 있는 것이 아니라, 여러 DNS 서버들이 계층적인 구조를 형성한다.

DNS Record

DNS는 주요 도메인 네임/IP 외에도 여러 레코드 유형을 사용하여 매핑 및 확인을 제공한다. DNS 영역 내의 특정 도메인에 대한 매핑 및 정보를 포함하는 파일을 DNS Zone File이라고 한다.

DNS Zone File에는 도메인 이름에 대한 IP 주소 매핑 정보가 담긴 DNS 레코드들이 저장된다. DNS 레코드는 (Name, Value, Type, TTL) 형식으로 구성된다. (ex. Name: test.com, Value: 10.10.10.10, Type: A, TTL: 14400)

일반적으로 DNS Zone에는 N, SOA 레코드가 필요하다.

- NS : 이름 서버 레코드. 도메인에 대한 권한 있는 이름 서버를 나타낸다.
- SOA : 권한 시작 레코드. 해당 DNS 영역의 주요 권한 이름 서버 명시.

그 이외에 여러 다른 유형의 레코드들이 포함된다.

- A : IPv4 주소.
- AAAA : IPv6 주소.
- MX : 메일 교환기 레코드. 도메인에 대한 SMTP 이메일 서버를 지정.
- CNAME : 표준 이름 레코드. 별칭 호스트 이름을 다른 도메인(정규 도메인)으로 매핑. 예를들어 own.test.com에 대한 IP 주소를 쿼리하는 경우, 먼저 own.test.com 도메인에 대한 CNAME 레코드를 확인하고, own.test.com이 test.com에 대한 alias임을 확인하였으니, test.com 도메인에 대한 DNS 쿼리를 요청하여 IP 주소를 반환한다.
- PTR : 포인터 레코드. 역방향 DNS Zone에서 IP 주소에 대응하는 도메인 이름을 지정.
- TXT : 텍스트 레코드. 메모 및 이메일 인증을 위한 발신자 정책 프레임워크 같은 자동화된 처리에 사용.

DNS 동작

1. 사용자가 웹 브라우저에 test.com을 입력한다.
2. 웹 브라우저의 DNS 캐시, Hosts 파일과 OS DNS 캐시를 확인한다. 유효한 캐시가 있다면 해당 IP를 사용하여 접근.
3. 브라우저에 설정된 Recursive DNS Resolver로 DNS 쿼리를 전송한다. (질의 과정 시작)
   1. DNS Resolver에서 질의 받은 도메인에 대해 캐싱하고 있다면 바로 IP 주소를 반환한다.
4. Recursive DNS Resolver는 Root DNS Server(.)에 test.com에 대해 질의한다.
5. Root DNS Server는 도메인에 대한 정보를 저장하는 TLD(최상위 도메인) DNS Server(.com)의 IP 주소를 반환한다.
6. Recursive DNS Resolver는 TLD DNS Server(.com)에 test.com에 대해 질의한다.
7. TLD DNS Server(.com)는 test.com에 대한 DNS Server의 IP 주소를 반환한다.
8. Recursive DNS Resolver가 test.com의 DNS Server에 test.com에 대해 질의한다.
9. test.com DNS Server는 IP 주소를 반환한다.
10. Recursive DNS Resolver가 결과를 캐싱하고 처음 요청한 도메인의 IP 주소로 웹 브라우저에 응답한다.
11. (DNS 조회 완료)
12. 사용자의 웹 브라우저가 회신받은 IP 주소로 TCP 연결 수립 및 HTTP 요청을 전송한다.

Q. 사용자가 웹페이지 접근 시, 무조건 DNS 쿼리가 진행되는지?
A. ㄴㄴ 웹에 접근할때마다 매번 DNS 질의 과정이 수행되면 성능이 떨어지거나 네트워크 부하가 발생할 수 있다. DNS 캐싱, hosts 파일을 이용하여 이를 방지한다.
일반적으로 웹 브라우저에서는 일정 시간 동안 DNS 레코드를 캐시하도록 한다.
이러한 DNS 캐싱이 되어있다면 재귀적인 DNS 쿼리를 요청하지 않고 바로 IP 주소를 확인하여 통신이 가능한다.
Recursive DNS Resolver에서도 일정 시간 동안 DNS 레코드를 캐싱하므로, 자주 질의되는 도메인 이름에 대해서는 바로 IP를 받아올 수 있다.

Q. DNS 서버들은 인터넷 어디서든 사용할 수 있는 공용인지?
A. Public DNS들은 ISP 또는 각 도메인 측에서 관리하며 인터넷에서 누구나 접근 가능하다.
Private DNS들은 기업 네트워크나 Virtual Private Clooud 같은 폐쇄된 내부 네트워크 내부 사용자들만 조회 가능하다. 이러한 Private DNS들은 내부 URL과 IP 주소를 외부에서 숨기며, 내부 사용자들에게만 DNS 서비스를 제공한다.
Public DNS와 Pricate DNS가 결합된 방식인 Split-Horizon DNS가 일반적인 기업 환경에서 사용된다. 이 구성에서는 동일한 도메인 이름에 대해 질의자의 네트워크 상 위치에 따라 서로 다른 DNS 응답을 제공한다. 내부에서는 사설 IP를 반환하고, 외부에서는 공인 IP를 반환하는 형태로 주로 구성된다.

DNS 보안 취약점

DNS Spoofing : 일반적으로 DNS Server에 캐시 포이즈닝을 이용하는 공격 방식. 공격자는 Recursive DNS Resolver의 캐시에 악의적으로 다른 주소 레코드를 삽입하여 Resolver가 도메인 질의에 대해 위조된 IP 주소를 반환하게 한다. 사용자가 해당 IP 주소로 접근하게 되면 악성 사이트로 리다이렉션 시킬 수 있다. 정상 응답보다 공격자가 더 빠르게 DNS 응답을 보내는 형식의 Sniffing 기반 DNS Spoofing도 있다.

DNS Amplification 공격 : 공격자가 출발지 IP를 특정 사용자 IP 주소로 위조하여 DNS 서버에 쿼리를 보내는 형식의 DDoS 공격. DNS 서버는 대량의 응답을 사용자 IP 주소로 전송하게 된다. 비연결적이며 출발지 IP 위조가 가능한 UDP 기반의 DNS 질의의 특성을 악용한다. 작은 쿼리로도 대량의 트래픽으로 증폭되어 사용자에게 전달되는 점을 이용하여 리소스 과부하를 일으킨다.

Keep-Alive 용어는 HTTP, TCP 연결에서 사용되지만, 둘은 목적과 동작 계층이 다르므로 구분해야 한다.

HTTP Keep-Alive : 하나의 전송 연결을 여러 HTTP 요청/응답에 대해 재사용하기 위한 것.

TCP Keep-Alive : 오랜 시간 유휴 상태인 TCP 연결에서 상대방이 여전히 살아있는지 확인하기 위한 것.

HTTP Keep-Alive

Connection을 유지하기 위한 수단으로, 하나의 TCP 연결을 재사용하여 여러 개의 HTTP 요청을 처리한다.

HTTP Reseponse header 중 하나로, 대략 아래와 같은 형태로 전송된다.

HTTP/1.1 200 OK
Server: Apache
Connection: Keep-Alive
Keep-Alive: timeout=5, max=1000
...

기본적으로 HTTP는 TCP 기반으로 동작하기 때문에, 하나의 TCP 연결에서 하나의 요청과 응답을 처리한 뒤 연결을 종료하는 비지속 연결 형태다. (HTTP/1.0 시절) 이렇게 매번 요청을 할 때마다 새로운 연결을 설정하고 끊는다면 자원 낭비가 심하다. 그래서 Keep-Alive를 보내 말그대로 그대여... 그 뭐냐 살아라... 하면서 연결을 계속 유지하라고 요청한다. 한마디로 하나의 TCP Connection을 활용하여 여러 개의 HTTP 요청/응답을 주고받을 수 있게 한다.

아마 I want style.css 즈음에서 client 답답해뒤져있음

timeout과 max를 지정하여 최소 timeout 시간 동안 최대 max개의 request 수를 연결 가능함을 알린다. 즉, 위의 경우에는 5초 동안 서버가 유휴 상태면 서버가 연결을 종료할 수 있으며, 하나의 연결에서 최대 1000개의 요청을 처리할 수 있다는 뜻이다.

위 옵션은 HTTP/1.0에서는 직접 지정해야 동작했지만, HTT로 동작한다. 야호! (근데 쓸 수는 있고 포함하여 응답하는 곳들이 많다) 반대로 Connection: Close를 헤더에 포함하여 전달하면 명시적으로 종료할 수 있다. HTTP/1.1에서는 Connection: Close 헤더가 없다면 서버가 응답 후에 해당 연결을 계속 재사용할 수 있다고 가정한다.

Q. 그럼 닫는다고 안 보내면 평생 열려있나요?
A. 겠냐?
서버나 프록시에 설정되어있는 timeout에 걸리거나, 최대 요청 수 초과, 자원 부족 등으로 연결을 닫을 수 있다.

Q. 왜 필요한가요? 
A. 연결 재사용으로 인해 3-way-handshake를 매번 다시 맺지 않으므로 오버헤드 감소 및 지연 시간 감소. 즉, 성능 향상.

Q. 무족권 좋은 거네요?? 단점은 없는지?
A. Keep-Alive에 의해 너무 많은 연결을 유지하게 되면 서버의 리소스 사용량이 증가할 수 있다. 따라서 timeout 값을 적절히 제한해줘야 한다.

TCP Keep-Alive

TCP 연결이 맺어진 이후, 서버와 클라이언트 간에 Keep-Alive Packet을 통해 지속적으로 연결이 되어있는지 확인한다.

OS에 의해 관리되며, 리눅스 기준 설정 옵션은 아래와 같다.

tcp_keepalive_time=120 : 최초 keep-alive를 보내는 시간
tcp_keepalive_probes=3 : 응답이 없으면 추가로 보내는 횟수
tcp_keepalive_intvl=10 : 추가로 보낼 때의 간격

위 설정에 따르면 120초 동안 연결이 유휴 상태인 경우, 10초 간격으로 3번의 Keep-Alive 패킷을 전송한다. 3회가 끝날 때까지 정상적으로 주고받지 못했다면 Connection을 종료한다.

Q. 왜 필요한가요?
A. 네트워크 문제나 상대의 비정상 종료를 감지할 수 있다. 또한, 방화벽이나 NAT 등 장비들은 유휴 연결을 자동으로 닫기 때문에 연결 확인 및 유지가 필요하다.

TCP

전송 계층에서 연결형 서비스 제공하는 통신 프로토콜로, 가상 회선 방식 제공.

흐름제어, 혼잡제어, 재전송 등을 제공한다. 전송이 양방향으로 동시에 발생하는 전이중 통신 방식이다. 2개의 종단점으로 구성된 점대점 방식이다.

TCP 헤더

구조 정도는 외워두자. 라떼는 교수님이 종이에 이거 그리는 걸 시험 문제로 냈다.

• Source Port, Destination Port : 출발지 포트와 목적지 포트
• Sequence Number : 순차 번호. 전송 바이트 수 기준으로 증가한다.
• Acknowledgment Number : 응답 번호. 받은 패킷에 대해 SEQ Num으로 응답하여 해당 패킷을 받았음을 알린다.
• Header Length : TCP 헤더 길이. TCP 헤더가 끝나는 지점, 즉 데이터 시작 위치를 표시한다.
• Resv : 예약 필드. 나중에 사용하기 위한 필드이며 0으로 채워둔다.
• 제어 비트 : 각각의 비트가 1로 세팅되었는지의 여부로 의미를 나타낸다.
  • SYN : 세션 성립 시 연결 설정 요청. (3-way handshake) 양단의 최초 패킷에만 설정.
  • ACK : 응답 번호 필드가 유효한지 설정할때 사용. 패킷 받았다는 것을 알림.
  • PSH : 버퍼링 된 데이터를 상위 계층에 즉시 전달.
  • RST : 연결 리셋.
  • URG : 긴급 포인터 필드 유효 여부.
  • FIN : 세션 연결을 종료시킬 때 사용.
• Window Size : 수신 윈도우 버퍼 크기 지정. 0이면 전송 중지.
• Checksum : TCP 세그먼트에 포함되는 프로토콜 헤더와 데이터에 대한 오류 검출 용도.
• Urgent Pointer : 긴급 데이터를 처리하기 위한 포인터. URG 플래그 세팅 시에 유효.

흐름 제어

데이터 처리 속도(양)을 조절하여 버퍼 오버플로우를 방지한다. Window Size를 이용하여 데이터 수신량을 교섭.

• Sliding Window : 수신자의 버퍼에 남은 공간 만큼 데이터를 전송 받는 방식.

혼잡 제어

네트워크 내의 패킷 수가 넘쳐나 혼잡해지는 것을 방지한다.

재전송

수신 측에서 받지 못하면 재전송하여 신뢰성은 높인다.

• Triple-Duplicate-ACK-based-retransmission : 송신 측에서 여러 개의 세그먼트를 전송했는데, 순서가 틀렸을 경우, 다시 보내달라는 의미의 ACK를 보냄. 송신 측에서 동일한 ACK를 3개 이상 받았을 경우, 해당 패킷은 손실되었다고 판단하여 재전송 요청.

• Timeout-based retransmission : 일정 시간 동안 수신자로부터 ACK를 받지 못하면 손실되었다고 판단하여 재전송 요청.

UDP

전송 계층에서 비연결형 서비스 제공하는 통신 프로토콜로, 데이터그램 형식. 비연결형이라서 신뢰성이 없지만, 빠른 속도로 전송이 가능하다.

UDP 헤더

출발지 Port, 목적지 Port, 데이터 길이, 체크썸 끝~

TCP / UDP 공통점

전송 계층에서의 데이터 전송을 담당하는 프로토콜이다. Port 번호를 이용해 주소를 지정하며, 데이터 오류 검사를 위해 체크섬을 포함한다.

TCP / UDP 차이점

TCP는 Handshake를 통해 연결을 성립시킨 후 통신한다. 반면 UDP는 연결 없이 통신하는 비연결형이다.

TCP는 Byte Stream(Segment) 형태로 전송하여 데이터의 경계를 구분하지 않음. 반면 UDP는 데이터그램 형식으로 데이터의 경계를 구분한다.

TCP는 재전송이 존재하여 신뢰성 있는 데이터 전송이 가능하다. 반면 UDP는 재전송이 없어 신뢰성이 없다.

음? 그러면 TCP가 좋은 거 아님? UDP 그거 왜 씀?

TCP는 연결할 때 3-way handshake가 이루어져 시간 지연이 발생한다. 텍스트, 파일 등은 신뢰성이 필요하지만 사진, 영상 등은 데이터 일부가 누락되어도 문제가 발생하지 않기 때문에 단순하게 전송 속도가 빠른 UDP를 사용해도 좋다.

실제 사용 예

TCP : 대부분의 웹사이트 연결, 이메일, 파일 전송 등 UDP : 영상, 온라인 게임, DNS 등

보안 취약점

TCP의 보안 취약점

TCP는 안전하다며? 꼭 그렇지는 않음.

TCP가 제공하는 연결 지향, 순서 보장, 재전송 등의 특성이 공격에 이용 되기도 한다.

SYN Flooding : SYN을 대량으로 전송하는 방식의 공격. Server는 Handshake 연결 과정의 SYN을 받는 순간 TCP Connection 연결 정보를 메모리에 생성. 그러나 ACK이 오지 않으면 Half Open Connection 상태가 되어 SYN을 받는대로 Connection을 계속 생성하다가 SYN Queue가 가득 찬다. 정상 사용자가 SYN을 보내도 접속하지 못하는 상태가 된다. 미라이 봇넷 등 여러 사레에서 DDoS 공격의 일종으로 사용 됨. 유사한 ACK Flooding 등도 있다.

TCP Sequence Number Prediction : TCP는 시퀀스 넘버로 패킷 순서를 관리. 공격자가 다음 번호를 예측하여 가짜 패킷을 위조해 전송할 수 있다. 시퀀스 넘버를 알맞게 예측하여 전송에 성공할 시, 서버는 공격자를 정상 사용자로 오인하게 만들 수 있다. 이는 악의적인 데이터 주입, 기존 연결 종료 및 TCP 세션 하이재킹으로 이어질 수 있다. 현재는 랜덤성이 강해져서 괜찮긴 한데...

UDP의 보안 취약점

UDP는 그냥 존재만으로도 위험하다. (연결 상태가 없어 발생 불가능한 SYN/ACK Flood 및 세션 하이재킹 제외 모든 취약점 존재)

UDP Reflection Attack : UDP는 기본적으로 연결을 하지 않으며, 응답할때 데이터그램을 보낸 IP주소로 되돌려 보낸다. 이때 데이터그램을 보낸 최초 송신자가 악의적으로 출발지 IP를 위조하여 전송할 시, server는 위조된 IP로 응답을 보낸다. 위조된 출발지 IP를 담은 데이터그램을 여러 server에 보내면 피해자(위조된 IP 보유자) 쪽으로 UDP 응답이 대량으로 되돌아와 리소스를 소모시킬 수 있다. 이외에도 이러한 'IP Spoofing + 반사 기법'을 다양한 프로토콜로 활용한 DNS Reflection, NTP Reflection 등이 있다.

사용자에게 애플리케이션 서비스를 제공.

주요 프로토콜 : SMTP, POP, FTP, HTTP, DNS

SMTP

전자 메일 전송 프로토콜.

메일 서버로쿠터 다른 곳으로 이메일을 보내는 프로토콜.

POP

수신된 메일을 다운로드 받기 위한 프로토콜

일반적으로 메일 환경은 특정 서버에 메일 주소를 개설하고, 서버에 수신된 메일을 PC나 폰으로 다운로드. SMTP와는 별도로 서버와 PC/폰을 연동하기 위한 프로토콜.

FTP

서버와 클라이언트 간의 파일 전송 프로토콜.

HTTP

웹 서버와 웹 브라우저 간의 데이터 전송을 위한 프로토콜

클라이언트는 HTTP requeset를 보내고, 서버에서는 HTTP response를 반환.

DNS

문자 형식인 URL 주소 표현을 IP 주소로 변환하는 프로토콜.

응용 프로세스 사이에 전송되는 데이터의 의미와 표현 방법 처리.

주요 프로토콜 : JPEG, ASCII

데이터 표현

서로 다른 표현 방식을 사용하는 시스템 간의 통신을 위해 형식 변환.

각 컴퓨터는 각기 다른 추상 문법을 갖고 있기 때문에 데이터 전송 시에는 네트워크 전체에 일관적으로 표현되는 전송 문법으로 변환하여 전송해야 함.

- 추상 문법 : 각 컴퓨터에서 사용하는 데이터 표현 규칙.
- 전송 문법 : 네트워크 전체에서 일관성을 지니는 데이터 표현 규칙.

암호화

데이터 보안을 위한 암호화 및 복호화.

데이터 압축

전송을 보다 효율적으로 하기 위해 데이터를 압축/해제.

- 비손실 압축 : 압축 과정에서 기존의 데이터의 내용이 유실되지 않고 동일.
- 손실 압축 : 압축 해제한 데이터 중 일부가 소실 됨. 압축 효율이 높음.

양 끝단 응용 프로세스들의 연결을 위해 세션을 설정, 유지, 종료

논리적인 연결 서비스인 세션을 제공.

주요 프로세스 : NetBIOS, SSL/TLS

데이터 단위 : Data, Message

세션

네트워크 상에서 양 끝단 간의 논리적 연결.

사용자가 접근한 시점에서부터 종료하여 연결을 끝내는 시점까지 들어오는 일련의 요구를 하나의 상태로 보고 그 상태를 일정하게 유지시키는 것.

다중 세션 연결 : 서버 프로세스가 다수의 클라이언트 프로세스에 동시에 여러 세션 연결 가능. 서비스 시간이 짧을 수록 유리. 서비스 이용 시간이 길어지면 세션 연결이 길게 유지되므로 다른 클라이언트의 대기 시간이 증가.

단일 세션 연결 : 서버 프로세스가 하나의 클라이언트 프로세스만 지원. 대표 서버를 두어서 대표 서버가 클라이언트마다 하위 서버 프로세스를 생성하여 각각 연결되는 형태. 클라이언트의 요구마다 프로세스를 생성해야 하므로 초기 환경 구축에 따른 오버헤드가 증가.

토큰

두 프로세스의 대화를 관리하기 위한 특수 메시지인 토큰을 관리하여 상호배타적인 동작 제어.

데이터 토큰 : 데이터 전송 권리 제공. 해제 토큰 : 통신 양단 간의 연결 해제 과정을 제어하기 위해 사용. 동기 토큰 : 세션 연결을 사용하는 과정에서 동기 처리가 필요한 시점에 사용.

동기화

동기점을 추가하여 복구 지점을 설정하고 제어.

대화 : 데이터 전송 과정에서 시간 경과에 따라 동기점을 부여하여 단계적인 신뢰성을 보장.

NetBIOS

세션 계층 관련 서비스들을 제공하여 응용 프로그램들이 근거리 통신망을 통해 통신할 수 있게 해주는 프로토콜.

이름 서비스 : 16바이트의 문자/숫자의 조합으로 컴퓨터를 식별. 데이터그램 분배 서비스 : 브로드캐스트 지원 및 통신 오류의 발견, 회복. 세션 서비스 : 두 컴퓨터가 통신할 수 있는 연결을 성립시킴. 데이터그램보다 더 큰 메시지 처리 가능.

SSL/TLS

안전한 통신 보장을 위한 프로토콜. 클라이언트와 서버 간의 데이터를 암호화 하거나 인증함으로써 중요 데이터 보호.

송수신 프로세스가 연결되어 신뢰성 있는 데이터 교환을 제공.

TCP와 UDP를 이용하여 단대단 통신을 제공.

연결 제어 : 패킷 전달 전에 목적지 시스템의 전송 계층과 연결 설정. 흐름 제어 : 데이터링크 계층과 같은 흐름제어를 제공. But 종단 to 종단 제공. 오류 제어 : 종단에서 종단까지의 오류 제어 제공. 데이터 순서 제어, 재전송.

주요 프로토콜 : TCP, UDP

장비 : L4 로드밸런서

데이터 단위 : TCP Segment, UDP Datagram

혼잡 제어

TCP에서는 종단 간의 혼잡을 제어.

ACK 수신 여부로 네트워크 상황을 판단하여 송신 데이터의 크기를 조절해 혼잡 상황을 제어.

AIMD : 혼잡 발생 시 해결하는 방식. 조금씩 패킷을 보내는 양을 늘리다가 데이터가 loss 되었을 시, 보내는 packet의 양을 절반으로 줄임.

Slow Start : Loss가 발생하기 전까지 지수적으로 패킷 양을 늘림. 일정 수준 이상으로 올라가면 AIMD 방식으로 변경.

Congestion Avoidance : 혼잡 상황이 발생하기 쉬운 구간에서는 1mss 씩 중가.

Fast Retransmit : 세 번의 Duplicate ACK가 발생 시, Timeout을 기다리지 않고 전송 시작.

Fast Recovery : Fast Retransmit 후에 Slow Start가 아닌 Congestion Avoidance 상태에서 전송.

TCP

상호 간에 신뢰성 있고 연결지향적인 전송을 제공.

UDP

비연결적이고 신뢰성이 없지만, 빠른 데이터 전송을 제공.

Port 번호

프로세스 구분을 위한 번호.

MAC/IP가 목적지 호스트까지 찾아가는데 사용되는 논리적 주소였다면, Port 번호는 해당 host 내에서 데이터가 실제 도달해야하는 프로세스를 구분하는 데 사용.

16비트로 구성, 65536개의 포트 번호 존재. - Well-known Port : 서버 측에 용도 별로 예약 되어있는 포트 번호. 01023 - Registered Port : 특정 용도로 사용되기 위해 등록된 포트 번호. 102449151 - Dynamic Port : 자유롭게 사용이 가능한 동적 포트 번호. 49152~65535

데이터를 목적지까지 안전하고 빠르게 전달하는 기능인 라우팅을 담당

송신 호스트가 전송한 데이터가 어떤 경로를 통해 수신 호스트까지 전달되는지를 결정하는 라우팅 문제를 처리.

흐름 제어 : 송수신 호스트 사이의 논리적인 점대점 전송 속도를 다룸.

세그먼테이션 : 데이터 전송을 위해 패킷을 분할하는 것.

주요 프로토콜 : IP, ICMP, IGMP, ARP/RARP

장비 : 라우터, 공유기

데이터 단위 : 패킷

라우팅 프로토콜

네트워크 구성 형태에 대한 정보를 저장해둔 라우팅 테이블을 이용하여 목적지까지 최선의 패킷 경로를 선택하여 전송하는 것.

혼잡 제어

네트워크에 트래픽이 과도하게 증가하면 전송 속도가 떨어지는 혼잡 발생. 데이터 전송 경로 선택에 따라 네트워크 혼잡에 영향이 감. 흐름 제어보다 더 넓은 관점에서의 네트워크 전송 능력 문제를 다룸.

트래픽 성형 : 혼잡은 트래픽이 특정 시간에 집중되는 현상에서 기인하는 경우가 많음. 송신 호스트가 전송하는 패킷의 발생 빈도가 네트워크에서 예측할 수 있는 일정한 전송률로 이루어지게 하는 기능.

ECN 패킷 : 라우터가 트래픽의 양을 모니터링하여 출력 선로의 사용 정도가 한계치를 초과하면 주의 표시를 함. 주의 표시 한 방향의 경로는 혼잡 발생 가능성이 높으므로 특별 관리.

IP

네트워크 상에서 목적지 호스트를 식별하고 찾아가기 위한 논리적 주소와 프로토콜.

ICMP

IP의 비신뢰성을 보완. 오류 보고 및 제어.

IGMP

멀티캐스팅에 필요한 그룹 관리.

멀티캐스팅 : 특정 그룹에 속하는 모든 호스트에 메시지를 전송.

이때 멀티캐스팅에 필요한 그룹을 생성, 제거, 가입, 탈퇴 등 관리.

ARP / RARP

IP 주소를 MAC 주소로 변환하는 프로토콜. / MAC 주소를 IP 주소로 변환하는 프로토콜.

일대일로 연결된 호스트 사이의 신뢰성 있는 전송을 보장

신뢰성을 보장하기 위해 데이터의 흐름을 제어하고 오류를 검출. - 신뢰성 : 물리적 전송 사이에는 오류 발생이 가능한데, 이러한 오류를 방지/검출/복구한다.

데이터링크 계층에서의 신뢰성은 각 노드 간의 신뢰성을 의미한다. - 흐름 제어 : 송수신 측의 처리 속도 차이를 해결하기 위해 데이터의 송신 속도를 제어. - 오류 제어 : 오류가 발생하였는지 검증하고 소실된 프레임을 재전송.

LAN 환경에서는 네트워크 자원의 효율적인 활용을 위해 MAC 계층과 LLC 계층으로 구분. - MAC 계층 : 물리적 전송 선로의 특징과 매체 간의 연결 방식. - LLC 계층 : 데이터링크 계층의 기본 기능. 오류 제어, 재전송, 흐름 제어.

주요 프로토콜 : MAC, 이더넷

장비 : 스위치 허브, 브리지

데이터 단위 : 프레임

회선 제어

각각의 컴퓨터가 통신할 때, 신호 간의 충돌이 발생하지 않도록 제어.

ENQ/ACK 방식

한 쪽이 ENQ를 보내 연결 초기화 과정이 진행되면 다른 쪽에서는 응답으로 ACK 프레임을 보내 데이터를 받을 준비가 되었음을 알림. 데이터 전송 뒤에는 EOT 프레임을 보냄으로써 종료.

Polling 방식

선택 모드 : 주 스테이션이 데이터를 전송하고자 할 때 사용. 주 스테이션이 링크에 대한 제어 권한을 가짐.

Poll 모드 : 주 스테이션이 다수의 종속 스테이션에 보낼 데이터가 있는지의 여부를 확인하여 전송.

오류 제어

전송 도중에 오류나 손실이 발생하면 이를 탐지하고 수정.

오류 수정

전진 오류 수정 (FEC) : 송신 축이 프레임에 부가적인 데이터를 추가해 전송하고, 수신 측이 이 부가적 데이터로 오류 검출 및 수정. 오류 검출 시, 재전송 요청 없이 스스로 수정.

후진 오류 수정 (BEC) : 송신 측이 확장 비트를 추가해 전송하고, 수신 측이 이를 토대로 오류를 검출 시 송신 측에 재전송을 요청.

오류 검출

패리티 검사 : 1의 개수를 홀/짝수 개로 맞춰서 보낼지를 송수신 측이 교섭하고, 여분의 비트(패리티 비트)를 채워 보냄. But 홀수 개의 오류만 검출 가능하다는 한계점.

2차원 패리티 검사 : 위의 한계점을 보완하여 수직과 수평으로 패리티 비트를 추가하고 모두 계산. 수평/수직 상에 짝수 개의 오류가 발생해도 반대쪽에서 검출 가능. But 수평/수직으로 모두 짝수 개 씩 오류가 발생하면 검출 불가능하다는 한계점.

3차원 패리티 검사 : 효율성이 장난 아니게 떨어지는 지점이라 방식을 바꾼다

순환 중복 검사 (CRC) : 패리티 검사의 한계를 보완. 데이터에 오류가 발생했는지 확인하는 코드를 덧붙여 보냄.

체크섬 : 데이터의 길이와 관계없이 오류 검출. 데이터링크보다는 네트워크/트랜스포트 계층에서 헤더에 붙여 주로 사용. 전송할 데이터의 전체 합을 붙여 보냄.

해밍 코드 : 하나의 데이터 단위에 대해 많은 패리티 비트를 추가해 오류를 검출하고 수정 가능. 패리티를 계산하여 모든 패리티가 0이면 오류 없음, 값이 있다면 위치를 나타냄.

오류 검출 시 재전송 (Automatic Repeat Request)

Stop & Wait ARQ : 송신 측에서 한 번에 한 개의 프레임을 송신. 수신 측에서는 수신된 프레임의 오류 여부를 ACK 또는 NAK으로 응답. 송신 측에서는 ACK을 받으면 다음 프레임을 전송. NAK을 받거나 일정 시간 동안 응답이 없으면 해당 프레임을 재전송.

Go Back N ARQ : 송신 측이 프레임을 여러 개 한꺼번에 전송. 중간의 프레임에 문제가 있으면 수신 측은 NAK와 오류 프레임의 순서번호를 송신 측에 전송. 송신 측은 해당 오류 프레임부터 그 이후의 모든 프레임들을 다시 전송.

Selective Repeat ARQ : 오류 검출 이후의 프레임들을 전부 다시 보내야하는 Go Back N의 한계점 보완. 문제가 생긴 프레임에 대해서만 NAK 응답을 보내 손상된 프레임만 선별하여 재전송

흐름 제어

송수신 측의 처리 속도 차이를 해결하기 위해 데이터의 송신 속도를 제어.

Stop & Wait : 전송 측이 프레임을 전송한 후, 각 데이터 프레임에 대한 ACK를 기다렸다가 다음 프레임을 전송. 한 번에 하나만 전송하고 응답이 올 때까지 대기하므로 비효율적.

Sliding Window : 전송한 프레임에 대한 ACK 프레임을 수신하지 않아도 여러 개의 프레임을 연속적으로 전송하도록 허용. Window에 포함된 만큼의 프레임은 연속적으로 보내고, 정상 전송이 확인되면 다음 Window에 해당하는 만큼의 프레임을 보냄. Window : 송수신 양쪽에서 만들어진 버퍼의 크기. ACK를 받지 않아도 연속적으로 전송 가능한 프레임의 개수.

MAC Address

컴퓨터 간 데이터를 전송하기 위한 고유의 물리적 주소.

데이터링크 계층에서 통신을 위해 네트워크 인터페이스 카드에 할당된 고유의 번호. 컴퓨터 네트워크에서 각 기긱를 구분하기 위해 사용하는 물리적 주소.

48비트 길이의 16진수로 구성. 앞의 24비트는 랜 카드를 만든 제조사의 번호, 뒤의 24비트는 랜 카드에 붙인 일련번호.

이더넷

LAN에서 데이터를 주고 받기 위한 규칙.

데이터링크 계층의 대표적인 통신 프로토콜. 이더넷은 CSMA/CD를 이용하여 여러 컴퓨터가 동시에 전송해도 충돌이 발생하지 않는 구조.

CSMA/CD

반송파를 이용한 충돌 감지 및 재전송.

1. 전송 전에 먼저 현재의 네트워크에 흐르고 있는 데이터가 있는지 감지.
2. 이미 전송 중이라면 사용할 수 있을 때까지 대기, 사용할 수 있다면 데이터 전송 시작.
3. 동시에 전송되어 충돌이 발생하면, 최소 패킷 시간 동안 전송을 계속하여 다른 컴퓨터가 충돌을 감지할 수 있게 함.
4. 일정 시간 기다린 뒤에 다시 신호를 감지하고 네트워크를 사용할 수 있다면 다시 전송 시작.

토큰 버스

버스 형태 + 토큰 제어 방식. 물리적인 버스 구조로 연결되지만, 논리적인 프레임 전달은 링 구조.

토큰이라는 제어 프레임을 사용하여 프레임 전송을 위해서는 토큰 확보가 필요.

토큰 링

순환되는 링 형태의 LAN 구성. 토큰 제어 프레임이 한 쪽으로 순환. 토큰을 획득한 호스트만 데이터 전송 가능.

• 대기 모드 : 입력단으로 들어온 비트를 출력단으로 즉시 내보냄.
• 전송 모드 : 호스트가 토큰을 획득해 프레임을 전송할 수 있는 상태. 프레임이 올바르게 전송되었음을 확인, 토큰을 링에 반환.

실제 물리적 연결. 데이터 전송을 위한 기계적, 전기적 수단의 정의

0과 1로 이루어진 비트를 전기 신호로 변환하여 전송. 전송 속도와 전송 모드를 규정하고 물리적인 접속 형태를 규정.

장비 : UTP 케이블, 광 케이블, 동축 케이블, 허브, 리피터 등

• UTP 케이블 : 일반적으로 근거리 통신망에 사용. 실생활에서 사용하는 컴퓨터 랜선, 허브/스위치/라우터 등 대부분의 네트워크 장비를 연결하는 데 사용. 절연체로 감싸여있지 않은, 꼬여있는 2개의 선 케이블. (Unshielded Twisted Pair Cable) 데이터센터 가면 즉석에서 이빨로 선 찝는 체험이 가능하다

• 동축 케이블 : 동심원의 중심에 있는 구리선을 매체로 하는 케이블. 전화 선, 회선망에 사용.

• 광 케이블 : 광섬유를 통해 빛을 매체로 하는 케이블. 동축 케이블에 비해 간섭이 없고 손실이 적으며 빠른 속도로 전송 가능.

데이터 단위 : bit

서로 다른 네트워크 간의 통신을 위해 ISO 국제표준화기구에서 제안한 표준 개방형 시스템 상호연결 모델

네트워크에서 통신이 일어나는 과정을 7단계로 나눠서 설명. 통신이 일어나는 과정을 단계별로 파악하고 관리 가능. (계층 별 문제 해결이 용이)

But, 개념적인 모델에 불과. 실제 인터넷 통신은 TCP/IP 모델 구분에 가까움. - OSI 7계층 : 이론적인 참조 모델. - TCP/IP 4계층 : 실제 구현되어 사용되는 실용적인 모델. 아무튼 네트워크 동작 및 프로토콜에 대해 순서대로 공부하기에 좋다.

L1 : 물리 계층 L2 : 데이터링크 계층 L3 : 네트워크 계층 L4 : 전송 계층 L5 : 세션 계층 L6 : 표현 계층 L7 : 응용 계층

네트워크 기초

OSI 7 Layer

• 물리 계층
• 데이터링크 계층
• 네트워크 계층
• 전송 계층
• 세션 계층
• 표현 계층
• 응용 계층

네트워크 장비

IP ICMP TCP/UDP ARP/RARP SSL/TLS FTP DNS

라우팅 프로토콜

Keep-Alive 3-way-handshake / 4-way-handshake TIME_WAIT TLS handshake