취준생을 위한 운영체제 기초지식

• TOC {:toc}

✅ 운영체제의 정의에 관해 설명해 주세요

• 운영체제는 컴퓨터 프로그램을 위한 기본적인 서비스를 제공하는 시스템 소프트웨어¹입니다. 컴퓨터 하드웨어와 소프트웨어의 자원을 관리하고 그 사이의 인터페이스 역할을 합니다. 대표적인 예로 Windows, Linux, Mac OS 등이 있습니다.
• 참고: Operating system (wikipedia), What is an Operating System? (GeeksforGeeks)

프로세스와 스레드

해당 항목의 하위 질문은 모두 다음의 글을 참고했습니다.

• Thread (computing) by Wikipedia
• 완전히 정복하는 프로세스 vs 스레드 개념 by Inpa Dev
• 멀티 프로세스 vs 멀티 스레드 비교 💯 완전 총정리 by Inpa Dev
• Process와 Thread 이야기 by Charlezz @Medium

✅ 프로세스와 스레드를 비교 설명해 주세요

프로세스와 스레드의 정의

• 프로세스는 프로그램이 메모리에 적재되고 CPU 자원을 할당받아 실행되고 있는 상태로, 운영체제로부터 자원을 할당받은 작업의 단위라고 할 수 있습니다. (프로그램의 인스턴스라고 표현하기도 합니다)
• 스레드는 프로세스 내에서 실행되는 흐름의 단위로, 일반적으로 운영체제의 스케줄러에 의해 독립적으로 관리 될 수 있는 명령어 시퀀스(흐름)의 가장 작은 단위를 말합니다.
• 기본적으로 프로세스 안에 스레드가 포함됩니다. 프로세스는 최소 1개의 스레드를 보유하며 여러 개의 스레드를 보유할 수 있습니다.

프로세스 vs 스레드

• 프로세스가 스레드보다 훨씬 많은 상태 정보를 갖고 전달하며 비교적 무겁습니다.
• 프로세스는 독립된 주소 공간²과 자원을 할당 받는 반면 스레드는 일부 주소 공간과 자원을 다른 스레드와 공유합니다.
  • 스레드는 Stack 영역만 별도로 할당받고 그 외는 다른 스레드와 공유합니다.
• 스레드는 이미 공유 중인 자원을 통해 비교적 쉽게 상호 작용할 수 있지만 프로세스는 메시지 전달이나 공유 메모리 등을 통해야 합니다.

✅ 운영체제의 메모리 영역(구조)에 대해 설명해주세요

• 코드(Code) 영역
  • 프로그래머가 작성한 코드가 저장되는 영역입니다. 실제 프로그램 동작을 구성하는 함수, 연산 구문 등의 명령어가 저장되며 CPU가 이를 순차적으로 가져와 실행합니다.
  • 일반적으로 읽기 전용이며 크기가 고정되어 있습니다.
  • 텍스트(Text) 영역이라고도 합니다.
• 데이터(Data) 영역
  • 전역 변수나 정적 변수 등 코드가 실행되는 데 필요한 데이터가 저장된 공간으로 데이터(.data) 영역과 BSS(.bss, block stated symbol) 영역으로 세분화 할 수 있습니다.
  • 데이터 영역은 초기화된 정적 변수를 포함합니다.
  • BSS 영역은 변수와 상수를 모두 포함한 초기화 되지 않은 정적 데이터를 포함합니다.
• 힙(Heap) 영역
  • 동적으로 할당된 메모리를 위한 공간입니다.
  • 일반적으로 BSS 영역 끝에서 시작하여 거기서부터 더 큰 주소로 증가합니다.
  • 영역을 할당하고, 해제하고, 크기를 조절하는 등 개발자가 직접 영역을 관리할 수 있습니다.
• 스택(Stack) 영역
  • 일반적으로 메모리의 상위 영역에 위치하며 LIFO 구조를 갖는 호출 스택(call stack)을 포함합니다.
  • 함수가 호출될 때 함수에 필요한 값의 집합이 호출 스택에 저장(push)되며 이를 스택 프레임(stack frame)이라고 합니다. 스택 프레임은 최소한으로는 반환 주소로 구성되며 지역 변수와 매개 변수 등을 포함할 수도 있습니다.
  • 함수 호출이 완료되면 해당 함수의 스택 프레임은 자동으로 해제(pop)됩니다.
  • 호출 스택에 함수가 push 되고 pop 되는 과정은 스택의 가장 위를 추적하는 스택 포인터(stack pointer)를 통해 알 수 있습니다.
• 참고: Code segment, Data segment (wikipedia)
• 추가자료: 메모리 영역(code, data, stack, heap) (Block Busting), 메모리 구조 [Memory Structure] (Stranger’s LAB)

✅ 스레드에서 독립적인 Stack 메모리 영역이 필요한 이유에 대해 설명해주세요

• 스택(stack)은 함수 호출 시 전달되는 인자, 함수 내의 지역 변수, 반환 주소 등을 저장하는 메모리 공간으로 독립적인 스택 영역을 가지면 독립적인 함수 호출이 가능합니다. 그리고 독립적인 함수 호출이 가능하다는 것은 독립적인 실행 흐름을 갖는다는 것과 같습니다.
• 즉 스레드에서 독립적인 실행 흐름이 이뤄지려면 함수 호출에 관여하는 스택 영역을 독립적으로 가져야 합니다.

✅ 멀티 프로세스와 멀티 스레드를 비교 설명해주세요

• 하나의 애플리케이션에 대해 여러 개의 프로세스가 작업을 처리할 수 있도록 하는 것을 멀티 프로세스, 여러 개의 스레드를 이용하는 것을 멀티 스레드라고 합니다.
• 멀티 스레드를 사용하면 멀티 프로세스를 사용할 때에 비해 보다 적은 리소스로 보다 빠르게 애플리케이션을 운영할 수 있습니다.
  • 스레드는 프로세스 내에서 생성되기 때문에 실행 환경을 설정하는 작업이 매우 간단하여 생성 및 종료가 빠릅니다.
  • 프로세스 사이의 컨텍스트 스위칭보다 (동일한 프로세스 내의) 스레드 사이의 컨텍스트 스위칭시 드는 비용이 훨씬 적습니다.
  • 프로세스는 독립적인 메모리 공간을 갖는데 비해 스레드는 Stack 영역을 제외한 나머지 영역을 서로 공유하기 때문에 메모리를 적게 소비하고 보다 효율적으로 자원을 공유하고 통신할 수 있습니다.
• 멀티 프로세스가 멀티 스레드보다 안정합니다.
  • 프로세스는 독립적이라 다른 프로세스가 비정상적으로 차단되거나 종료되었을 때 영향을 받지 않지만 하나의 스레드에서 문제가 발생하면 다른 스레드들도 영향을 받아 전체 프로그램이 종료될 수 있습니다.
  • 또한 멀티 스레드의 경우 여러 개의 스레드가 공유 자원에 동시에 접근할 수 있기 때문에 동기화 문제가 발생할 수 있습니다. 예를들어 여러 스레드가 동시에 하나의 값을 변경 할 경우 의도되지 않은 값을 읽어올 수도 있습니다.

✅ 프로세스와 스레드의 컨텍스트 스위칭 비용

프로세스 사이의 컨텍스트 스위칭보다 (동일한 프로세스 내의) 스레드 사이의 컨텍스트 스위칭시 드는 비용이 훨씬 적습니다.

• 프로세스는 컨텍스트 스위칭을 위해서 저장하고 불러와야 할 상태 정보가 훨씬 많고, 전환 과정에서 CPU 캐시 메모리를 초기화 해야 합니다.
• 반면 스레드 컨텍스트 스위칭시에는 스레드 간에 공유하는 자원을 제외한 정보(stack, register)만 교체하면 됩니다.

✅ 프로세스의 자원 공유

프로세스는 독립적인 메모리 공간을 갖는데 비해 스레드는 Stack 영역을 제외한 나머지 영역을 서로 공유하기 때문에 메모리를 적게 소비하고 보다 효율적으로 자원을 공유하고 통신할 수 있습니다.

• 프로세스도 공유 메모리를 생성하거나 IPC(Inter-Process Commnuication)를 사용해 자원을 공유할 수 있지만 이 또한 별도의 자원을 필요로 합니다.

✅ 멀티 스레드의 동기화 문제

멀티 스레드의 경우 여러 개의 스레드가 공유 자원에 동시에 접근할 수 있기 때문에 동기화 문제가 발생할 수 있습니다. 예를들어 여러 스레드가 동시에 하나의 값을 변경 할 경우 의도되지 않은 값을 읽어올 수도 있습니다.

• 스레드의 접근을 순차적으로 퉁제해 이를 방지할 수는 있으나 이 과정에서 병목 현상이 발생해 성능이 저하될 수 있습니다.

참고

✅ 문맥 전환(Context Switch)에 대해 설명해주세요

• 멀티 프로세스 혹은 멀티 스레드 환경에서, CPU를 사용하는 프로세스 혹은 스레드를 교체하는 과정입니다.
• 동작중인 프로세스 혹은 스레드의 경우 이후에 복원해 다시 실행할 수 있도록 현재의 상태 정보를 저장하고 대기하고 있던 다른 프로세스 혹은 스레드가 이전에 저장해둔 상태 정보를 복원하면서 동작하기 시작합니다.
• 이 과정을 처리하는 데 시간이 유의미하게 오래 걸리면 멀티 태스킹을 위한 간접적인 처리가 성능저하를 유발하는 꼴이 되므로 유의하여야 합니다.
• 참고: Context switch (wikipedia)

CPU 스케줄링

✅ 경쟁 상태(Race Condition)에 대해 설명해주세요

• 경쟁 상태는 시스템의 실질적인 동작이 제어할 수 없는 다른 이벤트의 순서나 타이밍에 따라 달라지는 상태를 말합니다.
• 일반적으로 컴퓨터 과학에서는 공유 자원에 대해 여러 프로세스나 스레드가 동시에 접근할 때 타이밍이나 순서 등에 따라 결과값이 달라질 수 있습니다.
• 경쟁 상태에서 실행 순서나 타이밍에 따라 예상하지 못한 결과가 반환되면 버그가 발생할 수 있습니다.
• 참고: Race condition (wikipedia), [OS] 4. 프로세스 동기화 (Process Synchronization) (슈퍼마리호)

✅ 경쟁 상태에서 발생할 수 있는 문제

위의 답변 중 “예상하지 못한 결과가 반환”되는 것의 부가 설명으로 추가점이 될 수도 있겠지만 무결성과 정합성을 제대로 설명하지 못한다면 오히려 마이너스가 될 수도.

꼬리 질문이라 가볍게 이해하고 작성해서 답변이 정확하지 않을 수 있습니다.

• 경쟁 상태에서는 무결성과 정합성을 위반하는 결과값이 반환될 수 있습니다.
• 무결성 위반
  • 무결성은 데이터의 값이 정확한 상태입니다. 즉 모든 결과값이 조건을 만족해야 합니다.
  • 동일한 조건을 확인하는 두 개의 동작이 수행될 때 첫 번째 수행의 결과가 반영되지 않은 채 컨텍스트 스위칭이 일어나 다시 처음 상태로 조건을 확인하는 경우 결과적으로 조건에 맞지 않는 결과가 반환될 수 있습니다.
• 정합성 위반
  • 정합성은 데이터의 값이 서로 일치하는 상태입니다. 즉 데이터를 변경할 때 모든 데이터에 해당 변경사항이 동일하게 적용되어야 합니다.
  • 동일한 변경사항을 적용하는 두 개의 동작이 수행될 때 첫 번째 동작에서 기존값을 읽고 컨텍스트 스위칭이 일어나 두 번째 동작을 수행하하고 돌아오면 두 번째 동작의 변경사항이 적용되지 않은 기존값에서 다시 변경사항을 적용한 결과를 반환하게 됩니다. 결과적으로 변경사항을 한 번 적용한 결과값을 반환하게 되며 이는 순차적으로 동작이 수행됐을 때의 결과값과 다를 수 있습니다.
• 참고: 경쟁상태, 임계영역의 개념과 동기화를 위한 여러 상호배제 기법 (mutex, semaphore, monitor) (hudi’s blog), 무결성과 정합성이란 무엇인가? (yangsijun528)

✅ 경쟁 상태의 해결 방법에 대해 설명해주세요

• 경쟁 상태를 해결하기 위해서는 공유 자원에 접근하는 과정에서 다음의 세 조건을 충족해야 합니다.
  • 상호 배제 (Mutual Exclusion): 한 프로세스가 공유 자원을 사용하고 있다면 다른 프로세스는 해당 공유 자원에 접근할 수 없습니다.
  • 진행 (Progress): 어떤 프로세스도 공유 자원을 사용하고 있지 않는 상태에서 해당 공유 자원에 접근하고자 하는 프로세스가 있다면 이를 허용해주어야 합니다. 즉, 해당 공유 자원을 사용하고 있지 않는 이상 한 프로세스는 다른 프로세스가 공유 자원에 접근하는 데 간섭할 수 없습니다.
  • 유한 대기 (Bounded Waiting): 프로세스가 공유 자원에 접근하기 위해 무한으로 대기하는 현상이 발생해서는 안됩니다.
• 프로그래밍적으로는 임계 영역(critical section)³의 코드를 구현할 때 위의 조건을 충족하는 다양한 알고리즘을 사용할 수 있습니다. 대표적으로 피터슨 알고리즘(Peterson’s algorithm) 등이 있습니다.
• 커널을 사용해 상호 배제를 충족한 여러 동기화 기법을 사용할 수도 있습니다. 대표적으로 뮤텍스(Mutex), 세마포어(Semaphore), 모니터(Monitor) 등이 있습니다.
• 참고: [OS] 4. 프로세스 동기화 (Process Synchronization) (슈퍼마리호), Critical section (wikipedia), Peterson’s algorithm (wikipedia), Mutual exclusion (wikipedia)

피터슨 알고리즘에 대해 설명해주세요

추후에 작성

✅ 뮤텍스와 세마포어에 대해 설명해주세요

• 뮤텍스와 세마포어는 모두 공유 자원을 안전하게 관리하기 위해 상호 배제를 달성할 수 있도록 고안된 기법입니다.
• 뮤텍스(Mutex)는 공유 자원을 잠김과 잠기지 않음 두 가지 상태로 관리하는 기법으로 Lock이라고도 합니다. 한 프로세스(혹은 스레드)가 공유 자원을 사용하기 전에 이를 잠그고 사용이 끝나면 잠금을 해제하는 것을 반복하며 공유 자원이 잠김 상태일 때는 다른 프로세스가 공유 자원에 접근할 수 없습니다.
• 세마포어(Semaphore)는 공유 자원에 접근할 수 있는 최대 허용치를 정해두고 그만큼의 프로세스만 접근할 수 있도록 하는 기법입니다. 프로세스가 공유자 원에 접근할 때마다 허용치가 감소하며 허용치가 0일 경우 프로세스는 허용치가 증가할 때까지 대기해야 합니다.
  • 0 또는 1의 값만 가질 수 있는 (허용치가 1) 세마포어를 이진 세마포어(binary semaphore)라고 하는데 이를 사용해서 뮤텍스를 구현할 수 있습니다.
• 참고: 경쟁상태, 임계영역의 개념과 동기화를 위한 여러 상호배제 기법 (mutex, semaphore, monitor) (hudi’s blog), Lock (computer science) (wikipedia), Semaphore (programming) (wikipedia)
• 추가자료: 뮤텍스(Mutex)와 세마포어(Semaphore)의 차이 (Kwoncheol Shin @Medium)

모니터에 대해 설명해주세요

추후에 작성

✅ 교착 상태(Deadlock)에 대해 설명해주세요

• 교착 상태는 프로세스(혹은 스레드)가 다른 프로세스에 자원을 요청했을 때, 자원을 요청 받은 프로세스 역시 다른 대기 상태의 프로세스로부터 자원을 기다리고 있는 상태라 이를 얻기 위해서 대기해야 할 때 발생합니다.
• 이런 상태가 무기한 유지되면서 프로세스가 상태를 변경할 수 없게되면 시스템이 교착 상태에 있다고 합니다.
• 대표적인 예로 두 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있어서 결과적으로 아무것도 완료되지 못하는 경우가 있습니다.
• 참고: Deadlock (wikipedia), [운영체제] 데드락(Deadlock, 교착 상태)이란? (ChanBLOG)

✅ 교착 상태의 발생 조건에 대해 설명해주세요

• 교착 상태는 다음의 네 조건이 모두 동시에 성립하는 경우에만 발생합니다.
• 상호 배제(Mutual Exclusion): 한 번에 하나의 프로세스만 자원을 사용할 수 있어야 합니다.
  • 그렇지 않으면 프로세스가 자원이 필요해 대기하는 상황이 발생하지 않을 수 있습니다.
• 점유 대기(Hold and Wait): 최소한 하나의 자원을 보유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 합니다.
• 비선점(No Preemption): 다른 프로세스에 할당된 자원은 강제로 빼앗을 수 없습니다. 자원을 보유하고 있는 프로세스만이 자발적으로 자원을 해제할 수 있습니다.
• 순환 대기(Circular Wait):각 프로세스는 다른 프로세스가 보유중인 자원을 대기하고 있어야 하며 이런 대기 프로세스들의 집합은 순환 형태여야 합니다.
  • 일반적으로 대기 중인 프로세스의 집합인 P = {P1, P2, …, PN}이 있을 때, P1은 P2가 보유한 리소스를 대기하고 P2는 P3이 보유한 리소스를 대기하며, PN이 P1이 보유한 리소스를 대기할 때까지 계속 대기하는 형태입니다.
• 참고: Deadlock (wikipedia), [운영체제] 데드락(Deadlock, 교착 상태)이란? (ChanBLOG)

교착 상태의 해결 방법에 대해 설명해주세요

추후에 작성

✅ 기아 상태(Starvation)에 대해 설명해주세요

• 기아 상태는 동시 컴퓨팅 환경에서 프로세스가 작업을 처리하는 데 필요한 자원을 지속적으로 할당받지 못하는 상태입니다.
• 프로세스들이 점유할 자원이 부족한 상황에서 발생하며, 스케줄링 또는 상호 배제 알고리즘의 오류, 자원 누수 등이 자원을 고갈시키는 원인이 될 수 있습니다.
• 참고: Starvation (computer science) (wikipedia)

✅ 교착 상태와 기아 상태의 차이에 대해 설명해주세요

• 교착 상태는 여러 프로세스가 동일한 자원을 점유하려고 할 때 발생하고 기아 상태는 여러 프로세스가 부족한 자원을 점유하려고 할 때 발생합니다.
• 참고: 29. 스레드(Thread) - 교착(Deadlock)과 기아(Starvation)상태 (개발자를 향하여)

기아 상태(Starvation)의 해결 방법에 대해 설명해주세요

추후에 작성

메모리

✅ 가상 메모리(Virtual Memory)에 대해 설명해주세요

• 가상 메모리는 메모리 관리 기법의 하나로 컴퓨터 시스템에 실제로 사용할 수 있는 메모리 자원을 이상적으로 추상화하여 사용자들에게 실제보다 더 큰 메모리를 사용하는 것처럼 보이게 하는 방법을 말합니다.
• 프로그램이 사용하는 논리적 메모리와 실제(물리적)메모리를 구분해 프로그램의 일부만 실제 메모리에 할당해 수행하며 필요할 때마다 메모리에 할당하는 부분을 교체해 사용합니다.
• 페이징과 같은 분할 기술을 사용하여 물리적으로 사용 가능한 것보다 더 많은 메모리를 개념적으로 사용할 수 있지만 메모리에 접근해 페이지를 교체하는 과정에서 성능 저하가 발생할 수 있으므로 메모리 관리 및 페이지 교체 알고리즘을 최적화하는 것이 중요합니다.
• 참고: Virtual memory (wikipedia), [운영체제] 가상 메모리란? (쩨리쪠리)

참고

✅ 메모리 단편화(Fragmentation)에 대해 설명해주세요

• 메모리 단편화는 저장 공간이 비효율적으로 사용되어 용량 또는 성능이 저하되는 현상입니다.
• 컴퓨터 프로그램이 메모리를 요청하고 해제하는 과정에서 메모리는 조각 단위로 할당되고 해제됩니다. 요청 크기와 조각이 유지되는 시간이 각각 다르기 때문에 그 과정에서 저장 공간이 비효율적으로 사용되면 용량이나 성능이 저하될 수 있습니다.
• 메모리 단편화로 인해 메모리 공간은 충분하지만 실제로 사용할 수 없게 되거나 사용할 수 있는 메모리를 찾거나 조각을 관리하는 과정에서 성능 저하가 발생할 수 있습니다.
• 참고: Fragmentation (computing) (wikipedia), 메모리 단편화(Memory Fragmentation) (hanhs4544)

✅ 내부 단편화와 외부 단편화에 대해 설명해주세요

• 내부 단편화는 메모리 할당에 적용되는 규칙으로 인해 필요한 것보다 더 많은 컴퓨터 메모리가 할당되어 발생합니다. 예를 들어 메모리가 4 byte의 조각 단위로만 프로그램에 제공될 수 있을 때 프로그램이 29 byte를 요청하면 실제로는 32 byte의 조각을 받게 되어 3 byte의 메모리가 낭비됩니다.
• 외부 단편화는 사용 가능한 메모리가 작은 조각으로 나뉘어 할당된 메모리에 산재되어 있을 때 발생합니다. 저장할 수 있는 공간은 충분하지만 불연속적인 작은 조각으로 나눠져 있어 프로그램이 요구하는 만큼의 연속된 저장 공간을 확보하지 못해 사실상 저장 공간을 사용할 수 없게 됩니다.

✅ 페이징(Paging)과 세그멘테이션(Segmentation)에 대해 설명해주세요

• 페이징과 세그멘테이션은 모두 가상 메모리 기법의 일종으로 연속적인 프로세스의 주소 공간(가상 주소 공간)을 분할해 실제 메모리에 불연속적으로 할당하는 방법입니다.
• 페이징은 메모리를 고정된 크기로 나눠 할당합니다. 가상 메모리와 실제 메모리를 동일한 크기로 나누어 페이지 테이블을 이용해 매핑하며 가상 메모리의 단위 조각을 페이지, 실제 메모리의 단위 조각을 프레임이라고 합니다. 실제 메모리의 불연속적으로 나눠져 있는 공간을 활용할 수 있어 외부 단편화를 해결할 수 있지만 고정된 크기의 메모리를 매핑하므로 내부 단편화가 발생힐 수 있습니다.
• 세그먼테이션은 메모리를 세그먼트라는 단위로 나눠 할당합니다. 세그먼트는 프로그램을 자연스러운 논리적 단위로 분할한 것으로 크기가 서로 다를 수 있습니다. 그러므로 세그먼트는 실제 메모리에 적재될 때 필요한 만큼의 비어있는 공간을 할당 받아야 합니다. 이 때문에 내부 단편화는 발생하지 않지만 할당과 해제를 반복하는 과정에서 외부 단편화가 발생할 수 있습니다.
• 참고: 메모리 단편화 (Memory Fragmentation) (끄적이는 개발노트), What are Paging and Segmentation? (AfterAcademy)

Wikipedia의 Memory paging 문서나 Page (computer memory)의 문서를 보면 가상 메모리 활용 과정에서 보조 저장소에 초점을 맞춰 보조 저장소에 저장한 데이터를 동일한 크기의 조각으로 가져오는 과정을 페이징으로 정의하고 있습니다. 하지만 세그멘테이션과 함께 작성하는 항목이므로 더 넓은 범위에서 가상 메모리를 실제 메모리에 할당하는 방식에 초점을 맞춰 기술했습니다.

✅ 요구 페이징(Demand Paging)에 대해 설명해주세요

• 요구 페이징은 가상 메모리의 관리 방법 중 하나입니다.
• 요구 페이징을 사용하는 시스템에서 운영체제는 실행 중인 프로세스가 페이지를 필요로 하는 경우, 즉 특정 디스크 페이지에 접근하려는 시도가 있고 해당 페이지가 아직 메모리에 없는 경우(즉 페이지 결함이 발생한 경우)에만 디스크 페이지를 실제 메모리로 복사합니다.
• 일반적으로 이 프로세스를 수행하기 위해 메모리 관리 유닛의 항목에 특정 페이지가 유효한지(valid) 또는 유효하지 않은지(invalid)를 나타내는 비트가 포함됩니다.
• 참고: Demand paging (wikipedia), [OS] 요구 페이징(가상메모리) (장장스), 16: 가상 메모리 (Virtual Memory) (완숙의 에그머니)

✅ 페이지 교체(Page Replacement) 알고리즘을 아는대로 설명해주세요

• 실행중인 프로세스가 페이지를 요청했을 때, 요청된 페이지가 아직 메모리에 없지만 사용 가능한 프레임이 없거나 그 수가 임계값보다 적어 요청된 페이지를 메모리에 할당할 수 없다면 페이지 교체가 발생합니다. 이때 메모리 관리를 위해 스왑 아웃 시킬 페이지를 정하는데 다양한 페이지 교체 알고리즘이 사용됩니다.
• 이론적으로는 요청된 페이지와 현 시점에서 가장 나중에 사용될 페이지를 교체하는 알고리즘이 가장 이상적인 알고리즘입니다. 페이지가 사용되기까지 걸리는 시간을 안정적으로 계산하는 것이 힘들기 때문에 실제로 구현하기는 어려우며, 근접하게는 프로세스 실행 과정에서 페이지 참조를 추적해 데이터를 쌓아 후속 실행에서 교체할 페이지를 결정할 수 있습니다.
• 대표적인 페이지 교체 알고리즘은 다음과 같습니다.
  • Not Recently Used (NRU): 최근에 사용한 페이지를 메모리에 유지하는 것을 선호하는 알고리즘 입니다. 현재로 부터 특정 시간 내의 참조 여부와 수정 여부를 기반으로 교체 여부를 결정합니다.
  • First-In, First-Out (FIFO): 모든 페이지를 대기열(큐)에 추적해 대기열의 가장 앞에 있는, 즉 가장 오래된 페이지를 교체합니다. 오버헤드가 가장 낮지만 실제 적용시 성능이 좋지 않은 편입니다.
  • Second-Chance: FIFO를 개선한 알고리즘으로 대기열에 참조 비트를 추가한 알고리즘 입니다. 대기열의 첫 번째 페이지를 바로 교체하는 대신 참조 비트가 설정 되어있는지 확인해 참조 비트가 설정 되어있지 않은 경우에만 교체합니다. 참조 비트가 설정되어 있는 경우는 참조 비트를 지우고 페이지를 대기열의 가장 뒤에 다시 삽입합니다.
  • Clock: Second-Chance와 거의 동일하지만 페이지를 꺼내 다시 삽입할 필요 없이 순환 대기열을 이용합니다. 페이지 교체시 참조 비트가 설정되어 있지 않은 경우에만 교체하고 참조 비트가 설정되어 있으면 페이지 교체가 발생할 때까지 순환 비트를 지우면서 대기열의 다음으로 전진합니다.
  • Least Recently Used (LRU): NRU와 유사하지만 특정 시간 내의 사용 여부를 확인하는 NRU와 달리 특정 기간 동안의 페이지 사용량을 추적해 최근에 사용한 페이지를 결정합니다. 이론적으로는 최적에 가까운 성능을 제공할 수 있지만 실제로 구현하는 데는 비용이 많이 듭니다.
  • Not Frequently Used (NFU): 페이지가 사용된 빈도를 기준으로 사용 빈도가 낮은 페이지를 교체합니다. 특정 시간 간격마다 해당 간격 내에 참조된 페이지의 카운트를 증가시켜 카운트가 가장 낮은 페이지를 교체합니다. 참조되는 시간 범위에 상관 없이 사용 빈도만 추적하므로 시점에 따라 교체 효율이 저하될 수 있습니다.
• 참고: Page replacement algorithm (wikipedia)

주석