[혼공컴운] 6주차 Chapter 14~15

yeon·2024년 2월 15일

기본 문제

p.400의 확인 문제 1번 풀고 인증하기

1. 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

[보기] 최초 적합, 최적 적합, 최악 적합

( ① ): 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
( ② ): 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
( ③ ): 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

정답
①: 최초 적합, ②: 최악 적합, ③: 최적 적합

선택 문제

ch.14 (14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423'일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

정답
페이지 폴트 3회 발생

내용 정리

14-1. 연속 메모리 할당

스와핑 (swaping): 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법

최초 적합 (first fit): 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식

최적 적합 (best fit): 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

최악 적합 (worst fit): 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식

외부 단편화 (external fragmentation): 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 의미

기본적인 메모리 관리 기법 (연속 메모리 할당)

스와핑 (swapping)

프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있음
스왑 영역 (swap space): 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
스왑 아웃 (swap-out): 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
스왑 인 (swap-in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

메모리 할당 (메모리에 프로세스를 할당하는 방식)

최초 적합 (first fit)
- 검색 최소화, 빠른 할당 가능
최적 적합 (best fit)
최악 적합 (worst fit)

-> 두 방식 모두 외부 단편화 (external fragmentation) 발생 (연속 메모리 할당의 부작용)

외부 단편화를 해결할 수 있는 대표적인 방안

메모리 압축 (compaction)
- 메모리 내에 저장된 프로세스를 적당히 재배치시켜 작은 빈 공간들을 하나의 큰 빈 공간으로 만듦
- 단점: 많은 오버헤드 야기, 최적의 압축 방법 결정하기 어려움
페이징 기법

14-2. 페이징을 통한 가상 메모리 관리

페이징 (paging): 물리 주소 공간을 프레임 단위로 자르고 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법

페이지 테이블을 통해 페이지가 적재된 프레임을 찾을 수 있음. 페이지 테이블에는 페이지 번호와 프레임 번호뿐만 아니라 유효 비트, 보호 비트, 접근 비트, 수정 비트 등이 있음

PTBR (Page Table Base Register): 각 프로세스의 페이지 테이블이 적재된 주소를 가리킴

TLB (Translation Lookaside Buffer): 페이지 테이블의 캐시 메모리 역할을 수행하기 위해 페이지 테이블의 일부를 저장

프로세스를 메모리에 연속적으로 할당하는 방식의 문제점
- 외부 단편화
- 물리 메모리보다 큰 프로세스를 실행할 수 없음
-> 가상 메모리 (virtual memory) 기법 사용 (페이징, 세그멘테이션 등등)

페이징 (paging)

페이지 단위로 스왑 아웃/스왓 인 (페이지 아웃/페이지 인)
- 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃, 실행에 필요한 페이지들은 메모리로 스왑 인
-> 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요X
-> 물리 메모리보다 더 큰 프로세스 실행할 수 있음

페이지 테이블

페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
- 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치하도록 함
-> 프로세스들이 메모리에 분산되어 저장되어 있어도, CPU는 논리 주소를 그저 순차적으로 실행하면 됨
내부 단편화 (internal fragmentation) 문제 야기
CPU 내의 페이지 테이블 베이스 레지스터 (PTBR: Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소 가리킴
페이지 테이블을 메모리에 두면, 메모리 접근 시간이 두 배로 늘어남
-> TLB (Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둠
- TLB 히트 (TLB hit): CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 (메모리 접근을 한 번으로 줄임)
- TLB 미스 (TLB miss): 메모리를 두 번 참조해야 함

페이징에서의 주소 변환

하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있음
-> 논리 주소는 페이지 번호 (page number)와 변위 (offset)로 이루어짐
-> 특정 주소에 접근 가능
논리 주소 <페이지 번호, 변위> → 물리 주소 <프레임 번호, 변위>로 변환
- 논리 주소의 변위 == 물리 주소의 변위 (페이지 크기와 프레임 크기가 같기 때문에)

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

페이지 번호
프레임 번호
유효 비트 (valid bit)
- 해당 페이지가 메모리에 적재되어 있는지 여부를 알려주는 비트
- 페이지가 메모리에 적재되어 있지 않으면 페이지 폴트 (page fault) 발생
보호 비트 (protection bit)
- 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
  ex) read, write, excute (100 -> r=1, w=0, x=0 -> read only)
참조 비트 (reference bit)
- 페이지에 접근한 적이 있는지 나타냄
- 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅됨
수정 비트 (modified bit, dirty bit)
- 해당 페이지가 수정된 적이 있는지 나타냄 (수정 비트가 1이면 변경된 적 있는 페이지)
- 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 판단하기 위해 존재
  - 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업 추가되어야 함

14-3. 페이지 교체와 프레임 할당

요구 페이징 (demand paging): 페이지가 필요할 때마다 메모리에 적재하는 기법

페이지 교체 알고리즘에는 FIFO, 최적, LRU 페이지 교체 알고리즘 등이 있음

스래싱 (thrashing): 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제를 뜻함

프레임 할당 방식에는 균등 할당과 비례 할당, 작업 집합 모델 기반과 페이지 폴트율 기반 프레임 할당 방식이 있음

요구 페이징 (demand paging)
물리 메모리의 크기는 한정되어 있기 때문에

기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 함 -> 페이지 교체
프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야 함 -> 프레임 할당

페이지 교체 알고리즘

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

적재된 페이지 순서대로 교체하는 알고리즘
프로그램 내내 사용될 페이지를 먼저 적재되었다고 해서 내쫓으면 안됨
-> 보완책: 2차 기회 페이지 교체 알고리즘 (second chance page replacement algorithm)
- 참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정함

최적 페이지 교체 알고리즘 (optimal page replacement algorithm)

앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
실제 구현이 어려움. 앞으로 오랫동안 사용되지 않을 페이지 예측하기 어려움
-> 주로 다른 페이지 교체 알고리즘이 이론상 성능을 평가하기 위한 목적으로 사용

LRU 페이지 교체 알고리즘 (LRU: Least Recently Used Page Replacement Algorithm)

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

스래싱과 프레임 할당

프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생
-> 스래싱 발생
-> 프로세스들에 적절한 수만큼 프레임을 할당해줘야 함

정적 할당 방식

균등 할당 (equal allocation)
- 모든 프로세스에 동일한 프레임을 배분하는 방식
비례 할당 (proportional allocation)
- 프로세스 크기에 따라 프레임을 배분하는 방식

동적 할당 방식

프로세스의 실행을 보고 할당할 프레임 수를 결정함
작업 집합 모델 (working set) 기반 프레임 할당
- 작업 집합의 크기만큼만 프레임을 할당하는 방식
- 작업 집합 (working set): 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
페이지 폴트율 (PFF: Page-Fault Frequency) 기반 프레임 할당
- 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

+) 페이징의 이점과 계층적 페이징

fork 시스템 호출을 하면 부모 프로세스의 복사본이 자식 프로세스로서 만들어짐
-> 부모 프로세스의 메모리 영역이 다른 영역에 자식 프로세스로서 복제.
각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킴
-> 복사 작업은 프로세스 생성 시간을 늦추고 불필요한 메모리 낭비를 야기함
-> 쓰기 시 복사 (copy on write) 사용

자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킴
읽기 작업만 이어 나간다면 이 상태 지속
프로세스 생성 시간을 줄이고, 메모리 공간도 절약

계층적 페이징 (hierarchical paging)

페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
: 다단계 페이지 테이블 (multilevel page table) 기법
모든 페이지 테이블을 항상 메모리에 유지할 필요 없음 -> 메모리 낭비 줄이기
계층적 페이징을 사용하는 경우 CPU가 발생하는 논리 주소
바깥 페이지 번호 | 안쪽 페이지 번호 | 변위
- 바깥 페이지 번호: CPU와 근접한 곳에 위치한 (바깥에 위치한) 페이지 테이블 엔트리를 가리킴
- 안쪽 페이지 번호: 첫 번째 페이지 테이블 바깥에 위치한 두 번째 페이지 테이블, 즉 페이지 테이블의 페이지 번호를 가리킴
페이지 테이블의 계층이 늘어날수록, 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 많아지므로 계층이 많다고 해서 반드시 좋다고 볼 수는 없음

15-1. 파일과 디렉터리

파일은 의미 있고 관련 있는 정보를 모은 논리적인 단위

운영체제는 파일의 확장자를 통해 파일의 유형을 파악할 수 있음

파일의 속성에는 파일과 관련된 다양한 부가 정보들이 있음

디렉터리를 이용하면 여러 개의 파일 또는 디렉터리를 묶어 관리할 수 있음

경로: 디렉터리를 이용해 위치를 특징 짓는 정보

절대 경로: 루트 디렉터리부터 시작하는 경로

상대 경로: 현재 디렉터리부터 시작하는 경로

파일

보조기억장치에 저장된 관련 정보의 집합
모든 파일에는 고유한 절대 경로가 있음
운영체제는 파일을 다루기 위한 시스템 호출 제공

디렉터리

디렉터리 엔트리에는 해당 디렉터리에 저장된 대상들에 대한 정보가 담김
운영체제는 디렉터리를 다루는 다양한 시스템 호출을 제공함
최상위 디렉터리를 루트 디렉터리라고 함

15-2. 파일 시스템

파티셔닝 (partitioning): 하드 디스크나 SSD처럼 용량이 큰 저장 장치를 하나 이상의 논리적인 여러 단위로 구획하는 작업을 의미

포매팅 (formatting): 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고, 새로운 데이터를 쓸 수 있게 하는 작업을 의미

연속 할당 (contiguous allocation): 보조기억장치 내 연속적인 블록에 파일을 할당하는 방식

연결 할당 (linked allocation): 각 블록 일부에 다음 블록의 주소를 저장하여 블록들을 연결 리스트 형태로 관리하는 방식

색인 할당 (indexed allocation): 파일의 모든 블록 주소를 색인 블록 (index block)에 모아 관리하는 방식

FAT 파일 시스템: FAT를 이용하는 연결 할당 기반의 파일 시스템

유닉스 파일 시스템: i-node를 이용하는 색인 할당 기반의 파일 시스템

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

파티셔닝과 포매팅 작업을 거쳐야 파일 시스템을 이용할 수 있음
파티션마다 각기 다른 파일 시스템을 이용할 수 있음
포매팅 작업을 거치면 파일 시스템이 결정됨

파일 할당 방법
파일 시스템은 블록 단위로 파일을 읽고 씀

연속 할당 (contiguous allocation)
- 장점: 구현이 단순
- 단점: 외부 단편화 야기
불연속 할당
- 연결 할당 (linked allocation)
  - 임의 접근 (random access) 속도가 매우 느림
  - 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없음
    - FAT 파일 시스템에서는 연결 할당을 변형하여 사용
- 색인 할당 (indexed allocation)
  - 디렉터리 엔트리에 파일 이름과 더불어 색인 블록 주소를 명시
  - 파일 내 임의의 위치에 접근하기 쉬움
  - 유닉스 파일 시스템은 색인 할당 기반임

파일 시스템

FAT 파일 시스템
- 파일 할당 테이블 (FAT: File Allocation Table) 이용
  -> 임의 접근 성능, 오류 발생 시 다음 블록 접근 문제 상당 부분 해소 가능
- FAT가 메모리가 캐시될 경우, 임의 접근 성능 개선됨
- USB 메모리, SD 카드 등의 저용량 저장 장치에서 사용됨
유닉스 파일 시스템
- i-node (index-node) 이용
  -> 파일 속성 정보와 열다섯 개의 블록 주소가 저장될 수 있음
  -> i-node 크기는 유한
  -> 파일의 크기가 크면 i-node는 단일 간접 블록 (single indirect block), 이중 간접 블록 (double indirect block), 삼중 간접 블록 (triple indirect block)을 가리킴
- 유닉스 계열 운영체제에서 사용됨

yeon

이전 포스트