이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

파티셔닝(partitioning)과 포매팅(formatting)

• 파티셔닝(파티션을 나누는 작업) : 저장 장치의 논리적인 영역을 구획하는 작업
• 파티션 : 파티셔닝 작업을 통해 나누어진 하나의 영역
• 포매팅 : 포맷을 하는 작업, 어떤 종류의 파일 시스템을 사용할지 결정하고 새로운 데이터를 쓸 준비를 하는 작업

포맷(포매팅)의 종류
저수준 포매팅 : 저장 장치를 생성할 당시 공장에서 수행되는 물리적인 포매팅
논리적 포매팅 : 파일 시스템을 생성하는 포매팅

이 글에서 포매팅은 논리적 포매팅을 뜻한다.

파일 할당 방법

• 포매팅까지 끝난 하드 디스크에 파일을 저장하기
• 운영체제는 파일/디렉터리를 블록 단위로 읽고 쓴다.(즉, 하나의 파일이 보조기억장치에 저장될 때에는 여러 블록에 걸쳐 저장된다.)

파일을 보조기억장치에 할당하는 방법에는 크게 연속 할당과 불연속 할당이 있고, 불연속 할당에는 크게 연결 할당과 색인 할당이 있다.

연속 할당과 불연속 할당
연속 할당보다는 불연속 할당을 많이 사용한다.

연속 할당(contiguous allocation)

• 이름 그대로 보조기억장치 내 연속적인 블록에 파일 할당
• 연속된 파일에 접근하기 위해 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다.
• 디렉터리 엔트리 : 파일 이름 & 첫 번째 블록 주소 & 블록 단위 길이 명시
• 구현이 단순하지만 외부 단편화를 야기할 수 있다.

연속 할당 외부 단편화 예시

이 상황에서 파일 D와 F가 삭제되었다면,

잔여블록은 11개이지만, 가장 큰 빈 블록이 6개이므로 블록 7개 이상 사용하는 파일을 할당할 수 없다.

불연속 할당

연결 할당(linked allocation)

• 각 블록의 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당
• 파일을 이루는 데이터 블록을 연결 리스트로 관리
• 불연속 할당의 일종이기 때문에, 파일이 여러 블록에 흩어져 저장되어도 무방하다
• 디렉터리 엔트리 : 파일이름 & 첫 번째 블록 주소 & 블록 단위의 길이
• 단점 : 반드시 첫 번째 블록부터 하나씩 읽어 들여야 함, 오류 발생 시 오류가 발생한 블록 이후 블록은 접근이 어렵다.

디렉터리 엔트리에 첫 번째 블록 주소와 마지막 블록 주소를 기록할 수도 있다.

색인 할당(indexed allocation)

• 파일의 모든 블록 주소를 색인 블록이라는 하나의 블록(색인 블록)에 모아 관리하는 방식
• 파일 내 임의의 위치에 접근하기 용이
• 디렉터리 엔트리 : 파일 이름 & 색인 블록 주소

FAT과 유닉스 파일 시스템

FAT 파일 시스템

• 연결 할당 기반 파일 시스템
• 연결 할당의 단점을 보안
• 각 블록에 포함된 다음 블록 주소를 한 곳에 모아 테이블(FAT:File Allocation Table)로 관리

위 그림에서 블록의 주소는 4 -> 8 -> 3 -> 5로 연결되어 있음을 알 수 있다.

FAT 파일 시스템
-USB 메모리, SD 카드와 같은 저용량 저장 장치용 파일 시스템으로 많이 사용
-FAT12 ,FAT16, FAT32가 있으며 FAT 뒤에 오는 숫자는 블록을 표현하는 비트 수를 의미
-윈도우에서 블록이라는 용어 대신 클러스터라는 용어를 사용한다.

1. FAT 영역에 FAT가 먼저 저장됨
2. 뒤이어 루트 디렉터리 영역
3. 다음에 서브 디렉터리와 파일들을 위한 영역

FAT가 메모리에 캐시
FAT는 파티션의 시작 부분에 있지만, 실행하는 도중 FAT가 메모리에 캐시 될 수 있다.
FAT가 메모리에 적재된 채 실행되면 기존 연결 할당보다 다음 블록을 찾는 속도가 매우 빨라지고, 결과적으로 연결 할당 방식보다 임의 접근에도 유리해진다.

FAT 파일 시스템의 디렉터리 엔트리

속성 항목은 해당 파일이 읽기 전용 파일인지, 숨김 파일인지, 시스템 파일인지, 일반 파일인지, 디렉터리인지 등을 식별하기 위한 항목

FAT 파일 시스템에서 파일을 읽는 과정

\home\minchul\a.sh에 접근하는 과정

1. home 디렉터리는 3번 블록에 있다.
2. minchul 디렉터리는 15번 블록에 있다.
3. a.sh 파일의 첫 번째 블록 주소가 9번 블록이라는 것을 알 수 있다.
4. a.sh 파일은 9->8->11->13번 블록 순서로 저장되어 있다.

유닉스 파일 시스템

• 색인 할당 기반 파일 시스템
• 유닉스에서 색인 블록을 i-node(index-node)라고 부른다.
• i-node에는 파일 속성 정보와 열다섯 개의 블록 주소가 저장될 수 있다.
• 디렉터리 엔트리는 i-node와 파일 이름으로 구성된다.

블록 주소 중 12개에는 직접 블록 주소 저장

• 직접 블록 : 파일 데이터가 저장된 블록

파일 크기가 크다면 13번째 주소에 단일 간접 블록 주소 저장

• 단일 간접 블록 : 파일 데이터를 저장한 블록 주소가 저장된 블록

충분하지 않다면 14번째 주소에 이중 간접 블록 주소 저장

• 이중 간접 블록 : 단일 간접 블록들의 주소를 저장하는 블록

아직도 충분하지 않다면 15번째 주소에 삼중 간접 블록 주소 저장

• 삼중 간접 블록 주소 : 이중 간접 블록들의 주소를 저장하는 블록

유닉스 파일 시스템의 디렉터리 엔트리

• 디렉터리 엔트리는 i-node가 파일 시스템의 핵심이다.

유닉스 파일 시스템에서 파일을 읽는 과정

\home\minchul\a.sh에 접근하는 과정

• 파일에 접근하기 위해 파일 시스템은 우선 루트 디렉터리 위치부터 찾는다
• 루트 디렉터리 위치는 루트 디렉터리의 i-node를 보면 알 수 있다.
• 유닉스 파일 시스템은 루트 디렉터리의 i-node를 항상 기억하고 있다.
• 아래의 그림은 2번 i-node가 루트 디렉터리의 i-node라고 가정

1. 2번 i-node에 접근하여 루트 디렉터리의 위치를 파악, 루트 디렉터리는 1번 블록에 있다.

2. 루트 디렉터리 안에 home 디렉터리의 i-node는 3번 i-node이다.

3. 3번 i-node에 접근하여 home 디렉터리 위치를 파악한다. home 디렉터리는 210번 블록에 있다.

4. 210번 블록을 읽으면  home 디렉터리 내용을 알 수 있다. minchul 디렉터리의 i-node는 8번이다.

5. 8번 i-node에 접근하여 minchul 디렉터리의 위치를 파악한다. minchul 디렉터리는 121번 블록에 있다.

6. 121번 블록을 읽으면 minchul 디렉터리의 내용을 알 수 있다. 파일 a.sh의 i-node 번은 9번이다.

7. 9번 i-node에 접근하여 파일 a.sh의 위치를 파악한다. a.sh 파일은 98, 12, 13번 블록에 있다.

8. \home\minchul\a.sh를 읽기 위해 98->12->13번 블록에 접근하면 된다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

파일과 디렉터리

• 모두 운영체제 내부 파일 시스템이 관리하는 존재들이다.
• 보조기억장치의 데이터 덩어리

파일(file)

• 보조기억장치에 저장된 관련 정보의 집합
• 의미 있고 관련 있는 정보를 모은 논리적 단위

파일을 이루는 정보

• 파일 이름
• 파일을 실행하기 위한 정보
• 파일 관련 부가 정보(=속성(attribute) 또는 메타데이터(metadata))

윈도우 운영체제에서 임의의 파일을 선택하고 마우스 우클릭을 하고 속성 버튼을 누르면 나타나는 정보가 파일 속성이다.

파일 속성과 유형

• 유형 : 운영체제가 인식하는 파일 종류(확장자)를 나타냄

파일 연산을 위한 시스템 호출

파일을 다루는 모든 작업은 운영체제에 의해 이뤄진다.

어떤 응용 프로그램도 임의로 파일을 조작할 수 없으며 파일을 다루려면 운영체제에 요청을 해야 한다.

운영체제는 이를 위해 다음과 같은 파일 연산을 위한 시스템 호출을 제공한다

• 파일 생성
• 파일 삭제
• 파일 열기
• 파일 닫기
• 파일 읽기
• 파일 쓰기

디렉터리(directory)

• 파일들을 관리하기 위해 디렉터리를 이용
• 윈도우 운영체제에서는 디렉터리를 폴더(folder)라고 부름
• 옛날 운영체제에서는 하나의 디렉터리만 존재했고 이를 1단계 디렉터리(single-level directory)라고 부른다.
• 현대에는 여러 계층을 가진 트리 구조 디렉터리(tree-structured directory)를 사용한다.
• 트리 구조 디렉터리는 최상위 디렉터리가 있고 그 아래에 여러 서브 디렉터리가 있고, 서브 디렉터리는 또 다른 서브 디렉터리를 가질 수 있다.
• 최상위 디렉터리는 흔히 루드 디렉터리(root directory)라 부르고, 윈도우에서는 (c:\), 유닉스에서는 (\) 로 표현한다.

절대 경로와 상대 경로

• 절대 경로(absolute path) : 루트 디렉터리에서 자기 자신까지 이르는 고유한 경로
• 상대 경로(relative path) : 현재 디렉터리에서 자기 자신까지 이르는 경로

절대 경로와 상대 경로
a.sh의 절대 경로는 / (또는 C:\)home\minchul\a.sh
현재 디렉터리 경로가 \home이라면 a.sh의 상대 경로는 minchul\a.sh 

디렉터리 연산을 위한 시스템 호출

운영체제는 디렉터리 연산을 위해 시스템 호출도 제공한다. 대표적인 종류는 아래와 같다.

• 디렉터리 생성
• 디렉터리 삭제
• 디렉터리 열기
• 디렉터리 닫기
• 디렉터리 읽기

디렉터리 엔트리

• 많은 운영체제에서 디렉터리를 그저 '특별한 형태의 파일'로 간주, 즉 디렉터리도 파일이다.
• 파일이 내부에 해당 파일과 관련된 정보를 담고 있다면, 디렉터리는 내부에 해당 디렉터리에 담겨있는 대상과 관련된 정보를 담고 있다.
• 대상과 관련된 정보는 보통 테이블(표) 형태로 구성된다. 즉, 디렉터리는 보조기억장치에 테이블 형태의 정보로 저장된다.

각각의 엔트리(행)에 담기는 정보는 파일 시스템마다 차이가 있다.

디렉터리 엔트리만 보아도 해당 디렉터리에 무엇이 담겨 있는지, 보조기억장치의 어디에 있는지를 직간접적으로 알 수 있다.

파일 시스템에 따라 디렉터리 엔트리에 아래와 같이 파일 속성을 명시하는 경우도 있다.

아래와 같은 구조의 디렉터리와 파일이 있다고 가정하면,

home 디렉터리 테이블은 위 그림의 오른쪽과 같이 구성된다.

..은 상위 디렉터리를 가리키고 .은 현재 디렉터리를 가리킨다.

디렉터리 엔트리를 통해 보조기억장치에 저장된 위치를 알 수 있기 때문에 home 디렉터리에서 minchul 디렉터리가 저장된 곳을 알 수 있고 따라서 그곳으로 이동할 수도 있다.

마찬가지로 minchul 디렉터리 엔트리에는 디렉터리에 속한 파일들의 이름과 이들의 위치를 알 수 있는 정보 등이 포함되어 있기 때문에 이 파일들이 보조기억장치 내에 저장된 위치를 알 수 있고 실행할 수 있다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

쓰기 시 복사(copy on write)

• 전통적인 관점에서 fork()함수를 이용하여 프로세스를 복제하면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 서로 다른 메모리 공간에 적재된다.
• 각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
• 이러한 복사 작업은 프로세스 생성 시간을 늦출 뿐만 아니라 불필요한 메모리 낭비를 야기한다.

쓰기 시 복사를 이용하면 각 프로세스(부모 프로세스와 자식 프로세스)는 동일한 프레임을 가리킨다.

이로써  굳이 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다.

만일 부모 프로세스와 자식 프로세스가 메모리에 어떠한 데이터도 쓰지 않고 그저 읽기 작업만 한다면 이상태가 지속되고, 둘중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제된다.

각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리키는 것이다.

이것이 쓰기 시 복사이다.

이러한 쓰기 시 복사를 통해 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간 절약도 가능하다

계층적 페이징

• 프로세스의 페이지 테이블 크기는 생각보다 작지 않다.
• 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비이다.

프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지 하지 않을 방법이 계층적 페이징이다.

계층적 페이징은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식이다.

여러 단계의 페이지를 둔다는 점에서 다단계 페이지 테이블(multilevel page table)기법이라고 부른다.

아래와 같은 기본적인 페이지 테이블이 있다고 가정하면, 

이 페이지 테이블을 여러 개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블(아래 그림의 outer 페이지 테이블)을 두는 방식이 계층적 페이지이다.

outer 페이지 테이블은 메모리에 항상 적재하고 일부분의 페이지 테이블이 필요하다면 outer페이지를 이용하여 일부분의 페이지 테이블만 메모리에 적재하는 것이다.

페이지 테이블을 이렇게 계층적으로 구성하면 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없고, 페이지 테이블 중 몇 개는 보조기억장치에 있어도 무방하며, 추후 해당 페이지 테이블을 참조해야할 때가 있으면 그때 메모리에 적재면 그만이다.

계층적 페이징을 사용하지 않을 경우에는 논리 주소는 페이지 번호와 변위로 이루어져 있다.

하지만 계층적 페이징을 사용하는 경우 CPU가 발생하는 논리 주소도 달라진다.

계층적 페이징을 사용하는 경우 논리 주소는 <변위, 바깥 페이지 번호, 안쪽 페이지 번호>로 구성된다.

이러한 논리 주소를 토대로 주소 변환은 아래와 같이 이루어진다.

1. 바깥 페이지 번호를 통해서 찾고자 하는 페이지 테이블 엔트리(row)를 찾는다.
2. 안쪽 페이지 번호를 통해서 해당 페이지 테이블 안에서 특정 페이지 엔트리를 찾는다.
3. 해당 프레임 번호에 변위를 더하여 물리 주소를 구한다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

운영체제는 한정된 물리적 메모리 용량 때문에, 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고, 프로세스들에게 적절한 수의 프레임을 할당해야 한다.

요구 페이징

• 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
• 요구되는 페이지만 적재하는 기법

요구 페이징은 아래의 과정으로 흘러간다.

순수 요구 페이징(pure demand paging)

• 아무런 페이지도 메모리에 적재하지 않은 채 일단 프로세스 실행
• 프로세스의 첫 명령어부터 페이지 폴트가 발생
• 어느 정도 시간이 지난 후부터 페이지 폴트 발생 빈도가 적어짐

요구 페이징이 안정적으로 작동하려면

요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 아래의 두 가지를 해결해야 한다.

• 페이지 교체
• 프레임 할당

페이지 교체 알고리즘

요구 페이징 기법으로 페이지를 적재하다 보면 언젠간 메모리가 가득 차게 된다.

메모리가 가득 찬 상황에서 당장 실행에 필요한 페이지를 적재하려면 기존에 적재된 페이지를 보조기억장치로 내보내야 한다.

이때, '기존에 적재된 페이지 중에 어떤 페이지를 내보낼 것인가'를 선택하는 것이 페이지 교체 알고리즘이다.

교체 알고리즘의 성능을 판단할 때 가장 좋다고 보는 것은 페이지 폴트의 횟수가 가장 적은 알고리즘이다.

페이지 폴트가 자주 발생하면 보조기억장치에 접근하는 횟수가 증가한다는 뜻이기 때문이다.

그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 한다.

그리고 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있다.

페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지 열을 의미한다.

예를 들어
2 2 2 3 5 5 5 3 7이라는 연속된 페이지열이 있다고 하면
페이지 참조열은
2 3 5 3 7이다.

• 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.
• 페이지 교체 알고리즘을 평가할 때 관심 있게 고려할 것은 오직 페이지 폴트의 발생 횟수이기 때문이고, 어차피 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않아도 된다.

FIFO(First-In First-Out) 페이지 교체 알고리즘

• 가장 단순한 방식
• 메모리에 가장 먼저 적재된 페이지부터 교체되는 알고리즘
• 프로그램 실행 내내 사용될 페이지조차 오래되면 교체되기 때문에 페이지 폴트가 빈번하게 일어날 수 있다

2차 기회(second-chance) 페이지 교체 알고리즘
-FIFO 페이지 교체 알고리즘의 단점을 보완
-페이지의 참조 비트가 1일 경우(페이지를 참조한 적이 있을 경우) 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 변경
-메모리에 오래 적재되었더라도 CPU가 최근에 접근한 적이 있다면 교체를 미룬다.

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
• 사용 빈도가 가장 낮은 페이지를 예측하여 해당 페이지를 교체하는 알고리즘
• 실제 구현이 매우 어렵다.(예측을 하는 것이 까다롭다)
• 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용
• 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 다른 페이지 교체 알고리즘에서 발생하는 페이지 폴트의 하한선으로 간주(평가 목적)

LRU(Least Recently Used) 페이지 교체 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
• 페이지마다 마지막으로 사용한 시간을 토대로 가장 사용이 적었던 페이지를 교체

스레싱과 프레임 할당

스레싱(thrashing)

페이지 폴트가 자주 발생하는 이유는 아래와 같다.

• 나쁜 페이지 교체 알고리즘을 사용해서
• 프로세스가 사용할 수 있는 프레임 자체가 적어서(메모리 용량이 적어서) (근본적인 이유)

프로세스가 사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트 빈도는 감소한다

반대로 프로세스가 사용할 수 있는 프레임 수가 적어지면 페이지 폴트는 자주 발생한다.

페이지 폴트로 인한 페이지 교체 빈도가 올라가면 성능은 크게 저하된다.

이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱이라고 한다.

스래싱을 그래프로 표현하면 아래와 같다.

• x축(멀티프로그래밍의 정도) : 메모리에서 동시 실행되는 프로세스의 수
• y축(CPU 이용률) : 말 그대로 CPU 이용률을 뜻한다
• 이 그래프는 동시에 실행되는 프로세스의 수를 늘린다고 해서 CPU 이용률이 비례해서 증가하는 것이 아님을 나타냄
• 아무리 CPU의 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리적 메모리 용량이 적다면 전체 컴퓨터의 성능이 나빠진다.

스레싱이 발생하는 근본적 원인은 각 프로세스가 필요로 하는 프레임 수가 보장되지 않았기 때문이다.

예를 들어, A 프로세스는 최소 10개의 프레임이 필요한데, 5개의 프레임 밖에 없다면 페이지 폴트가 자주 발생한다.

따라서 스레싱 발생 위험도 높아진다.

그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.

프레임 할당

정적 할당 방식

• 균등 할당(equal allocation) : 모든 프로세스들에게 균등하게 프레임을 할당하는 방식(프로세스들의 크기는 각기 다른데 모두 동일하게 할당)
• 비례 할당(proportonal allocation) : 프로세스의 크기에 비례하여 프레임을 할당하는 방식

균등 할당은 기초대사량이 많은 사람과 적은 사람에게 모두 동일한 양의 음식을 주는 것과 같다.

비례 할당은 프로세스의 크기가 클지라도 막상 실행해 보면 많은 프레임을 필요로 하지 않는 경우(지역성이 높은 프로그램)도 많다.

위 두 방식은 단순히 프로세스의 크기와 물리 메모리의 크기만 고려한 방식이라는 점에서 정적 할당 방식이라고 한다.

즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많다.  

동적 할당 방식

프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 아래 두 가지 방법이 있다.

• 작업 집합 모델(working set model) : '프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 방지하는 방식
• 페이지 폴트 빈도(PFF:Page-Fault Frequency) : 페이지 폴트의 빈도수의 상한선과 하한선을 정하여, 상한선이면 프레임을 더 할당하고, 하한선이라면 프레임을 회수하는 방식

작업 집합을 구하는 방법
작업 집합 : 프로세스가 일정 기간 동안 참조한 페이지 집합

페이지 폴트 빈도

-상한선이라면 프레임을 더 할당함
-하한선이라면 프레임을 회수함

작업 집합 모델과 페이지 폴트 빈도는 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고 한다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

연속 메모리 할당의 문제점은 아래와 같다.

• 외부 단편화
• 물리 메모리의 크기보다 크기가 큰 프로세스 실행 불가

예를 들어 램 용량이 4GB인데 프로세스 크기가 5GB면 실행할 수 없는 것이다.

하지만 가상 메모리(virtual memory)를 이용하면 이게 가능하다. 또한 외부 단편화 문제도 해결할 수 있다.

가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.

가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있지만, 페이징 기법이 일반적으로 더 많이 사용된다.

따라서 이 글에서는 페이징 관리 기법만 다루겠다.

페이징(Paging)

• 메모리 연속 할당에서 외부 단편화가 발생했던 근본적 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.
• 아래의 그림처럼 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로 할당할 수 있다면 외부 단편화는 발생하지 않는다.

페이징의 기본 개념

• 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
• 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 일정한 단위로 자른 뒤
• 페이지를 프레임에 할당하는 가상 메모리 관리 기법

페이징에서 스와핑

• 페이징에서도 스와핑 사용 가능
• 페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 인/아웃이 아닌, 페이지 단위로 스왑 인/아웃이 된다.
• 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
• 실행에 필요한 페이지들은 메모리로 스왑 인

이렇게 스와핑을 함으로써 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없게 된다.

즉, 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있다.

이와 같은 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블(Page Table)

페이징을 사용하면 아래의 문제를 해결해야 한다.

• 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 일일이 알기가 어렵다.
• 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없다.
• CPU 입장에서 다음에 실행할 명령어 위치를 찾기가 어려워진다.

이를 해결하기 위해 페이지 테이블이라는 개념을 도입한다.

페이지 테이블이란 물리 주소(실제 메모리 주소)에 불연속적으로 배치되더라도 논리 주소(CPU가 인식하는 주소)에는 연속적으로 배치되도록 하는 방법이다.

즉, 페이지 번호와 프레임 번호를 매핑시킨 것을 나타낸 표이다. 또한 프로세스마다 페이지 테이블이 있다.

이렇게 하면 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU입장에서는 연속적으로 보일 수 있다.

즉 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

페이징은 외부 단편화는 해결하지만, 내부 단편화는 막을 수 없다.
페이징은 프로세스의 논리 주소공간을 페이지라는 일정한 크기로 자른다. 하지만 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다.
예를 들어, 페이지 크기가 10KB인데 프로세스 크기가 108KB라면 마지막 페이지는 2KB가 남는다.
이러한 메모리 낭비는 페이징에서는 해결할 수 없다.

페이지 테이블 베이스 레지스터(PTBR)

프로세스들은 각기 페이지 테이블이 있고, 각 페이지 테이블은 CPU 내의 PTBR이 가리킨다.

즉, PTBR은 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.

각 프로세스들의 페이지 테이블 정보들은 각 프로세스 PCB에 기록된다. 그리고 프로세스의 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경된다.

Translation Lookaside Buffer(TLB)

페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어난다.

1. 메모리에 있는 페이지 테이블을 보기 위해
2. 테이블을 통해 알게 된 프레임에 접근하기 위해

이렇게 총 두 번의 메모리 접근이 필요하기 때문이다.

이와 같은 문제를 해결하기 위해 TLB를 사용한다.

• TLB : CPU 근처에 있는 페이지 테이블의 캐시 메모리
• 참조 지역성에 근거해 페이지 테이블의 일부를 가져와 저장

TLB 히트 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우

• 이 경우는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다.

TLB 미스 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 을 경우

• 이 경우는 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근해야 한다.

페이징에서의 주소 변환(Mapping)

하나의 페이지 혹은 프레인은 여러 주소를 포괄하고 있다. 그렇기 때문에 특정 주소에 접근하려면 아래와 같은 정보가 필요하다

• 어떤 페이지 혹은 프레임에 접근하고 싶은지
• 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

이렇기 때문에 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(page number)와 변위(offset)로 이뤄져 있다.

예를 들어
CPU가 32비트 주소를 보냈다면 이 중 N비트는 페이지 번호, 32-N비트는 변위로 이뤄져 있다

• <페이지 번호, 변위>로 이뤄진 논리 주소는 페이지 테이블을 통해 <프레임 번호, 변위>로 이뤄진 물리 주소로 변환된다.

페이지와 프레임은 단위가 같기 때문에
논리 주소의 변위와 물리 주소의 변위 값은 같다.

예를 들어

논리주소 <5,2>는 <1,2>로 변환되고 CPU는 10번지에 접근하게 된다.

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

페이지 테이블 안에 있는 각각의 행(row)들을 페이지 테이블 엔트리라고 한다.

페이지 테이블 엔트리에 담기는 정보로 페이지 번호, 프레임 번호뿐만 아니라 유효 비트, 보호 비트, 참조 비트, 수정 비트 등이 담긴다.

유효 비트(valid bit)

유효 비트는 현재 해당 페이지에 접근 가능한지 여부를 나타낸다.

• 프레임 번호 다음으로 중요한 정보
• 현재 페이지가 메모리에 적재되어 있는지 보조기억장치에 있는지를 알려주는 비트(스와핑)
• 유효 비트가 1 : 페이지가 메모리에 적재되어 있음
• 유효 비트가 0 : 페이지가 메모리에 적재되어 있지 않음

페이지 폴트(page fault)
CPU가 유효 비트가 0인 메모리(메모리에 적재되어 있지 않은 페이지)에 접근하려고 하면 페이지 폴트라는 예외(Exception)가 발생한다.
CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사하다

보호 비트(protection bit)

• 페이지 보호 기능을 위해 존재하는 비트
• 읽고 쓰기가 모두 가능한 페이지인지, 읽기만 가능한 페이지인지를 나타냄
• 보호 비트가 0 : 읽기만 가능한 페이지를 뜻함
• 보호 비트가 1 : 읽고 쓰기가 모두 가능한 페이지를 뜻함

프로세스를 이루는 요소 중 코드 영역은 읽기 전용 영역이다.

이러한 읽기 전용 페이지에 쓰기 시도를 하면 운영체제가 이를 막아준다.

이와 같은 방식으로 페이지들을 보호한다.

보호 비트는 세 개의 비트로 조금 더 복잡하게 구현할 수도 있다.

읽기(Read)를 나타내는 r, 쓰기(Write)를 나타내는 w, 실행(eXecute)을 나타내는 x의 조합으로 읽기, 쓰기, 실행하기 권한의 조합을 나타낸다.

참조 비트(reference bit)

• CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냄
• 참조 비트가 1 : 적재 이후 CPU가 읽거나 쓴 페이지를 뜻함
• 참조 비트가 0 : 적재 이후 CPU가 한 번도 읽거나 쓴 적이 없는 페이지를 뜻함

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

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 나타냄
• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단
• 수정 비트가 1 : 변경된 적이 있는 페이지를 뜻함
• 수정 비트가 0 : 변경된 적이 없는 페이지를 뜻함

CPU는 메모리를 읽는 것뿐만 아니라 메모리에 값을 쓰기도 하는데, 한 번도 수정된 적이 없는 페이지가 스왑 아웃될 경우 아무런 추가 작업을 하지 않아도 된다.

어차피 같은 페이지가 보조기억장치에 저장되어 있기 때문이다.

반대로 수정된 적이 있는 경우, 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 하기 때문에 이러한 작업이 필요한지 아닌지를 판단하기 위해 수정 비트가 존재하는 것이다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

프로세스에 연속적인 메모리 공간을 할당하는 방식을 연속 메모리 할당 방식이라고 한다.

스와핑(Swaping)

현재 실행되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 메모리에 생긴 빈 공간에 새로운 프로세스를 적재시키는 방법

• 스왑 영역(swap space) : 프로세스들이 쫓겨나서 머무는 보조기억장치의 일부 영역
• 스왑 아웃(swap out) : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
• 스왑 인(swap in) : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
• 스왑 아웃되었던 프로세스가 다시 스왑 인이 될 때는 이전 물리 주소와 다른 주소에 적재될 수 있음

스와핑을 이용하면 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 크더라도 모든 프로세스를 동시 실행할 수 있다.

아래 그림은 스와핑을 이용하여 프로세스들을 모두 실행시키는 것을 나타낸 것이고, 검은색 영역은 프로세스를 적재할 수 있는 메모리 영역을 나타낸다.

메모리 할당

프로세스는 메모리의 빈 공간에 할당되어야 한다.

빈 공간이 여러 개 있다면 어떤 공간에 메모리를 할당할지에 대한 방법으로 아래의 세 가지가 있다.

• 최초 적합(first-fit)
• 최적 적합(best-fit)
• 최악 적합(worst-fit)

아래의 설명에서 각 예시들은 모두 200MB 메모리에서 새로 적재할 프로세스가 20MB라고 가정한다.

최초 적합

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
• 적재할만한 공간을 찾으면 바로 할당하기 때문에 다른 방식보다 탐색시간이 적고, 빠른 할당이 가능함

최적 적합

• 운영체제가 빈 공간을 모두 검색해 본 뒤, 적재 가능한 가장 작은 공간에 할당하는 방식

최악 적합

• 운영체제가 빈 공간을 모두 검색해 본 뒤, 적재 가능한 가장 큰 공간에 할당하는 방식

단편화(external fragmentation)

• 주기억장치에 프로그램을 할당하고 반납하는 과정에서 발생하는 사용되지 않는 작은 조각 공간을 뜻한다.
• 주기억장치 상에서 빈번하게 기억장소가 할당되고 반납됨에 따라 기억장소들이 조각들로 나누어지는 현상을 뜻하기도 한다.

최초 적합, 최적 적합, 최악 적합 모두 단편화를 피해갈 수 없다.

단편화에는 내부 단편화와 외부 단편화가 있다.

내부 단편화(internal fragmentation)

• 내부 단편화란 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말한다. 

위와 같이 100MB의 메모리에 80MB 크기의 프로세스를 올리게 되면, 20MB가 남게 된다.

즉, 이렇게 적은 크기의 잔여 메모리가 발생해 해당 메모리를 사용할 수 없게 되는 것을 내부 단편화라고 한다.

외부 단편화(external fragmentation) 

• 외부 단편화란 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적(contiguous)이지 않아 발생하는 현상이다.

위와 같이 남아있는 메모리 공간은 50MB + 50MB = 100MB로 요청한 메모리 공간 80MB보다 크지만, 남아있는 공간이 연속적이지 않아서, Process C를 할당할 수가 없게 된다.

따라서 남아있는 메모리 공간이 낭비되게 되는 문제가 발생한다.

이를 외부 단편화라고 한다.

외부 단편화 해결방안 : 압축(compaction)

• 외부 단편화 문제를 해결하기 위해서 압축 기법을 사용할 수 있다.
• 압축 기법은 주기억장치 내 분산되어 있는 단편화된 공간들을 통합하여 하나의 커다란 빈 공간을 만드는 작업을 의미한다.

아래의 그림은 외부 단편화가 발생한 상황을 나타낸 그림이다.

이 상황에서 프로세스 D를 B 밑으로 이동시키면 된다.

즉, 프로세스 A, B, D를 연속적으로 할당시키면 빈 공간이 연속적으로 100MB가 되어 80MB인 프로세스 C를 적재시킬 수 있게 된다.

하지만 압축이 무조건 좋은 점만 있는 것은 아니다. 압축의 단점은 아래와 같다.

• 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 작업을 중지해야 한다.
• 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기가 어렵다.
• 메모리에 있는 내용을 옮기는(압축하는) 작업은 많은 오버헤드를 야기한다.

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

운영체제는 아래의 방법으로 교착 상태를 해결한다.

• 예방 : 애초에 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배
• 회피 : 교착 상태가 발생하지 않을 정도로 조금씩 자원을 할당하다가 교착 상태의 위험이 있으면 자원을 할당을 멈춤
• 검출 후 회복 : 자원을 제약 없이 할당하다가 교착 상태가 검출되면, 교착 상태를 회복

교착 상태 예방

애초에 교착 상태가 발생하지 않도록, 교착 상태 발생조건(상호배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애는 것이다.

상호 배제를 없애기

• 모든 자원을 공유 가능하게 만든다
• 상호 배제를 없애면 동기화를 할 때 큰 문제가 될 수 있다.
• 현실적으로 불가능

점유와 대기를 없애기

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
• 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다.
• 자원을 많이 필요로 하는 프로세스가 무한정 기다리게 되므로 기아 현상을 야기할 우려가 있다.

비선점 조건을 없애기(선점형으로 변환)

• 선점이 가능한 자원(CPU 등)에 한에 효과적
• 선점이 불가능한 자원(프린터 등)은 불가능
• 범용성이 떨어지는 방법

원형 대기 조건을 없애기

모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.

• 앞선 세 방식에 비해서 비교적 현실적이다.
• 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것이 쉽지 않다.
• 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 달라진다.

위 그림은 교착 상태의 대표적인 예시인 식사하는 철학자 문제이다.

식사하는 철학자 문제에서 모든 포크에 1번부터 5번까지 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크에서 높은 포크 순으로 집어 들게 한다면 원형 대기는 발생하지 않는다.

왜냐하면 5번 포크를 집어들고 1번 포크를 집어들 수 없기 때문이다.

이는 마치 철학자들이 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사를 하는 상황과 유사하다.

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼만 자원을 할당

교착 상태 회피에 대해 깊이 알려면 아래의 용어를 알아야 한다.

• 안전 순서열(safe seqnence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태(safe state) : 교착 상태 없이 프로세스가 자원을 할당받고 종료될 수 있는 상태, 안전 순서열이 있는 상태
• 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상태, 안전 순서열이 없는 상태

예를 들어 A, B, C 프로세스가 동시에 운영체제에 자원을 요청한 상황에서 B -> A -> C 순서로 자원을 할당하면 교착 상태가 발생하지 않는다고 가정하면 B -> A -> C가 안전 순서열이 된다.

안전 순서열이 있는 상태를 안전 상태이고, 없는 상태가 불완전 상태이다.

운영체제는 교착 상태를 회피하기 위해 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다.

즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이다.

교착 상태 회피 예제

• 컴퓨터 시스템에 총 12개의 자원이 있다고 가정
• 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 실행 중이라 가정
• 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정

프로세스와 스레드는 우선 자원을 운영체제에게 요청하고, 운영체제로부터 자원을 할당받아 사용하고, 자원 사용이 끝나면 자원을 반환한다.

안전 상태

이 상태는 안전 상태이다. P2 -> P1 -> P3이라는 안전 순서열이 있기 때문이다.

왜냐하면 각 프로세스들이 최대로 자원을 요구한 최악의 상황이라면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
3. 이미 자원을 2개 점유하고 있던 P3는 남은 자원에서 7개를 추가적으로 할당 받아 작업을 끝내고 쓰던 모든 자원을 반환한다.

불안전 상태

이번에는 P3가 2개의 자원을 쓰고있는 상태가 아니라 3개의 자원을 쓰고 있는 상태라 가정

이는 불안전 상태이다. 즉, 안전 순서열이 없으므로 교착 상태가 일어날 수 있다.

예를 들어, 최악의 상황인 각 프로세스가 최대로 자원을 요구하면 시나리오는 아래와 같다.

1. 이미 자원 2개를 점유하고 있던 P2는 남은 자원에서 2개를 추가적으로 할당받아 작업을 끝내고 쓰던 모든 자원을 반환한다.
2. 이미 자원을 5개 점유하고 있던 P1은 남은 자원에서 5개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
3. 이미 자원을 3개 점유하고 있던 P3은 남은 자원에서 6개를 추가적으로 할당받고 싶지만, 남은 자원이 4개이므로 작업을 완료할 수 없게 된다.
4. 교착 상태에 빠진다.

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 회복에는 선점을 통한 회복과 프로세스 강제 종료를 통한 회복이 있다.

선점을 통한 회복

• 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당

프로세스 강제 종료를 통한 회복

프로세스 강제 종료를 통한 회복에는 아래의 두 가지 방법이 있다.

• 교착 상태에 놓인 프로세스를 모두 강제 종료하는 방법(작업 내역을 잃을 위험)
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(교착 상태가 해결되었는지 확인하는 과정에서 오버헤드 발생)

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

교착 상태(Deadlock)

교착 상태의 정의 : 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

예를 들어, 아래와 같은 상황을 교착 상태라고 말할 수 있다.

• 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용을 기다림
• 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다림

또 다른 교착상태의 예를 들면 식사하는 철학자 문제가 있다.

식사하는 철학자 문제에서 한두 명의 철학자가 식사를 할 때는 문제가 되지 않지만, 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없다.(교착 상태)

자원 할당 그래프(resource-allocation graph)

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는 지를 표현하는 간단한 그래프이다.

자원 할당 그래프는 아래와 같은 규칙으로 그려진다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

자원할당 그래프 예제

• SSD자원은 세 개, CPU 자원은 두 개, 프린터는 하나
• 프로세스 A는 SSD를 할당받아 사용 중, 프로세스 B와 C는 CPU를 할당받아 사용 중, 프로세스 D는 프린터를 사용 중
• 프로세스 E는 프린터 자원을, 프로세스 F는 CPU 자원의 할당을 기다리는 중

교착 상태 발생 조건

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

위에서 교착 상태 예제로 들었던 상태들을 자원 할당 그래프로 나타내면 아래와 같다.