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)

각각의 파일에 대해 free block을 어떻게 할당할 것인가?

하드 디스크의 구조

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

연속 할당 (Contiguous Allocation)

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

• 장점

  • 디스크 헤더의 이동 최소화 → 빠른 i/o 성능

  • 순차 접근(sequential access) 가능 → 순서대로 읽어옴

  • 직접 접근(direct access) 가능 → 특정 부분을 바로 읽어옴 (디렉토리에서 시작 블록 넘버 정보 이용)

• 단점

  • 외부 단편화: 파일이 삭제되면 홀이 생긴다 → 반복적인 생성과 삭제로 흩어져있는 다수의 홀 발생

  • 외부 단편화로 인한 디스크 공간 낭비

  • 파일을 저장할 때 실제 크기를 알 수 없고, 지속적인 사용으로 파일의 크기가 계속 증가할 수 있기 때문에 기존 홀 배치(연속 할당)는 부적절함

연결 할당 (Linked Allocation)

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

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

• 특징

  • 마지막에 **주소를 저장하는 포인터 공간(4bytes)**이 존재

  • 마지막 블록의 포인터 공간에는 끝임을 나타내는 값이 저장

• 장점

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

  • 순차 접근 가능

• 단점

  • 직접 접근 불가능 → 파일의 블록들은 모두 흩어져 있으므로 시작 블록 번호를 가지고는 원하는 위치의 블록에 바로 접근 불가

  • 포인터를 저장으로 4 bytes 이상의 손해 발생

  • 낮은 신뢰성 → 중간 블록의 포인터가 끊어지면 그 이후의 모든 블록에 접근 불가

  • 느린 속도 → 블록이 모두 흩어져 있으므로 디스크 헤더의 움직임 증가

FAT(File Allocation Table) 시스템

• 다음 블록을 가리키는 포인터들만 모아서 하나의 테이블(FAT)을 만들어 한 블록에 저장하는 방식

• 특징

  • 직접 접근 가능

  • FAT만 문제가 없다면 중간 블록에 문제가 생겨도 그 다음 블록을 읽는 것이 가능

  • 디스크 헤더가 움직는 것은 블록이 흩어져 있으므로 여전히 느림

  • 손실 시 복구를 위해 이중 저장

  • FAT의 각 인덱스 크기는 전체 블록의 개수를 저장할 만큼의 크기를 가지고 있어야 하는데, 현재는 일반적으로 32bit 크기를 사용 → FAT32 (이전에는 FAT16, FAT12 등이 있었음)

색인 할당 (Indexed Allocation)

• 데이터를 랜덤한 블록 번호에 할당하지만 할당된 블록 번호(포인터)를 하나의 블록에 따로 저장(인덱스 블록)

• 특징

  • 파일 당 하나의 인덱스 블록이 존재

  • 디렉토리 정보에 시작 블록 번호가 아닌 인덱스 블록 번호를 저장

• 장점

  • 직접 접근 가능

  • 외부 단편화 없음

• 단점

  • 인덱스 블록 할당에 따른 저장 공간 손실

  • 하나의 인덱스 블록을 가지고는 크기가 큰 파일을 저장 불가 → Linked, Multilevel index, Combined 등으로 해결

색인 할당 단점 보완

• Linked

  • 인덱스 블록을 여러 개 만들어 연결 할당

  • 각 인덱스 블록의 마지막에 다음 인덱스 블록을 가리키는 포인터 저장

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

• Combined

  • Linked + Multilevel index

  • 한 인덱스 블록의 포인터들은 데이터 블록과 또 다른 인덱스 블록 둘 다 가리킬 수 있음

참고 자료

• [운영체제(OS)] 17. 프레임 할당

• [운영체제(OS)] 18. 파일 할당

• 하드디스크의 구조 (Hard Disk Drive) 플래터, 섹터, 실린더

• 운영체제(OS)와 컴퓨터 시스템 - 디스크