[컴구웅 스터디 8회차] 교착 상태(Deadlock), 페이징을 통한 가상 메모리 관리

heiler·2025년 6월 27일

Deadlock Fragmentation Paging Virtual Memory System swapping tlb

컴구웅(컴퓨터 구조 + 운영체제) 스터디

목록 보기

8/9

💬 Intro

안녕하세요, 헤일러입니다.

아래는 학습한 내용 목차입니다.

교착 상태
- 교착 상태를 예방하는 방법
- 교착 상태를 회피하는 방법
- 교착 상태를 회복하는 방법
메모리 스와핑
메모리 공간에 프로세스를 연속적으로 할당하는 방식과 외부 단편화 문제
페이징과 내부 단편화 문제
TLB
페이지 주소 변환

❓ 식사하는 철학자 문제가 무엇인가요? 자원 할당 그래프는 무엇인가요?

✅ 식사하는 철학자 문제(Dining Philosophers Problem)

식사하는 철학자 문제는 동기화 문제와 이를 해결하기 위한 기술을 설명하는 데 자주 사용되는 예시 문제입니다.

둥근 원탁에 5명의 철학자가 앉아 있습니다. 각 철학자 앞에는 스파게티가 담긴 접시가 하나씩 놓여있고, 접시와 접시 사이에 포크가 하나씩 놓여있습니다.

스파게티는 두 개의 포크를 사용해야만 먹을 수 있습니다. 두 포크는 양 옆의 철학자가 둘 다 식사하지 않고 있을 때만 사용할 수 있습니다. 철학자가 식사를 마치면 두 포크를 모두 내려놓습니다.

모든 철학자가 동시에 본인의 왼쪽에 있는 포크를 집고 나서 오른쪽에 있는 포크를 집으려고 하는 경우, 본인 오른쪽에 있는 철학자가 포크를 놓기를 기다리며 영원한 기다림의 굴레에 갇히게 되는데 이런 상태를 교착 상태(deadlock)라고 부릅니다.

✅ 자원 할당 그래프(RAG: Resource Allocation Graph)

자원 할당 그래프는 프로세스와 자원 사이의 할당/요청 관계를 표현한 그래프 입니다. 주로 교착 상태의 발생 가능성을 분석하기 위해 사용합니다.

자원 할당 그래프의 구성 요소는 프로세스 노드, 자원 노드, 자원, 간선이 있습니다.

구성 요소	설명	기호
프로세스 노드	프로세스에 일대일 대응되는 노드입니다.	원으로 표시합니다.
자원 노드	점유 가능한 자원을 나타내는 노드입니다. 자원 노드 내의 자원 인스턴스의 개수는 2개 이상이 될 수 있습니다.	사각형으로 경계를 표시하고, 사각형 내에 자원 인스턴스를 점으로 표시합니다.
간선	할당 간선: 자원이 프로세스에게 할당되었음을 나타내는 간선입니다. 요청 간선: 프로세스가 자원 할당을 요청했음을 나타내는 간선입니다.	할당 간선: 자원 인스턴스(점)->프로세스 요청 간선: 프로세스->자원 노드(사각형)

4명의 철학자가 교착 상태에 빠진 상태를 자원 할당 그래프로 그리면 다음과 같습니다.

철학자들(=프로세스): P1, P2, P3, P4
포크(=공유 자원): 하나의 포크는 동시에 한 명의 철학자만 사용할 수 있으므로, 하나의 점으로 표시됩니다.

❓ 교착 상태 발생 조건은 무엇이 있나요?

교착 상태가 발생하기 위해서는 다음 네 가지 조건이 필요합니다.
다음 네 가지 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않고, 네 가지 조건을 모두 만족하면 교착 상태가 발생할 가능성이 생깁니다.

상호 배제(mutual exclusion): 어떤 포크도 여러 철학자가 동시에 사용할 수 없습니다.
자원 점유(resource holding): 철학자들이 한 손에 포크 하나를 들고 있는 채로, 두 번째로 집을 포크를 기다리고 있을 수 있습니다.
비선점(non-preemption): 어떤 철학자도 다른 철학자가 이미 들고 있는 포크를 빼앗을 수 없습니다.
순환 대기(circular wait): 각 철학자는 자신의 왼쪽에 있는 철학자를 기다리고 있을 수 있습니다.

❓ 교착 상태를 예방하는 방법은 무엇이 있나요?

교착 상태의 발생 조건 네 가지 중 한 가지 이상을 충족하지 못하게 만들어, 교착 상태가 발생할 수 없게 만드는 방법을 교착 상태 예방이라고 합니다.

1. 상호 배제 조건을 예방하는 방법

자원을 공유 가능한 구조로 변경하면 상호 배제가 발생하지 않습니다.

하지만 모든 자원을 공유 자원으로 만드는 것은 캡슐화의 관점, 자원 접근 권한 문제, 동시성 문제를 생각했을 때 현실적으로 적용하기 어려운 방법입니다.

2. 점유와 대기를 예방하는 방법

프로세스에게 실행에 필요한 자원을 모두 몰아주거나, 하나도 점유하지 못하게 하는 방법입니다. 식사하는 철학자들로 예시를 들면 철학자에게 포크를 2개를 동시에 쥐어주거나, 아니면 1개도 들지 못하게 하는 거죠.

하지만 어떤 프로세스부터 자원을 몰아주어야 할 지 그 순서를 결정하는 과정이 굉장히 어렵고 비효율적인 방식입니다. 자원을 많이 필요로 하는 프로세스는 하나의 자원이라도 모자르면 실행이 되지 않기 때문에, 기아 현상(starvation)이 발생할 가능성이 높습니다.

3. 비선점을 예방하는 방법 = 선점을 사용한다

더 높은 우선순위 프로세스가 자원을 요청하면, 현재 점유한 자원을 강제로 회수해버리는 방법입니다. 선점 방식은 일부 자원에 대해서는 효과적입니다. 예를 들면 CPU가 선점 방식이 효과적인 대표적인 자원입니다.

하지만 모든 하드웨어 자원이 선점 가능하지는 않습니다. 예를 들어 한 번에 하나의 프로세스만 이용 가능한 프린터 자원이 있다고 했을 때, 한 프로세스가 이 프린터를 이용하는 도중에 다른 프로세스가 프린터 자원을 뺏어서 다른 프린트 명령을 내리는 것은 어렵습니다. 대게 CPU를 제외한 다른 자원에 대해서 선점 방식으로 교착 상태를 예방하는 것은 어렵습니다.

4. 순환 대기를 예방하는 방법

자원 순서를 고정하고 순서대로 자원을 할당하면 순환 대기는 발생하지 않습니다. 마치 철학자들이 원형 식탁이 아닌 일자형 식탁에서 식사를 하게 만드는 것과 같습니다.

앞의 3가지 예방 방법보다는 비교적 현실적이지만 역시 한계가 있습니다.

컴퓨터 시스템 내의 모든 자원에 순서를 부여하는 것은 어렵습니다.
각 자원에 어떤 번호를 붙이는 지에 따라 특정 자원의 활용률이 떨어질 수 있습니다.

✅ 교착 상태 예방이 현실적인가?

교착 상태의 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 예방하는 방식은 현실적으로 어렵고 여러 부작용이 따릅니다. 그래서 실제 시스템에서는 회피, 혹은 검출 후 회복 방식을 통해 해결하는 경우가 많습니다.

❓ 교착 상태를 회피하는 방법(Avoidance)은 무엇이 있나요?

시스템이 현재 자원 상태와 앞으로의 자원 요청을 고려하여, 교착 상태로 이어질 수 있는 자원 할당을 회피하는 방식을 교착 상태 회피라고 합니다.

교착 상태 회피는 시스템이 불안전 상태가 되지 않음을 보장해줌으로써 이루어집니다.

안전 순서열(safe sequence): 교착 상태 없이 프로세스들에게 자원 할당하는 순서
안전 상태(safe state): 안전 순서열대로 프로세스들에 자원을 할당하여 교착 상태가 발생하지 않는 상태
불안전 상태(unsafe state): 안전 순서열이 없어 교착 상태가 발생할 수 있는 상태

대표적인 교착 상태 회피 기법으로는 Banker's Algorithm이 있습니다. 자원 할당 요청이 들어왔을 때, 그 요청을 수락할 경우 시스템이 안전 상태로 유지되는지 시뮬레이션해보는 기법입니다. 시뮬레이션 후 안전 상태가 유지되면 자원 요청을 승인하고, 비안전 상태가 되는 경우 요청을 거절합니다.

안전 상태를 유지함으로써 교착 상태를 완전히 회피할 수 있는 대신, 자원 할당 요청을 받을 때마다 시뮬레이션을 통해 검사를 해야 하는 비용이 발생하기 때문에 실시간 시스템에는 부적합한 방식입니다.

❓ 교착 상태일 때 회복하는 방법(Detection & Recovery)은 무엇이 있나요?

교차 상태 검출 후 회복 방법에서는 교착 상태가 발생하는 것을 사전에 막지 않습니다. 시스템을 주기적으로 검사하여, 교착 상태에 빠졌다는 것을 검출해내고, 교착 상태를 풀어줍니다.

✅ 검출 방법

자원 할당 그래프를 이용하는 방법

순환 검사만으로 교착 상태를 판단할 수 있습니다.
단, 자원이 1개일 경우에만 유효합니다. 2개 이상의 자원 조건에서는 교착 상태 여부를 장담할 수 없습니다.

Banker's Algorithm를 이용한 방법
Wait-For Graph Algorithm

✅ 회복 방법

선점을 통한 회복
교착 상태가 해결될 때까지 한 프로세스에 자원을 몰아주는 방식입니다.
프로세스 강제 종료
교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 없어질 때 까지 한 프로세스씩 강제 종료할 수 있습니다. 가장 단순하면서 확실한 방법입니다. 하지만 전자는 많은 프로세스들의 작업 내역을 잃게 될 가능성이 있고, 후자는 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드가 발생합니다.
프로세스 롤백
교착 상태에 빠진 프로세스를 교착 상태가 발생하기 이전의 상태로 롤백하는 방법입니다. 이 방법을 사용하기 위해서는 특정 체크포인트에 프로세스들의 상태를 주기적으로 저장해야 합니다.

❓ 메모리 스와핑이 무엇인가요?

메모리(RAM)에 로드된 프로세스들 중에 현재 실행에 필요하지 않은 프로세스를 보조기억장치로 내쫓고, 메모리 빈 공간을 확보하여 그 곳에 실행에 필요한 프로세스를 로드하여 실행하는 방식을 스와핑(Swapping)이라고 합니다.

이 때 쫓겨난 프로세스들이 자리 잡는 보조기억장치의 일부 영역을 스왑 영역(swap space)라고 부릅니다. 그리고 메모리에서 스왑 영역으로 옮겨지는 것을 스왑 아웃(swap-out), 반대로 스왑 영역에서 다시 메모리로 로드되는 것을 스왑 인(swap-in)이라고 합니다.

스와핑을 이용하면 각 프로세스들이 요구하는 메모리 주소 공간 크기의 합이 실제 메모리 크기보다 큰 경우에도 동시에 실행할 수 있습니다. (병렬x 동시o)

📌 스왑 영역 지정 & 확인하기
UNIX 계열 운영체제에서는 free -h, top 등의 명령어를 통해 스왑 영역의 크기를 확인할 수 있습니다. 또한 스왑 영역의 크기와 사용 여부를 사용자가 임의로 설정할 수 있습니다.

# 2GB 스왑 영역 확보
fallocate -l 2G /swapfile

# 루트 권한에만 read, write 권한 부여
chmod 600 /swapfile
# /swapfile을 스왑 영역으로 지정
mkswap /swapfile
# 스왑 영역 사용 활성화
swapon /swapfile

# 확인
free -h
swapon -s

fallocate명령어는 dd명령어에 비해 속도가 빠르지만 XFS, ext4 등 일부 파일 시스템에서만 지원하므로, swapon에서 오류를 발생시킬 수 있습니다. 호환성 보장을 위해서는 dd 명령어를 사용하는 것이 일반적입니다.

❓ 메모리 공간에 프로세스를 연속적으로 할당하는 방식은 무엇이 있나요? 외부 단편화 문제도 설명해주세요.

메모리 공간에 프로세스를 연속적으로 할당하는 방식에는 최초 적합, 최적 적합, 최악 적합 세 가지 방식이 있습니다.

✅ 최초 적합(First Fit)

동작 흐름

메모리의 낮은 주소부터 순차적으로 빈 공간(hole)을 탐색합니다.
실행 요청한 프로세스를 수용할 수 있는 첫 번째 빈 공간이 발견되면 그 자리에 바로 할당하고 탐색을 중지합니다.

유리한 상황

속도가 중요한 상황에서 유리합니다.

✅ 최적 적합(Best Fit)

동작 흐름

메모리의 낮은 주소부터 순차적으로 모든 빈 공간을 탐색합니다. (메모리 전체 탐색)
프로세스를 수용할 수 있는 빈 공간 중에서 가장 크기가 작은 최적의 공간을 찾습니다.
그 최적의 공간에 프로세스를 할당합니다.

유리한 상황

공간 절약이 중요한 경우 유리합니다.

✅ 최악 적합(Worst Fit)

동작 흐름

메모리의 낮은 주소부터 순차적으로 모든 빈 공간을 탐색합니다.
프로세스를 수용할 수 있는 빈 공간 중에서 가장 큰 공간을 찾습니다.
그 가장 큰 공간에 프로세스를 할당합니다.

유리한 상황

큰 요청이 자주 들어올 때 유리합니다.

✅ 외부 단편화(External Fragmentation)

프로세스들이 메모리에 물리적으로 연속적으로 할당되는 환경에서는, 메모리 빈 공간들의 크기 총합은 충분하지만 연속된 빈 공간이 없어서 새로운 프로세스에게 메모리를 할당할 수 없는 경우가 발생할 수 있습니다.

이런 현상을 외부 단편화라고 합니다.

외부 단편화를 해결하는 방식에는 압축, 페이징이 있습니다.

압축: 메모리 내에 로드된 프로세스들을 한쪽 공간으로 밀어넣어 연속된 빈 공간을 확보하는 방법
페이징: 논리 메모리를 페이지 단위로 쪼개어 물리적인 메모리 공간 상에서는 메모리 비연속적으로 로드하는 방법

❓ 페이징이란 무엇인가요?

운영체제가 프로세스를 실행할 때 사용할 수 있는 물리적인 메모리 공간은 한정적입니다. DDR5-44800 메모리를 사용한다면 용량이 16GB 정도 밖에 안되겠죠. 이 적은 공간에 모든 실행 중인 프로세스의 데이터를 로드할 수는 없습니다.

이 공간 부족의 한계를 해결하기 위해 가상 메모리(Virtual Memory) 기술이 등장했습니다. 가상 메모리는 사용자 프로세스에 논리적으로 연속적인 메모리 공간을 제공하는 메모리 모델로, 실제 물리 메모리의 크기보다 큰 주소 공간을 사용하는 것을 가능하게 해주는데요. 가상 메모리를 구성하는 핵심 요소는 다음과 같습니다.

핵심 요소	설명
가상 주소(VA: Virtual Address)	프로그램 입장에서 바라보는 논리 주소
물리 주소(PA: Physical Address)	실제 메모리의 물리적인 주소.
페이지(Page)	가상 메모리를 동일한 크기로 나눈 단위. 보통 4KB.
프레임(Frame)	물리 메모리를 동일한 크기로 나눈 단위. 페이지와 1:1로 매핑되므로 페이지와 크기가 같음.
페이지 테이블(Page Table)	가상 주소를 물리 주소로 매핑해주는 자료구조
MMU(Memory Management Unit)	CPU 안에 존재하며 가상 주소를 물리 주소로 변환해주는 하드웨어

페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리의 물리 주소 공간을 페이지와 동일한 크기의 프레임이라는 단위로 자른 뒤, 페이지를 프레임에 할당하는 가상 메모리 관리 기법입니다. 프로세스들이 메모리에 물리적으로 연속적으로 저장되어 있지 않더라도, CPU는 페이지 순서(논리 순서)를 기반으로 순차적으로 실행할 수 있습니다.

그리고 위에서 언급했던 스와핑 기법은 프로세스 전체를 통째로 스왑 아웃, 스왑 인하는 방식인데요. 프로세스 전체를 스왑하는 것은 디스크 I/O가 많이 발생하기 때문에 속도가 매우 느리고 현대 시스템에서는 잘 사용되지 않습니다.

그래서 현대 시스템에서는 스와핑 기법을 페이징에서 응용해서 사용합니다. 프로세스 단위가 아닌 페이지 단위로 메모리에 로드하고 제거하는 방식인데요. 페이징 시스템에서의 스왑 아웃은 페이지 아웃(page out), 스왑 인은 페이지 인(page in)에 대응됩니다. 페이지는 크기가 작기 때문에 I/O 속도가 빠르다는 장점이 있습니다. 대신 마지막 페이지 내부에 빈 공간이 생기는 내부 단편화 문제가 생길 수 있다는 단점이 있습니다.

❓ 내부 단편화(Internal Fragmentation)란 무엇인가요?

페이지를 사용하게 되면 외부 단편화 문제는 해결할 수 있지만 내부 단편화 문제가 발생합니다. 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자르는데, 모든 프로세스의 크기가 페이지 크기의 배수는 아니기 때문입니다.

예를 들어 페이지의 크기가 8KB인데, 프로세스의 크기가 70KB이라고 하면, 해당 프로세스는 9개의 페이지를 할당 받고, 마지막 페이지는 2KB만큼의 빈 공간이 생깁니다. 이렇게 페이지 내부의 빈 공간이 쌓여 메모리가 낭비되는 현상을 내부 단편화라고 합니다.

❓ TLB(Translation Lookaside Buffer)가 무엇인가요? TLB 히트, 미스를 포함하여 설명해주세요.

운영체제는 각 프로세스마다 고유한 페이지 테이블을 생성하고, 이 페이지 테이블은 메모리(RAM)에 저장됩니다. CPU의 MMU가 주소 변환 시 메모리에 있는 이 페이지 테이블을 참조하여 가상 주소->물리 주소 변환을 수행합니다. 매번 MMU가 메모리에 있는 페이지 테이블을 조회한다면, 메모리 접근 시간이 2배로 늘어나겠죠. 이 시간을 줄여주기 위해 TLB를 사용합니다.

TLB는 CPU 내의 MMU 내에 존재하며, 페이지 테이블의 일부를 캐싱하여 빠르게 주소 변환을 할 수 있도록 도와주는 하드웨어 캐시입니다.

CPU가 가상 주소 VA1에 접근하려고 하면, MMU가 페이지 번호를 추출해서 TLB에 해당 페이지 번호가 존재하는지 먼저 확인합니다.

TLB에 존재하면(TLB 히트), 바로 물리 주소를 반환합니다.
TLB에 존재하지 않으면(TLB 미스), 메모리의 페이지 테이블에 접근하여 물리 주소를 가져옵니다. 그리고 가져온 페이지-프레임 변환 정보를 TLB에 저장합니다.

출처: https://en.wikipedia.org/wiki/Translation_lookaside_buffer

❓ 페이지 주소 변환은 어떻게 이루어지나요? 페이지 테이블 엔트리 내용을 포함해 설명해 주세요.

✅ 주소 변환

하나의 페이지는 보통 4KB라는 넓은 범위의 주소를 포괄하고 있습니다. 그렇기 때문에 32bit, 64bit 단위의 특정 메모리 주소에 접근하기 위해서는 페이지 단위보다 더 세분화된 주소 변환이 필요합니다.

접근하려는 메모리 주소가 어떤 페이지 내부에 포함되는지 (페이지 번호)
접근하려는 메모리 주소가 해당 페이지 첫 주소로부터 얼마나 떨어져 있는지 (오프셋)

페이지 번호와 오프셋까지 알아야 실제 물리 메모리의 주소를 정확하게 찾아갈 수 있습니다.

메모리 주소 = 페이지 번호를 페이지 테이블을 통해 변환한 프레임 번호 x 페이지 크기(4KB) + 오프셋

한 페이지의 크기가 4KB= $2^{12}$ B 라고 하면 오프셋은 12bit가 필요합니다.
32bit 주소 체계에서는 32bit 단위로 페이지 주소 정보를 저장하기 때문에 상위 20bit를 페이지 번호, 하위 12bit를 오프셋으로 사용하여 한 프로세스 당 최대 $2^{20} = 1,048,576$ 개의 페이지를 사용할 수 있습니다.

✅ 페이지 테이블 엔트리(Page Table Entry)

페이지 테이블의 각 행들을 페이지 테이블 엔트리라고 부릅니다.
이전까지는 페이지 테이블에 담기는 정보로 페이지 번호, 프레임 번호만 언급했지만 다른 정보들도 존재합니다. 대표적인 정보가 유효 비트, 보호 비트, 참조 비트, 수정 비트입니다.

▶️ 유효 비트(valid bit)

유효 비트는 해당 페이지가 현재 물리 메모리에 로드되어 있는지 여부를 나타냅니다. 로드되어 있으면 1, 아니면 0입니다.
CPU가 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트가 발생합니다.

📌 페이지 폴트(Page Fault)
CPU가 접근하려는 페이지가 물리 메모리에 로드되어 있지 않을 때 발생하는 예외를 페이지 폴트라고 합니다.

CPU가 가상 주소->물리 주소 변환을 시도합니다.
MMU가 페이지 테이블에서 해당 페이지 엔트리의 유효 비트가 0임을 확인합니다.
CPU는 페이지 폴트 예외를 발생시킵니다.
커널의 페이지 폴트 핸들러로 이동하여 예외를 처리합니다.
커널은 필요한 페이지를 보조기억장치에서 메모리로 로드하고, 페이지 테이블을 업데이트합니다.
페이지 폴트 예외가 발생한 지점부터 재실행합니다.

▶️ 보호 비트(protection bit)

보호 비트는 해당 페이지의 다양한 접근 권한을 제어하는 역할을 합니다.
보호 비트는 주로 읽기/쓰기/실행 권한을 제어하기 위한 목적으로 사용됩니다.

보호 비트	기능 설명
R (Read)	읽기 허용 여부
W (Write)	쓰기 허용 여부
X (Execute)	실행 허용 여부
U/S (User/Supervisor)	사용자 모드 접근 가능 여부

보통 메모리의 Text 영역은 쓰기를 금지하고 Data, Stack, Heap 영역은 실행을 금지합니다.

📌 Protection Fault
1. CPU가 쓰기 명령어를 실행합니다.
2. MMU가 페이지 테이블에서 해당 페이지 엔트리의 보호 비트가 0임을 확인합니다.
3. 보호 비트 W가 0이면 접근을 거부합니다.
4. CPU는 Protection Fault 또는 Page Fault(Access Violation) 예외를 발생시킵니다.
5. 커널이 해당 예외를 처리합니다.

▶️ 참조 비트(reference bit)

참조 비트는 페이지가 메모리에 로드된 이후, 한 번이라도 접근이 된 적 있는지 여부를 나타냅니다. 참조된 적 있으면 1, 아니면 0입니다.
참조 비트는 페이지 교체 시 최근 사용 여부를 판단하기 위한 목적으로 사용됩니다.
페이지가 메모리에 로드될 때 참조 비트는 0으로 초기화됩니다.
해당 페이지에 접근이 발생하면 그 때 MMU에 의해 1이 됩니다.
운영체제가 주기적으로 0으로 초기화한 후 다시 감시합니다.

참조 비트를 통해 오랜 기간 참조되지 않은 페이지를 제거 대상으로 두는 페이지 교체 알고리즘이 있습니다. 페이지 교체 알고리즘은 다음 스터디 범위에 포함되니 다음 주차에 정리하도록 하겠습니다 :)

▶️ 수정 비트(modified bit = dirty bit)

수정 비트는 해당 페이지가 메모리에 적재된 이후, 한 번이라도 쓰기(write) 연산이 수행된 적 있는지 여부를 나타냅니다. 쓰인 적이 있으면 1, 아니면 0입니다.
페이지가 메모리에 로드될 때 수정 비트는 0으로 초기화됩니다.
CPU가 해당 페이지에 쓰기 연산을 수행하면 MMU가 수정 비트를 1로 설정합니다.
운영체제가 페이지 교체를 수행할 때, 수정 비트를 참조해서 1이면 보조기억장치에 저장(write-back) 작업을 수행하고, 0이면 그대로 폐기합니다.
즉, 수정 비트는 페이지 교체 시 디스크에 저장이 필요한지 판단하기 위한 목적으로 사용됩니다.

Reference

혼자 공부하는 컴퓨터 구조+운영체제, 강민철
식사하는 철학자 문제
- https://en.wikipedia.org/wiki/Dining_philosophers_problem
Resource Allocation Graph (RAG) in Operating System
- https://www.geeksforgeeks.org/operating-systems/resource-allocation-graph-rag-in-operating-system/
External Fragmentation in OS
- https://www.geeksforgeeks.org/operating-systems/external-fragmentation-in-os/
Introduction to Paging
- https://cs4118.github.io/www/2023-1/lect/17-paging-intro.html
TLB
- https://en.wikipedia.org/wiki/Translation_lookaside_buffer

heiler

Smiley

이전 포스트

[컴구웅 스터디 7회차] CPU 스케줄링, 프로세스 동기화

다음 포스트

[컴구웅 스터디 8회차] 교착 상태(Deadlock), 페이징을 통한 가상 메모리 관리

컴구웅(컴퓨터 구조 + 운영체제) 스터디

💬 Intro

❓ 식사하는 철학자 문제가 무엇인가요? 자원 할당 그래프는 무엇인가요?

✅ 식사하는 철학자 문제(Dining Philosophers Problem)

✅ 자원 할당 그래프(RAG: Resource Allocation Graph)

❓ 교착 상태 발생 조건은 무엇이 있나요?

❓ 교착 상태를 예방하는 방법은 무엇이 있나요?

1. 상호 배제 조건을 예방하는 방법

2. 점유와 대기를 예방하는 방법

3. 비선점을 예방하는 방법 = 선점을 사용한다

4. 순환 대기를 예방하는 방법

✅ 교착 상태 예방이 현실적인가?

❓ 교착 상태를 회피하는 방법(Avoidance)은 무엇이 있나요?

❓ 교착 상태일 때 회복하는 방법(Detection & Recovery)은 무엇이 있나요?

✅ 검출 방법

✅ 회복 방법

❓ 메모리 스와핑이 무엇인가요?

❓ 메모리 공간에 프로세스를 연속적으로 할당하는 방식은 무엇이 있나요? 외부 단편화 문제도 설명해주세요.

✅ 최초 적합(First Fit)

동작 흐름

유리한 상황

✅ 최적 적합(Best Fit)

동작 흐름

유리한 상황

✅ 최악 적합(Worst Fit)

동작 흐름

유리한 상황

✅ 외부 단편화(External Fragmentation)

❓ 페이징이란 무엇인가요?

❓ 내부 단편화(Internal Fragmentation)란 무엇인가요?

❓ TLB(Translation Lookaside Buffer)가 무엇인가요? TLB 히트, 미스를 포함하여 설명해주세요.

❓ 페이지 주소 변환은 어떻게 이루어지나요? 페이지 테이블 엔트리 내용을 포함해 설명해 주세요.

✅ 주소 변환

✅ 페이지 테이블 엔트리(Page Table Entry)

▶️ 유효 비트(valid bit)

▶️ 보호 비트(protection bit)

▶️ 참조 비트(reference bit)

▶️ 수정 비트(modified bit = dirty bit)

Reference

[컴구웅 스터디 7회차] CPU 스케줄링, 프로세스 동기화

[컴구웅 스터디 9회차(마지막)] 페이지 교체와 프레임 할당, 파일 시스템

0개의 댓글