> For the complete documentation index, see [llms.txt](https://cs-study.gitbook.io/os-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs-study.gitbook.io/os-study/11..md).

# 11. 프레임 할당, 파일 할당

발표자: 김성연

## 프레임 할당 (Allocation of Frames)

### 쓰레싱 (Thrashing)

* I/O 작업이 증가하여 CPU 이용률이 떨어지는 현상

* 프로세스 개수가 증가 → CPU의 이용률 증가 → 일정 범위를 넘어서면 오히려 CPU 이용률이 감소하는 현상 발생

* 원인

  * 빈번한 페이지 교체로 인한 i/o 시간 증가
  * page in/out 작업 → 디스크 I/O 작업으로 CPU를 사용하지 않는 작업

* 해결 방법
  * Global Replacement보다 Local Replacement를 사용 → 메모리 사용 효율이 떨어지는 단점
  * 프로세스당 충분한/적절한 수의 프레임(메모리)을 할당

### 정적 할당 (Static Allocation)

* 동일 할당(Equal Allocation)

  * 모든 프로세스에 똑같은 수의 프레임을 할당 → 프로세스의 크기에 따라 매우 비효율적

* 비례 할당(Proportional Allocation)
  * 프로세스의 크기에 따라 프레임을 할당 → 프로세스 크기가 크더라도 모든 기능을 사용하지 않기 때문에 비효율적

### 동적 할당 (Dynamic Allocation)

#### Working Set Model

* locality

  * Locality 성질 이용 → 특정 시간에는 일정 범위의 페이지를 주로 참조
  * 특정 시간에 따라 사용하는 페이지의 개수만큼 프레임을 할당
  * 프로세스를 미리 수행해봐야 할 수 있다는 단점
  * 프로세스를 수행할 때마다 사용하는 기능이 달라질 수 있기 때문에 비현실적

* working set
  * locality의 방식과 유사
  * 과거 기록을 보고 예측
  * working set → 현재 시간에서 일정 시간 이전동안 사용되었던 페이지의 집합
  * 시간은 운영체제 내부에서 정하는 기준에 따라 다르며, 이를 working set window 라고함
  * working set의 개수만큼 프레임을 할당

####

#### Page-Fault Frequency(PFF)

* 페이지 부재의 비율은 프로세스에 할당된 프레임의 수에 반비례
* 페이지 폴트 발생 비율의 상한선과 하한선을 설정
* 상한선 초과 프로세스에 더 많은 프레임을 할당하고 하한선 이하 프로세스의 프레임은 회수하는 방식

## 파일 할당 (File Allocation)

{% hint style="info" %}
 각각의 파일에 대해 free block을 어떻게 할당할 것인가?
{% endhint %}

### 하드 디스크의 구조

> **Sector**: 자체적으로 주소를 가지는 스토리지 단위, 트랙의 재 분할, sector size는 일반적으로 512 bytes이며 주로 여러 개를 묶어서 사용 **Track**: 동심원 형태의 영역, 데이터가 기록되는 부분 **Cylinder**: 모든 platter에서 같은 track 위치의 집합 **Block**: sector 집합, 분할 처리 단위 (하드디스크는 블록 단위로 읽고 쓰기 때문에 block device 라고 불리기도 함)

<figure><img src="https://1131902653-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fexfu4hpVR2H9xLvepQp6%2Fuploads%2F8tZ6hd7B8PJ0lGTD258v%2Fimage.png?alt=media&amp;token=475968d3-adb3-4a9f-88b3-302ef87d868f" alt=""><figcaption></figcaption></figure>

###

###

### 연속 할당 (Contiguous Allocation)

<figure><img src="https://1131902653-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fexfu4hpVR2H9xLvepQp6%2Fuploads%2F5U65HNmgKP6WIgG8QgRk%2Fimage.png?alt=media&amp;token=acaa06e3-a4c9-4233-a25e-53e713ee315e" alt=""><figcaption></figcaption></figure>

* 각 파일에 대해 디스크 상의 연속된 블록을 할당

* 장점

  * 디스크 헤더의 이동 최소화 → 빠른 i/o 성능
  * 순차 접근(sequential access) 가능 → 순서대로 읽어옴
  * 직접 접근(direct access) 가능 → 특정 부분을 바로 읽어옴 (디렉토리에서 시작 블록 넘버 정보 이용)

* 단점
  * 외부 단편화: 파일이 삭제되면 홀이 생긴다 → 반복적인 생성과 삭제로 흩어져있는 다수의 홀 발생
  * 외부 단편화로 인한 디스크 공간 낭비
  * 파일을 저장할 때 실제 크기를 알 수 없고, 지속적인 사용으로 파일의 크기가 계속 증가할 수 있기 때문에 기존 홀 배치(연속 할당)는 부적절함

### 연결 할당 (Linked Allocation)

<figure><img src="https://1131902653-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fexfu4hpVR2H9xLvepQp6%2Fuploads%2FlrfMBD5buFEBKdA3gaRM%2Fimage.png?alt=media&amp;token=bdf6804e-df37-4edd-bdca-2cb302bc1290" alt=""><figcaption></figcaption></figure>

* 연결 할당은 연속 할당의 문제점을 해결하기 위해 나온 방법

* 연결 리스트(linked list) 와 같은 방식으로 파일을 할당

* 특징

  * 마지막에 \*\*주소를 저장하는 포인터 공간(4bytes)\*\*이 존재
  * 마지막 블록의 포인터 공간에는 끝임을 나타내는 값이 저장

* 장점

  * 연결 할당은 위치와 상관없이 할당이 가능하므로 외부 단편화 문제 없음 → 디스크 낭비 없음
  * 순차 접근 가능

* 단점
  * 직접 접근 불가능 → 파일의 블록들은 모두 흩어져 있으므로 시작 블록 번호를 가지고는 원하는 위치의 블록에 바로 접근 불가
  * 포인터를 저장으로 4 bytes 이상의 손해 발생
  * 낮은 신뢰성 → 중간 블록의 포인터가 끊어지면 그 이후의 모든 블록에 접근 불가
  * 느린 속도 → 블록이 모두 흩어져 있으므로 디스크 헤더의 움직임 증가

####

#### **FAT(File Allocation Table) 시스템**

<figure><img src="https://1131902653-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fexfu4hpVR2H9xLvepQp6%2Fuploads%2FLwgEWd91uJ1tTTbWKaTm%2Fimage.png?alt=media&amp;token=9567fff6-4d49-43e3-a871-d122ef65ccce" alt=""><figcaption></figcaption></figure>

* 다음 블록을 가리키는 포인터들만 모아서 하나의 테이블(FAT)을 만들어 한 블록에 저장하는 방식
* 특징
  * 직접 접근 가능
  * FAT만 문제가 없다면 중간 블록에 문제가 생겨도 그 다음 블록을 읽는 것이 가능
  * 디스크 헤더가 움직는 것은 블록이 흩어져 있으므로 여전히 느림
  * 손실 시 복구를 위해 이중 저장
  * FAT의 각 인덱스 크기는 전체 블록의 개수를 저장할 만큼의 크기를 가지고 있어야 하는데, 현재는 일반적으로 32bit 크기를 사용 → FAT32 (이전에는 FAT16, FAT12 등이 있었음)

### 색인 할당 (Indexed Allocation)

<figure><img src="https://1131902653-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Fexfu4hpVR2H9xLvepQp6%2Fuploads%2Fkwpj2jseEhuy4MrcLhPT%2Fimage.png?alt=media&amp;token=ea3f200e-1267-4c78-ac27-2d5b623e6a38" alt=""><figcaption></figcaption></figure>

* 데이터를 랜덤한 블록 번호에 할당하지만 할당된 블록 번호(포인터)를 하나의 블록에 따로 저장(인덱스 블록)
* 특징
  * 파일 당 하나의 인덱스 블록이 존재
  * 디렉토리 정보에 시작 블록 번호가 아닌 인덱스 블록 번호를 저장
* 장점
  * 직접 접근 가능
  * 외부 단편화 없음
* 단점
  * 인덱스 블록 할당에 따른 저장 공간 손실
  * 하나의 인덱스 블록을 가지고는 크기가 큰 파일을 저장 불가 → Linked, Multilevel index, Combined 등으로 해결

####

####

#### 색인 할당 단점 보완

* Linked
  * 인덱스 블록을 여러 개 만들어 연결 할당
  * 각 인덱스 블록의 마지막에 다음 인덱스 블록을 가리키는 포인터 저장

![https://user-images.githubusercontent.com/34755287/57186871-7344bf80-6f21-11e9-93a2-ded535b8b74b.png](https://user-images.githubusercontent.com/34755287/57186871-7344bf80-6f21-11e9-93a2-ded535b8b74b.png)

* Multilevel index
  * 하나의 인덱스 블록의 **모든 포인터**가 다른 인덱스 블록을 가리킴

![https://user-images.githubusercontent.com/34755287/57186872-7344bf80-6f21-11e9-84ac-4fe150977f63.png](https://user-images.githubusercontent.com/34755287/57186872-7344bf80-6f21-11e9-84ac-4fe150977f63.png)

* Combined
  * Linked + Multilevel index
  * 한 인덱스 블록의 포인터들은 데이터 블록과 또 다른 인덱스 블록 둘 다 가리킬 수 있음

## 참고 자료

* [\[운영체제(OS)\] 17. 프레임 할당](https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-17.-%ED%94%84%EB%A0%88%EC%9E%84-%ED%95%A0%EB%8B%B9)
* [\[운영체제(OS)\] 18. 파일 할당](https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-18.-%ED%8C%8C%EC%9D%BC-%ED%95%A0%EB%8B%B9)
* [하드디스크의 구조 (Hard Disk Drive) 플래터, 섹터, 실린더](https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true\&blogId=capemay\&logNo=220221154613) &#x20;
* [운영체제(OS)와 컴퓨터 시스템 - 디스크](https://www.inflearn.com/blogs/1970)

  <br>

  <br>

<br>