운영체제

유석현(SeokHyun Yu)·2023년 10월 8일

기술면접

목록 보기

3/3

운영체제 (Operating System)란?

하드웨어 자원을 관리하는 소프트웨어: 컴퓨터의 하드웨어 자원을 효율적으로 관리하고 제어하는 역할을 수행합니다.
인터페이스 역할: 운영체제는 응용 프로그램과 하드웨어 간의 상호작용을 조정하고 관리합니다.
- 인터페이스 (Interface): 서로 다른 두 개의 시스템 사이에서 정보나 신호를 주고 받는 접점이나 경계를 의미합니다. 운영체제는 응용 프로그램이 하드웨어를 직접 다루지 않도록 중간에 위치하여 응용 프로그램이 하드웨어 자원을 쉽게 활용할 수 있게 합니다.

커널 (Kernel)이란?

커널은 운영체제의 핵심 부분으로, 항상 필요한 운영체제 기능을 수행하기 위해 메인 메모리에 상주하는 부분을 의미합니다.

커널의 역할

메모리 관리: 커널은 메모리 공간을 효율적으로 관리하고, 프로세스들이 메모리를 공유하고 충돌하지 않도록 합니다.
프로세스 관리: 프로세스를 생성, 제어, 종료하는 역할을 수행하며, 프로세스 간의 통신과 스케줄링을 조정합니다.
파일 시스템 관리: 파일의 생성, 읽기, 쓰기, 삭제 등 파일 시스템의 기능을 제공합니다.
입출력 관리: 입출력 장치와의 상호 작용을 관리하며, 데이터의 입출력을 조절합니다.
시스템 콜 제공: 응용 프로그램이 운영체제 기능을 활용할 수 있도록 시스템 콜을 제공합니다.

메모리의 구조

메모리는 다음과 같이 여러 영역으로 나눌 수 있습니다.

코드 영역 (텍스트 영역):
- 실행할 프로그램의 코드가 저장되는 영역입니다.
- CPU는 해당 코드 영역에 저장된 명령어를 하나씩 가져와 실행합니다.
데이터 영역 (Static 영역):
- 전역 변수와 정적 변수가 저장되는 영역입니다.
- 프로그램이 시작할 때 할당되고, 종료 시에 소멸합니다.
힙 영역 (Heap):
- 사용자가 직접 관리하는 동적 메모리 할당 영역입니다.
- 프로그램 실행 중에 메모리 공간을 동적으로 할당하고 해제할 수 있습니다.
- 주로 객체 지향 프로그래밍에서 객체가 힙 영역에 할당됩니다.
- 동적으로 할당되므로 사용자가 메모리 관리를 책임져야 합니다.
스택 영역 (Stack):
- 함수의 호출에 따른 지역 변수와 매개변수가 저장되는 영역입니다.
- 컴파일 시에 크기가 결정되며, 함수의 호출과 함께 할당되고 종료되면 소멸합니다.
- 함수 호출 스택을 관리하여 함수가 반환될 때 지역 변수를 제거합니다.

힙 영역과 스택 영역의 차이

저장하는 데이터

스택 영역 (Stack Area): 주로 지역 변수와 매개변수가 저장됩니다. 함수 호출과 함께 할당되며 함수 종료 시에 소멸합니다.
힙 영역 (Heap Area): 동적으로 생성된 변수 및 객체가 저장됩니다. new 연산자나 malloc 함수로 할당되며, 명시적으로 해제되기 전까지 메모리에 유지됩니다.

크기가 결정되는 타이밍

스택 영역: 컴파일 시에 크기가 결정되며, 컴파일 타임에 할당 및 해제됩니다.
힙 영역: 런타임(실행 중)에 크기가 동적으로 결정되며, 프로그램 실행 중에 할당 및 해제됩니다.

크기 제한

스택 영역: 스택 크기가 제한되어 있어 스택 오버플로우(Overflow)가 발생할 수 있습니다.
힙 영역: 크기가 제한되어있지 않아 필요에 따라 동적으로 메모리를 할당할 수 있습니다.

주소 할당 방향

스택 영역: 높은 주소에서 낮은 주소 방향으로 데이터를 저장합니다.
힙 영역: 낮은 주소에서 높은 주소 방향으로 데이터를 저장합니다.

비교

스택 영역: 스택은 힙에 비해 접근 및 소멸이 빠르며 함수 호출 및 반환과 관련하여 자동으로 관리됩니다.
힙 영역: 힙은 스택에 비해 접근 및 소멸이 느리며, 개발자가 직접 메모리를 할당하고 해제해야 합니다. 그러므로 주의가 필요합니다.

힙 영역을 너무 크게 잡는 문제점

메모리 낭비:
- 힙 영역을 너무 크게 설정하면 메모리 낭비가 발생할 수 있습니다.
- 사용하지 않는 메모리를 너무 많이 할당하면 다른 프로세스나 작업에서 사용할 수 있는 메모리가 줄어들게 됩니다.
Garbage Collection (GC) 오버헤드:
- 힙 영역이 너무 크면 GC의 수행 시간이 길어질 수 있습니다.
- GC는 사용하지 않는 객체를 메모리에서 정리하는 작업인데, 힙 영역이 크면 GC가 참조 여부를 확인하는 데 시간이 오래 걸릴 수 있습니다.
- 이로 인해 애플리케이션의 응답 시간이 지연될 수 있습니다.
메모리 관리 어려움:
- 힙 영역이 크면 메모리 관리가 어려워질 수 있습니다.
- 사용자가 직접 동적 메모리를 할당하고 해제해야 하므로 메모리 누수의 가능성이 높아질 수 있습니다.

일반적으로 힙 영역은 필요한 만큼만 할당하고, 필요할 때 동적으로 확장하는 방식으로 관리됩니다. 예를 들어, Java의 JVM(Java Virtual Machine)은 힙 영역을 처음부터 크게 설정하지 않고, Heap 영역이 꽉 찼을 때 GC를 진행한 후 Heap 영역을 확장합니다. 이렇게 함으로써 메모리 사용을 효율적으로 관리하고 GC의 오버헤드를 최소화할 수 있습니다.

프로세스

프로세스는 메인 메모리(주기억장치)에 적재되어 실행되는 프로그램을 의미합니다.
각 프로세스는 PCB(Process Control Block), 코드(Code), 데이터(Data), 힙(Heap), 스택(Stack) 영역을 갖습니다.
프로세스끼리는 각각의 영역을 독립적으로 갖기 때문에 별다른 동기화 작업이 필요하지 않습니다.
각 프로세스는 독립된 메모리 공간을 사용하므로 컨텍스트 스위칭(Context Switching) 비용이 큽니다.
프로세스는 생성 및 관리에 비용이 많이 들며, 생성 시간이 상대적으로 길다.
한 프로세스에서 오류가 발생하더라도 다른 프로세스에 영향을 주지 않습니다.

쓰레드

쓰레드(Thread)는 한 프로세스 내의 실행 단위, 실행의 흐름을 의미합니다.
쓰레드는 스택(Stack) 영역만을 별도로 갖고, 나머지 영역(code, data, heap)에 대해서는 해당 쓰레드를 포함한 프로세스의 자원을 공유합니다.
쓰레드가 공유 자원에 접근할 때는 동기화 작업이 필요합니다.
스택 영역 외부를 공유하므로 컨텍스트 스위칭 비용이 상대적으로 적습니다.
쓰레드는 프로세스보다 가볍기 때문에 생성 시간이 더 짧습니다.
한 쓰레드에서 오류가 발생하면, 나머지 프로세스 내의 쓰레드에 영향을 줄 수 있습니다.

프로세스와 쓰레드의 차이

독립성:
- 프로세스는 각각 독립된 메모리 공간을 갖고 독립성이 높습니다.
- 쓰레드는 같은 프로세스 내에서 자원을 공유하므로 상대적으로 독립성이 낮습니다.
동기화:
- 프로세스는 각각의 메모리 공간을 가지므로 별다른 동기화 작업이 필요하지 않습니다.
- 쓰레드는 공유 자원에 대한 동기화 작업이 필요합니다.
자원 공유:
- 프로세스 간의 자원 공유가 어렵습니다.
- 쓰레드는 같은 프로세스 내에서 자원을 공유할 수 있습니다.
성능:
- 프로세스 간의 컨텍스트 스위칭 비용이 크며, 생성 및 관리 비용이 더 높습니다.
- 쓰레드는 컨텍스트 스위칭 비용이 낮고, 생성 및 관리 비용이 적습니다.

프로세스와 쓰레드는 각각의 장단점이 있으며, 사용 목적에 따라 선택되어야 합니다. 프로그램의 병렬 처리와 자원 공유가 필요한 경우 쓰레드를 사용하고, 독립적인 프로그램 실행이 필요한 경우 프로세스를 사용할 수 있습니다.

컨텍스트 스위칭(Context Switching)이란?

컨텍스트 스위칭은 여러 프로세스를 처리해야 할 때, 현재 실행 중인 Task(프로세스 또는 스레드)의 상태를 저장하고, 다음에 실행할 Task의 상태를 읽어 레지스터에 적재하는 과정을 의미합니다. 이 과정을 통해 CPU는 여러 프로세스 간에 작업을 전환할 수 있습니다.

컨텍스트 스위칭이 필요한 이유

효율적인 CPU 활용:
- CPU의 사이클 속도는 매우 빠릅니다. 하지만 I/O 작업과 같은 대기 상태에 있는 작업이 발생하면 CPU는 아무 작업도 수행하지 않고 대기해야 합니다.
- 컨텍스트 스위칭을 통해 다른 프로세스나 스레드로 전환함으로써 CPU의 사용률을 향상시킬 수 있습니다.
다중 작업 처리:
- 운영체제는 여러 프로세스를 동시에 관리하고 실행해야 합니다. 컨텍스트 스위칭은 이를 가능하게 합니다.
- 한 번에 하나의 프로세스만 CPU를 점유하고 있어도, 빠르게 전환함으로써 여러 작업을 동시에 처리할 수 있습니다.

컨텍스트 스위칭 과정

현재 프로세스의 상태 저장:
- CPU가 현재 실행 중인 프로세스의 레지스터 상태 및 다른 관련 정보를 프로세스 제어 블록(PCB)에 저장합니다.
다음 프로세스 선택:
- 프로세스 스케줄러가 대기 중인 프로세스 중 하나를 선택합니다.
다음 프로세스의 상태 복원:
- 선택한 다음 프로세스의 PCB에 저장된 정보를 레지스터로 복원합니다.
프로세스 실행 재개:
- 복원된 프로세스는 이전에 중단된 지점에서 실행을 계속합니다.

프로세스 제어 블록 (PCB)란?

프로세스 제어 블록(PCB)은 운영체제 내에서 프로세스를 관리하기 위한 중요한 자료 구조입니다. 각 프로세스마다 하나의 PCB가 할당되며, PCB에는 프로세스와 관련된 중요한 정보를 저장하고 있습니다.

PCB의 주요 역할

프로세스 식별자 (Process ID, PID):
- PCB에는 각 프로세스를 고유하게 식별하는 PID가 저장됩니다. 이를 통해 운영체제는 원하는 프로세스를 식별할 수 있습니다.
프로세스 상태:
- 프로세스의 현재 상태 (예: new, ready, running, waiting, terminated)가 PCB에 저장됩니다. 이를 통해 운영체제는 프로세스의 진행 상황을 파악합니다.
프로그램 카운터:
- 프로세스가 다음에 실행할 명령어의 주소를 나타내는 프로그램 카운터가 PCB에 저장됩니다.
CPU 레지스터:
- 현재 프로세스의 레지스터 상태를 PCB에 보관합니다. 이를 통해 CPU의 레지스터 값을 저장하고 복원할 수 있습니다.
CPU 스케줄링 정보:
- 프로세스의 우선순위, 스케줄 큐에 대한 포인터 등 스케줄링과 관련된 정보가 PCB에 저장됩니다.
메모리 관리 정보:
- 페이지 테이블 또는 세그먼트 테이블 등과 같은 메모리 관리 정보가 PCB에 저장됩니다. 이를 통해 메모리 할당과 관리가 가능합니다.
입출력 상태 정보:
- 프로세스에 할당된 입출력 장치와 열린 파일 목록 등과 같은 입출력 상태 정보가 PCB에 포함됩니다.
어카운팅 정보:
- 사용된 CPU 시간, 시간 제한, 계정 번호 등과 같은 어카운팅 정보가 PCB에 저장됩니다.

Context Switching과 PCB

컨텍스트 스위칭(Context Switching)이 발생할 때, 현재 실행 중인 프로세스의 상태는 해당 프로세스의 PCB에 저장됩니다. 그리고 다음에 실행할 프로세스의 PCB에서 상태 정보를 불러와서 작업을 이어나가게 됩니다. 이렇게 PCB를 통해 프로세스 간에 상태를 전환하고 관리합니다.

PCB는 각 프로세스마다 고유하며 중요한 정보를 담고 있어서 보호된 메모리 영역에 위치하며, 운영체제의 핵심 역할 중 하나입니다. 이를 통해 운영체제는 다중 프로세스를 효과적으로 관리하고 실행할 수 있습니다.

크롬 브라우저의 탭은 프로세스인가요? 쓰레드인가요?

크롬 브라우저에서 각 탭은 별도의 프로세스로 실행됩니다. 이것을 "프로세스 기반 멀티태스킹"이라고 합니다. 이러한 구조는 여러 가지 이점을 제공합니다.

안정성: 각 탭은 독립된 프로세스에서 실행되므로 하나의 탭에서 오류가 발생해도 다른 탭에는 영향을 미치지 않습니다. 이것이 브라우저 크래시를 방지하고 사용자 경험을 향상시키는 데 도움이 됩니다.
보안: 각 탭은 분리된 프로세스에서 실행되므로 다른 탭의 데이터에 접근하기 어려워 보안을 강화합니다.
성능: 멀티프로세스 아키텍처는 여러 CPU 코어를 활용하여 병렬로 작업을 수행할 수 있어 빠른 브라우징을 가능하게 합니다.

멀티 쓰레드 vs. 멀티 프로세스

멀티 쓰레드

하나의 프로세스를 여러 개의 쓰레드로 구성하여 작업을 수행하는 것을 의미합니다.
쓰레드들은 같은 프로세스 내에서 자원을 공유합니다.
장점:
1. 적은 메모리 공간을 차지합니다.
2. Context Switching(프로세스 간 전환)이 빠릅니다.
단점:
1. 하나의 쓰레드가 오류로 인해 종료되면 전체 쓰레드가 종료될 수 있습니다.
2. 동기화 문제가 발생할 수 있어, 쓰레드 간의 자원 접근 및 제어에 주의가 필요합니다.

멀티 프로세스

하나의 프로그램을 여러 개의 프로세스로 구성하여 병렬적으로 작업을 수행하는 것입니다.
각각의 프로세스는 독립적으로 실행됩니다.
장점:
1. 하나의 프로세스가 죽더라도 다른 프로세스에 영향을 주지 않습니다.
2. 각각의 프로세스는 독립된 메모리 공간을 차지하므로 메모리 누수 및 충돌 문제가 줄어듭니다.
단점:
1. 멀티 쓰레드에 비해 메모리 공간을 많이 차지합니다.
2. 프로세스 생성 및 관리에 더 많은 시스템 자원이 필요합니다.

왜 멀티 쓰레드를 더 많이 사용하는가?

멀티 쓰레드는 하나의 프로그램 안에서 여러 작업을 효율적으로 해결할 수 있으며, Context Switching 시에 Stack 영역만 초기화하면 되기 때문에 빠르게 작업을 전환할 수 있습니다. 또한, 프로세스를 생성할 때 자원을 할당하는 오버헤드가 적어 자원을 효율적으로 관리할 수 있는 장점이 있습니다.

그러나 쓰레드 간 동기화와 오류 처리에 주의해야 하며, 안정성을 보장하기 위한 추가 작업이 필요할 수 있습니다. 선택은 상황과 요구사항에 따라 달라지므로, 프로젝트의 성격과 목표에 따라 쓰레드 또는 프로세스를 선택해야 합니다.

쓰레드마다 독립적으로 할당되는 요소

독립적으로 스택 영역을 갖는 이유:
- 스택 영역은 함수의 실행과 관련이 있습니다. 각 쓰레드가 독립적으로 스택 영역을 갖는 것은 곧 각 쓰레드가 독립적으로 함수 호출을 할 수 있다는 의미입니다.
- 프로세스 내에서 독립적인 실행 흐름을 유지하기 위해 각 쓰레드마다 스택 영역을 할당합니다.
- 이렇게 하면 한 쓰레드의 스택에서의 작업이 다른 쓰레드에 영향을 미치지 않으며, 독립적인 함수 호출 및 로컬 변수 저장이 가능해집니다.

독립적으로 PC Register를 갖는 이유:
- PC(Register) 값은 쓰레드가 현재 수행 중인 명령어의 위치를 가리키는 값입니다.
- 쓰레드는 CPU를 할당받아 실행하다가 스케줄러에 의해 다른 쓰레드로 전환될 수 있습니다. 이때 이전 쓰레드의 상태를 저장하고 다음 쓰레드의 상태로 복원해야 합니다.
- 따라서 각 쓰레드는 독립적으로 PC Register 값을 가지고 있어야 하며, 이를 통해 컨텍스트 스위칭 과정에서 쓰레드의 실행 위치를 올바르게 유지할 수 있습니다.

멀티 쓰레드 환경에서의 주의해야 할 점

멀티 쓰레드 환경에서 작업할 때에는 다음과 같은 주의사항을 고려해야 합니다:

동기화 (Synchronization):
- 멀티 쓰레드는 서로 한 프로세스 내의 자원을 공유하므로, 데이터 무결성을 유지하기 위해 동기화가 필요합니다.
- 공유된 데이터나 자원에 동시에 접근하는 경우, 쓰레드 간의 경합 조건과 데이터 불일치 문제가 발생할 수 있습니다.
- 동기화 기술을 사용하여 공유 자원에 대한 접근을 제어하고, 뮤텍스, 세마포어, 스레드 세이프한 자료 구조 등을 활용합니다.
데드락 (Deadlock) 및 교착 상태 (Starvation) 방지:
- 여러 쓰레드 간에 상호 의존성이 있는 경우 데드락이 발생할 수 있습니다.
- 데드락을 예방하기 위해 적절한 자원 할당 순서 및 타임아웃 정책을 적용합니다.
- 교착 상태나 기아 상태 (Starvation)를 방지하기 위해 쓰레드 우선순위 및 공정한 자원 할당을 고려합니다.
공유 자원 접근 제한:
- 공유 자원에 대한 접근을 제한하고, 꼭 필요한 경우에만 공유합니다.
- 불필요한 공유 자원의 접근을 최소화하여 쓰레드 간 충돌 가능성을 낮춥니다.
Race Condition 방지:
- 여러 쓰레드가 공유 자원에 동시에 접근할 때 발생하는 경합 조건을 방지합니다.
- 원자적인 연산, 락 기반의 동기화, CAS (Compare-And-Swap) 등을 활용하여 Race Condition을 방지합니다.
메모리 일관성 (Memory Consistency):
- 멀티 쓰레드 환경에서는 캐시와 메모리 간의 일관성을 유지해야 합니다.
- 메모리 모델과 동기화 명령을 사용하여 메모리 일관성을 관리합니다.

동기 vs 비동기

동기(Synchronous)

동기는 요청과 그 결과가 동시에 일어난다는 약속입니다. 즉, 어떤 작업을 요청하면 그 작업이 완료되어 결과가 반환될 때까지 대기합니다. 이때 결과가 주어지기 전까지는 다른 작업을 진행하지 않습니다.

예시:

A 함수가 B 함수를 호출하면, B 함수의 실행이 끝나야만 A 함수가 다음 작업을 수행합니다. 이는 설계가 간단하고 직관적이지만, 결과를 기다리는 동안 아무런 다른 작업을 수행하지 못하고 대기해야 합니다.

비동기 (Asynchronous)

비동기는 요청과 결과가 동시에 발생하지 않을 것이라는 약속입니다. 요청한 작업이 완료되면 결과를 반환하는 대신, 다른 작업을 수행하다가 결과가 준비되면 이를 처리하는 방식입니다. 이로써 자원을 효율적으로 활용할 수 있습니다.

예시:

A 함수가 B 함수를 호출하면 B 함수의 실행은 백그라운드에서 비동기적으로 진행됩니다. A 함수는 결과를 기다리지 않고 다른 작업을 수행할 수 있습니다. 그러다가 B 함수의 결과가 준비되면 B가 A에게 callback을 통해 알려주고, A는 결과를 처리합니다.

비동기 방식은 복잡할 수 있지만, 결과를 기다리는 동안 다른 작업을 수행할 수 있어서 효율적인 자원 활용을 가능하게 합니다. 이는 네트워크 호출, 파일 입출력 등 시간이 걸리는 작업에서 특히 유용합니다.

프로세스의 종류

자식 프로세스 (Child Process):
- fork 함수를 사용하여 부모 프로세스로부터 새로운 자식 프로세스를 생성한 상태입니다.
- 자식 프로세스는 부모의 데이터, 힙, 스택, PCB(Process Control Block) 등을 복사하여 독립적으로 실행됩니다.
데몬 프로세스 (Daemon Process):
- 백그라운드에서 동작하면서 특정한 서비스를 제공하는 프로세스입니다.
- 주로 시스템 서비스나 백그라운드 작업을 수행하는데 사용됩니다.
고아 프로세스 (Orphan Process):
- 부모 프로세스가 먼저 종료되어 고립된 자식 프로세스를 의미합니다.
- 이런 경우, 부모가 없는 프로세스는 시스템이 자동으로 새로운 부모를 할당합니다.
좀비 프로세스 (Zombie Process):
- 자식 프로세스가 종료되었음에도 불구하고 부모 프로세스로부터 작업 종료에 대한 승인을 받지 못한 프로세스를 지칭합니다.
- 이 상태에서 프로세스는 메모리를 소비하며 시스템 리소스를 낭비합니다.

Race Condition과 Critical Section

Race Condition(경쟁상태)은 두 개 이상의 쓰레드나 프로세스가 공유 자원에 접근할 때 서로 경쟁하며 예상치 못한 동작을 발생시키는 현상입니다. 이러한 상황은 데이터 일관성과 무결성을 깨뜨릴 수 있습니다.

Critical Section(임계영역)은 Race Condition이 발생할 수 있는 부분을 가리키며, 여러 쓰레드 또는 프로세스가 공유 자원을 동시에 접근하는 부분입니다.

경쟁상태 방지를 위한 상호배제(Mutual Exclusion)

Race Condition을 방지하고 Critical Section을 안전하게 관리하기 위해 상호배제(Mutual Exclusion) 메커니즘을 사용합니다. 이것은 다음과 같이 동작합니다:

임계영역 진입 (Enter Critical Section):
- 한 쓰레드가 Critical Section에 진입하려고 할 때, 다른 쓰레드들은 대기 상태로 들어갑니다.
임계영역에서 작업 수행 (Perform Operations):
- 진입한 쓰레드는 Critical Section에서 필요한 작업을 수행합니다. 다른 쓰레드들은 대기 상태로 남아있습니다.
임계영역 빠져나옴 (Exit Critical Section):
- 작업을 마치고 Critical Section을 빠져나가면 다른 쓰레드들이 진입할 수 있도록 허용합니다.

상호배제를 구현하기 위한 여러 방법이 있으며, 가장 일반적인 방법은 뮤텍스(Mutex)와 세마포어(Semaphore)를 사용하는 것입니다. 이러한 메커니즘은 쓰레드나 프로세스가 공유 자원을 안전하게 접근하도록 보장하며, Race Condition을 방지하여 데이터 일관성을 유지합니다.

Deadlock(교착상태)란?

Deadlock은 두 개 이상의 프로세스나 스레드가 서로 자원을 기다리면서 무한히 대기하는 상태를 의미합니다. Deadlock이 발생하려면 네 가지 조건이 동시에 충족되어야 합니다:

상호 배제 (Mutual Exclusion): 한 자원에 여러 프로세스가 동시에 접근할 수 없어야 합니다.
점유 대기 (Hold and Wait): 하나의 자원을 소유한 상태에서 다른 자원을 기다릴 때 발생합니다.
비선점 (Non-preemption): 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 다른 프로세스가 뺏을 수 없어야 합니다.
순환 대기 (Circular Wait): 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있어야 합니다.

Deadlock 해결 방법

교착상태를 해결하기 위해서는 위에서 언급한 네 가지 조건 중 하나 이상을 제거해야 합니다.

예방 (Prevention):
- 교착 상태 조건 중 하나를 제거함으로써 데드락이 발생하지 않도록 예방하는 방식입니다.
- 하지만 이 방법은 자원을 낭비하는 단점이 있습니다.
회피 (Avoidance):
- 데드락 발생 가능성을 인정하면서도 적절하게 회피하는 방식입니다.
- 은행원 알고리즘과 같은 방법으로 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있는지 사전에 검사합니다.
- 발생하지 않으면 자원을 할당하고, 발생하면 다른 프로세스가 자원을 해제할 때까지 대기합니다.
회복 (Recovery):
- 데드락이 발생하면 데드락 상태를 탐지하고 회복합니다.
- 데드락 상태의 프로세스를 중단시키거나 자원을 선점하여 해결합니다.
- 자원 섬점을 통해 해결하기: 교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당합니다.

식사하는 철학자 문제

"식사하는 철학자 문제"에서 Deadlock은 다음 조건들이 동시에 충족될 때 발생합니다:

점유대기 (Hold and Wait): 철학자는 이미 한 손에 포크를 들고 있으면서 다른 손에 포크를 얻으려고 대기합니다.
비선점 (Non-preemption): 철학자가 이미 어떤 포크를 들고 있으면 다른 철학자가 그 포크를 빼앗을 수 없습니다.
환형대기 (Circular Wait): 모든 철학자가 오른쪽 포크를 얻기 위해 서로를 기다립니다.
상호배제 (Mutual Exclusion): 한 번에 하나의 철학자만이 포크를 얻을 수 있어야 합니다.

해결 방법

"식사하는 철학자 문제"를 해결하기 위해서는 다음과 같은 방법들을 사용할 수 있습니다:

예방 (Prevention):
- 모든 철학자가 동시에 왼쪽 포크를 들도록 하는 방법입니다.
- 이로써 환형대기 조건을 제거할 수 있습니다.
- 하지만 이 방법은 자원을 비효율적으로 사용할 수 있습니다.
회피 (Avoidance):
- 데드락이 발생하지 않을 때까지 포크를 얻지 않는 방법입니다.
- 즉, 철학자는 포크를 얻을 때 데드락이 발생하지 않는 것을 보장할 때까지 기다립니다.
- 이 방법은 데드락을 회피할 수 있지만, 자원 이용률을 낮출 수 있습니다.
강제로 포크를 뺏기 (Force Fork Releasing):
- 일정 시간이 지나면 철학자에게 포크를 뺏어주는 방법입니다.
- 철학자가 어떤 포크를 오랜 시간 동안 가지고 있는 경우, 다른 철학자에게 포크를 강제로 뺏어주어 데드락을 방지합니다.
상호배제 원칙 완화 (Relax Mutual Exclusion):
- 모든 철학자가 한 번에 두 개의 포크를 동시에 들 수 있도록 허용하는 방법입니다.
- 이로써 상호배제 원칙을 완화하여 데드락 가능성을 줄일 수 있습니다.

뮤텍스 (Mutex)

뮤텍스는 "상호 배제"라고도 불리며, 다음과 같은 특징을 가집니다:

단일 접근: 오직 1개의 스레드(또는 프로세스)만이 뮤텍스를 획득하여 특정 자원에 접근할 수 있습니다.
락 해제: 락을 획득한 스레드(또는 프로세스)가 락을 해제하기 전까지 다른 스레드(또는 프로세스)는 해당 자원에 접근할 수 없습니다.

뮤텍스는 주로 공유 자원에 대한 동시 접근을 제어하기 위해 사용됩니다.

세마포어 (Semaphore)

세마포어는 "동시 접근 제어"를 위한 도구로, 다음과 같은 특징을 가집니다:

다중 접근: 세마포어 변수만큼의 스레드(또는 프로세스)가 동시에 특정 자원에 접근할 수 있습니다.
타 스레드 해제: 현재 수행 중인 스레드가 아닌 다른 스레드(또는 프로세스)가 세마포어를 해제할 수 있습니다.

세마포어는 이진 세마포어와 카운팅 세마포어로 나누어집니다:

이진 세마포어: 두 가지 상태(0 또는 1)만을 가지며, 뮤텍스와 유사한 역할을 합니다. 즉, 1개 스레드만 접근할 수 있는 상태와 0으로 세팅되면 접근이 차단된 상태로 사용됩니다.
카운팅 세마포어: 세마포어 변수가 지정된 수치를 가지며, 해당 수치만큼의 스레드(또는 프로세스)가 동시에 접근할 수 있습니다.

CPU Scheduling (CPU 스케줄링)이란?

CPU Scheduling은 Ready Queue(준비 큐)에 있는 프로세스 중에서 다음에 CPU를 할당할 프로세스를 선택하는 알고리즘을 의미합니다. 이것은 다중 프로세스 환경에서 CPU 자원을 효율적으로 관리하기 위해 사용됩니다.

CPU 스케줄링의 종류

비선점 (Non-Preemptive) 스케줄링:

First Come First Served (FCFS):
- 큐에 도착한 순서대로 실행되는 방식입니다.
- 가장 먼저 도착한 프로세스가 가장 먼저 실행됩니다.
- 최악의 경우 오래 걸리는 프로세스가 먼저 실행되어 기아(Starvation) 문제가 발생할 수 있습니다.
Shortest Job First (SJF):
- CPU 점유 시간이 가장 짧은 프로세스에 CPU를 할당하는 방식입니다.
- 기아 문제가 발생할 수 있으며, 미래의 CPU 사용 시간을 예측해야 합니다.
Highest Response Ratio Next (HRRN):
- 응답 비율이 가장 큰 프로세스를 먼저 처리하는 방식입니다.
- 응답 비율은 서비스 받을 시간을 분모로, 대기 시간을 분자로 가지며 대기 시간이 큰 경우 우선 순위가 높아집니다.

선점 (Preemptive) 스케줄링:

Round Robin (RR):
- 시간 할당량을 각 프로세스에 주고, 할당된 시간 내에 완료하지 못한 프로세스는 뒤로 보내는 방식입니다.
- 시분할 시스템에서 많이 사용되며, 모든 프로세스가 공정하게 CPU를 사용합니다.
Shortest Remaining Time First (SRTF):
- CPU 점유 시간이 가장 짧은 프로세스에 CPU를 할당하는 방식으로, SJF 방식의 선점 버전입니다.
- 미래의 CPU 사용 시간을 예측해야 하며, 기아 문제가 발생할 수 있습니다.
Multilevel Feedback Queue (다중 레벨 피드백 큐):
- 다중 큐를 사용하며, 각 큐는 서로 다른 시간 할당량을 가집니다.
- 프로세스는 큐 사이를 이동할 수 있으며, 우선순위가 단계적으로 증가합니다.

콘보이 현상 (Convoy Effect)

콘보이 현상은 작업 시간이 긴 프로세스가 먼저 큐에 도착하여 다른 프로세스의 실행 시간이 전부 늦춰져 효율성을 떨어뜨리는 현상을 말합니다. 이는 주로 CPU 스케줄러의 선택 방식에 의해 발생합니다.

FCFS (First-Come First-Served) 스케줄링

FCFS 스케줄링은 비선점형 스케줄링으로, 먼저 큐에 도착한 작업부터 순차적으로 실행합니다. 이 때, 콘보이 현상이 발생할 수 있습니다. 예를 들어, 하나의 프로세스가 긴 시간 동안 CPU를 점유하는 경우, 그 이후에 도착하는 프로세스들은 기다려야 하므로 실행이 지연됩니다. 이로 인해 효율성이 저하될 수 있습니다.

해결 방법

콘보이 현상을 해결하기 위해서는 다양한 스케줄링 알고리즘이 사용됩니다. 예를 들어, Round Robin 스케줄링은 시간 할당량을 설정하여 각 프로세스에 동등한 실행 기회를 부여하고, 긴 작업 시간을 가진 프로세스가 다른 프로세스를 지연시키는 현상을 완화합니다.

또한, 우선순위 기반 스케줄링은 각 프로세스에 우선순위를 부여하여 중요한 작업이 먼저 실행되도록 하는 방식으로, 콘보이 현상을 방지하는 데 도움이 됩니다.

이렇게 CPU 스케줄러 알고리즘을 효과적으로 선택하고 구성함으로써 콘보이 현상을 최소화하고 시스템의 성능을 향상시킬 수 있습니다.

CPU 성능 척도

CPU Utilization(이용률):
- CPU가 놀지 않고 일한 시간의 비율을 나타냅니다. 이것은 CPU가 작업을 수행하는 데 얼마나 효율적으로 사용되는지를 측정합니다.
- 이용률이 높을수록 CPU가 더 효율적으로 활용되고 있다는 것을 의미합니다.
Throughput(처리량):
- 단위 시간당 CPU가 처리하는 작업의 양을 나타냅니다. 즉, CPU가 얼마나 많은 작업을 수행했는지 측정합니다.
- 높은 처리량은 CPU의 성능이 우수하다는 것을 나타냅니다.
Turnaround Time(소요시간, 반환시간):
- 프로세스의 CPU 사용 시간과 기다린 시간을 합한 것입니다. 이것은 특정 작업이 시스템에서 완료되기까지 걸리는 전체 시간을 의미합니다.
- 소요시간이 짧을수록 작업이 빨리 완료됩니다.
Waiting Time(대기시간):
- 프로세스가 Ready Queue에서 기다린 전체 시간의 합을 나타냅니다. 이것은 프로세스가 CPU를 얻기 위해 얼마나 기다려야 하는지를 측정합니다.
- 대기시간이 적을수록 작업이 빨리 처리됩니다.
Response Time(응답시간):
- 프로세스가 Ready Queue에 들어가서 최초로 CPU를 얻기까지 걸린 시간을 나타냅니다. 이것은 사용자가 시스템의 응답을 받는 데 걸리는 시간을 측정합니다.
- 짧은 응답시간은 사용자 경험을 향상시킵니다.

선점과 비선점

선점 (Preemption) 방식

선점 방식은 CPU 스케줄링에서 사용되는 방식 중 하나로, 특정 프로세스가 실행 중이더라도 CPU 할당을 뺏어 다른 프로세스에게 할당할 수 있는 방식입니다. 이 방식은 다음과 같은 상황에서 CPU를 다른 프로세스로 넘길 수 있습니다:

System Call: 특정 프로세스가 시스템 호출(System Call)을 요청하면 CPU가 해당 호출을 처리하기 위해 다른 프로세스에게 넘어갈 수 있습니다.
Time Quantum: 각 프로세스는 일정한 시간 할당량(타임 슬라이스)을 받고, 이 시간이 경과하면 CPU를 다른 프로세스에게 양보하게 됩니다.
Interrupt: 하드웨어나 소프트웨어 인터럽트가 발생하면 현재 실행 중인 프로세스는 중단되고, 인터럽트 처리를 위한 코드가 실행됩니다. 이후 다른 프로세스로 CPU가 전환됩니다.

비선점 (Non-Preemption) 방식

비선점 방식은 특정 프로세스가 실행 중이면 그 프로세스가 끝날 때까지는 CPU를 다른 프로세스에게 양보하지 않는 방식입니다. 즉, 한 번 CPU를 할당받은 프로세스는 자발적으로 CPU를 양보하지 않는 한 계속 실행됩니다.

선점 방식과 달리, 비선점 방식에서는 프로세스가 자발적으로 끝나야만 CPU가 다른 프로세스로 넘어갑니다.

이러한 방식은 실시간 시스템에서 사용되거나 특정 상황에서 프로세스의 우선순위를 고려할 때 유용합니다.

동시성과 병렬성

동시성 (Concurrency)

동시성은 멀티 프로그래밍 (Multi-Programming) 환경에서 나온 개념으로, 주기억장치에 여러 프로세스를 적재하여 Context Switching을 통해 동시에 실행되는 것 처럼 보이게 하는 것을 의미합니다. 그러나 실제로는 동시에 실행되는 것이 아닌 번갈아가며 실행됩니다. 이 개념은 싱글 코어(CPU)에서 멀티스레드를 동작시키기 위한 방식으로 사용됩니다.

특징:

여러 프로세스 또는 스레드가 동시에 실행되는 것처럼 보이지만, 하나의 코어에서 번갈아가며 실행됩니다.
동시성은 프로세스 간의 실행 순서를 관리하고 Context Switching을 사용하여 각 프로세스 또는 스레드를 교체합니다.
주로 I/O 작업이나 대기 상태에 있는 프로세스 간에 전환이 이루어집니다.

병렬성 (Parallelism)

병렬성은 멀티 프로세싱 (Multi-Processing) 환경에서 나온 개념으로, 실제로 동시에 여러 프로세스를 병렬적으로 실행하는 방식을 의미합니다. 이를 위해서는 CPU가 멀티코어를 가지고 있어야 합니다.

특징:

여러 프로세스가 실제로 동시에 병렬적으로 실행됩니다.
병렬성은 멀티코어 CPU를 활용하여 여러 작업을 동시에 처리하는 것을 가능하게 합니다.
주로 CPU 바운드 작업(연산 집약적 작업)에 유용하며, 병렬 프로그래밍을 통해 성능을 향상시킬 수 있습니다.

Interrupt(인터럽트)란?

Interrupt(인터럽트)는 프로그램을 실행하고 있는 도중에 입출력 요청이나 예외 상황과 같은 이벤트가 발생하면, 현재 실행 중인 프로그램을 일시적으로 멈추고 CPU가 해당 작업을 처리하도록 하는 메커니즘입니다. 이는 컴퓨터 시스템이 다양한 작업을 동시에 처리하고 효율적으로 관리하기 위한 중요한 개념 중 하나입니다.

인터럽트의 주요 역할

입출력(I/O) 처리: 사용자가 키보드로 입력하거나 디스크에서 데이터를 읽거나 쓸 때와 같은 입출력 작업을 비동기적으로 처리합니다. CPU가 직접 대기하지 않고 다른 작업을 수행할 수 있게 합니다.
예외 처리: 프로그램 실행 중에 예외 상황(예: 0으로 나누기)이 발생하면 이를 처리하고 예외 상황을 해결하거나 적절한 조치를 취할 수 있도록 합니다.
타이머 인터럽트: 일정 시간마다 발생하여 운영체제의 스케줄러에 의해 다른 프로세스로 CPU를 전환시켜 다중 작업을 지원합니다.

인터럽트의 유형

하드웨어 인터럽트: 하드웨어 장치가 CPU에 신호를 보내는 경우로, 주로 입출력 장치나 타이머 등의 하드웨어 관련 이벤트에서 발생합니다.
소프트웨어 인터럽트: 프로그램 내에서 명시적으로 발생시키는 소프트웨어 이벤트로, 주로 예외 상황에서 처리됩니다.

시스템 콜 (System Call)이란?

시스템 콜은 사용자나 응용 프로그램이 운영체제 커널에서 제공하는 기능을 사용하기 위한 인터페이스입니다. 이러한 인터페이스를 통해 운영체제는 커널에서 제공하는 서비스를 사용할 수 있도록 허용하면서 컴퓨터 자원을 보호합니다. 사용자나 응용 프로그램은 시스템 콜을 통해 운영체제의 기능을 호출하고, 운영체제는 이러한 호출을 처리합니다.

시스템 콜의 역할

커널 접근: 시스템 콜은 사용자 영역에서 커널 영역으로 전환을 수행합니다. 이렇게 함으로써 사용자 프로세스가 직접 커널에 접근하지 않고, 커널이 제공하는 서비스를 사용할 수 있습니다.
자원 보호: 시스템 콜을 통해 운영체제는 컴퓨터 자원을 효과적으로 보호합니다. 사용자나 응용 프로그램은 직접 자원에 접근할 수 없고, 운영체제를 통해 접근해야 합니다.
서비스 제공: 운영체제는 시스템 콜을 통해 다양한 서비스를 제공합니다. 이 서비스에는 파일 관리, 프로세스 관리, 메모리 관리, 네트워크 통신 등이 포함됩니다.

메모리의 종류

1. 레지스터 (Registers)

가장 빠르고 직접적인 메모리로, CPU에 내장되어 있습니다.
속도가 빠르며 매우 제한적인 용량을 가집니다.
주로 프로세서의 연산을 지원하고 중간 결과를 저장하는 데 사용됩니다.

2. 캐시 (Cache)

CPU와 주기억장치(메인 메모리) 사이에 위치한 고속 버퍼 메모리입니다.
주기억장치로부터 데이터를 미리 읽어와 CPU가 빠르게 액세스할 수 있도록 합니다.
레벨 1(L1), 레벨 2(L2), 레벨 3(L3) 등 다수의 캐시 레벨이 있습니다.

3. 주기억장치 (Main Memory)

프로그램 실행 중에 사용되는 데이터와 명령어를 저장하는 메모리입니다.
레지스터와 캐시보다는 느리지만, 용량은 크고 접근이 CPU에 비해 빠릅니다.
주로 RAM(Random Access Memory)으로 구현되며, 전원이 끊기면 데이터가 사라집니다.

4. 보조기억장치 (Secondary Storage)

주기억장치와는 달리 데이터가 영구적으로 보존되는 메모리입니다.
하드 디스크 드라이브(HDD)와 고성능의 고체 상태 드라이브(SSD) 등이 있습니다.
주로 데이터의 장기 저장, 프로그램 및 운영 체제의 설치에 사용됩니다.

다양한 메모리 종류의 이유

메모리의 다양한 종류가 존재하는 이유는 접근 속도와 저장 용량에 따른 차이 때문입니다. 여기에 몇 가지 이유가 있습니다:

접근 속도: 메모리의 종류에 따라 접근 속도가 다릅니다. CPU에 가까운 레지스터와 캐시는 매우 빠른 속도로 데이터에 접근할 수 있어 프로세서의 성능을 향상시킵니다.
용량: 레지스터와 캐시는 용량이 제한적이며 주로 중요한 데이터나 명령어를 저장합니다. 주기억장치는 용량이 더 크지만 상대적으로 느립니다.
영구 저장: 보조기억장치는 데이터를 영구적으로 보존할 수 있어, 시스템이 종료되어도 정보가 유지됩니다.
비용: 메모리 종류에 따라 비용도 다릅니다. 레지스터와 캐시는 빠르지만 비용이 높고, 주기억장치는 비교적 저렴합니다.

메모리 관리의 필요성

각각의 프로세스는 독립된 메모리 공간을 갖기 때문에 다른 프로세스의 메모리 영역에 접근할 수 없습니다. 이러한 분리된 메모리 공간은 다음과 같은 이유로 메모리 관리가 필요합니다:

보안: 프로세스 간의 상호 간섭을 방지하고, 각 프로세스가 자신의 데이터를 안전하게 보호하기 위해 메모리 공간을 분리합니다.
효율성: 각 프로세스가 필요한 메모리 공간을 독립적으로 할당받아 작업을 수행하므로 효율적인 멀티태스킹을 지원합니다.
가상 메모리: 물리적인 RAM 크기보다 큰 메모리 공간을 프로세스에 제공하여 더 많은 프로세스를 동시에 실행할 수 있게 합니다.

메모리 관리 전략

운영체제는 다양한 전략을 사용하여 메모리를 관리합니다. 일반적인 메모리 관리 전략으로는 다음과 같은 것들이 있습니다:

Swapping: 가장 오래동안 사용되지 않은 프로세스나 프로세스의 일부를 디스크로 스왑하여 더 많은 공간을 확보합니다. 필요할 때 디스크에서 다시 가져옵니다.
페이징 (Paging): 물리적 메모리와 논리적 메모리를 일정한 크기의 페이지로 나누고, 페이지 단위로 메모리를 할당합니다. 페이지 교체 알고리즘을 사용하여 필요한 페이지를 물리적 메모리에 올립니다.
세그멘테이션 (Segmentation): 논리적 메모리를 여러 세그먼트로 나누고 각 세그먼트를 독립적으로 할당합니다. 이는 프로세스의 논리적 구조를 반영하며 메모리 할당을 관리합니다.
고정 길이 할당 / 가변 길이 할당: 메모리 공간을 고정 길이 블록 또는 가변 길이 블록으로 나누어 관리합니다. 고정 길이 할당은 메모리의 파편화 문제를 줄이지만, 가변 길이 할당은 더 효율적으로 메모리를 사용할 수 있습니다.
압축 (Compression): 더 많은 프로세스를 메모리에 유지하기 위해 압축 기술을 사용하여 메모리 공간을 압축합니다. 필요할 때 압축을 해제하여 사용합니다.

메모리의 fit의 종류

1. First Fit (첫 번째 핏)

동작 방식: 메모리의 처음부터 검사하여 크기가 충분한 첫 번째 메모리 공간에 할당합니다.
장점: 간단하며 빠른 할당이 가능합니다.
단점: 내부 단편화 문제가 발생할 수 있으며, 첫 번째 공간이 항상 최적이라는 보장은 없습니다.

2. Next Fit (다음 핏)

동작 방식: 마지막으로 참조한 메모리 공간에서부터 탐색을 시작하여 할당 가능한 공간을 찾습니다.
장점: 이전에 할당한 메모리 영역과의 연속성을 유지하기 쉽습니다.
단점: 내부 단편화 문제가 발생할 수 있으며, 메모리 조각화 문제가 지속될 수 있습니다.

3. Best Fit (최적 핏)

동작 방식: 모든 메모리 공간을 검사하여 내부 단편화를 최소화하는 크기의 공간에 할당합니다.
장점: 내부 단편화를 최소화하므로 메모리를 효율적으로 사용합니다.
단점: 메모리 할당 속도가 느릴 수 있으며, 완벽한 최적해를 찾는 것은 어려울 수 있습니다.

4. Worst Fit (최악 핏)

동작 방식: 남은 공간 중에서 가장 큰 공간에 할당합니다.
장점: 큰 메모리 공간에 할당하여 내부 단편화를 줄일 수 있습니다.
단점: 메모리 낭비가 발생할 수 있으며, 할당 속도가 느릴 수 있습니다.

페이징 (Paging)

페이징은 프로세스를 동일한 크기의 페이지로 분리하여 메모리에 불연속적으로 저장하는 메모리 관리 방식입니다. 예를 들어, 프로세스가 13MB이고 페이지 크기가 4MB인 경우, 각 페이지는 4MB가 됩니다. 프레임은 일정한 크기(예: 4MB)로 나누어져 메모리에 배치됩니다. 이로 인해 연속 할당 방식보다 내부 단편화가 적게 발생합니다.

페이징의 특징:

페이지와 프레임은 동일한 크기로 나눠집니다.
내부 단편화가 발생할 수 있지만, 연속 할당 방식보다는 적습니다.
주소 변환을 위한 페이지 테이블을 사용합니다.

세그멘테이션 (Segmentation)

세그멘테이션은 프로세스를 가변적인 크기의 세그먼트로 분리하고 메모리에 적재하는 메모리 관리 방식입니다. 주로 논리적인 블록 단위 세그먼트로 Code, Data, Stack, Heap 등으로 분리할 수 있습니다. 세그멘테이션 역시 외부 단편화가 발생할 수 있습니다.

세그멘테이션의 특징:

프로세스를 가변 크기의 세그먼트로 분리합니다.
외부 단편화가 발생할 수 있으며, 이를 해결하기 위해 압축 기법을 사용할 수 있습니다.
세그먼트 테이블을 사용하여 세그먼트의 위치 및 크기 정보를 유지합니다. 각 세그먼트에 대한 정보는 세그먼트 테이블 내에 저장됩니다.

단편화

내부 단편화 (Internal Fragmentation)

내부 단편화는 고정 길이 할당 또는 페이지 기반 할당에서 발생하며, 물리 메모리를 고정된 길이의 파티션 또는 페이지로 분할할 때, 해당 파티션 또는 페이지의 실제 데이터보다 작은 크기의 공간이 남는 현상을 의미합니다.

예를 들어, 물리 메모리를 4KB 페이지로 분할하고 프로세스가 2KB 데이터를 저장한다면, 이 페이지에는 2KB의 내용과 2KB의 빈 공간이 발생하게 됩니다. 이 빈 공간은 사용할 수 없으며 메모리 공간을 낭비하게 됩니다.

외부 단편화 (External Fragmentation)

외부 단편화는 가변 길이 할당 또는 세그멘테이션에서 주로 발생합니다. 물리 메모리의 최대 크기에서 현재 사용 중인 공간의 크기를 뺀 나머지 공간을 차지하지 못할 만큼 작은 조각으로 나누는 현상을 의미합니다. 이로 인해 새로운 프로세스를 메모리에 적재할 때, 이러한 조각들로 인해 적재할 공간을 찾지 못하게 됩니다.

예를 들어, 메모리에 여러 프로세스가 로드되어 있고 중간에 작은 빈 공간이 여러 개 있다면, 이 작은 빈 공간들이 외부 단편화를 형성하게 됩니다. 크기가 충분하더라도 연속된 공간이 아니므로 새로운 프로세스를 적재할 수 없습니다.

내부 단편화와 외부 단편화는 메모리 관리에서 중요한 문제이며, 효율적인 메모리 할당과 해제 전략을 사용하여 최소화해야 합니다.

페이지 교체 알고리즘 (Page Replacement Algorithms)

운영체제에서 메모리를 관리하는 페이징 기법에서 필요한 페이지가 주기억장치에 적재되지 않았을 때, 어떤 페이지 프레임을 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 합니다. 다양한 페이지 교체 알고리즘이 존재하며, 이들 중 몇 가지 주요한 알고리즘을 설명하겠습니다.

1. FIFO (First In, First Out)

FIFO 알고리즘은 가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체합니다. 이 알고리즘은 큐(Queue) 자료구조를 사용하여 페이지가 메모리에 올라온 순서를 저장하고, 교체가 필요할 때 가장 먼저 들어온 페이지를 교체합니다. 간단하고 초기화 코드에 적절한 방법이지만, 페이지 교체의 효율성이 낮을 수 있습니다.

2. 최적 (Optimal) 페이지 교체

최적 페이지 교체는 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘입니다. 이 알고리즘은 이론적으로는 가장 효율적인 알고리즘으로 모든 페이지 참조 시퀀스를 미리 파악해야 합니다. 그러나 실제 활용에선 알 방법이 없기 때문에 주로 연구를 위해 사용됩니다.

3. LRU (Least Recently Used)

LRU 알고리즘은 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘입니다. 이전에 참조된 페이지 중에서 오래 전에 참조된 페이지를 교체합니다. OPT 알고리즘의 방식과 유사한 효과를 낼 수 있으며, FIFO 알고리즘보다 효율적입니다.

4. LFU (Least Frequently Used)

LFU 알고리즘은 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘입니다. 대상인 페이지가 여러 개일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체합니다. LFU와 MFU 알고리즘은 실제 사용에 잘 쓰이지 않는데, 이유는 구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 제대로 유사하게 구현하기 어렵기 때문입니다.

Thrashing(쓰레싱)란?

Thrashing(쓰레싱)은 페이지 부재율이 높은 상태를 의미합니다. 이 상태에서는 메모리 부재로 인해 프로세스가 원활하게 실행되지 못하며, 다음과 같은 상황에서 발생합니다.

메모리 부재: 페이지 부재가 발생하면 페이지 교체나 페이지 로드가 필요합니다. 여러 프로세스가 메모리에 올라옴에 따라 메모리의 유효 사용 가능한 공간이 줄어들고, CPU 사용 시간이 증가하면서 자원을 최대한 활용하게 됩니다.
메모리 과다 사용: 그러나 메모리에 너무 많은 프로세스가 올라가면, 프로세스당 사용 가능한 물리 메모리 프레임의 수가 감소하며, 페이지가 물리 메모리에 부족하게 올라가는 경우가 발생합니다. 이로 인해 페이지 교체와 Page Fault가 빈번하게 발생하며 CPU 사용률이 감소합니다.
CPU 놀림 현상: 페이지를 교체하는 과정에서 CPU가 사용되지 않고 페이지 교체만 지속적으로 실행됩니다. 이때 운영체제는 CPU가 놀고 있으므로 더 많은 프로세스를 메모리에 올리려고 시도하면서 악순환이 발생합니다. 이 현상을 Thrashing(쓰레싱)이라고 부릅니다.

Thrashing을 해결하기 위해서는 다음과 같은 알고리즘을 사용합니다:

Working Set(워킹 셋) 알고리즘: 대부분의 프로세스가 특정 페이지를 집중적으로 참조하는 특성을 이용하여, 참조되는 페이지의 개수를 파악하고 그 페이지 수만큼 여분의 프레임을 확보하는 알고리즘입니다.
Page Fault Frequency(페이지 폴트 빈도) 알고리즘: 페이지 폴트 비율의 상한과 하한을 설정하여 상한을 넘으면 페이지에게 지급하는 프레임 개수를 늘리고, 하한을 넘으면 지급 프레임 개수를 줄입니다.

또한, CPU 사용률과 메모리 적재량을 함께 체크하여 쓰레싱 상태를 확인하고 관리합니다.

메모리 할당 방식

연속 할당 방식 (Contiguous Allocation)

연속 할당 방식은 프로세스 이미지가 분리되지 않은 온전한 프로세스를 메인 메모리에 적재하는 방식입니다. 이 방식에는 크게 두 가지 하위 방식이 있습니다.

1. 고정 길이 할당 (Fixed-Length Allocation)

메모리를 고정된 길이로 파트로 분리하고, 프로세스를 해당 파트에 삽입합니다. 각 파트는 고정된 크기를 가지므로 내부 단편화가 발생할 수 있습니다. 내부 단편화란 파트 내에 프로세스가 들어가면서 생기는 여백을 의미합니다.

2. 가변 길이 할당 (Variable-Length Allocation)

메모리를 프로세스의 길이에 따라 동적으로 파트로 분리하고, 해당 프로세스를 적재합니다. 가변 길이 할당을 사용하면 내부 단편화는 발생하지 않지만, 파트의 크기가 가변하기 때문에 외부 단편화가 발생할 수 있습니다. 외부 단편화는 파트 간의 빈 공간을 의미합니다.

불연속 할당 방식 (Non-Contiguous Allocation)

불연속 할당 방식은 프로세스가 연속된 이미지가 아닌 분리된 이미지로 구성되어 메인 메모리에 적재하는 방식입니다. 이 방식에는 두 가지 주요 방식이 있습니다.

1. 페이징 (Paging)

프로세스를 동일한 크기의 페이지로 분리하고, 메모리는 해당 페이지와 동일한 크기의 프레임으로 분리하여 불연속적으로 저장합니다. 예를 들어, 프로세스가 13MB이고 페이지 크기가 4MB라면, 한 페이지는 4MB가 됩니다. 이 방식에서는 프레임 크기가 고정되어 있으므로 내부 단편화가 발생할 수 있습니다.

2. 세그멘테이션 (Segmentation)

프로세스를 가변적인 크기의 세그먼트로 분리하고 메모리에 적재합니다. 주로 논리적 블록 단위로 세그먼트를 분리할 수 있으며, 예를 들어 Code, Data, Stack, Heap 등으로 분리할 수 있습니다. 세그멘테이션 역시 외부 단편화가 발생할 수 있습니다. 외부 단편화는 세그먼트 간의 빈 공간을 의미합니다.

유석현(SeokHyun Yu)

Backend Engineer

이전 포스트