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 addressphysical address변환한다.
  • 위 그림에서 2번 page page table2의 위치에서 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번 하는 것을 피하기 위한 방법
  • TLBpage 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

*2단계 Page Table

- 현대 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다.

32 비트 주소 사용 시 : 2^32 (4G)의 주소 공간 사용 가능

  • 각 page 크기가 4K1M개의 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 entry4B)
    -> 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