https://github.com/BOOOO0/linux-operating-system
GitHub - BOOOO0/linux-operating-system: 리눅스 명령어, 이론과 운영체제 실습
리눅스 명령어, 이론과 운영체제 실습. Contribute to BOOOO0/linux-operating-system development by creating an account on GitHub.
github.com
깃허브에 더 많은 내용이 있습니다.
페이징 (Paging)
페이징 기법은 한 프로세스의 물리적 주소 공간을 연속적이지 않게 해서 연속 메모리 할당(Contiguous Allocation)의 단점인 외부 단편화를 피하고 hole들의 압축을 하지 않을 수 있게끔 한다.
● 운영체제와 하드웨어의 도움을 받아서 수행한다.
페이징의 기본 방법 (Basic Method of Paging)
물리적 주소를 고정된 크기의 블록(Frame)으로 쪼갠다.
그리고 논리적 주소도 고정된 크기의 블록(Page)으로 쪼갠 다음에 서로 맵핑 시킨다.
1MB인 메모리를 1KB씩 프레임으로 나눴다고 가정하고
64KB 논리적 주소 공간을 1KB씩 페이지로 나눈 상태라면 이 페이지가 물리적 주소의 어느 프레임을 가더라도 상관이 없다.
논리적 주소 공간을 물리적 주소와 완전히 분리시킨다.
페이지 번호를 부여하고 페이지 변위를 부여한다.
CPU가 generate 했을 때 어떤 주소가 물리주소를 쓸 필요없이 예를들면 2번 페이지의 34번째 주소를 aceess하는 것이다.
페이지 번호 (The page number)
프로세스별로 크기와 페이지 수가 다르기 때문에 페이지 테이블(Page Table)에 의해서 관리된다.
CPU가 주소를 generate하면 몇번 페이지의 몇번 변위에 특정 주소가 있다는 정보가 정해진다.
그 페이지 번호를 따라 페이지 테이블로 가면 페이지 테이블엔 몇번 프레임에 할당되는지 물리적 주소로 표현되어있고 페이지 변위는 그대로 전달된다.
페이지 테이블에 기반해서 물리 메모리의 프레임의 순서와 상관없이 자유롭게 할당하고 프레임의 크기가 모두 같기 때문에 외부 단편화는 발생하지 않는다.
페이지 사이즈 (Page Size)
- 하드웨어에 의해서 정의된다.
- 반드시 2의 배수여야 한다.
논리적 주소 공간이 2^m이고 페이지 사이즈가 2^n이라면 상위 m-n 비트는 페이지 번호 하위 n 비트는 페이지 변위이다.
논리적 주소 공간은 2^m 으로 16이고 페이지의 크기는 2^n으로 4이다.
페이지의 크기와 프레임의 크기는 같고 페이지 테이블의 정보에 따라 정해진 물리 메모리의 프레임에 할당 된다.
새로운 프로세스가 도착해서 실행될 때
페이지들을 Memory Allocation 하기 위해서는 free-frame list의 순서에 기반해서 새로운 프로세스 페이지 테이블이 생성된다.
하드웨어 지원 (Hardware Support)
CPU 스케줄러가 새로운 프로세스를 실행하려 할 때, 문맥교환이 일어날 때 페이지 테이블도 다시 적재해야한다.
왜냐면 문맥교환이 일어나는 동안 나가있다가 재진입을 하는데 페이지 테이블의 주소가 여전히 유효할지는 알 수가 없기 때문이다.
또한 프로그램의 크기가 크면 페이지 테이블의 크기도 크기 때문에 특별한 관리가 필요하다.
페이지 테이블 기준 레지스터 (Page-Table Base Register)
페이지 테이블 자체는 메모리에 두고 PTBR로 페이지 테이블의 주소를 가리킨다.
PTBR만 PCB에 저장하면 되기 때문에 문맥교환이 빨라진다.
그러나 여전히 메모리 접근 시간은 느리다.
PTBR로 페이지 테이블 그리고 페이지 테이블에서 프레임으로 두번의 access가 필요하기 때문이다.
TLB (Translation Look-aside Buffer)
소형 하드웨어 캐시이며 key와 value를 가지고 있다.
찾는 페이지 번호와 같은 key를 찾으면 value인 frame 번호를 즉시 알려주고 매우 빠르다.
Effective Memory Access Time
- TLB hit : 우리가 찾고자 하는 페이지가 TLB 안에 있는 경우
- TLB miss : 우리가 찾고자 하는 페이지가 TLB 안에 없는 경우
적중률 (hit ratio)
ex) 10ns to access memory
80% hit ratio : EAT = 0.8 x 10 + 0.2 x 20(TLB에 없으면 2번 접근으로 2배) = 12ns
99% hit ratio : EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns
페이징에서의 메모리 보호
각 페이지에 붙은 보호 비트(Protection Bit)에 의해 보호가 이루어진다.
보호비트는 주로 페이지 테이블에 속해있다.
각 엔트리에 유효/무효 비트를 추가하여 접근 가능 여부를 판단한다.
비트가 유효로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타내고 비트가 무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
Illegal address access라면 트랩을 건다.
페이지 테이블을 보면 페이지 수가 6개이기 때문에 할당된 6개 프레임 외의 접근은 보호 비트가 무효로 설정되어있다.
공유 페이지 (Shared Page)
공유하는 공통의 코드(ex.공유 라이브러리, DLL)의 공유에 용이하다.
Standard C Libary를 생각해보면 libc라는 라이브러리 모듈이 있는데 각 프로세스가 libc의 복사본을 각각 다른 물리 주소에 가지고 있다면 굉장히 비효율적이다.
그래서 공유가 필요하고 공유를 하려면 코드가 재진입 가능(Reentrant)해야한다.
재진입 가능 코드는 수행하는 동안 절대로 변하지 않는다. (Read Only)
P1, P2, P3 모두 페이지에 libc를 가지고 있다.
그러나 물리적으로는 한번만 주소 할당이 되고 논리적으로 copy되어 있기 때문에 페이지 테이블이 가리키는 프레임은 모두 동일한 것을 알 수 있다.
※ 읽기만하고 수행도중 변하지 않기 때문에 데드락이 발생하지 않는다.
페이지 테이블의 구조 (Structure of Page Table)
논리적 주소 공간이 크기가 너무 커지면 페이지 테이블도 그것에 따라서 크기가 지나치게 커져버린다.
그렇기 때문에 페이지 테이블에 대한 관리가 필요한데 3가지 방법이 있다.
계층적 페이징 (Hierarchical Paging)
페이지 테이블을 페이지로 나눈다. 그리고 해당 페이지 테이블의 페이지 내에 페이지 테이블을 갖고 있는 것이다.
여기서 p1은 바깥 페이지 테이블의 페이지 번호이고 p2는 안쪾 페이지 테이블의 페이지 내의 변위이다.
그리고 p1과 p2는 같다.
그 후 변위인 d를 따라 이동한 후 거기서 나타내는 물리 주소의 프레임을 찾아 할당된다.
해시 페이지 테이블 (Hash Page Table)
우리가 어떤 데이터를 넣고 빼고를 반복할때 가장 효율적인 방법은 해시 테이블이다.
page number를 해시 함수로 해싱해서 얻은 해시 값으로 물리적 주소에 접근한다.
주소 공간이 32비트보다 커지면 주로 사용한다.
역 페이지 테이블 (Inverted Page Table)
역 페이지 테이블은 pid를 가지고 어떤 프로세스가 어떤 페이지를 가졌는지를 역으로 저장해서 효율적으로 주소를 맵핑하고 페이지 테이블의 크기를 줄이는 효과를 얻을 수 있다.
'Operating System' 카테고리의 다른 글
| Operating System : Concepts - 가상 메모리 (Virtual Memory) (2) (0) | 2022.10.06 |
|---|---|
| Operating System : Concepts - 가상 메모리(Virtual Memory) (1) (0) | 2022.08.06 |
| Operating System : Concepts - 주 메모리(Main Memory) (4) (0) | 2022.07.19 |
| Operating System : Concepts - 주 메모리(Main Memory) (2) (0) | 2022.07.18 |
| Operating System : Concepts - 주 메모리(Main Memory) (1) (0) | 2022.07.15 |