혼공컴운 6주차 미션
1. 기본 미션 - 메모리 할당 방식
14장 14-1의 메모리 할당 참조
2. 선택 미션 - LRU 페이지 교체 알고리즘의 페이지 폴트 발생 횟수
페이지 참조열
2 3 1 3 5 2 3 4 2 3
사용할 수 있는 프레임: 3개
LRU 페이지 교체 알고리즘: 가장 오랫동안 사용하지 않은 페이지 교체
2 → 3 → 1(프레임 충만) → 3(반복) → 5(페이지 폴트, 오랫동안 사용하지 않은 2 교체) → 2(페이지 폴트, 오랫동안 사용하지 않은 1 교체) → 3(반복) → 4(페이지 폴트, 오랫동안 사용하지 않은 5 교체) → 2(반복) → 3(반복)
페이지 폴트 발생 횟수: 3회
14장 가상 메모리
14-1 연속 메모리 할당
프로세스에 연속적인 메모리 공간을 할당하는 방식
- 메모리에 적재된 프로세스 중 현재 실행되지 못하는 프로세스가 존재함
- 물리 메모리보다 큰 프로세스는 실행할 수 없음
스와핑(Swapping; 교체)
적재된 프로세스 중 실행되지 못한 프로세스들은 임시로 보조기억장치로 쫓아내어 생긴 메모리의 빈 곳에 다른 프로세스를 적재하여 실행하는 방식
→ 실제 메모리 크기보다 큰 프로세스를 동시에 실행할 수 있음
- 스왑 영역(swap space): 스와핑 되는 구역 = 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
- 스왑-아웃(swap-out): 스왑 영역으로 옮겨지는 것 (쫓겨 나감)
- 스왑-인(swap-in): 스왑 영역에 있다가 다시 메모리로 옮겨오는 것 (다시 들어옴)
메모리 할당
메모리 공간에 프로세스를 연속적으로 할당하는 방식
- 최초 적합(first fit)
최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 형식 - 최악 적합(worst fit)
프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 형식
→ 공간이 가장 낭비되는 최악의 형식 - 최적 적합(best fit)
프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 형식
→ 프로세스가 필요한 만큼의 딱 맞는 공간
외부 단편화(external fragmentation)
연속 메모리 할당에서 다양한 크기의 프로세스 실행/종료 반복 시 발생하는 빈 곳으로 인해, 프로세스를 적재할 수 없는 메모리 낭비 상황이 발생하는 현상
→ 여유 공간이 있어도 쪼개져 있어 한 번에 큰 프로세스를 적재할 수 없음
※ 내부 단편화(internal fragmetation): 일정 크기의 페이지에 프로세스를 할당할 때, 페이지보다 프로세스의 크기가 작아서 발생하는 메모리 낭비 현상 (아래 14-2의 페이징 참조)
압축(compaction; 메모리 조각 모음)
외부 단편화를 해결하기 위한 대표적인 방법
흩어진 텅 빈 공간을 하나로 모아서, 하나의 큰 공간으로 합치는 것(프로세스 재배치)
- 단점
- 압축 과정 중, 시스템의 동작이 제한된다.
- 메모리 재배치로 인한 오버헤드가 발생한다.
이러한 단점으로 오늘날에는 가상 메모리 기법 중 페이징 기법을 사용한다. (14-2)
14-2 페이징을 통한 가상 메모리 관리
가상 메모리(Virtual Memory)
실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리의 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
가상 메모리 관리 기법 → 페이징, 세그멘테이션 (참고 1, 참고 2)
페이징
프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고,
메모리 물리 주소 공간을 프레임(frame)이라는 페이지와 동일 크기 단위로 자른 뒤,
페이지를 프레임에 할당하는 가상 메모리 관리 기법
- 페이징에서의 스와핑(페이지 단위로 움직임)
- 스왑 아웃 == 페이지 아웃(page out)
- 스왑 인 == 페이지 인(page in)
페이지 테이블(page table)
프로세스가 메모리에 불연속적으로 배치되면 CPU가 다음 실행할 명령어를 찾기 어려우므로, 물리 주소에서는 불연속적으로 배치되더라도 논리 주소에서 연속적으로 배치되도록 하는 표.
다시 말해, 페이지 번호와 프레임 번호를 짝지어 주는 이정표
- 프로세스마다 각자의 프로세스 테이블을,
각 프로세스의 페이지 테이블은 메모리에 적재되고
CPU의 페이지 테이블 베이스 레지스터는
각 프로세스의 페이지 테이블이 적재된 주소를 가리킴 - 메모리 이중 접근(페이지 테이블 접근, 프레임에 접근)을 해결하기 위해 CPU에
Translation Lookable Buffer(변환 색인 버퍼)를 두어 페이지 테이블의 일부 내용을 참조 지역성의 원리에 근거해 미리 저장한다.
- TLB hit: 페이지 번호가 TLB에 있을 때
- TLB miss: 페이지 번호가 TLB에 없어 메모리에 접근해야 할 때
페이징 주소 변환
페이지와 프레임은 여러 주소를 포함하고 있으므로, 특정 주소에 접근하기 위해서는 접근하고자 하는 페이지 번호와 그로부터 얼마나 떨어져 있는지 알기 위한 변위(offset)를 통해 접근할 수 있다.
페이지 테이블 엔트리(page table "entry" - 입력, 표제어)
페이지 테이블의 각각의 행(에 담기는 내용)
- 페이지/프레임 번호
- 유효 비트(valid bit): 현재 해당 페이지에 접근 가능한지 여부
(= 메모리 =1 / 보조기억장치 = 0에 적재되어 있는지 표시 → CPU가 유효비트가 0인 메모리로 접근 시, 페이지 폴트 예외 발생)
※ 페이지 폴트(page fault): 메모리에 적재되지 않은 페이지를 참조할 경우 발생하는 인터럽트 - 보호 비트(protection bit): 해당 페이지가 읽기 & 쓰기, 읽기만, 쓰기만 가능한 페이지인지 나타내는 비트
- 참조 비트(reference bit): CPU가 해당 페이지에 접근한 적이 있는지 여부
- 수정 비트(modified bit or dirty bit): 해당 페이지에 데이터를 쓴지 여부
14-3 페이지 교체와 프레임 할당
가상 메모리로 물리 메모리의 한계를 일부 극복했지만, 절대적인 물리 메모리는 부족하다. 따라서 운영체제는 메모리를 효율적으로 이용하기 위해 페이지 인/아웃을 통해 적절하게 메모리 자원을 할당해야 한다.
요구 페이징(demand paging)
프로세스를 메모리에 적재할 때, 필요한 페이지만 메모리에 적재하는 기법
→ 페이지 교체 / 프레임 할당
페이지 교체 알고리즘
메모리에 적재된 페이지 중 보조기억장치로 내보낼 페이지를 결정하는 알고리즘
페이지 폴트가 적은 알고리즘이 좋은 알고리즘이다.
페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있다.
- First-In First-Out 페이지 교체 알고리즘
메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식 - Optimal 페이지 교체 알고리즘
앞으로의 사용 빈도가 가장 낮은 페이지 교체 - Least Recently Used 페이지 교체 알고리즘
가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
스레싱(thrashing)
프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
동시 실행되는 프로세스의 수(멀티프로그래밍의 정도)를 늘린다고 해서 CPU의 이용률이 비례해서 증가하는 것은 아니다. 물리적인 메모리의 한계로 CPU 성능과 무관하게 전체 컴퓨터의 성능이 하락할 수 있다.
페이지 폴트가 발생하는 근본적인 원인은 프로세스가 사용할 수 있는 프레임 수가 적기 때문이다. 이처럼 스레싱이 발생하는 근본적인 이유는 각 프로세스가 요구하는 최소한의 프레임 수가 보장되지 않기 때문이다.
프레임 할당
- 정적 할당 방식(프로세스, 메모리의 크기만 단순 고려)
- 균등 할당(equal allocation)
모든 프로세스에 균등하게 프레임을 제공하는 방식
획일적인 할당은 비합리적
- 비례 할당(proportional allocation)
프로세스의 크기에 따라 프레임을 제공하는 방식
프로세스를 실행해 봐야 필요한 프레임을 알게 되므로 완벽하지 않다 - 동적 할당 방식(프로세스 실행을 보고 프레임 수 결정)
- 작업 집합 모델(working set model)
실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합(작업 집합)을 기억하여 빈번한 페이지 교체를 방지하는 방법
- 페이지 폴트 빈도
페이지 폴트율의 상한/하한을 정하고, 그 범위 안에서만 프레임을 할당하는 방식
15장 파일 시스템
15-1 파일과 디렉터리
파일(File)
보조기억장치에 저장된 관련 정보의 집합
- 이름
- 실행을 위한 정보
- 파일 부가 정보: 속성(attribute) 또는 메타데이터(metadata)
- 파일 속성 중, 파일 유형은 운영체제가 인식하는 파일 종류를 나타낸다. 주로 파일 이름 뒤의 확장자를 통해 표현한다. 다른 방식
- 파일을 다루는 모든 작업은 운영체제의 시스템 호출을 통해 이루어진다.
디렉터리(Directory)
컴퓨팅에서 파일을 분류하기 위해 사용하는 이름공간
파일들을 묶어서 관리하기 위한 특별한 형태의 파일
- 루트 디렉터리(root ~): 최상위 디렉터리 = /
- 경로(path): 디렉터리를 이용해 파일 위치와 이름을 특정 짓는 정보
- 절대 경로(absolute ~): 루트 디렉터리에서 자기 자신까지 이르는 고유한 경로
- 상대 경로(relative ~): 현재 디렉터리부터 시작하는 경로
15-2 파일 시스템
파일과 디렉터리를 보조기억장치에 할당하고 접근할 수 있게 하는 운영체제 내부 프로그램
새 보조기억장치를 사용 준비 - 파티셔닝, 포매팅
파티셔닝
저장 장치의 논리적인 영역(partition; 칸막이)을 구획하는 작업
(논리적) 포매팅(formatting)
사용할 파일 시스템을 결정하고, 새로운 데이터 쓰기를 준비하는 작업
파일 할당 방법
운영체제는 파일, 디렉터리를 '블록' 단위로 읽고 쓴다.
블록 번호는 블록 위치를 식별하는 주소이며, 파일 크기에 따라 할당되는 블록의 수도 달라진다.
연속 할당(contiguous allocation)
연속적인 블록에 파일을 할당하는 방식
파일의 첫 번째 블록 주소와 블록 단위길이를 통해 접근
단순한 구현 vs 외부 단편화
불연속 할당
- 연결 할당(linked ~)
각 블록 일부에 다음 블록 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방식(연결 리스트로 관리)
- 외부 단편화 해결 vs- 반드시 첫 번째 블록에서 차례대로 읽어야 하므로, 임의 접근(random access; 파일 임의의 위치에서 접근) 속도가 매우 느리다.
- 하드웨어 오류 발생 시 해당 블록 이후의 블록은 접근 불가능
- 색인 할당(indexed ~)
파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아서 관리하는 방식
색인 블록을 알고 있으면 해당 파일 데이터에 접근 가능
디렉터리의 행에 파일 이름과 색인 블록 주소를 명시한다.
파일 시스템의 종류
FAT(File Allocation Table; 파일 할당 테이블) 파일 시스템
연결 할당의 단점을 보완한 파일 시스템
각 블록에 포함된 다음 블록의 주소를 테이블 형태로 관리(FAT)
파티션 영역 구성: 예약 / FAT / 루트 디렉터리 / 데이터
FAT는 파티션의 앞부분에 만들어지고, 메모리에 적재/실행되면 임의 접근에도 유리하다.
유닉스 파일 시스템
색인 할당 기반의 파일 시스템
유닉스 파일 시스템에서의 색인 블록 = index-node(= i-node)
파티션 영역 구성: 예약 / i-node / 데이터
i-node는 15개의 블록 주소를 저장할 수 있으므로 그 이상의 블록을 저장할 때는 다음과 같이 해결한다.
1. 첫 번째 ~ 열두 번째 주소에는 파일 데이터를 직접 저장한다 = 직접 블록(direct ~)
2. 1번의 내용으로 부족하면, 열세 번째 주소에는 단일 간접 블록(single indirect ~; 파일 데이터가 저장된 블록의 주소가 저장된 블록) 주소를 저장한다.
3. 2번의 내용으로 부족하면, 열네 번째 주소에는 이중 간접 블록(double ~; 단일 간접 블록 주소를 저장하는 블록)을 저장한다.
4. 3번의 내용으로 부족하면, 열다섯 번째 주소에 삼중 간접 블록(triple; 이중 간접 주소가 저장된 블록) 주소를 저장한다
※ 저널링(journaling) 파일 시스템
작업 로그를 통해 시스템 크래시가 발생했을 때, 로그 검사를 통해 빠르게 파일 시스템을 복구하기 위한 방법
※ 마운팅(mounting)
한 저장장치의 파일 시스템에서 다른 저장장치의 파일 시스템에 접근할 수 있도록 파일 시스템을 편입시키는 작업
