[혼공컴운] 6주차_Ch14~15

Ch14. 가상 메모리

스와핑

스와핑 (swapping): 메모리에서 사용되지 않는 프로세스를 보조기억장치(스왑 영역)로 내보내고(스왑 아웃), 빈 공간에 다른 프로세스를 적재하는(스왑 인) 메모리 관리 기법
스와핑을 이용하면 프로세스들이 요구하는 메모리 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있음.

연속 메모리 할당 방식

• 최초 적합 (first fit): 메모리 내 빈 공간을 순차 검색하여 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식
• 최적 적합 (best fit): 빈 공간을 모두 검색하여 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 메모리를 할당하는 방식
• 최악 적합 (worst fit): 빈 공간을 모두 검색하여 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 메모리를 할당하는 방식

연속 메모리 할당 방식의 문제점

1. 외부 단편화 (external fragmentation): 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상.
연속 메모리 할당 시 프로세스들이 실행과 종료를 반복하며 메모리 사이 사이에 빈 공간들이 생기므로 외부 단편화가 발생하게 됨.

해결 방안:

• 메모리 압축 (메모리 조각 모음): 흩어져 있는 빈 공간을 하나로 모으는 방식.
  작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하모, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기함.
• 가상 메모리 기법

2. 물리 메모리보다 큰 프로세스를 실행할 수 없음.

가상 메모리

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

페이징

페이징 (paging): 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법

프로세스 전체가 아닌, 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만 메모리에 적재하는 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있음.

그러나, 프로세스가 메모리에 불연속적으로 배치되어 있으면 CPU 입장에서 다음에 실행할 명령어 위치를 찾기 어려워짐. 이를 해결하기 위해 논리 주소를 연속적으로 보이게 하는 페이지 테이블을 이용함.

페이지 테이블

페이지 테이블: 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있는 테이블

프로세스마다 각자의 페이지 테이블이 존재하며, 메모리에 적재되어 있음.
CPU 내의 페이지 테이블 베이스 레지스터 (PTBR)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있음.

TLB (Translation Lookaside Buffer): 페이지 테이블의 캐시 메모리로 페이지 테이블의 일부를 저장함. 일반적으로 CPU의 MMU(메모리 관리 장치) 내에 위치함.

페이지 테이블 접근과 프레임 접근, 총 2번의 메모리 접근이 필요하므로 이를 개선하기 위해 TLB를 사용함. CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트, 없을 경우 TLB 미스라고 함.

내부 단편화 (internal fragmentation): 하나의 페이지보다 프로세스의 크기가 작아 공간이 낭비되는 현상
1. 내부 단편화를 줄이면서 2. 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요함.

페이징에서의 주소 변환

변위 (offset): 접근하려는 주소에서 프레임의 시작 번지로부터의 거리

논리 주소 <페이지 번호, 변위> -- 페이지 테이블 --> 물리 주소 <프레임 번호, 변위>

페이지 테이블 엔트리

페이지 테이블 엔트리 (PTE; Page Table Entry): 페이지 테이블의 각 행을 의미하며, 페이지와 관련된 정보를 포함함.

PTE 구성:

• 페이지 번호

• 프레임 번호

• 유효 비트 (valid bit): 해당 페이지가 메모리에 적재되어 있는지를 나타냄.

  • 페이지가 메모리에 적재되어 있다면 1, 아니면 0
  • 접근하려는 페이지가 메모리에 적재되어 있지 않다면, 페이지 폴트가 발생함.

• 보호 비트 (protection bit): 페이지 보호 기능을 위해 존재하는 비트로, 페이지 접근 권한을 나타냄.

  • 읽기만 가능한 페이지는 0, 읽고 쓰기가 모두 가능한 페이지는 1
  • r(read), w(write), x(execute)로 구성된 세 개의 비트를 사용하여 접근 권한을 세밀하게 나타낼 수도 있음.

• 참조 비트 (reference bit): CPU가 해당 페이지에 접근했는지를 나타냄.

  • 적재 이후 CPU가 페이지에 접근했다면 1, 아니면 0

• 수정 비트 (modified bit, dirty bit): 페이지가 수정되었는지를 나타냄.

  • 페이작 변경된 적이 있다면 1, 아니면 0
  • 페이지가 스왑 아웃될 때, 해당 페이지를 보조기억장치에 다시 저장해야 하는지를 결정하는 데 사용됨.

요구 페이징

요구 페이징 (demand paging): 프로세스를 메모리에 적재할 때, 실행에 요구되는 필요한 페이지만을 메모리에 적재하는 기법

기본 동작:
1. CPU가 특정 페이지에 접근하는 명령어 실행
2. 유효 비트가 1이면, CPU는 페이지가 적재된 프레임에 접근
3. 유효 비트가 0이면, 페이지 폴트가 발생
4. 페이지 폴트 처리 루틴: 필요한 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5. 다시 1번 수행

메모리가 가득 찰 경우 페이지 교체가 필요하며, 어떤 페이지를 내보낼지 결정하는 방법을 페이지 교체 알고리즘이라고 함.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘: 페이지 폴트를 최소하하는 알고리즘

페이지 참조열 (page reference string): CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

• FIFO 페이지 교체 알고리즘
  메모리에 적재된 페이지 순서대로 교체하는 알고리즘
  구현이 간단하나, 성능은 좋지 않음.

• 2차 기회 페이지 교체 알고리즘
  FIFO 페이지 교체 알고리즘 + 참조 비트 참고
  가장 오래된 페이지를 교체하되, 참조 비트가 1인 경우 이를 0으로 바꾸고, 페이지 교체를 보류하여 1번의 기회를 줌.

• 최적 페이지 교체 알고리즘
  가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
  페이지 폴트 발생 빈도가 가장 적으나, 미래의 접근을 예측해야 하므로 실제 구현이 어려움.
  주로 다른 페이지 교체 알고리즘의 성능 평가를 위한 기준으로 사용됨.

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

스래싱

페이지 폴트가 자주 발생하는 이유:
1. 나쁜 페이지 교체 알고리즘
2. 프로세스가 사용할 수 있는 프레임 수가 적은.

스래싱 (thrashing): 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 현상
스래싱의 근본적인 원인: 각 프로세스가 원활하게 실행되기 위해 필요한 최소한의 프레임 수가 보장되지 않음.

=> OS는 각 프로세스가 무리 없이 실행되도록 충분한 프레임을 할당해야 함.

프레임 할당

프레임 할당 방식:

• 균등 할당 (equal allocation)
  모든 프로세스에 균등한 프레임을 배분하는 방식
  프로세스 크기가 다르므로 균등한 배분은 비효율적일 수 있음.

• 비례 할당 (proportional allocation)
  프로세스 크기에 따라 프레임을 배분하는 방식
  실제로 얼마나 많은 프레임이 필요한지는 실행해봐야 알 수 있어, 프로세스 크기만을 기준으로 하는 것은 제한적일 수 있음.

• 작업 집합 모델 (working set model) 기반 프레임 할당
  작업 집합의 크기만큼만 프레임을 할당하는 방식
  작업 집합: 프로세스가 일정 기간 동안 참조할 페이지 집합

• 페이지 폴트 빈도(PFF; Page-Fault Frequency) 기반 프레임 할당
  페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

정적 할당 방식 (단순히 프로세스 크기와 물리 메모리 크기만을 고려): 균등 할당, 비례 할당
동적 할당 방식 (프로세스의 실행 상황을 고려하여 프레임 수를 조정): 작업 집합 모델 기반 프레임 할당, PFF 기반 프레임 할당

Ch15. 파일 시스템

파일과 디렉터리

파일 (file): 의미 있고 관련 있는 정보를 모은 논리적 단위
파일 구성: 이름, 파일을 실행하기 위한 정보, 파일 관련 부가 정보(속성/메타데이터)
확장자: 파일 유형을 나타내며, OS에 파일의 형식을 알려줌.

디렉터리 (directory, folder): 여러 개의 파일 또는 디렉터리를 묶어 관리하는 특별한 형태의 파일
모든 파일이 하나의 디렉터리 아래에 있는 1단계 디렉터리에서 시작하여, 여러 계층을 가진 트리 구조 디렉터리로 발전함.
트리 구조 디렉터리: 최상위 디렉터리(루트 디렉터리)와 그 아래 여러 서브 디렉터리(자식 디렉터리)로 구성됨.
루트 디렉터리는 일반적으로 슬래시(/)로 나타내며, Windows OS에서는 C:\로 표시됨.

절대 경로 (absolute path): 루트 디렉터리에서 시작하는 경로
상대 경로 (relative path): 현재 디렉터리에서 시작하는 경로

파티셔닝과 포매팅

파티셔닝 (partitioning): 하드 디스크나 SSD처럼 용량이 큰 저장 장치를 하나 이상의 논리적인 단위로 구획하는 작업. 파티셔닝 작업으로 나누어진 각 영역을 파티션이라고 함.

포매팅 (formatting): 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지 결정하고, 새로운 데이터를 쓸 수 있게 하는 작업

• 저수준 포매팅: 저장 장치를 생성할 당시 공장에서 수행되는 물리적인 포매팅
• 논리적 포매팅: 사용자가 파일 시스템을 생성하는 포매팅

파일 할당 방법

OS는 하나 이상의 섹터를 블록이라는 단위로 묶어 블록 단위로 파일과 디렉터리를 관리함.

• 연속 할당 (contiguous allocation)
  보조기억장치 내 연속적인 블록에 파일을 할당하는 방식
  디렉터리 엔트리에 파일 이름, 첫 번째 블록 주소, 블록 단위의 길이가 명시됨.
  구현이 단순하나, 외부 단편화를 야기함.

• 연결 할당 (linked allocation)
  각 블록 일부에 다음 블록의 주소를 저장하여 블록들을 연결 리스트 형태로 관리하는 방식
  디렉터리 엔트리에 파일 이름, 첫 번째 블록 주소가 명시됨.
  외부 단편화 문제는 해결되지만, 임의 접근이 느리고 하드웨어 고장 시 이후 블록에 접근할 수 없는 단점이 있음.

• 색인 할당 (indexed allocation)
  파일의 모든 블록 주소를 색인 블록 (index block)에 모아 관리하는 방식
  디렉터리 엔트리에 파일 이름과 색인 블록 주소가 명시됨.
  연결 할당과 달리 파일 내 임의 접근이 용이함.

현재는 불연속 할당 방식을 사용함.

파일 시스템 종류

• FAT 파일 시스템
  파일 할당 테이블(FAT; Faile Allocation Table)을 이용하는 연결 할당 기반의 파일 시스템
  USB 메모리, SD 카드 등 저용량 저장 장치에 주로 사용됨.
  FAT 파일 시스템은 연결 할당 방식을 사용하지만, 각 블록에 포함된 다음 블록의 주소들을 FAT로 관리하여 임의 접근 성능을 개선함.
  연결된 블록의 주소를 디스크의 한 위치에 모아 둔 구조로, 파일의 처음부터 순차적으로 접근하지 않고도 빠르게 특정 블록에 접근할 수 있음.

• 유닉스 파일 시스템
  i-node (index-node, 색인 블록)를 이용하는 색인 할당 기반의 파일 시스템
  유닉스 계열 OS에서 주로 사용됨.
  유닉스 파일 시스템에서는 파일마다 고유한 i-node가 있고, 각 i-node에는 파일 속성 정보와 15개의 블록 주소가 저장됨.
  15개의 블록 주소 중 처음 12개에는 파일 데이터가 저장된 블록 주소를 직접적으로 명시하며 이를 직접 블록이라 함.
  파일 크기가 커서 12개의 직접 블록만으로 모든 데이터를 가리킬 수 없는 경우, 13번째 블록에 단일 간접 블록의 주소를 저장함. 이 블록에는 파일 데이터를 저장한 블록 주소가 저장됨.
  14번째 블록은 단일 간접 블록들의 주소를 저장하는 이중 간접 블록이고, 15번째 블록은 이중 간접 블록들의 주소를 저장하는 삼중 간접 블록임.
  

기본 숙제

p.400 확인 문제 1번

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

추가 숙제

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

페이지 폴트가 3회 발생한다.