[운영체제] Chapter 8. Memory Management (2), (3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

Paging, Dynamic Relocation, Address Translation Architecture, Implementation of Page Table, Paging Hardware with TLB, Associative Register, Effective Access Time, Two-Level Page Table, Address-Translation Scheme, Two-Level Paging Example, Multilevel Paging and Performance, Two-Level Page Table, Valid/Invalid Bit in a page Table, Memory Protection, Inverted Page Table, Inverted Page Table Architecture, Shared Page, Shared Pages Example

 

5. 물리적 메모리의 할당 방식

• 메모리는 일반적으로 OS 상주 영역과 사용자 프로세스 영역으로 나뉘어 사용된다.
  • 사용자 프로세스 영역: 물리적 메모리의 높은 주소 영역을 사용, 여러 사용자 프로세스들이 적재되어 실행
    • 사용자 프로세스 영역의 할당 방법: 연속 할당(Contiguous allocation)과 불연속 할당(Noncontiguous allocation)

5-1. 연속 할당 (Contiguous allocation)

• 각각의 프로세스가 메모리의 한 곳에 연속적인 공간에 적재되도록 하는 것

5-1-1. 고정 분할 방식 (Fixed partition allocation)

• 물리적 메모리를 고정된 크기의 분할로 미리 나누어두는 방식

5-1-2. 가변 분할 방식 (Variable partition allocation)

• 분할을 미리 나누어 놓지 않은 채 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식

5-2. 불연속 할당 (Noncontiguous allocation)

• 하나의 프로세스가 메모리의 여러 영역에 분산되어 적재될 수 있는 것

5-2-1. 페이징 기법 (Paging)

• 프로세스의 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식
  • 논리적 메모리의 내용이 페이지 단위로 noncontiguous(불연속적)하게 저장됨
  • 물리적 메모리에 한꺼번에 올릴 필요가 없어 일부는 backing stoarage에, 일부는 물리적 메모리에 저장
• Basic Method

  

  • 물리적 메모리를 동일한 크기의 frame(= page가 들어갈 수 있는 위치, 틀)으로 나눈다.
    • 모든 가용 프레임들을 OS가 관리한다.
  • 논리적 메모리를 동일한 크기(= frame과 같은 크기)의 page으로 나눈다.
    • 페이징 기법은 메모리를 같은 크기로 미리 분할해 두더라도 페이지와 프레임의 크기가 같이 때문에 빈 프레임이 있으면 어떤 위치이든 사용될 수 있어서 연속할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다.
  • page table: 주소 변환이 페이지 단위로 이루어지기 때문에 특정 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어있다는 페이지별 주소 변환 정보를 유지하는 일종의 배열
    • 페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블을 가짐
    • 테이블은 프로세스가 가질 수 있는 페이지의 개수(= 논리적 메모리의 페이지 개수)만큼 주소 변환 엔트리를 가짐
    • 인덱스를 통해 순차 검색 없이 곧바로 접근할 수 있는 구조
  • 페이지의 크기와 프레임의 크기가 동일하기 때문에
    • 메모리상의 가용 공간의 크기가 작아서 빈 공간임에도 활용하지 못하는 외부 조각 문제 발생 X
    • 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부조각이 발생할 가능성 O
      • 제일 마지막에 위치한 페이지의 크기가 frame의 배수가 된다는 보장이 없기 때문에

5-2-1-1. 주소 변환 기법

• 페이징 기법에서는 CPU가 사용하는 논리적 주소를 페이지 번호(p)와 페이지 오프셋(d)으로 나누어 주소 변환에 사용한다.
  • 페이지 번호: 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스로 사용
    • 해당 인덱스의 항목(entry)에는 그 페이지의 물리적인 메모리상의 기준 주소(=시작 주소)가 저장
  • 페이지 오프셋: 하나의 페이지 내에서 변위(displacement)를 알려준다. 
    • 페이지 안에서 얼마만큼 떨어져 있는지를 나타내는 오프셋은 변하지 않는다.
    • 기준 주소 + 변위 = 논리적 주소에 대응하는 물리적 주소

5-2-1-2. 페이지 테이블의 구현

• 페이지 테이블은 메인 메모리에 상주한다. 즉 물리적 메모리에 위치한다.
  • 각 프로그램마다 페이지 테이블이 별도로 존재
  • 페이지 테이블의 크기가 너무 크기 때문에 레지스터나 캐시메모리에 위치할 수 없다.
  • 또한 메모리 접근을 위한 주소 변환 자료구조인데 하드디스크에 저장할 수 없다.
• PTBR(Page-table base register): 페이지 테이블 기준 레지스터: 메모리 내에서 페이지 테이블의 시작 위치를 가리킴
• PTLR(Page-table length register): 페이지 테이블 길이 레지스터: 페이지 테이블의 크기를 보관
• 페이징 테이블 기법에서의 메모리 접근 연산은 2번
  • 주소 변환을 위해 페이지 테이블에 접근 + 변환된 주소에서 실제 데이터에 접근
    • 메모리 한 번 접근하기 위해 메모리에 두 번 접근하는 오버헤드 발생 ⇒ TLB 속도 향상
• TLB(Translaction Look-aside Buffer): 고속의 주소 변환용 하드웨어 캐시

  

  • TLB에는 페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱하고 있다.
    • TBL에는 메인메모리보다 접근속도가 빠른 하드웨어로 구성
    • 요청되는 페이지에 대한 주소는 변환 정보가 TLB에 존재할 수도 있고 그렇지 않을 수도 있다.
    • TLB에는 프로세스의 모든 페이지에 대한 주소 변환 정보를 가지고 있지 않기 때문에 논리적인 페이지 번호(= 인덱스)와 이에 대응하는 물리적 메모리의 프레임 번호가 쌍으로 저장되어야 한다.
  • CPU가 논리적인 주소에 접근하려 하면
    1. 페이지 테이블에 접근하기 전에 TLB를 먼저 검색한다.
       • TLB는 특정 항목을 검색하는 것이 아니라 전체를 다 검색해야 한다. (parallel search)
       • parallel search: TLB의 모든 항목을 검색하는 오버헤드를 줄이기 위해 모든 항목을 동시에 검색하는 병렬탐색이 가능한 연관 레지스터(associative register)를 사용
       • 병렬탐색으로 한 번의 TLB 접근 시간에 TLB내의 모든 항목을 한꺼번에 조사
    2. (TLB hit) 요청된 페이지 번호가 TLB에 존재한다면 곧바로 대응하는 물리적 메모리의 프레임 번호를 얻을 수 있다.
       - 메모리 접근 1번
    3. (TLB miss) TLB에 존재하지 않는 경우 메인 메모리에 있는 페이지 테이블로부터 프레임 번호를 알아내서 물리적 메모리에 접근한다. - 메모리 접근 2회
  • 주소 변환 정보는 프로세스별로 다 다르기 때문에 문맥교환 시 이전 프로세스의 주소 변환 정보를 담고 있던 TLB 내용은 모두 지워버려야 한다.
  • 연관 레지스트를 사용할 때 평균적인 메모리 접근시간(Effectice Access Time: EAT)
    • TLB접근 시간 ε < 메모리 접근 시간 1
    • TLB로부터 주소 변환이 되는 비율 α
    • Effective Access Time = (1 + ε)α + (2 + ε)(1 - α) = 2 + ε - α
      • hit: (1 + ε)α: (TLB 접근 시간 + 실제 데이터 접근 메모리 시간) * TLB 변환 비율
      • miss: (2 + ε)(1 - α): (TLB 접근 시간 + 페이지 테이블 접근 시간 + 실제 데이터 접근 메모리 시간) * TLB 변환 실패 비율
      • ε은 매우 적은 값, α은 거의 1에 가까운 값
        → 2 + ε - α는 페이지 테이블만 있을 때 접근하는 시간인 2보다 훨씬 적은 값

5-2-1-3. 계층적 페이징(Multilevel Paging)

• 32비트 주소 체계를 사용하는 컴퓨터에서는 2^32byte(= 4GB)의 주소 공간을 갖는 프로그램을 지원할 수 있다.
  • 페이지 크기가 4KB → 페이지 테이블 항목은 1M 개(4GB/4KB)
    • 2^10 = K, 2^20 = M, 2^30 = G
  • 페이지 테이블 항목이 4byte를 필요 → 한 프로세스당 페이지 테이블을 위해 4MB 크기의 메모리 공간 필요 (4byte * 1M)
  • 수행 중인 프로세스의 수가 증가함에 따라 전체 메모리의 상당 부분이 주소 변환을 위한 페이지 테이블에 할애되어 실제로 사용가능한 메모리 공간이 크게 줄어들게 된다.
• 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부분만을 사용하므로 페이지 테이블을 위한 메모리의 사용은 심각한 공간 낭비라고 할 수 있다.
  • 페이지 테이블은 중간에 사용이 안 되는 항목이 있다고 해도 빼고 만들 수 없다 - 배열은 인덱스를 통해 접근하는데 인덱스를 중간에 빼먹을 수 없기 때문
  • 페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징(two-level paging) 기법 사용
• 2단계 페이징(Two-Level Page Table)
  • 주소 변환을 위해 외부 페이지 테이블(outer page table)과 내부 페이지 테이블(inner page table)의 두 단계에 걸친 페이지 테이블을 사용한다.
    • 32bit machine, 4K(=2^12) page size 일 때 → 20 bit의 page number, 12 bit의 page offset
      • (d) 내부 페이지 테이블의 크기가 4KB, 외부 페이지 테이블에서 내부 페이지 테이블이 얼마나 떨어져 있는지를 구분하기 위해서는 4KB(= 2^12), 즉 12bit만큼이 필요하다.
    • page table 자체가 page로 구성되기 때문에 → 10 bit의 page number, 10 bit의 page offset
      • (P2) 내부 페이지 테이블이 페이지화되어서 물리적 메모리의 프레임에 올라감, 내부 페이지의 엔트리 수는 1K개(= 4KB/4B), 즉 외부 페이지 테이블에서 내부 페이지 테이블에서 몇 번째에 떨어져 있는지를 구분하기 위해서는 10bit(= 2^10) 만큼이 필요하다.
      • (P1) 나머지 10bit
    • 외부 페이지 테이블의 시작 주소는 PTBR이 가지고 있다.

  

  • 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하여, 여기에 대응하는 내부 페이지 테이블을 생성하지 않는 것이다.
  • 내부 페이지 테이블 하나(= 외부 페이지 테이블 하나가 가리키는 내부 페이지 테이블 전체)의 크기가 4KB, 내부 페이지 테이블 내부의 페이지들은 각 4B가 1K 개 있음 ~ 내부 페이지 테이블 하나하나가 페이지화 되어서 물리적인 메모리의 페이지 프레임 하나에 들어가 있는 형태
  • 주소 공간이 더 커지면 다단계 페이지 테이블이 필요하다. ~ 최외곽 페이지 테이블만 만들어진다.
  • • 페이지 테이블을 위해 사용되는 메모리 공간의 소모는 줄일 수 있지만 그만큼 메모리에 대한 접근 횟수가 많아지기 때문에 메모리 접근시간이 크게 늘어나는 문제 발생
    • TLB를 함께 사용하면 다단계 페이지 테이블의 공간적 이득과 메모리 접근시간도 그다지 늘지 않음
      • 4단계 페이지 테이블을 사용하는 경우
      • 메모리 접근시간 100ns, TLB 접근시간 20ns, TLB hit ratio 98%
      • EAT = 0.98 * 120 + 0.02 * 520(4번 메모리 접근 400ns + 실제 데이터 접근 100ns + TLB 접근 20ns) = 128ns
      • 결과적으로 실제 메모리에 접근하는 100ns를 제외하면 주소 변환을 위해 28ns만 소요되므로 페이지 테이블을 4단계로 구성해서 발생하는 시간 오버헤드는 그다지 크지 않지만 공간의 효율적인 사용효과는 매우 클 것으로 기대할 수 있다.

5-2-1-4. 메모리 보호(Memory Protection)

• 페이지 테이블의 각 항목에는 주소 변환 정보뿐 아니라 메모리 보호를 위한 protection bit(보호비트)와 valid-invalid bit(유효-무효 비트)를 두고 있다.
• protection bit(보호비트): 각 페이지에 대한 연산 접근 권한의 내용을 담고 있다.
  • 한 프로세스의 주소 공간은 다른 프로세스에 의해 접근될 수 없으므로 ‘누구’에 해당하는 접근 권한을 설정할 필요는 없다
  • 각 페이지에 대해 어떠한 접근을 허용하는지의 정보가 저장: read/write/read-only
    • 코드 영역: read-only
    • 스택, 데이터 영역: read/write
• valid-invalid bit(유효-무효 비트): 해당 페이지에 대한 내용이 유효한지에 대한 내용을 담고 있다.
  • valid: 해당 주소의 프레임에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻하며 접근이 허용된다.
  • invalid: 해당 주소의 프레임에 유효한 내용이 없음을 뜻하고 유효한 접근 권한이 없다.
    • 그 프로세스가 그 주소부분을 사용하지 않거나
    • 해당 페이지가 물리적 메모리에 올라와 있지 않고 백킹스토어에 있는 경우
      • 하지만 이 경우에도 프로그램의 최대 크기만큼 페이지 테이블의 엔트리는 생겨야 한다.

5-2-1-5. 역페이지 테이블(Inverted Page Table)

• 페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유
  • 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문
  • 대응하는 페이지가 메모리가 있든 아니든 간에 페이지 테이블에는 엔트리로 존재하기 때문
  • 이를 해결하기 위한 대안: 역페이지 테이블(inverted page table)
• 역페이지 테이블(inverted page table)

  

  • 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것
    • 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식
    • 시스템 전체에 페이지 테이블을 하나만 두는 방법
  • 페이지 테이블의 각 항목은 각각의 물리적 메모리의 페이지 프레임이 담고 있는 내용을 표시한다.
    • 프로세스 번호 pid, 프로세스 내의 논리적 페이지 번호 p
  • 물리적 주소로부터 논리적 주소를 얻기 수월한 구조
    • 역페이지 테이블에서의 주소 변환은 다소 비효율적 측면이 있다.
      • 주소 변환 요청 → 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부 판단을 위해 페이지 테이블 전체를 다 탐색해야 하는 오버헤드가 있다.
    • associative register(연관 레지스터)에 보관해 테이블 전체 항목에 대한 parallel search(병렬 탐색)을 가능하게 함으로써 시간적 효율성을 꾀하게 된다.

5-2-1-6. Shared Page(공유 페이지)

• Shared code(공유 코드): 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드
  • re-entrant code(재진입 가능 코드), pure code(순수 코드)라고도 불림
• Shared Page(공유 페이지)란 공유 코드를 담고 있는 페이지를 말한다.
  • 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있게 한다.
  • read-only로 하여 프로세스 간에 하나의 코드만 메모리에 올린다.
  • 모든 프로세스의 logical address space에 동일한 위치에 있어야 한다.
    • shared code에 해당하는 페이지는 동일한 logical address - 주소 바인딩 예제처럼 코드 안에는 logical address가 적혀 있다. 이 logical address는 컴파일 된 코드를 어디다 올려놓을 것인가만 바꾸는 것이지 기계어 코드 자체를 바꿀 수는 없다.
    • 동일한 physical address는 당연함
    • → 공유 페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다.
• private page(사유 페이지): 프로세스들이 공유하지 않고 프로세스별로 독자적으로 사용하는 페이지
  • 해당 프로세스의 논리적 주소 공간 중 어떠한 위치에 있어도 무방

 

[복습]

1. 주소변환은 논리 주소로부터 물리 주소를 얻는 과정, 이 과정은 하드웨어의 몫, 운영체제가 관여하지 않는다.
2. 연속 할당
   
   • 고정 분할 방식
   • 가변 분할 방식
3. 불연속 할당- 페이징 기법: 주소 공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장
   • frame(물리) 크기 == page(논리) 크기
4. 페이지 테이블: 메인 메모리(물리적 메모리)에 상주
   
   • PTBR: 메모리 내에서 페이지 테이블의 시작 위치
   • PTLR: 페이지 테이블의 크기 보관
5. TLB(Translaction Look-aside Buffer): 페이지 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱
   1. 문맥교환 시 이전 프로세스의 주소 변환 정보를 담고 있던 TLB 내용은 모두 지워버려야 한다.
6. 계층적 페이징 - 2단계 페이징: 외부 페이지 테이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블
   
   • 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 항목을 NULL로 설정하여, 여기에 대응하는 페이지 테이블을 생성하지 않는다.
7. 메모리 보호-보호비트: 각 페이지에 대한 연산 접근 권한의 내용을 담고 있다. valid-invalid bit(유효-무효 비트)
8. 역페이지 테이블: 물리적 메모리의 페이지 프레임 하나당 페이지 테이블에 하나씩의 항목을 두는 방식, 메모리 공간을 위해
9. 공유 페이지: 여러 프로세스에 의해 공유되는 페이지로 물리적 메모리에 하나만 적재되어 메모리를 효율적으로 사용, 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가짐

 

 

 

 

---

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제]강의 정리입니다.

 반효경 교수님의 [운영체제와 정보기술의 원리] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140429132440045277?vmode=f 

반효경 [운영체제] 19. Memory Management 2

https://core.ewha.ac.kr/publicview/C0101020140502151452123728?vmode=f 

반효경 [운영체제] 20. Memory Management 3