혼공학습단 10기 - 혼공컴운 (6주차)
6주 차 목표
| # | 진도 | 기본 미션 | 선택 미션 |
| 6주차 (8/14 ~ 8/20) |
Chapter 14 ~ 15 | p. 400의 확인 문제 1번 풀고 인증하기 | Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기 |
드디어 마지막 주차!
이러니 저러니 해도 지금까지 공부하느라 고생한 나 자신이 대견하다 ㅋㅋㅋ
1/3 안에는 든 것이니 뿌듯 ^~^
기본 미션
p.400 확인 문제 1번
Q. 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.
[보기] 최초 적합, 최적 적합, 최악 적합
- ( 1 ): 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
- ( 2 ): 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
- ( 3 ): 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
A. 1: 최초 적합, 2: 최악 적합, 3: 최적 적합
선택 미션
Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기
LRU 페이지 교체 알고리즘은 '오랫동안 사용되지 않은 페이지를 교체하는 알고리즘'이다.
페이지 참조열을 바탕으로 어떤 페이지가 어디에 있을지 표를 만들어보자.
| 페이지 참조열 | 프레임 1 | 프레임 2 | 프레임 3 | 보조기억장치 | 설명 |
| 2 | 2 | 페이지2 적재 | |||
| 3 | 2 | 3 | 페이지3 적재 | ||
| 1 | 2 | 3 | 1 | 페이지1 적재 | |
| 3 | 2 | 3 | 1 | 페이지3 이미 적재되어 있음 | |
| 5 | 5 | 3 | 1 | 2 | 페이지 폴트 발생! 페이지2가 가장 오랫동안 사용되지 않음 |
| 2 | 5 | 3 | 2 | 1 | 페이지 폴트 발생! 페이지1이 가장 오랫동안 사용되지 않음 |
| 3 | 5 | 3 | 2 | 1 | 페이지3 이미 적재되어 있음 |
| 4 | 4 | 3 | 2 | 1, 5 | 페이지 폴트 발생! 페이지5가 가장 오랫동안 사용되지 않음 |
| 2 | 4 | 3 | 2 | 1, 5 | 페이지2 이미 적재되어 있음 |
| 3 | 4 | 3 | 2 | 1, 5 | 페이지3 이미 적재되어 있음 |
그러므로 페이지 폴트는 총 3번 발생함을 알 수 있다.
메모
14 - 1 연속 메모리 할당
1. 연속 메모리 할당: 프로세스에 연속적인 메모리 공간을 할당
2. 스와핑: 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고(스왑 아웃(swap out)), 생긴 빈 공간에 새 프로세스 적재(스왑 인(swap in)).
- 실제 메모리 크기보다 더 많은 프로세스 실행 가능.
3. 프로세스는 메모리 내의 빈 공간에 적재되어야 하는데, 빈 공간이 여러 개 있을 때 적재되는 방법은 아래와 같다.
- 최초 적합(first-fit): 적재가 가능한 첫 공간.
- 최적 적합(best-fit): 적재가 가능한 제일 알맞는(사이즈가) 공간.
- 최악 적합(worst-fit): 적재가 가능한 제일 큰 공간.
4. 외부 단편화(external fragmntation): 프로세스들이 실행되고 종료되길 반복하며 메모리 사이에 빈 공간이 발생하는데, 프로세스를 할당하기 어려울 만큼 작은 공간들이 발생하여 메모리 낭비가 되는 것. 해결 방법은 아래와 같음.
- 메모리 압축(compaction): 프로세스를 재배치 시켜 빈 공간들을 하나로 모으는 방식. 그러나 재배치하는 과정에서 많은 오버헤드 발생 가능.
- 가상 메모리 기법, 페이징 기법(14 - 2)
14 - 2 페이징을 통한 가상 메모리 관리
1. 가상 메모리(virtual memory): 물리 메모리보다 더 큰 프로세스를 실행하는 기법. 실행할 프로세스의 일부만 메모리에 적재한다.
- 가상메모리 관리 기법에는 크게 페이징(주로 사용), 세그멘테이션이 있음.
2. 페이징(paging): 프로세스의 논리 주소 공간을 일정 단위로 자르고(페이지), 메모리의 물리 주소 공간을 페이지와 동일한 단위로 잘라서(프레임), 페이지를 프레임들에 불연속적으로 할당하는 기법. 일정한 크기로 잘라져 있기 때문에 외부 단편화 발생 억제.
- 페이징에서도 스와핑이 가능함. 페이지를 내보내고(스왑 아웃, 페이지 아웃(page out)) 페이지를 가져옴(스왑 인, 페이지 인(page in)). 즉 일부 페이지가 메모리에 적재되지 않아도 프로세스는 실행 가능하다.
3. CPU는 페이지가 어느 프레임이 적재되어 있는지 모르기 때문에 다음에 실행할 명령어를 찾기 어려움. 그래서 페이지 번호와 프레임 번호를 매핑해주는 페이지 테이블(page table)을 이용. 페이지 테이블은 프로세스별로 존재함.
- 외부 단편화는 해결되나 내부 단편화(internal fragmentation)의 문제가 발생 가능. 마지막 페이지는 보통 하나의 페이지 크기보다 작기 때문. 물론 외부 단편화에 비해 메모리 낭비가 적음.
- 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
- 페이지 테이블이 메모리에 있으면, 1. 페이지 테이블을 참조 2. 페이지를 참조하느라 메모리 접근 시간이 두 배가 걸린다. 그래서 TLB라는 캐시 메모리에 페이지 테이블의 일부를 저장한다. (TLB 미스, TLB 히트.)
- 페이징 시스템에서의 논리 주소는 페이지 번호(page number, 어떤 페이지에 접근하고 싶은지)와 변위(offset, 접근하려는 주소가 페이지로부터 얼마나 떨어져 있는지)으로 이루어져 있다.
- <페이지 번호, 변위> 논리 주소는 페이지 테이블을 통해 <프레임 번호, 변위>로 변환된다.
4. 페이지 테이블의 행들을 페이지 테이블 엔트리(PTE; Page Table Entry)라 부르는데 여기에는 대표적으로 아래와 같은 정보가 담긴다.
- 유효 비트(valid bit): 현재 해당 페이지에 접근 가능한지 여부. 메모리에 적재되어 있는지를 나타낸다. 페이지 아웃되었다는 뜻. 유효 비트가 0인 페이지에 접근하려고 하면, 페이지 폴트(page fault)라는 인터럽트가 발생한다.
- 보호 비트(protection bit): 페이지 보호를 위해 존재하는 비트. 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지 나타냄. 0일 경우 readonly, 1일 경우 둘 다 가능. 세 개의 비트로도 구현할 수 있으며 읽기(Read)의 R, 쓰기(Write)의 W, 실행 (eXecute)의 x로 나타낸다.
- 참조 비트(reference bit): CPU가 접근한 적이 있는지 여부.
- 수정 비트(modified bit, 더티 비트(dirty bit)): 페이지가 수정된 적이 있는지 여부. 수정된 적이 있다면 스왑 아웃 될 때, 보조기억장치에 덮어쓸 때 변경된 내용을 반영해야 함.
5. 쓰기 시 복사(copy on write): fork 시스템을 호출하면 부모 프로세스를 복사하여 자식 프로세스가 생성되는데, 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리킨다. 물론 프로세스는 자원을 공유하지 않기 때문에, 둘 중 한 프로세스가 페이지에 쓰기 작업을 수행하면 해당 페이지는 별도의 공간으로 복제된다.
- 프로세스 생성 시간 절약, 메모리 절약
6. 계층적 페이징(hierarchical paging, 다단계 페이지 테이블(multilevel page table)): 페이지 테이블 전체를 메모리에 두는 것은 메모리 낭비이기 때문에 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식.
14 - 3 페이지 교체와 프레임 할당
1. 처음부터 모든 페이지를 적재하지 않고, 요구되는 페이지만 메모리에 적재하는 기법을 요구 페이징(demand paging)이라고 함. CPU가 특정 페이지에 접근하는 명령어를 실행하면, 유효 비트를 확인하여 1일 때는 바로 프레임에 접근하고, 0일 경우 페이지 폴트가 발생하여 루틴을 실행하여 페이지를 메모리에 적재한다.
- 순수 요구 페이징(pure demand paging)은 프로세스를 실행할 때 아무 페이지도 메모리에 적재하지 않는 것.
2. 메모리가 꽉 찼을 때 어떤 페이지를 쫓아낼지 결정하는 것을 페이지 교체 알고리즘이라 한다.
- 좋은 페이지 교체 알고리즘은 일반적으로 페이지 폴트가 적은 것. 보조기억장치에 접근하는 것은 성능 저하를 일으키기 때문.
- 페이지 참조열(page reference string): CPU가 참조하는 페이지들 중 연속된 페이지를 생략한(가져올 때 페이지 폴트 없음) 페이지열
3. 대표적인 페이지 교체 알고리즘
- 1. FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm): 가장 오래된 페이지부터 내쫓는다. 구현은 간단하나 내쫓는 기준에 빈도가 반영되지 않음.
- 2. 2차 기회(second chance) 페이지 교체 알고리즘: FIFO 페이지 교체 알고리즘과 마찬가지로 가장 오래된 페이지를 대상으로 하나, 만약 해당 페이지의 참조 비트가 1이라면 0으로 만들고 적재 시간을 현재 시간으로 설정한다.
- 3. 최적 페이지 교체 알고리즘(optimal page replacement algorithm): CPU가 참조하는 횟수를 고려. 앞으로의 사용 빈도가 가장 낮은 페이지를 교체한다. 페이지 교체 알고리즘 중 페이지 폴트 발생 빈도가 가장 낮다. 그러나 앞으로 오랫동안 사용되지 않을 페이지를 알아내기 힘들기 때문에 이론상의 성능 하한선으로서 존재.
- 4. LRU(Least-Recently-Used) 페이지 교체 알고리즘: 가장 오래되지 사용되지 않은 페이지 교체. 이 알고리즘에서 파생된 알고리즘도 많다.
4. 페이지 폴트가 자주 발생하는 근본적인 이유는 프로세스가 사용할 수 있는 프레임 자체가 적은 것. 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱(thrashing)이라고 함.
- 메모리에서 동시에 실행되는 프로세스의 수를 멀티프로그래밍의 정도(degree of multiprogramming)이라고 하는데, 멀티프로그래밍의 정도가 어느정도 높아질 때까지는 CPU 이용률이 늘어나나 프레임 수가 보장되지 않을 정도가 되면 페이지 폴트가 빈번하게 발생하여 성능이 저하된다.
- 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
- 프레임 할당 방식
- 균등 할당(equal allocation): 모든 프로세스들에게 균등하게 프레임을 할당하는 방식.
- 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 프레임을 할당하는 방식. 그러나 실행 전의 물리 메모리 크기와 프로세스의 크기만을 고려한 정적 할당 방식이기 때문에 실행한 뒤는 알 수 없음.
- 작업 집합 모델(working set model): CPU가 특정 시간 동안 참조한 페이지 개수만큼만 프레임을 할당하는 방식.
15 - 1 파일과 디렉터리
1. 파일 시스템(file system): 파일과 디렉터리를 관리하는 운영체제 내의 프로그램. 파일과 디렉터리는 보조기억장치 내의 데이터 덩어리로, 이를 사용할 수 있게 도와줌.
2. 파일(file): 보조기억장치에 저장된 관련 정보의 집합. 파일을 실행하기 위한 정보와 부가 정보 (속성(attribute), 메타데이터(metadata))로 이루어져 있다.
- 대표적인 속성의 종류: 유형(확장자(extension)), 크기, 보호, 생성 날짜, 마지막 접근 날짜, 마지막 수정 날짜, 생성자, 소유자, 위치
- 파일을 다루는 모든 작업은 운영체제에 의해 이루어진다. 운영체제는 파일 연산을 위한 시스템 호출을 제공한다.
3. 디렉터리(directory): 윈도우 운영체제에서는 폴더(folder)라고 부른다. 예전 디렉터리는 하나만 존재하였으나(1단계 디렉터리(single-level-directory)) 현재는 여러 계층(트리 구조 디렉터리(tree-structured directory))으로 파일 및 폴더를 관리한다. 최상위 디렉터리는 루트 디렉터리(root directory)라고 한다.
- 경로(path): 특정 파일에 접근하기 위하여 디렉터리, 파일 위치, 파일 이름을 특정 짓는 정보.
- 절대 경로(absolute path): 루트 디렉터리에서부터 자기 자신까지 이르는 고유한 경로.
- 상대 경로(relative path): 현재 디렉터리에서 자기 자신까지 이르는 경로.
- 많은 운영체제에서는 디렉터리를 특별한 형태의 파일로 간주. 파일과 디렉터리를 구분 짓지 않음. 디렉터리는 해당 디렉터리에 담겨 있는 대상과 관련된 정보를 담고 있음. 그리고 이는 테이블 형태로 구성되며 공통적으로 파일 이름과 위치를 유추할 수 있는 정보를 담고 있음.
- ..는 상위 디렉터리, .은 현재 디렉터리를 가리킴.
15 - 2 파일 시스템
1. 새로운 저장 장치를 사용할 때 파티셔닝과 포매팅이 필요하다.
- 파티셔닝(partitioning): 저장 장치의 논리적인 영역을 구획하는 작업. 파티셔닝 작업을 통해 나누어진 영역 하나하나를 파티션(partition)이라고 한다.
- 포매팅(formatting): 어떤 방식으로 파일을 관리할지 결정하고 새로운 데이터를 쓸 준비를 하는 작업. 포맷 작업을 할 때 파일 시스템이 결정된다. 파일 시스템은 파티션마다 다르게 설정할 수 있다.
2. 운영체제는 파일/디렉터리를 블록 단위(섹터가 모인 단위)로 읽고 쓴다. 하나의 파일은 여러 블록에 걸쳐 저장되는데, 블록에 할당하는 방법에는 크게 연속 할당과 불연속 할당 두 가지가 있으며 불연속 할당은 또 연결 할당, 색인 할당으로 나누어진다. 주로 쓰이는 방법은 불연속 할당.
- 연속 할당(contiguous allocation): 연속적인 블록에 파일을 할당하는 방식. 연속 할당을 사용하는 파일 시스템의 디렉터리 엔트리에는 파일 이름, 첫 번째 블록 주소, 블록 단위 길이를 명시한다.
- 단순한 방법이나 외부 단편화를 야기한다. (메모리 연속 할당과 동일한 문제)
- 연결 할당(linked allocation): 연결 리스트 형태로 할당. 각 블록의 일부에 다음 블록의 주소를 저장. 다음 주소가 없다면 특별한 표시자를 기록한다. 디렉터리 엔트리에는 파일 이름, 천 번째 블록 주소, 블록 단위 길이를 명시한다.
- 반드시 첫 번째 블록부터 차례로 읽어야 한다. 파일 내 임의의 위치에 접근하는, 임의 접근(random access)속도가 매우 느리다. 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없다.
- 이런 단점들을 보완한 파일 시스템이 FAT 파일 시스템이다.
- 색인 할당(indexed allocation): 파일의 모든 블록 주소를 색인 블록(index block)이라는 한 블록에 기록한다. 디렉터리 엔트라에는 파일 이름, 색인 블록 주소를 명시한다.
3. FAT 파일 시스템: 연결 할당 기반의 파일 시스템. USB 메모리, SD 카드 등 저용량 저장 장치에서 사용. 다음 블록 주소들을 모아 테이블 형태로 관리하는데 이를 파일 할당 테이블(FAT; File Allocation Table)이라고 부름. FAT가 메모리에 캐시 될 경우 임의 접근 속도 개선됨.
- 버전에 따라 FAT12, FAT16, FAT32가 있는데 뒤에 오는 숫자들은 블록을 표현하는 비트 수를 의미.
- FAT 파일 시스템의 파티션은 예약 영역, FAT 영역, 루트 디렉터리 영역, 데이터 영역 순으로 구성된다.
- FAT 파일 시스템의 디렉터리 엔트리에는 파일 이름, 첫 번째 블록 주소, 이 외에도 파일 속성과 관련한 다양한 정보들이 명시된다.
4. 유닉스 파일 시스템: 색인 할당 기반의 파일 시스템. 색인 블록을 i-node(index-node)라고도 부른다. i-node에는 파일 속성 정보와 15개의 블록 주소가 저장될 수 있다.
- 유닉스 파일 시스템의 파티션은 예약 영역, i-node, 데이터 영역 순으로 구성된다.
- 주소를 저장하는 방법
- 1. 블록 주소 중 12개에는 직접 블록(direct block, 파일 데이터를 저장한 블록) 주소를 저장.
- 2. 블록이 충분하지 않다면 13번째 주소에 단일 간접 블록(single indirect block, 파일 데이터를 저장한 블록 주소가 저장된 블록) 주소를 저장한다.
- 3. 이래도 부족하다면 14번째 주소에 이중 간접 블록(double indirect block, 파일 데이터를 저장한 블록 주소를 저장한 블록 주소가 저장된 블록) 주소를 저장한다.
- 4. 그래도 부족하다면 15번째 주소에 삼중 간접 블록(triple indirect block, 파일 데이터를 저장한 블록 주소를 저장한 블록 주소를 저장한 블록 주소가 저장된 블록) 주소를 저장한다.
- 유닉스 파일 시스템의 디렉터리 엔트리에는 파일 이름과 i-node 번호로 구성된다.