CS(Computer science)
[운영체제] 메모리 관리 (4) : 프로세스의 불연속적 할당에 대해
오늘도 타는중
2023. 1. 19. 14:43
메모리 관리 (4) : 프로세스의 불연속적 할당에 대해
# Allocation of Physical Memory
# Paging
# Page Table의 구현
# Effective Access Time
# 2단계 Page Table
✍️ 본 포스팅은 이화여자대학교 반효경 교수님의 "운영체제" 강의를 들으며 정리한 내용입니다.
공부했던 내용을 다시 되짚어 보자. 프로세스의 physical memory를 어떻게 할당했었지??
*Allocation of Physical Memory

- 메모리는 일반적으로 두 영역으로 나뉘어 사용한다.
- 여기서 말하는 메모리는 physical memory를 말함
- OS 상주 영역 : inherrupt vector와 함께 낮은 주소 영역 사용
- 사용자 프로세스 영역 : 높은 주소 영역 사용
- 사용자 프로세스 영역의 할당 방법
- Contiguous allocation
- 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
- 고정 분할 방식(Fixed partitiion allocation)
- 가변 분할 방식(Variable partition allocation)
- Noncontiguous allocation
- 하나의 프로세스가 메모리의 여러 영역에 분산(불연속)되어 올라갈 수 있음
- Paging
- Segmentation
- Paged Segmentation
-> 이번 시간에는 사용자 프로세스의 불연속적 할당(Noncontiguous allocation)에 대해 자세히 알아보자.
*Paging

- 프로세스의 virtual memory를 동일한 사이즈의 page 단위로 나눈다.
- Virtual memory의 내용이 page 단위로 불연속적으로 저장된다.
- 일부는 backing storage에, 일부는 physical memory에 저장된다.
- 기본적인 방법
- physical memory를 동일한 크기의 frame으로 나눈다.
- logical memory를 동일 크기의 page로 나눈다. (frame과 같은 크기로)
- 모든 가용 frame들을 관리한다.
- page table을 사용하여 logical address를 physical address로 변환한다.
- 위 그림에서 2번 page는 page table의 2의 위치에서 3을 가리키고 이 3은 physical memory의 frame을 의미
- 외부 조각(External fragmentation) 발생 X
- 내부 조각(Internal fragmentation) 발생 O
*Page Table의 구현
- Page table은 main memory에 상주한다.
- Page-table base register (PTBR)가 page table의 시작지점 가리킨다.
- Page-table length register (PTLR)가 테이블 크기를 보관한다.
- 모든 메모리 접근 연산에는 2번의 메모리 access가 필요하다.
- page table을 통한 주소 변환을 위한 접근 1번, 실제 데이터 수행을 위한 접근 1번
- 속도 향상을 위해 associative register 혹은 translation look-aside buffer (TLB)라 불리는
고속의 캐시 메모리(lookup hardware cache)를 사용한다.
- TLB를 활용한 Paging

- 기존처럼 모든 메모리 접근 연산을 2번 하는 것을 피하기 위한 방법
- TLB는 page table에서 빈번히 참조되는 일부 엔트리(page 번호, frame 번호)를 캐싱(임시 저장) 하고 있다.
- CPU가 논리적인 주소를 요청하면 page table로 접근하기 전에 TLB를 먼저 검색해본다.
- TLB에 존재하는 엔트리 값들로 처리가 가능한지 확인한다.
- 가능하다면 TLB를 통해 바로 주소 변환이 이루어 진다. (page table 접근 총 1번)
- 불가능하다면 원래처럼 pge table에 접근하여 주소 변환을 한다. (page table 접근 총 2번)
- 하지만, 매번 TLB의 데이터를 모두 검색해야하는 문제가 존재하는데
-> 이를 Associative Register을 통해 해결한다.
- Associative Register의 주소 변환 과정
- page table 중 일부가 associative register에 보관되어 있다.
- 만약 해당 page 번호가 associative register에 있는 경우 곧바로 frame 번호를 얻는다.
- 없는 경우 main memory에 존재하는 page table로부터 frame 번호를 얻는다.
- TLB는 각 프로세스마다 존재하는데, CPU가 다른 프로세스가 넘어가서 context switch가 일어나면
새 TLB를 사용하기 위해 기존 TLB를 flush (모든 엔트리 비워주기) 해야한다.
-> 그렇다면 실제로 메모리 접근하는데 시간이 얼마나 소요되는걸까??
*Effective Access Time
- TLB 접근 시간(Associative register lookup time) = t (메인 메모리 접근 시간 이하임)
- 메인 메모리 접근 시간(memory cycle time) = 1
- Hit ratio = a : associative register에서 찾아지는 비율
- Effective Access Time (EAT)
- <hit> <miss>
EAT = (1 + t)a + (2 + t)(1 - a)
= 2 + t - a
- <hit> <miss>
*2단계 Page Table

- 현대 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다.
32 비트 주소 사용 시 : 2^32 (4G)의 주소 공간 사용 가능
- 각 page 크기가 4K 시 1M개의 page table 엔트리가 필요
- 각 page 엔트리가 4B 시 프로세스 당 4M의 page table 필요
- 그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비된다.
-> 해결 방법 : page table 자체를 page로 구성하면
-> 사용되지 않는 주소 공간에 대한 바깥 페이지 테이블(outer page table)의 엔트리 값은 Null
(대응하는 안쪽 페이지 테이블(inner page table)이 없음)
*2단계 Page Table 예시
- logical address (32비트 muchine with 4K page 크기)의 구성
- 20 비트의 page number
- 12 비트의 page offset
- page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다.
(각 page tabe entry가 4B)
-> p2 : 안쪽 테이블은 실제 memory와 동일하게 구성해야하므로
page 크기 4KB를 page 테이블 엔트리 크기 4B로 나누면 1KB = 1K -> 2^10개 -> 10비트
-> page offset : page 전체 크기인 4KB = 2^10 * 4 = 2^12 = 12비트
-> p1 : 바깥쪽 테이블의 페이지는 전체 주소 공간에서 남은 공간을 차지 -> 32비트 - (10비트 + 12비트) = 10비트
- 10 비트의 page number
- 10 비트의 page offset
- 따라서, logical address는 다음과 같다.

- P1은 바깥 page table의 page number이고
- P2는 안쪽 page table의 page number
- d는 page 안에서 bite 단위로 얼마나 떨어져 있는지를 구분하는 page offset을 의미
- 2단계 Paging에서의 주소 변환 scheme
