저자 github
- Chapter 14 ~ 15
- p. 400의 확인 문제 1번 풀고 인증하기
- Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
14 가상메모리
14-1 연속 메모리 할당
- 프로세스에 연속적인 메모리 공간을 할당하는 방식
스와핑(swapping)
- 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
- 스왑 영역(swap space): 프로세스들이 쫓겨나는 보조 기억장치의 일부 영역
- swap-out: 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
- swap-in: 스왑 영역에 있던 프로세스가 다시 메모리에 옮겨오는 것. 스왑 아웃 되었던 프로세스가 다시 스왑 인 될 때, 전의 물리 주소와 다른 주소에 적재될 수 있다.
- 스와핑을 이용해 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들 동시 실행 가능
스왑 영역 확인하기

메모리 할당
1) 최초 적합(first fit): 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식. 검색 최소화/ 빠른 할당
2) 최적 적합(best fit): 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
3) 최악 적합(worst fit): 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
연속 메모리 할당의 문제 1. 외부 단편화
- 연속 메모리 할당은 문제가 있다. 어떤? -> 외부 단편화(external fragmentation)
- 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이에 빈 공간이 생긴다. 프로세스를 새로 할당하기 어려운 작은 메모리 공간들 때문에, 메모리 낭비 현상이 발생한다.
- 해결방안
- 압축(compaction): 메모 조각 모음. 흩어져 있는 빈 공간들을 하나로 모음. 하나의 큰 빈 공간으로 만든다. -> [문제점] 시스템이 하던 일을 중지해야 함. 메모리의 내용을 옮기는 과정 중에 오버 헤드 야기
연속 메모리 할당의 문제 2.
물리 메모리보다 큰 프로세스를 실행할 수 없다.
(스와핑을 통해 실제 메모리보다 큰 여러 프로세스를 실행하는 것과 다른 부분)
14-2 페이징을 통한 가상 메모리 관리
페이징이란
- paging
- 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고,
메모리 물리 주소 공간을 frame이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
- 페이지 아웃: 페이징 시스템에서의 스왑 아웃
- 페이지 인: 페이징 시스템에서의 스왑 인
- 어떤 프로세스를 실행하려면 모든 페이지가 전부 메모리에 적재될 필요가 없다. (일부만 있어도 된다 -> 물리 메모리보다 커도 실행 가능)
- 장점:
- 외부 단편화 문제 해결
- 프로세스 간의 페이지 공유
페이지 테이블

출처: wiki
- 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
- 물리 주소상 프로세스들이 분산되어 있더라도, CPU 입장에서 논리 주소는 연속적으로 보일 수 있다.
- 내부 단편화: 하나의 페이지 크기보다 작은 크기로 발생하는 메모리 낭비 문제
PRBR(Page Table Base Register)
페이지 테이블 베이스 레지스터, 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있는 레지스터

- TLB(Translation Lookaside Buffer)
- 페이지 테이블을 메모리에 두면, 보기 위해/ 알게 된 프레임 접근을 위한 접근 시간이 2배 이상 증가하는 문제점이 있다. 이를 해결하기 위해 TLB
- 페이지 테이블의 일부를 가져와 저장하는 캐시 메모리
- TLB hit: cpu가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
- TLB miss: 페이지 번호가 TLB에 없어서 메모리 내 페이지 테이블에 접근하는 경우
페이징에서의 주소 변환
페이지 테이블 엔트리(PTE: Page Table Entry)
유효 비트(valid bit)
현재 해당 페이지에 접근 가능한 지 여부를 알려준다.
- 페이지 폴트(page fault) 인터럽트
- 유효 비트가 0인 페이지에 접근하려고 할 때
1) CPU는 기존 작업 내역 백업
2) 페이지 폴트 처리 루틴 실행
3) 페이지 처리 루틴은 원하는 페이지를 메모리에 가져온 뒤 유효 비트를 1로 변경
4) 페이지 폴트를 처리했다면 이제 CPU는 해당 페이지에 접근할 수 있게 된다.
보호 비트(protection bit)
페이지 보호 기능을 위해 존재하는 비트
해당 페이지가 읽고 쓰기가 가능한 페이지인지 나타낼 수 있다.
- 읽기만 가능 0, 읽고 쓰기 가능하면 1
- 예컨대, 보호 비트가 100이면 읽기만 가능, 111이면 읽고 쓰고 실행 가능
참조 비트(reference bit): CPU가 이 페이지에 접근한 적이 있는 지 여부를 나타낸다.
- 적재 이후 사용했으면 1, 한 번도 사용한 적 없으면 0
수정 비트(modified bit): 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부
- dirty bit라고도 부름
- 1이면 변경된 적 있음, 0이면 없음
- 스와핑과 관련되어 있다. 수정된 페이지는 스왑 아웃될 때 보조기억장치에도 쓰기 작업을 거쳐야 한다.
14-3 페이지 교체와 프레임 할당
요구 페이징(demand paging)
-
프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
-
요구되는 페이지만 적재하는 기법
1) cpu가 특정 페이지에 접근하는 명령어를 실행
2) 해당 페이지가 현재 메모리에 있다면(유효 비트 1) cpu는 페이지가 적재된 프레임에 접근
3) 해당 페이지가 현재 메모리에 없다면(유효 비트 0) 페이지 폴트 발생
4) 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정
5) 1번 수행
-
요구 페이징 시스템이 안정적으로 작동하려면!
- 페이지 교체
- 프레임 할당
- 페이지 교체 알고리즘: 쫓아낼 페이지를 결정하는 방법
페이지 교체 알고리즘
- 무엇이 좋은 페이지 교체 알고리즘일까?
- 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가
- 페이지 폴트 횟수
- 페이지 참고열(page reference string)을 통해 알 수 있음
- 페이지 참고열: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
FIFO 페이지 교체 알고리즘(First-In-First-One Page Replacement Algorithm):
메모리에 먼저 올라온 페이지부터 내쫓는 방식
- 단점: 먼저 적재되었다고 내쫓아서는 안된다. 실행 내내 사용될 페이지가 있을 수도 있음.
2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm):
FIFO 페이지 교체 알고리즘의 변형/보완책. 기회를 한 번 더 줌.
참조 비트가 1인 경우 당장 내쫓지 않는다. = cpu가 한 번 참조한 적이 있는 페이지
※ 참조 비트 0: CPU가 참조한 적 없음(바로 내쫓음)
최적 페이지 교체 알고리즘(optimal page replacement algorithm)
- CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘. 사용 빈도가 가장 낮은 페이지를 교체
- 구현이 어렵다.
- 운영체제에 사용하기보다는(현실적으로 예측 불가) 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적.
LRU 페이지 교체 알고리즘(LRU: Least Recently Used Page Replacement Algorithm)
- 최적 페이지 교체 알고리즘은 구현하기가 어렵지만 현실적으로 적용가능한 알고리즘이다.
- 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것
외우려고 하지말고, 왜 사용하는지, 대표적인 건 무엇인지 아는 정도로 보기
스레싱과 프레임 할당
-
페이지 폴트는 프로세스가 사용할 수 있는 프레임 수가 적어도 자주 발생한다.(더 근본적인 이유)
-
스레싱(thrashing)
- 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
- 근본적인 원인: 각 프로세스가 필요로 하는 최소한의 프레임의 수가 보장되지 않기 때문에 발생.
-
동시 실행되는 프로세스 수를 늘린다고 CPU 이용률이 높아지는 것은 아니다.
-
멀티프로그래밍의 정도(degree of multiprogramming): 메모리에서 동시 실행되는 프로세스의 수

프레임 할당 방식
1) 정적 할당 방식
- 균등 할당(equal allocation): 모든 프로세스들에게 균등하게 프레임을 할당하는 방식. 가장 단순한 할당 방식. 비합리적
- 비례 할당(proportional allocation): 프로세스 크기에 비례하여 프레임 할당. 결국 프로세스가 필요로 하는 프레임 수는 실행해봐야 안다.
2) 동적 할당 방식(프로세스의 실행을 보고 할당하는 방식)
페이징의 이점과 계층적 페이징
쓰기 시 복사(copy on write)

- 부모 프로세스/자식 프로세스 둘 중 하나가 페이지에 쓰기 작업 수행 시 해당 페이지는 별도의 공간으로 복제(프로세스 생성 시간, 메모리 절약)
계층적 페이징
-
프로세스 테이블의 크기는 생각보다 작지 않다
-
프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비
-
프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법
-
계층적 페이지(hierarchical paging): 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식, 다단계 페이지 테이블(multilevel page table) 기법이라고도 부름
-
계층적 페이지 논리 주소
- 바깥 페이지 번호를 통해 페이지 테이블의 페이지를 찾기
- 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기

파일 시스템
파일과 디렉터리를 관리하는 운영체제 내의 프로그램
파일과 디렉터리를 다루어 주는 프로그램
파일과 디렉터리
파일
- 보조 기억 장치에 저장된 관련 정보의 집합
- 의미 있고 관련 있는 정보를 모은 논리적 단위
- 파일을 이루는 정보 (파일을 실행하기 위한 정보 + 부가 정보 = 속성, 메타 데이터)
- 파일 유형: 확장자(extension)을 이용해 운영체제에게 파일 유형을 알려준다.
- 파일 연산을 위한 시스템 호출: 생성, 삭제, 열기, 닫기, 읽기, 쓰기 등
디렉토리
-
여러 계층으로 파일 및 폴더를 관리하는 트리 구조 디렉터리
-
최상위 디렉터리(루트 디렉터리, /), 서브 디렉터리

-
경로: 디렉터리를 이용해 파일/디렉터리의 위치, 나아가 이름까지 특정 지을 수 있는 정보
- 절대 경로: 루트부터 시작하는 경로
- 상대 경로: 현재 디렉터리부터 시작하는 경로
-
디렉터리 연산을 위한 시스템 호출: 생성, 삭제, 열기, 닫기, 읽기 등
-
디렉터리 엔트리
- 디렉터리를 그저 특별한 형태의 파일로 간주한다. 포함된 정보가 조금 특별한 파일
- 파일 내부에는 파일과 관련된 정보들이 있다면, 디렉터리 내부에는 해당 디렉터리에 담겨 있는 대상과 관련된 정보들이 담겨 있다.
- 담겨 있는 것
- 디렉터리에 포함된 대상의 이름
- 그 대상이 보조기억장치 내에 저장된 위치
파일 시스템
- 파일 시스템이 파일과 디렉터리를 보조기억장치에 할당하고 접근하는 방법
- 대표적인 파일 시스템의 종류(FAT 파일 시스템, 유닉스 파일 시스템) 학습
파티셔닝과 포매팅
- partitioning : 저장 장치의 논리적인 영역을 구획하는 작업
- formmatting: 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고, 새로운 데이터를 쓸 준비를 하는 작업
파일 할당 방법
연속 할당
- 이름 그대로 보조기억장치 내 연속적인 블록에 파일 할당
- 연속된 파일에 접근하기 위해 파일의 첫 번째 블록 주소와 블록 단위의 길이만 알면 된다.
- 디렉터리 엔트리: 파일 이름, 첫 번째 블록 주소, 블록 단위 길이 명시
- 구현이 단순하지만, 외부 단편화를 야기한다.
불연속 할당
- 연결 할당: 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방식. 파일을 이루는 데이터를 연결 리스트로 관리. C언어의 포인터와 같은 개념
- 디렉터리 엔트리: 파일 이름, 첫 번째 블록 주소, 블록 단위의 길이
- 단점:
- 하나씩 차례대로 읽어야 한다.(임의 접근 속도가 느림)
- 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없음.
- 색인 할당(indexed allocation): 파일의 모든 주소를 색인 블록에 모아 관리하는 방식
파일 시스템 살펴보기
1) FAT 파일 시스템
- 연결 할당 기반 파일 시스템
- 연결 할당의 단점 보완: 각 블록에 포함된 다음 블록 주소를 모아 테이블(FAT: File Allocation Table)로 관리
- 디렉터리 엔트리

2) 유닉스 파일 시스템
- 색인 할당, 유닉스 파일 시스템에서 색인 블록을 i-node라고 부른다.
- 디렉터리 엔트리: i-node가 파일 시스템의 핵심이다

- i-node: 파일의 속성 정보와 15개의 블록 주소 저장 가능
15개 블록이 넘으면?
- 블록 주소 중 12개에는 직접 블록 주소 저장
- 1번으로 충분하지 않으면 13번째 주소에 단일 간접 블록 주소 저장
- 단일 블록: 파일 데이터를 저장한 블록 주소가 저장된 블록
- 2번으로도 충분하지 않다면 14번째 주소에 이중 간접 블록 주소 저장
- 이중 간접 블록: 단일 간접 블록들의 주소를 저장하는 블록
- 3번으로도 충분하지 않다면 15번째 주소에 삼중 간접 블록 주소 저장
- 삼중 간접 블록: 이중 간접 블록들의 주소를 저장하는 블록
참고
- 저널링 파일 시스템: 시스템 크래시가 발생한 직후에 로그 영역을 읽어 크래시가 발생한 당시 어떤 작업을 실행 중이었는지 알아낸 다음 해당 작업을 완료. MS NT 파일 시스템, 리눅스의 ext3, ext4 파일 시스템을 포함해 대부분의 파일 시스템이 저널링 기능을 지원한다.
- 마운트: 한 저장 장치의 파일 시스템에서 다른 저장 장치의 파일 시스템에 접근할 수 있도록 파일 시스템을 편입시키는 작업
숙제
숙제 1: 400의 확인 문제 1번 풀고 인증하기
1) 최초 적합: 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
2) 최악 적합: 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
3) 최적 적합: 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
추가 숙제: Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
3번
- 노트에 그려 풀었는데(사실 책에 예제가 그대로 있음) 예쁘게 그리는 건 실패했습니다..ㅋ 그래서 저만 볼게요.!