✏️ 6주차 진도: Chapter 14 ~ 15
- 기본 숙제(필수): p. 400의 확인 문제 1번 풀고 인증하기
- 추가 숙제(선택): Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
Chapter 14. 가상 메모리
연속 메모리 할당
프로세스에 연속적인 메모리 공간을 할당하는 것. 프로세스의 크기만큼 메모리 주소를 할당받아 연속적으로 배치.
스와핑
현재 실행되지 않는 프로세스를 임시로 보조기억장치로 쫓아내서 만들어진 빈 공간에 새로운 프로세스를 적재해서 실행하는 방식
스왑 영역
메모리에 있던 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
스왑 아웃
현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 쫓겨나는 것
스왑 인
스왑 영역에 있던 프로세스가 다시 메모리로 옮겨 오는 것
메모리 할당
메모리 공간에 프로세스를 어떻게 연속적으로 할당할 수 있을까?
최초 적합
메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식. 넣을 수 있는 공간 발견하면 무조건 배치하자!
- 검색 최소화
- 빠른 할당 가능
최적 적합
빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식. 낭비되는 공간을 최대한 줄일 수 있게 배치하자!
최악 적합
빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식. 가장 널널한 곳에 프로세스를 배치하자!
External Fragmentation(외부 단편화)
연속 메모리 할당 환경에서는 전체 빈 공간이 충분함에도 불구하고 빈 공간들이 너무 쪼개어져 있어서 프로세스들을 적재하기 어려운 상황(external fragmentation)이 발생할 수 있다. -> 메모리 낭비로 이어짐.
external fragmentation 해결 방법
- 메모리 압축 : 여기 저기 흩어져 있는 빈 공간들을 하나로 모으는 방식. 빈 자리가 없어보이는 쓰레기통을 발로 밟아 공간을 만드는 것과 유사하다고 볼 수 있다.
- 단점 : 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 한다. 또, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 발생시키며, 오버헤드 최소화에 대한 명확한 방법을 찾기 어렵다. 이를 보완하기 위해 나타난 것이 페이징 기법.
가상 메모리
실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
페이징
프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤, 페이지를 프렘임에 할당하는 가상 메모리 관리 기법.
- 페이지 단위로 스와핑이 일어남(페이지 아웃, 페이지 인)
- 프로세스 간 페이지를 공유할 수 있다.(쓰기 시 복사를 통해 자식 프로세스가 페이지를 수정할 때만 해당 페이지가 별도의 공간으로 복제된다.)
페이지 테이블
페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표. 페이지 번호를 이용해 페이지가 적재된 프레임을 찾아서 프로세스를 순차적으로 실행할 수 있다.
CPU 내의 페이지 테이블 베이스 레지스터(PTBR)가 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어난다. 이 문제를 완화하기 위해 CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다. (페이지 번호가 TLB에 있을 경우 TLB 히트, 없을 경우 TLB 미스)
- 페이지 테이블 엔트리(페이지 테이블의 행)
페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트가 있다.유효 비트 : 현재 해당 페이지에 접근 가능한지(페이지가 메모리에 적재되어 있는지)
보호 비트 : 페이지의 읽기, 쓰기, 실행 가능 여부를 나타냄(페이지 접근 권한 제한)
참조 비트 : CPU가 이 페이지에 접근한 적잉 있는지 나타냄
수정 비트 : 해당 페이지에 데이터를 쓴 적이 있는지 여부를 나타냄(페이지 아웃이 될 때 보조기억장치에 쓰기 작업을 해야하는지 알려준다)
Internal Fragmentation (내부 단편화)
프로세스가 페이지 단위로 잘릴 때, 딱 맞게 잘리지 않고 애매하게 남은 부분에 의해 일어나는 메모리 낭비. 하나의 페이지 크기가 작다면 internal fragmentation의 크기는 작아지겠지만, 페이지 크기가 너무 작아진다면 페이지 테이블의 크기가 너무 커질 수도 있다. 따라서 페이지의 크기를 잘 조정하는 것이 중요하다!
페이징에서의 주소 변환
페이징 시스템에서의 논리 주소는 page number(접근하고자 하는 페이지 번호)와 offset(접근하고자 하는 프레임의 시작 번지로부터 얼만큼 떨어져 있는가)으로 이루어져 있다.
계층적 페이징
페이지 테이블 자체를 페이징 하여 여러 단계의 페이지를 두는 방식
- 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없다.
- 2단계 페이징의 경우, 바깥 페이지 번호(CPU와 근접한 곳에 위치한 페이지 테이블 엔트리) | 안쪽 페이지 번호(페이지 테이블의 페이지 번호) | 변위 형식으로 이루어진 논리 주소를 사용한다.
요구 페이징
필요한 페이지만을 메모리에 적재하는 기법
순수 요구 페이징
아무런 페이지도 메모리에 적재하지 않은 채 실행부터 먼저 하는 방법. 첫 명령어를 실행할 때부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다.
페이지 교체 알고리즘
일반적으로 페이지 폴트 횟수가 적은 알고리즘이 좋은 페이지 교체 알고리즘이다. 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있다.
- 페이지 참조열 : CPU가 참조하는 페이지들의 나열(연속해서 참조하는 경우는 제거)
FIFO 페이지 교체 알고리즘
메모리에 가장 먼저 들어온 페이지부터 페이지 아웃하는 알고리즘
- 아이디어와 구현은 간단하나, 먼저 들어왔다는 이유만으로 프로그램 실행 내내 자주 참조 되는 페이지를 아웃시킬 수 있다는 단점이 있다.
2차 기회 페이지 교체 알고리즘
FIFO 알고리즘처럼 기본적으로 메모리에서 가장 오래 머물렀던 페이지를 대상으로 아웃할 페이지를 선정한다. 하지만, 참조 비트가 1일 경우 바로 아웃시키지 않고 참조 비트를 0으로 바꾼 후 해당 페이지를 최근에 적재된 페이지라고 간주하는 방식으로 기회를 한 번 더 준다.
최적 페이지 교체 알고리즘
CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘. 가장 오랫동안 사용하지 않을 페이지를 우선적으로 아웃시킨다.
- 앞으로 오랫동안 사용하지 않을 페이지를 예측하는 것을 어려우므로 실제 사용하는 방법이라기 보다는 주로 다른 페이지 알고리즘의 이론상 기능을 평가하기 위해 사용한다.
LRU 페이지 교체 알고리즘
가장 오랫동안 사용하지 않은 페이지를 우선적으로 아웃 시키는 알고리즘. 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 만들어졌다.
스래싱(Thrashing)
프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요(페이지 폴트가 자주 발생)하여 성능이 저해되는 문제
- 근본적인 원인 : 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문!
프레임 할당 방식
정적 할당 방식
-
균등 할당
프로세스마다 프레임을 똑같이 나누어 할당하는 방식 -
비례 할당
프로세스의 크기에 비례하여 프레임을 할당하는 방식
동적 할당 방식
프로세스를 실행하는 과정에서 배분할 프레임을 결정
-
작업 집합 모델을 사용하는 방식
프로세스가 일정 기간 동안 참조한 페이지 집합(작업 집합)을 기억하고, 해당 페이지 개수만큼 프레임을 할당해서 빈번한 페이지 교체를 방지한다. -
페이지 폴트 빈도를 사용하는 방식
페이지 폴트율이 너무 높으면 프레임을 더 할당해주고, 페이지 폴트율이 너무 낮으면 프레임을 다시 회수한다.
Chapter 15. 파일 시스템
파일
보조기억장치에 저장된 관련 정보의 집합
이름, 파일을 실행하기 위한 정보, 파일 관련 부가 정보(속성, 메타데이터)로 구성되어 있다.
디렉터리(폴더)
1단계 디렉터리
모든 파일이 하나의 디렉터리 아래에 있는 구조
트리 구조 디렉터리
최상위 디렉터리(루트)가 있고 그 아래 여러 서브 디렉터리가 있는 구조
절대 경로
루트 디렉터리에서 자기 자신까지 이르는 고유한 경로
상대 경로
현재 디렉터리부터 시작하는 경로
파티셔닝
용량이 큰 저장 장치를 하나 이상의 논리적인 영역으로 나누는 작업
포매팅
파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지 결정하고, 새로운 데이터를 쓸 준비를 하는 작업
파일 할당 방법
운영체제는 파일과 디렉터리를 블록 단위(섹터의 묶음 단위)로 읽고 쓴다.
연속 할당
보조기억장치 내 연속적인 블록에 파일을 할당하는 방식
연속 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름, 첫 번째 블록 주소, 길이를 저장한다.
- external fragmentation을 일으킬 수도 있다.
연결 할당
각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방식 (연결 리스트로 관리)
연결 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름, 첫 번째 블록 주소, 길이를 저장한다.
- 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 한다.(임의 접근 속도가 매우 느려짐)
- 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없게 됨.
색인 할당
파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리하는 방식
색인 할당을 사용하는 파일 시스템에서는 디렉터리 엔트리에 파일 이름, 색인 블록 주소를 저장한다.
- 파일 내 임의의 위치에 접근하기 쉽다.
파일 시스템
FAT 파일 시스템
각 블록이 가리키고 있는 다음 블록의 주소를 한데 모아 테이블 형태(파일 할당 테이블, File Allocation Table)로 관리하는 파일 시스템
디렉터리 엔트리에 파일 이름과 첫 번째 블록 주소를 저장한다.
- USB 메모리, SD 카드와 같은 저용량 저장 장치용 파일 시스템으로 많이 이용되고 있음
유닉스 파일 시스템
i-node라는 색인 블록을 사용한다. i-node에는 파일 속성 정보와 열다섯 개의 블록 주소를 저장할 수 있다. 블록 주소 열두 개에는 직접 블록 주소를 저장하고, 이것으로 충분하지 않다면 열세 번째 주소에 단일 간접 블록 주소(파일 데이터를 저장한 블록 주소가 저장된 블록)를 저장한다. 단일 갑접 블록 주소로도 충분하지 않다면 열네 번째 주소에 이중 간접 블록 주소를 저장한다. 만약에 이것도 충분하지 않다면....! 열다섯 번째 주소에 삼중 간접 블록 주소를 지정하면 된다.
✏️ 기본 숙제
p. 400 확인 문제 1번
메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요
최초 적합 : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
최악 적합 : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배피하는 방식
최적 적합 : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
📖추가 숙제
Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
답: 3번
