[혼공컴운] 6주차_책 한 권을 끝내다니(Ch 14~ 15)

14-1) 연속 메모리 할당

• 연속 메모리 할당 : 프로세스에 연속적인 메모리 공간을 할당하는 방식

• 스와핑 : 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식

  • 스왑 영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역

  • 스왑 아웃 : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것

  • 스왑 인 : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것

→ 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기 > 실제 메모리 크기인 경우에도 프로세스들 동시 실행 가능

---

프로세스는 메모리 내의 빈 공간(적재되어도 괜찮은 공간)에 적재되어야 한다.

• 최초 적합 : 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재될 수 있는 공간을 발견하는 즉시 메모리 할당하는 방식

  • 검색 최소화, 빠른 할당 가능

• 최적 적합 : 운영체제가 빈 공간을 모두 검색해 본 후에 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스 배치하는 방식

• 최악 적합 : 운영체제가 빈 공간을 모두 검색해 본 후에 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식

---

⇒ 연속 메모리 할당은 외부 단편화라는 문제를 내포!

프로세스들이 실행되고 종료되기를 반복하면 메모리 사이 사이에 빈 공간이 생기는데 이러한 빈 공간들을 온전히 합쳐서 사용할 수 없음. 결국에는

• 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래 ⇒ 메모리 낭비

이러한 현상을 외부 단편화라고 한다.

---

외부 단편화를 해결하기 위한 대표적인 방안으로 압축 = 조각모음

• 메모리 내의 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법

• 단점

  1. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일 중지

  2. 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기

⇒ 그래서 등장한 또 다른 해결 방안 : 가상 메모리 기법, 그 중에서 페이징 기법

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

• 가상 메모리 : 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술

  • 페이징과 세그멘테이션

---

• 페이징 프로세스의 논리 주소 공간을

  • 페이지라는 일정한 단위로 자르고

  • 메모리 물리 주소 공간을 프레임이라는 페이지와 동일 한 크기의 일정한 단위로 자른 후

  • 페이지를 프레임에 할당하는 가상 메모리 관리 기법

• 페이징에서도 스와핑 사용 가능

  • 페이지 단위로 스왑 아웃 / 스왑 인 ⇒ 페이지 아웃 / 페이지 인

⇒ 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다.

---

근데 이렇게 프로세스가 메모리에 불연속적으로 배치되어 있으면 CPU가 어떻게 실행할까?

CPU 입장에서는 ‘다음에 실행할 명령어 위치’를 어떻게 알 수 있을까?

⇒ 프로세스가 물리 주소에 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용

• 페이지 테이블 : 현재 어떤 페이지가 어떤 프레임에 할당되었는지 알려줌

  • 프로세스마다 각자의 프로세스 테이블이 있다.

  • 그래서 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있다.

---

페이징은 외부 단편화 문제를 해결할 수 있지만 내부 단편화 문제를 야기할 수 있다.

• 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생.

기본적으로 설정된 페이지보다 큰 페이지를 대형 페이지라고 함.

---

• 프로세스의 페이지 테이블들은 메모리에 적재

• CPU 내의 페이지 테이블 베이스 레지스터 (PTBR)

  • 프로세스의 페이지 테이블이 적재된 주소를 가리킴.

페이지 테이블이 메모리에 있으면 메모리 접근 시간이 두 배로 늘어난다

1. 페이지 테이블 접근

2. 프레임 접근

→ 이러한 문제를 해결하기 위해 CPU 곁에(일반적으로 MMU 내에) TLB 라는 페이지 테이블의 캐시 메모리

• 페이지 테이블의 일부 내용을 저장 - 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 저장

• TLB 히트 : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우

  • 메모리에 한 번만 접근

• TLB 미스 : 페이지 번호가 TLB에 없을 경우

---

하나의 페이지와 프레임은 여러 주소를 포괄하고 있어서 특정 주소에 접근하려면

1. 어떤 페이지 혹은 프레임에 접근하고 싶은지

2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

페이징 시스템에서는 논리 주소가 페이지 번호와 변위로 이루어져 있다.

• ex) cpu가 32비트 주소를 내보냈다면 N비트는 페이지 번호, 32-N은 변위

• 페이지 번호 : 접근하고자 하는 번호

• 논리 주소 <페이지 번호, 변위> → 물리 주소<프레임 번호, 변위>

  • 논리 주소 변위 = 물리 주소 변위

---

• 페이지 테이블 엔트리 : 페이지 테이블의 각각의 행들

  • 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트

• 유효 비트 : 현재 해당 페이지에 접근 가능한지 여부

  • 메모리에 적재되어 있다 : 1

  • 메모리에 적재되어 있지 않다 : 0

⇒ 페이지 폴트 : CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 할 때 예외 발생

• 보호 비트 : 페이지 보호 기능을 위해 존재하는 비트

  • 읽고 쓰기가 모두 가능 : 1

  • 읽기만 가능 : 0

  • r 읽기, w 쓰기, x 실행

    • 100 , r 1, w 0 , x 0 읽기만 가능

• 참조 비트 : CPU가 이 페이지에 접근한 적이 있는지 여부

  • 적재 이후 CPU가 읽거나 쓴 페이지 : 1

  • 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지 : 0

• 수정 비트 : 해당 페이지에 데이터를 쓴 적이 있는지 없는 수정 여부 = 더티 비트

  • 변경된 적이 있는 페이지 : 1

  • 변경된 적이 없는 페이지 : 0

  • 수정 비트는 페이지가 메모리에 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재 → 왜냐하면 쓰기 작업을 수행한 페이지는 보조기억장치에 저장된 내용과 서로 다른 값을 갖기 때문에 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 하기 떄문에

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

물리 메모리의 크기는 한정되어 있다. 운영체제는 프로세스들이 한정된 메모리에 적재된 페이지를 선별해서 보조기억장치로 내보내고 프레임에 적절한 페이지를 어떻게 할당할까?

• 요구 페이징 : 실행에 요구되는 필요한 페이지만 메모리에 적재하는 기법

• 순수 요구 페이징 : 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 함

  • 첫 명령어 실행하는 순간부터 페이지 폴트 발생, 어느정도 페이지가 적재된 이후부터는 페이지 폴트 발생 빈도 감소

요구 페이징 시스템이 안정적으로 작동하려면

1. 페이지 교체

2. 프레임 할당이 해결되어야 함.

---

메모리에 적재된 많고 많은 페이지 중에 어떤 페이지를 내보내는 것이 최선일까? ⇒ 페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은? ⇒ 페이지 폴트를 가정 적게 일으키는 알고리즘

• 그럼 페이지 폴트 횟수를 알아야겠다. → 페이지 참조열을 통해 알 수 있음

• 페이지 참조열 : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

  • 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문에 연속된 페이지를 생략함.

---

• FIFO 페이지 교체 알고리즘 : 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식

  • 메모리에 가장 먼저 올라와서 프로그램 실행 초기에만 사용되었을 수도 있지만 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있기 때문에 먼저 적재되었다고 내쫓아서는 안된다.

• 2차 기회 페이지 교체 알고리즘 : 한 번 더 기회를 주는 알고리즘

  • 메모리에서 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별해서 참조 비트가 1인 경우 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정

• 최적 페이지 교체 알고리즘 : CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘

  • 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘

  • 근데 앞으로 오랫동안 사용되지 않을 페이지를 어떻게 예측해? → 그래서 실제 구현이 어려움

  • 그래서 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됨.

• LRU 페이지 교체 알고리즘 : 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

  • 페이지마다 마지막으로 사용한 시간을 토대로 교체

---

페이지 폴트가 자주 발생하는 이유

1. 나쁜 페이지 교체 알고리즘

2. 프로세스가 사용할 수 있는 프레임 수가 적음(더 근본적인 이유)

• 스래싱 : 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제

• 멀티프로그래밍의 정도 : 메모리에서 동시 실행되는 프로세스의 수

스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문

⇒ 그래서 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.

• 프레임 할당 방식

  • 정적 할당 방식

    • 균등 할당 : 모든 프로세스에 균등하게 프레임 제공

    • 비례 할당 : 프로세스 크기에 따라 프레임 배분

  • 동적 할당 방식 (프로세스를 실행하는 과정에서 배분할 프레임을 결정)

    • 작업 집합 모델 : 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지

      • 작업 집합 : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합

    • 페이지 폴트 빈도 : 페이지 폴트율에 상한선과 하한산을 정하고, 이 범위 안에서만 프레임을 할당하는 방식

15-1) 파일과 디렉터리

• 파일 : 하드 디스크나 SSD와 같은 보조기억장치에 저장된 관련 정보의 집합 = 의미 있고 관련 있는 정보를 모은 논리적 단위

  • 이름

  • 파일을 실행하기 위한 정보

  • 파일 관련 부가 정보 = 속성 = 메타 데이터

• 파일 속성 : 유형, 크기, 보호, 생성 날짜, 마지막 접근 날짜, 마지막 수정 날짜, 생성자, 소유자, 위치

  • 파일 유형 : 운영체제가 인식하는 파일 종류, 확장자를 이용.

→ 운영체제는 파일 연산(생성, 삭제, 열기, 닫기, 읽기)을 위한 시스템 호출 제공

---

• 디렉터리(폴더) : 파일들을 일목요연하게 관리하기 위해

  • 1단계 디렉터리 : 모든 파일이 하나의 디렉터리 아래

  • 트리 구조 디렉터리 : 여러 계층

    • 최상위 디렉터리 = 루트 디렉터리 : 슬래시(/) 로 표현

    • 서브 디렉터리 = 자식 디렉터리

• 경로 : 디렉터리를 이용해 파일 위치, 파일 이름 특정 짓는 정보

  • 절대 경로 : 루트 디렉터리부터 자기 자신까지 이르는 고유한 경로

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

→ 운영체제는 디렉터리 연산(생성, 삭제,열기, 닫기, 읽기)을 위한 시스템 호출 제공

---

디렉터리는 단지 포함된 정보가 조금 특별한 파일이다.

파일은 내부에 해당 파일과 관련된 정보를 담고 있다면, 디렉터리는 내부에 해당 디렉터리에 담겨 있는 대상과 관련된 정보를 담고 있고 이 정보는 테이블(표) 형태로 구성.

→ 디렉터리는 보조기억장치에 테이블 형태의 정보로 저장.

• 디렉터리 엔터리

  • 디렉터리에 포함된 대상의 이름

  • 해당 대상이 보조기억장치 내에 저장된 위치를 유추할 수 있는 정보

---

• 현재 작업 디렉터리 : 마침표(.)

• 현재 작업 디렉터리의 상위 디렉터리 : 마침표 두 번(..)

15-2) 파일 시스템

⇒ 보조기억장치를 사용하려면 파티션을 나누는 작업(파티셔닝)과 포맷 작업(포매팅)을 거쳐야 사용 가능

• 파티셔닝 : 저장 장치의 논리적인 영역을 구획하는 작업

  • 하드 디스크나 SSD처럼 용량이 큰 저장 장치를 하나 이상의 논리적인 단위로 구획하는 것

• 파티션 : 파티셔닝 작업을 통해 나누어진 영역

• 포매팅 : 파일 시스템을 설정하여

  1. 어떤 방식으로 파일을 저장하고 관리할 것인지 결정

  2. 새로운 데이터를 쓸 준비를 하는 작업

→ 파일 시스템에는 여러 종류가 있고 파티션마다 다른 파일 시스템 설정 가능

보통 파티셔닝과 포매팅은 동시에 진행되는 경우가 많다.

---

운영체제는 파일과 디렉터리를 블록 단위로 읽고 쓴다.

• 파일 할당

  • 연속 할당 : 가장 단순한 방식, 보조기억장치 내 연속적인 블록에 파일을 할당

    1. 파일의 펏 번째 블록 주소

    2. 블록 단위의 길이만 알면 파일에 접근 가능

• 외부 단편화 야기

⇒ 연속 할당 변형 : FAT 파일 시스템

• 불연속 할당

  • 연결 할당 : 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태

    • 파일을 이루는 데이터를 연결 리스트로 관리

    • 외부 단편화 문제를 해결하지만

      1. 반드시 첫 번째 블록부터 읽어야 함. 임의 접슨 속도가 매우 느리다.

      2. 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근 불가능

  • 색인 할당 : 파일의 모든 블록 주소를 색인 블록이라는 하나의 블록에 모아 관리

    • 파일 내 임의의 위치에 접근하기 쉽다.

⇒ 색인 할당 기반 파일 시스템 : 유닉스 파일 시스템

---

• FAT 파일 시스템: 각 블록에 포함된 다음 블록의 주소들을 한데 모아 테이블의 형태로 관리(파일 할당 테이블)

  • FAT를 참고하여 파일의 첫 번재 블록 주소를 알면 파일의 데이터가 담긴 모든 블록에 접근 가능

  • 최근까지 USB 메모리, SD 카드와 같은 저용량 저장 장치용 파일 시스템으로 많이 이용

  • FAT12, FAT16, FAT32, FAT 뒤에 오는 숫자는 블록을 표현하는 비트 수

    • 윈도우에서는 블록대신 클러스터

  • FAT 파일 시스템에서 FAT는 파티션의 앞부분에 만들어진다.

  • 실행하는 도중 FAT가 메모리에 캐시될 수 있다. →임의 접근 성능이 개선

  • FAT 파일 시스템의 디렉터리 엔트리에는 파일 속성과 관련한 다양한 정보가 있다.

• 유닉스 파일 시스템 : 색인 할당 기반, 색인 블록 = i-node

  • i-node에는 파일 속성 정보와 열다섯 개의 블록 주소가 저장

    • i-node의 크기는 유한하다. 그래서

      1. 블록 주소 중 열두 개에는 직접 블록 주소를 저장

      2. 위의 내용으로 충분하지 않다면 열세 번째 주소에 단일 간접 블록 주소 저장

      3. 위의 내용으로 충분하지 않다면 열네 번째 주소에 이중 간접 블록 주소를 저장

      4. 위의 내용으로 충분하지 않다면 열다섯 번째 주소에 삼중 간접 블록 주소를 저장

⇒ 이로써 i-node만 알면 파일 속성뿐만 아니라 파일 크기가 크더라도 파일 데이터를 모두 가리킴.

---

더 알아보기

• 윈도우 운영체제에서 사용되는 NT 파일 시스템(NTFS)

• 리눅스 운영체제에서 사용되는 ext 파일 시스템

숙제!

• p 400, 1번 문제

  • 최초 적합

  • 최악 적합

  • 최적 적합