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
인덱스 블록을 여러 개 만들어 연결 할당
각 인덱스 블록의 마지막에 다음 인덱스 블록을 가리키는 포인터 저장
Multilevel index
하나의 인덱스 블록의 모든 포인터가 다른 인덱스 블록을 가리킴
Combined
Linked + Multilevel index
한 인덱스 블록의 포인터들은 데이터 블록과 또 다른 인덱스 블록 둘 다 가리킬 수 있음
참고 자료
Last updated
