[혼공학습단 11기 혼공컴운💿] 컴퓨터구조+운영체제 week6

✍️기본 미션

p. 400의 확인 문제 1번 풀고 인증하기

 

 

✍️선택미션

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

 
2 3 1 -> 5 3 1 -> 5 3 2 -> 4 3 2 로 변화하는 과정에서 3번의 페이지 폴트가 발생한다.

---

🗒️내용 정리

Chap14. 가상 메모리

14.1 *연속 메모리 할당

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

1) 스와핑 (swaping)

- 현재 실행되지 않는 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재해 실행하는 방식
- 스왑 영역 (swap space) : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
- 스왑 아웃 (swap out) : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
- 스왑 인 (swap in) : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
- 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시에 실행 가능하다.
 

2) 메모리 할당

(1) 최초 적합 (first fit)

• 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스 배치
• 검색을 최소화할 수 있고, 빠른 할당이 가능하다.

(2) 최적 적합 (best fit)

• 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치한다. 

(3) 최악 적합 (worst fit)

• 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치한다. 

 

3) 외부 단편화 (external fragmentation)

- 연속 메모리 할당은 외부 단편화 문제를 내포한다.

• 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이에 빈 공간들이 생긴다.
• 프로세스 바깥에 생기는 빈 공간들은 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래한다. → 메모리 낭비

- 외부 단편화의 해결 : 메모리를 압축(compaction)

• 메모리 내에 저장된 프로세스를 적당히 재배치해 흩어져 있는 작은 빈 공간을 하나의 큰 빈 공간으로 만든다.
• 작은 빈 공간들을 모으는 과정에서 시스템은 하던 일을 중단해야 한다.
• 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기한다.
• 오버헤드를 최소화하면서 압축할 수 있는 것에 대한 명확한 방법을 결정하기 어렵다.

- 외부 단편화의 해결 : 가상 메모리 기법 중 페이징 기법
 

14.2 페이징을 통한 가상 메모리 관리

1) 페이징 (page)

- 가상 메모리 (virtual memory) : 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
- 페이징
: 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
- 페이징에서도 스와핑을 사용 가능하다.

• 페이징 시스템에서의 스왑 아웃 : 페이지 아웃 (page out)
• 페이징 시스템에서의 스왑 인 : 페이지 인 (page in)

- 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에적재하고, 당장 실행에 필요하지 않은 페이지들은보조기억장치에 남겨둔다. 
 

2) 페이지 테이블 (page table)

- 프로세스가 메모리에 불연속적으로 배치되어 있다면 이를 순차적으로 실행할 수 없다.
- 논리 주소에는 프로세스가 연속적으로 배치되도록 페이지 테이블을 이용한다.
- 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 순차적으로 실행하면 된다.
- 페이지 테이블 베이스 레지스터 (PTBR : Page Table Base Register)

• 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
• 페이지 테이블을 메모리에 두면 메모리에 있는 페이지 테이블을 보고, 알게 된 프레임에 접근한다. → 2번의 메모리 참조
• 위의 문제를 해결하기 위해 CPU(일반적으로 MMU 내에) TLB(Translation Lookable Buffer)라는 페이지 테이블의 캐시 메모리를 둔다. (참조 지역성에 근거)
  • TLB 히트 (TLB hit) : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 존재한다.
  • TLB 미스 (TLB miss) : CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 존재하지 않는다.

* 내부 단편화 (internal fragmentation)

• 프로세스 크기가 페이지의 배수가 아닐 때 발생
• 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생
• 내부 단편화를 적당히 방치하면서 너무 크지 않은 페이지 테이블이 만들어지지 않도록 페이지 크기를 조정해야 한다.

 

3) 페이징에서의 주소 변환

- 특정 주소에 접근하기 위해 필요한 정보

• 접근하고 싶은 페이지나 프레임
• 접근하려는 주소가 그 페이지이나 프레임으로부터 떨어져 있는 정도 

- 페이징 시스템에서는 모든 논리 주소가 페이지 번호(page number)와 변위(offset)로 이루어져 있다.

• 페이지 번호 : 접근하고자 하는 페이지 번호
• 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 떨어져 있는지에 대한 정보

- 논리 주소 <페이지 번호, 변위>가 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환된다.
 

4) 페이지 테이블 엔트리 (PTE : Page Table Entry)

- 페이지 테이블의 각각의 행
- 페이지 번호, 프레임 번호 외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트와 같이 중요한 정보가 담긴다.
- 유효 비트 (valid bit) 

• 현재 해당 페이지에 접근 가능한지 여부를 알려준다.
• 현재 페이지가 메모리에 적재되어 있다면 1,  적재되어 있지 않다면(보조기억장치에 있다면) 0
• 페이지가 유효 비트가 0인 메모리에 접근하려 하면 페이지 폴트(page fault)라는 예외가 발생한다.

CPU의 페이지 폴트 처리 : 하드웨어 인터럽트 처리와 유사

① CPU는 기존의 작업 내역을 백업한다.
② 페이지 폴트 처리 루틴을 실행한다.
③ 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤에 유효 비트를 1로 변경한다.
④ 페이지 폴트를 처리했다면 CPU는 이제 해당 페이지에 접근 가능하다.

 
- 보호 비트 (protection bit)

• 페이지 보호 기능을 위해 존재한다.
• 읽기만 가능한 페이지 : 0
• 읽고 쓰는 것이 가능한 페이지 : 1
• read, write, execute를 모두 표현하기 위해 3비트(rwx)로 복잡하게 구현할 수 있다.

- 참조 비트 (reference bit)

• CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.
• 적재 이후 CPU가 읽고 쓴 페이지 : 1
• 적재 이후 한 번도 읽거나 쓴 적이 없는 페이지 : 0

- 수정 비트 (modified bit)

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다.
• 더티 비트(dirty bit)라고도 한다.
• 변경된 적이 있는 페이지 : 1
• 변경된 적이 없는 페이지 : 0
• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 유무를 판단하는 데 사용된다.

 

5) 페이징의 이점 :  쓰기 시 복사 (copy on write)

- 프로세스 간에 페이지를 공유 가능하다.
- 부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리킨다.
- 부모 혹은 자식 프로세스 중 하나가 페이지에 쓰기 작업을 하면 그 순간 해당 페이지가 별도의 공간으로 복제되어 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
- 프로세스 생성 시간을 줄이고, 메모리 공간 절약이 가능하다.
 
6) 계층적 페이징 (hierarchical paging)
- 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않아도 된다.
- 페이지 테이블을 여러 개의 페이지로 쪼개고, 이 페이지들을 가리키는 페이지 테이블(항상 메모리에 있어야 한다.)을 둔다.
- 논리주소 : 바깥 페이지 번호(페이지 테이블의 페이지 찾기), 안쪽 페이지 번호, 변위
- 페이지 테이블의 계층이 늘어날수록 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 늘어난다. 
 

14.3 페이지 교체와 프레임 할당

1) 요구 페이징 (demand paging)

- 프로세스를 메모리에 적재할 때 필요한 페이지만을 메모리에 적재하는 방법
- 요구 페이징의 기본적인 양상

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

- 순수 요구 페이징 (pure demand paging)

• 어떤 페이지도 메모리에 적재하지 않은 채 시작
• 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생
• 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다.

- 페이징 시스템이 안정적으로 작동하기 위해 페이지 교체, 프레임 할당을 해결해야 한다.
 

2) 페이지 교체 알고리즘

- 메모리가 가득 찼을 때 보조기억장치로 내보낼 페이지를 결정하는 알고리즘
- 페이지 폴트를 가장 적게 일으키는 알고리즘이 좋은 알고리즘이다.
- 페이지 폴트 횟수를 알아야 하고, 이를 위해 페이지 참조열(page reference string)을 이용한다.
- 페이지 참조열 : CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지 열 
 
(1) FIFO 페이지 교체 알고리즘 (First-In First-Out Page Replacement Algorithm)
- 메모리에 가장 먼저 올라온 페이지부터 내보낸다.
- 아이디어와 구현이 간단하지만, 자주 참조되는 페이지가 내보내질 수 있다.
- 2차 기회 페이지 교체 알고리즘 (second chance page replacement algorithm)

• FIFO 페이지 교체 알고리즘의 변형
• 기본적으로 메모리에서 가장 오래 머무른 페이지를 대상으로 내보낼 페이지를 선별한다.
• 페이지 참조 비트가 1일 경우, 참조 비트를 0으로 만들고 현재 시간을 적재 시간으로 설정한다. 

(2) 최적 페이지 교체 알고리즘 (optimal page replacement algorithm)
- CPU에 의해 참조되는 횟수를 고려한다.
- 가장 낮은 페이지 폴트율을 보장한다.
- 실제 구현이 어려우므로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용한다. (최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 페이지 폴트의 하한선으로 간주)
 
(3) LRU 페이지 교체 알고리즘 (LRU ; Least Recently Used Page Replacement Algorithm)
- 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
- 아이디어 : 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이다.
 

3) 스래싱과 프레임 할당

(1) 스래싱 (thrashing)

• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요해 성능이 저해되는 문제
• 프레임이 부족하면 CPU는 페이지 폴트가 자주 발생할 수밖에 없다.
• 멀티프로그래밍의 정도 (degree of multiprogramming) : 메모리에서 동시 실행되는 프로세스의 수
• 멀티프로그래밍의 정도를 늘린다고 해서 CPU 사용률이 비례해서 증가하지 않는다.

 
(2) 프레임 할당

• 스래싱이 발생하는 근본적인 원인 : 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았다.
• 운영체제는 각 프로세스들이 무리없이 실행되기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼의 프레임을 할당해 줄 수 있어야 한다.
• 정적 할당 방식: 프로세스의 크기와 물리 메모리의 크기만 고려
  • 균등 할당 (equal allocation) : 모든 프로세스에 균등하게 프레임 분배 → 비합리적
  • 비례 할당 (proportional allocation) : 프로세스 크기에 비례하게 프레임 분배
  • 하나의 프로세스가 필요로 하는 프레임의 양은 실제 실행해야 아는 경우가 많다.
• 동적 할당 방식: 프로세스를 실행하는 과정에서 배분할 프레임을 결정
  •  작업 집합 모델 (working set model)를 사용하는 방식
    • 프로세스가 일정 기간 참조한 페이지 집합을 기억해 빈번한 페이지 교체 방지
    • 작업 집합 (working set) : 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
  • 페이지 폴트 빈도(PFF; Page-Fault Frequency)를 사용하는 방식
    • 페이지 폴트율이 너무 낮으면 해당 프로세스가 너무 많은 프레임을 가진다는 가정과 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 가지고 있다는 가정에서 출발
    • 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임 할당

 
 

Chap15. 파일 시스템

15.1 파일과 디렉터리

1) 파일 (file)
- 보조기억장치에 저장된 관련 정보의 집합
- 파일의 구성

• 이름
• 파일을 실행하기 위한 정보
• 속성(attribue) : 파일 관련 부가 정보, 메타데이터(metadata)라고도 한다. 

 
2) 디렉터리(directory)
- 파일을 일목요연하게 관리하기 위해 사용
- 1단계 디렉터리 (single-level directory) : 모든 파일이 하나의 디렉터리 하에 있다.
- 트리 구조 디렉터리 (tree-structured directory) : 최상위 디렉터리(루트 디렉터리, root directory) 하에 여러 서브 디렉터리가 있고, 서브 디렉터리가 다른 서브 디렉터리를 가질 수 있다.
- 대부분의 운영체제에서 디렉터리는 특별한 형태의 파일로 간주한다.
- 디렉터리 엔트리 : 해당 디렉터리에 담겨 있는 대상과 곤련된 정보가 표의 형태로 저장되어 있다. 
 

15.2 파일 시스템

1) 파티셔닝과 포매팅

- 파티셔닝 (partitioning)

• 저장 장치의 논리적인 영역을 구획하는 작업
• 파티션 (partition) : 파티셔닝 작업을 통해 나누어진 영역

- (논리적) 포매팅 (formating)

• 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지를 결정하고, 새로운 데이터를 쓸 준비를 하는 작업
• 포매팅까지 완료하여 파일 시스템을 설정했다면 파일과 디렉터리를 생성할 수 있다.

 

2)  파일 할당 방법

- 운영체제는 파일과 디렉터리를 블록 단위로 읽고 쓴다.
- 하드 디스크의 가장 작은 단위는 섹터이지만, 운영체제는 하나 이상의 섹터를 블록이라는 단위로 묶어 관리한다.
- 파일을 보조기억장치에 할당하는 방법

• 연속 할당
• 불연속 할당
  • 연결 할당
  • 색인 할당

(1) 연속 할당 (contiguous allocation)
- 보조기억장치 내 연속적인 블록에 파일을 할당하는 방식
- 디렉터리 엔트리에 파일 이름과 첫 번째 블록 주소, 블록 단위의 길이를 명시한다.
- 구현이 단순하지만, 외부 단편화를 야기한다. 
 
(2) 연결 할당 (linked allocation)
- 각 블록 일부에 다음 블록의 주소를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당한다.
- 파일을 이루는 데이터를 연결 리스트로 관리한다.
- 디렉터리 엔트리에 파일 이름과 첫 번째 블록 주소, 블록 단위의 길이를 명시한다.
- 외부 단편화를 해결한다.
- 파일 내 임의의 위치에 접근하는 임의 접근(random access) 속도가 매우 느리다.(반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 한다.)
- 하드웨어 고장이나 오류 발생 시 해당 블록 이후는 접근할 수 없다.
- 연결 할당을 조금 변형한 FAT 파일 시스템이 오늘날까지 많이 사용된다.
 
(3) 색인 할당 (indexed allocation)
- 파일의 모든 블록 주소를 색인 블록(indexed block)에 모아 관리한다.
- 파일 내 임의의 위치에 접근하기 쉽다.
- 디렉터리 엔트리에 파일 이름과 색인 블록 주소를 명시한다.
- 색인 할당을 기반으로 유닉스 파일 시스템이 만들어졌다.
 

3) 파일 시스템 살펴보기

(1) FAT 파일 시스템
- 연결 할당의 단점을 보완한 파일 시스템
- FAT을 이용하는 파일 시스템 
- 파일 할당 테이블 (FAT; File Allocation Table) : 각 블록에 포함된 다음 블록의 주소들을 모아 테이블 형태로 관리한다.
- FAT는 파티션의 앞 부분에 만들어진다.

- FAT는 하드 디스크 파티션 시작 부분에 있지만, 실행 도중 FAT가 메모리에 캐시될 수있다. → 임의 접근의 성능 향상
 
(2) 유닉스 파일 시스템
- 색인 할당 기반 
- 유닉스 파일 시스템에서는 색인 블록을 i-node(index-node)라고 부른다.
- i-node에는 15개의 블록 주소와 파일 속성 정보가 저장될 수 있다.
- 파일마다 i-node가 있고, i-node마다 번호가 부여되어 있다. i-node 들은 파티션 내 특정 영역에 모여 있다. 

- i-node의 크기는 유한하다.

• 블록 주소 중 12개에는 직접 블록 주소를 저장한다.
  • 파일 데이터가 저장된 블록 주소가 직접적으로 명시된다.
  • 직접 블록(direct block) :파일 데이터가 저장된 블록
• 위의 내용으로 충분하지 않다면 13번째 주소에 단일 간접 블록 주소를 저장한다.
  • 단일 간접 블록(single indirect block) : 파일 데이터를 저장한 블록 주소가 저장된 블록
• 위의 내용으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소를 저장한다.
  • 이중 간접 블록 주소(double indirect block) : 데이터 블록 주소(단일 간접 블록의 주소)를 저장된 블록
• 위의 내용으로 충분하지 않다면 15번째 주소에삼중 간접 블록 주소를 저장한다.
  • 삼중 간접 블록(triple indirect block) : 이중 간접 블록 주소가 저장된 블록

(3) 기타 파일 시스템 : NTFS, ext 파일 시스템
 
(4) 저널링 파일 시스템
- 파일 시스템 변경 도중 시스템 크래시(컴퓨터가 강제로 종료된 상황)가 발생하면 파일 시스템이 훼손될 수 있다.
- 저널링 파일 시스템 이전에는 부팅 직후 시스템을 검사하고 복구하는 프로그램을 실행해 파일 시스템 내 모든 블록에 대해 파일 시스템을 검사한다. → 시간이 매우 오래 걸린다.
- 저널링 파일 시스템

• 저널링(journaling) 기법을 이용한다.
• 저널링 기법 : 작업 로그를 통해 시스템 크래시가 발생했을 때 빠르게 복구한다.
• 파일 시스템 변경 작업 진행 순서
  1. 작업 직전 파티션의 로그 영역에 수행 작업에 대한 로그를 남긴다.
  2. 로그를 남긴 후 작업을 수행한다.
  3. 작업이 완료되면 로그를 삭제한다.
• 시스템 크래시가 발생한 직후에 로그 영역을 읽어 당시 실행 중이던 작업을 알아내고 해당 작업을 완료한다.

 
 

---

🤔 느낀 점

지난 기수에서 혼공자바를 완주하면서도 했던 생각이지만 책 1회독을 마치니 굉장히 뿌듯하네요. 이번 여름에도 혼공학습단을 할 생각이라 벌써 책도 골라뒀습니다. 아마  혼공머신을 할 것 같습니다.
 
6주동안 다들 수고 많으셨습니다. 행복한 설 연휴 보내세요!