[혼공컴운] 6주차_가상 메모리 & 파일 시스템

과제

p. 400의 확인 문제 1번 : 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

보기 : 최초 적합, 최적 적합, 최악 적합

1. 최초 적합 : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
2. 최악 적합 : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
3. 최적 적합 : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

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

폴트 3번 발생!

가상 메모리

실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술. (기법으로는 페이징 기법과 세그멘테이션 기법이 있다.)

연속 메모리 할당

메모리에 프로세스들이 연속적으로(순서대로 차례차례) 배치된, 메모리 공간을 할당하는 방식

스와핑

입출력 작업을 위해 대기 상태인 프로세스나 오랫동안 사용되지 않은 프로세스들을 임시로 보조기억장치에 보내서 메모리 공간을 확보하는 방식

스왑 영역 : 프로세스가 들어간 보조기억장치의 영역

스왑 아웃 : 메모리에서 스왑 영역으로 옮겨지는 상황

스왑 인 : 다시 메모리로 돌아오는 상황

메모리 할당 방식

프로세스는 메모리의 많은 공간 중에 어디로 가하지! 어느 메모리 공간에 프로세스를 연속적으로 할당하지!

최초 적합

메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간이 있으면 바로 넣어버리는 방식

• 검색을 최소화해서 빠르다

최적 적합

빈 공간을 모두 검색한 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간으로 배치하는 방식

• 검색이 느리다
• 메모리 공간을 효율적으로 사용한다

최악 적합

빈 공간을 모두 검색한 후, 가장 큰 공간에 적재하는 방식

• ? 왜… 그럴까?

외부 단편화

연속 메모리 할당이 내포하는 문제

연속적으로 프로세스를 쌓다보면 효율적이지 않게 쌓이게 된다. 프로세스의 종료되면 빈 공간이 생기지만 다른 프로세스를 적재하지 못하는 상황이 생기고 메모리 낭비로 이어진다.

• 20MB 짜리 공간이 비었지만, 실행해야 할 프로세스들이20MB를 넘는다면 못쓰는 공간이 된다.

외부 단편화 해결책 ‘압축’

대표적인 방법으로 ‘압축’이 있다. 메모리 조각모음.

프로세스를 재배치하여 빈공간을 하나로 만드는 기법

• 옮기는 작업은 오버헤드를 발생시킨다.
• 어떻게 움직여야하는지 방법을 결정하기도 어렵다.

→ 압축으로는 해결책이 오묘하다. 그래서 페이징 기법이 나왔다.

페이징

메모리를 연속적으로 할당하니 문제다.

→ 메모리와 프로세스를 일정 단위로 잘라서 불연속적으로 관리한다면 단편화를 해결

프로세스를 쪼개서(페이지들로) 나누고 메모리를 쪼갠 단위인 프레임에 꽂아넣는다.

• 페이지 : 프로세스의 논리 주소 공간
• 프레임 : 메모리 물리 주소 공간

페이지 단위 스와핑

• 스왑 인, 아웃처럼 페이지 아웃, 페이지 인으로 부른다.

페이지 테이블

불연속적인 프로세스들의 배치에서 CPU는 어떻게 찾아서 실행할까?

→ 테이블(표)를 둬서 CPU는 연속적으로 찾아갈 수 있게 하기

• 프로세스는 각자 프로세스 테이블을 갖고 있다.
• CPU 내의 **페이지 테이블 베이스 레지스터(PTBR)**는 각 프로세스의 페이지 테이블이 적재된 메모리 주소를 가리킨다.

TLB(Translation Lookaside Buffer)

테이블이 있는 메모리에 접근하고 프레임 주소에 접근하면 시간이 2배로 든다.

→ CPU 곁에 TLB라는 페이지 테이블의 캐시 메모리를 둔다.

→ 캐시에 테이블의 일부를 저장한다!

• 페이지 번호가 캐시된 테이블에 있는 경우 TLB 히트, 없으면 TLB 미스라고 한다.

페이징에서의 주소 변환

CPU가 특정 주소에 접근하기 위해서는 어떤 페이지(또는 프레임)에 접근하고 싶은지, 접근하려는 주소가 그 페이지(또는 프레임)으로부터 얼마나 떨어져 있는지 알아야한다.

→ 페이징 시스템에서 모든 논리 주소는 페이지 번호와 변위로 이뤄진다.

→ 이 논리를 페이지 테이블을 통해 프레임 번호, 변위로 변환한다.

페이지 테이블 엔트리

→ 페이지 테이블의 각각 행들을 의미한다.

엔트리에는 페이지 번호, 프레임 번호 뿐만 아니라 유효 피트, 보호 비트, 참조 비트, 수정 비트가 있다.

유효 비트

현재 해당 페이지에 접근 가능한가?

유효 비트 0 : 보조기억장치로 스왑 된 경우. 접근시 페이지 폴트라는 예외 발생

페이지 폴트 처리 과정

1. CPU는 기존 작업 내역 백업
2. 페이지 폴트 처리 루틴 실행
3. 페이지 처리 루틴을 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
4. 페이지 폴트 처리를 했다면 CPU가 접근 가능

보호 비트

페이지 보호 기능에 필요. 읽기 전용은 0, 읽기 쓰기 가능시 1로 표기 하거나 비트 3개를 사용해서 RWX(읽기/쓰기/실행) 권한 부여도 가능

참조 비트

CPU가 접근한 유무를 보여줌

수정 비트

해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줌

왜 필요한가?

• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지 판단하기 위함
• 한 번도 접근하지 않았거나 읽기만한 페이지는 보조기억장치에 저장된 페이지 내용과 메모리 내에 있는 페이지 내용이 동일하다. 해당 페이지가 스왓아웃되면 추가작업 없이 덮어쓰면 된다. 동일하지 않다면(사용한 적 있다면) 보조기억장치에 기록하는 작업이 필요하다.

쓰기 시 복사 (copy on write)

쓰기 시 복사를 사용하면 부모 프로세스와 자식 프로세스가 같은 작업을 수행한다면 부모로 인해 생긴 메모리의 프레임을 동일하게 자식도 가리킨다. 읽기작업만 한다면 그대로 간다.

• 만약 쓰기(Write)를 사용하게 된다면 그 부분의 프레임만 복제해서 별도의 공간에서 사용한다.

계층적 페이징

프로세스가 커지면 프로세스 테이블이 커져서 메모리 낭비를 초래한다.

→ 페이징 테이블을 페이징해서 다단계로 관리하자! (다단계 페이지 테이블 기법이라고도 한다)

→ 모든 페이지 테이블을 메모리에 유지할 필요가 없어진다. 보조장치로 보내버린다.

계층적으로 사용시 바깥 페이지 번호와 안쪽 페이지번호로 논리주소가 구성된다

요구 페이징

메모리에 프로세스를 적재할 때, 모든 페이지를 적재하지 않고 필요한 것만 적재하는 기법

1. CPU가 특정 페이지에 접근하는 명령어 실행
2. 해당 페이지가 현재 메모리가 있는 경우 CPU는 페이지가 적재된 프레임에 접근
3. 없는 경우 페이지 폴트 발생
4. 페이지 폴트 처리 루틴으로 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5. 다시 1번으로 수행

→ 첫 명령어부터 페이지 폴트가 발생한다. 적재가 어느정도 된 이후부터 페이지 폴트 발생이 줄어든다.

페이지 교체 알고리즘

페이지 폴트를 가장 적게 일으키는 알고리즘.

페이지를 메모리에 적재하다보면 메모리가 꽉찬다. 어떤 페이지를 페이지 아웃시킬지 결정하는 방법이다.

페이지 폴트 횟수를 페이지 참조열을 통해 알 수 있다.

(페이지 참조열은 연속으로 사용된 페이지를 생략한 페이지열을 의미함)

• CPU가 접근한 페이지 순서 : 2 2 2 3 5 5 5 3 3 7
• 페이지 참조열 : 2 3 5 3 7

FIFO 페이지 교체 알고리즘

가장 먼저 들어온 페이지부터 내보내는 방식

2차 기회 페이지 교체 알고리즘

FIFO를 사용하다보면 자주 사용하는 페이지가 자주 빠질 수 있다. 참조 비트가 1이면 한 번 봐주는 대신 참조 비트를 0으로 바꿔서 큐에 다시 넣어준다.

최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘. 사용빈도가 낮을 것 같으면 내보낸다. 페이지 폴트율을 가장 낮게 보장하는 알고리즘.

자주 사용할 페이지는 오랫동안 보관해야한다.

오랫동안 쓰지 않을 페이지는 내보낸다!

• 오랫동안 사용되지 않을 페이지를 예측해야하기 때문에 구현이 어렵다.
• 이론상 다른 페이지 교체 알고리즘의 성능 평가를 하기 위해서 사용한다.

LRU 페이지 교체 알고리즘

최적 페이지와 비슷한 알고리즘

→ 오랫동안 사용되지 않은 페이지를 교체

스레싱

→ 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간이 걸리는 성능 저하 문제를 스레싱이라고 한다.

프로세스가 사용할 프레임 수가 많으면 (메모리가 부족한다거나) 페이지 폴트는 자주 발생한다.

• 많은 프로세스가 동시 실행중일수록 조금씩 CPU 이용률이 올라가다가 스레싱이 발생하면서 CPU 이용률이 감소하고 처리 시간이 늘어난다.

→ 근본적인 스레싱의 원인은 프로세스가 필요로 하는 최소한의 프레임을 할당하지 않았기 때문이다. 필요보다 적게 할당되면 페이지 폴트는 더 자주 발생한다.

스레싱 해결 방법 : 프레임 할당 방식

정적 할당 방식 : 프로세스의 실행 과정을 고려하지 않고 프로세스의 크기, 메모리 크기만 고려한 방식

• 균등 할당 : 프로세스별로 공평하게 프레임을 제공
• 비례 할당 : 프로세스 크기에 따라 프레임을 제공

동적 할당 방식 : 프로세스의 실행을 보고 프레임 수를 결정하는 방식

• 작업 집합 모델 : 프로세스가 일정 시간동안 참조한 페이지의 집합(작업 집합)의 크기만큼 할당
• 페이지 폴트 빈도 : 폴트 도가 높으면 프레임이 적은 것이니 늘려주는 방식. 폴트 율의 상한선과 하한선을 정해서 유동적으로 관리.

파일 시스템

파일

파일에는 속성 또는 메타 데이터가 존재한다.

파일 속성

파일의 정보를 알려주는 부분

• 파일 유형 : 파일의 종류 (주로 확장자를 힌트로 줌)
• 크기, 보호, 생성 날짜, 위치 등 등등이 있음
• 시스템 호출 : 운영체제에서는 파일 연산을 위해 시스템 호출을 제공한다.
  • 파일 생성, 삭제, 열기, 닫기, 읽기, 쓰기

디렉토리 (윈도우에선 폴더)

옛날에는 한 디렉토리에 파일을 두는 1단계 디렉토리였으나 현재는 트리 구조를 사용한다.

그리고 디렉토리는 많은 운영체제에서 **특별한 형태의 ‘파일’**이다. 별개가 아니다.

• 루트 디렉토리 : 최상위 디렉토리 슬래시(/)로 표시
• 경로
  • 절대 경로 : 루트 디렉토리에서 자신까지 이르는 고유 경로 (/으로 시작)
  • 상대 경로 : 현재 디렉토리를 기준으로 자신까지 이르는 경로
• 시스템 호출 : 운영체제에서 디렉토리 연산을 위해서 시스템 호출을 제공한다.
  • 디렉토리 생성, 삭제, 열기, 닫기, 읽기

디렉토리 엔트리

디렉토리는 내부에 담겨있는 정보를 테이블 형태로 담고 있다. 파일명과 위치를 유추할 수 있는 정보로 테이블을 두게 된다. (파일 시스템에 따라서 생성, 수정시간, 크기 등도 명시할 수 있다.)

파티셔닝과 포매팅

하드나 SSD를 사면 파티션을 나누는 작업과 포맷 작업을 거쳐야한다.

• 파티셔닝 : 저장 장치의 논리적 영역을 구획하는 작업. 영역 하나하나를 파티션이라고 한다.
• 포매팅 : 포맷. 어떤 방식으로 파일을 저장하고 관리할 것인지 결정하고, 새로운 데이터를 쓸 준비를 하는 작업. (파일을 싹 지우는 개념이랑은 다름)

파일 할당 방법

운영체제는 파일, 디렉토리를 저장하는 것은 블록이라는 단위로 한다.

하드 디스크의 가장 작은 저장 단위는 섹터이다. 하나 이상의 섹터를 블록이라는 단위로 묶은 뒤 블록 단위로 운영체제는 관리한다.

• 하드 내에 블록에 번호를 매겨서 블록 위치를 식별하는 주소로 사용.
• 크기가 클수록 여러 블록에 걸쳐서 저장.
• 할당 방법에는 크게 연속 할당과 불연속 할당이 있다.
  • 연속 할당 : 보조기억장치에 연속적인 블록에 파일을 할당하는 방식으로 구현이 단순하지만 외부 단편화를 야기할 수 있다.
  • 불연속 할당 : 오늘날에는 불연속 할당이 사용된다.
    • 불연속 할당에는 크게 연결 할당과 색인 할당이 있다.
    • 연결 할당 : 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다른 블록을 가리키는 형태. 포인터와 같은 개념. (링크드리스트 느낌으로 구현한듯)
      • FAT 파일 시스템이 대표적인 예. (단점을 보완함)
      • 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야한다는 단점이 있다. 임의 접근 속도가 느리다.
      • 하드웨어 고장, 오류 발생시 해당 블록 이후 블록에 접근할 수 없다는 단점이 있다.
    • 색인 할당 : 파일의 모든 블록 주소를 테이블로 만들어서 하나의 블록에 모아 관리하는 방식 (이 블록을 색인 블록이라 함) 딕셔너리 느낌.
      • UNIX 파일 시스템이 대표적인 예.
      • 디렉토리 엔트리에 파일 이름과 색인 블록 주소를 명시해야한다.

파일 시스템별 특징

FAT 파일 시스템

연결 할당 방식의 한계를 해결하기 위해서 블록의 주소들을 모아서 테이블 형태로 관리한다. (파일 할당 테이블 FAT. File Allocation Table)

• 윈도우에서는 블록 대신 클러스터라는 용어로 사용한다.
• 하드를 파티션을 나누게 되면 FAT은 파티션의 맨 앞 부분에 만들어진다. FAT이 저장되고 뒤이어 루트 디렉토리, 데이터 영역이 있다.
• 하드 맨 앞에 FAT이 있지만, 실행 도중 메모리에 캐시될 수 있다. (더 빨라진다!)

FAT 파일 시스템에서 파일을 읽는 방법

/home/abc/d.sh를 읽어보자

1. 루트 디렉토리의 테이블에서 home 디렉토리의 첫 번째 블록을 찾는다.
2. home 디렉토리의 테이블에서 abc 디렉토리의 첫 번째 블록을 찾는다.
3. abc 디렉토리의 테이블에서 d.sh 파일의 첫 번째 블록을 찾는다.
4. FAT을 통해 d.sh의 첫 번째 블록부터 순서대로 접근한다.

유닉스 파일 시스템

색인 블록 방식을 기반. (색인 블록을 i-node, index-node라고 부른다.)

• i-node에는 파일 속성 정보와 15개의 블록 주소가 저장될 수 있다. (크기가 유한하다.)
• 파일마다 i-node가 있고, i-node마다 번호가 부여되어 있다.

만약 파일 크기가 블록 15개보다 크다면?

1. 블록 주소 중 12개에는 직접 블록 주소를 저장
   1. 직접 블록 : 파일 데이터가 저장된 블록
2. 13번째 블록 주소에 단일 간접 블록의 주소 저장
   1. 단일 간접 블록 : 파일 데이터가 저장된 블록이 아니라 파일 데이터를 저장한 블록 주소를 저장한 블록
3. 13번째 블록으로 충분치 않다면 14번째 블록 주소에 이중 간접 블록주소 저장
   1. 이중 간접 블록 : 데이터 블록 주소를 저장하는 단일 블록 주소가 저장된 블록
4. 그래도 안되면 마지막 블록(15번)은 삼중 간접 블록 주소를 저장한다.
   1. 삼중으로 가면 어지간해선 저장이 된다고 한다.

유닉스 파일 시스템에서 파일을 읽는 방법

/home/abc/d.sh를 읽어보자

1. 루트 디렉토리의 i-node를 i-node 영역에서 본다. (주로 루트 디렉토리의 i-node는 미리 저장이 되있다.) 그러면 루트 디렉토리의 블록 위치가 보인다.
2. 루트 디렉토리의 블록을 읽으면 내용을 알 수 있다. home 디렉토리의 i-node 번호가 보인다.
3. home 디렉토리의 i-node를 i-node 영역에서 본다. home 디렉토리의 블록 번호가 보인다.
4. home 디렉토리의 블록 번호를 통해 데이터 영역에서 디렉토리의 내용을 확인한다.
5. abc 디렉토리의 i-node 번호가 보인다. i-node 영역에서 해당 i-node를 확인한다.
6. (반복)
7. d.sh파일의 i-node에는 파일이 저장된 블록 번호들이 있다.

그 밖에 다른 파일 시스템

• NT 파일 시스템 (NTFS) - 윈도우에서 주로 사용
• ext 파일 시스템 - 리눅스에서 주로 사용