Background

• Program must be brought (from disk) into memory and placed within a process for it to be run
• Main memory and registers are only storage CPU can access directly
• Memory unit only sees a stream of:
  • addresses + read requests, or
  • address + data and write requests
• Register access is done in one CPU clock (or less)
• Main memory can take many cycles, causing a stall
• Cache sits between main memory and CPU registers
• Protection of memory required to ensure correct operation

• 프로그램을 실행하려면 (디스크에서) 메모리로 가져와 프로세스 내에 배치해야 한다.
• 기본 메모리 및 레지스터는 스토리지 CPU만 직접 액세스할 수 있다.
• 메모리 장치에는 다음 스트림만 표시된다.
  • 주소 + 읽기 요청 또는
  • 주소 + 데이터 및 쓰기 요청
• 레지스터 액세스는 하나의 CPU clock (or less)에서 수행된다.
• 기본 메모리는 여러 사이클이 소요되어 정지를 유발할 수 있다.
• 캐시는 메인 메모리와 CPU 레지스터 사이에 위치한다.
• 올바른 작동을 위해 필요한 메모리 보호

Protection

• Need to censure that a process can access only access those addresses in it address space.
• We can provide this protection by using a pair of base and limit registers define the logical address space of a process

• 프로세스가 주소 공간에 있는 해당 주소에만 액세스할 수 있는지 확인해야 한다.
• base와 limit registers 쌍을 사용하여 프로세스의 논리적 주소 공간을 정의함으로써 이러한 보호를 제공할 수 있다.

Hardware Address Protection

• CPU must check every memory access generated in user mode to be sure it is between base and limit for that user
• CPU는 사용자 모드에서 생성된 모든 메모리 액세스를 확인하여 해당 사용자의 기준과 제한 사이에 있는지 확인해야 한다.

• the instructions to loading the base and limit registers are privileged
• 기본 레지스터 및 제한 레지스터를 로드하는 명령은 권한이 있다.

Address Binding

• Programs on disk, ready to be brought into memory to execute form an input queue
  • Without support, must be loaded into address 0000
• Inconvenient to have first user process physical address always at 0000
  • How can it not be?
• Addresses represented in different ways at different stages of a program’s life
  • Source code addresses usually symbolic
  • Compiled code addresses bind to relocatable addresses
    • i.e. “14 bytes from beginning of this module”
  • Linker or loader will bind relocatable addresses to absolute addresses
    • i.e. 74014
  • Each binding maps one address space to another

• 디스크에 있는 프로그램, 입력 대기열에서 실행할 수 있도록 메모리에 가져올 준비가 된다.
  • 지원되지 않는 경우 주소 0000에 로드해야 한다.
• 항상 0000에 첫 번째 사용자 처리 물리적 주소가 있어야 하는 불편함
  • 어떻게 안 그럴 수가 있을까?
• 프로그램 수명의 다른 단계에서 서로 다른 방식으로 표현되는 주소
  • 소스 코드 주소는 일반적으로 심볼릭입니다.
  • 재배치 가능한 주소로 코드 주소 바인드를 컴파일했습니다.
    • 즉, "이 모듈의 시작부터 14바이트"
  • 링커 또는 로더가 재배치 가능한 주소를 절대 주소로 바인딩합니다.
    • 즉, 74014
  • 각 바인딩은 한 주소 공간을 다른 주소 공간에 매핑합니다.

Binding of Instructions and Data to Memory

• Address binding of instructions and data to memory addresses can happen at three different stages
  • Compile time: If memory location known a priori, absolute code can be generated; must recompile code if starting location changes
  • Load time: Must generate relocatable code if memory location is not known at compile time
  • Execution time: Binding delayed until run time if the process can be moved during its execution from one memory segment to another
    • Need hardware support for address maps (e.g., base and limit registers)

• 명령어와 데이터를 메모리 주소에 대한 주소 바인딩은 세 가지 다른 단계에서 발생할 수 있다.
  • Compile time: 메모리 위치가 priori로 알려진 경우 절대 코드를 생성할 수 있다. 시작 위치가 변경되면 코드를 다시 컴파일해야 한다.
  • Load time: 컴파일 시 메모리 위치를 알 수 없는 경우 재배치 가능 코드를 생성해야 한다.
  • Execution time: 실행 중에 프로세스가 메모리 세그먼트에서 다른 세그먼트로 이동할 수 있는 경우 실행 시간까지 바인딩이 지연된다.
    • address map(예: 기본 레지스터 및 제한 레지스터)에 대한 하드웨어 지원이 필요하다.

Multistep Processing of a User Program

Logical vs. Physical Address Space

• The concept of a logical address space that is bound to a separate physical address space is central to proper memory management
  • Logical address – generated by the CPU; also referred to as virtual address
  • Physical address – address seen by the memory unit
• Logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme
• Logical address space is the set of all logical addresses generated by a program
• Physical address space is the set of all physical addresses generated by a program

• 별도의 물리적 주소 공간에 바인딩된 논리적 주소 공간의 개념은 적절한 메모리 관리의 핵심이다.
  • 논리 주소 – CPU에 의해 생성되며 가상 주소라고도 한다.
  • 물리적 주소 – 메모리 장치에 표시되는 주소이다.
• 논리적 주소와 물리적 주소는 컴파일 타임과 로드 타임 주소 바인딩 체계에서 동일하다. 논리적(가상) 주소와 물리적 주소는 실행 타임 주소 바인딩 체계에서 서로 다르다.
• 논리 주소 공간은 프로그램에 의해 생성된 모든 논리 주소의 집합이다.
• 물리적 주소 공간은 프로그램에 의해 생성된 모든 물리적 주소의 집합이다.

Memory-Management Unit (MMU)

• Hardware device that at run time maps virtual to physical address
  
• Many methods possible, covered in the rest of this chapter

• 런타임에 가상을 물리적 주소로 매핑하는 하드웨어 디바이스
• 다양한 방법은, 이 장의 나머지 부분에서 다룬다.

---

• Consider simple scheme. which is a generalization of the base-register scheme.
• The base register now called relocation register
• The value in the relocation register is added to every address generated by a user process at the time it is sent to memory
• The user program deals with logical addresses; it never sees the real physical addresses
  • Execution-time binding occurs when reference is made to location in memory
  • Logical address bound to physical addresses

• 간단한 계획을 생각해 보세요. 기본 레지스터 방식의 일반화이다.
• 이제 기본 레지스터는 재배치 레지스터라고 한다.
• 재배치 레지스터의 값은 메모리로 전송될 때 사용자 프로세스에 의해 생성된 모든 주소에 추가된다.
• 사용자 프로그램은 논리적 주소를 처리한다; 그것은 결코 실제 물리적 주소를 보지 못한다.
  • 메모리의 위치를 참조할 때 실행 시간 바인딩이 발생한다.
  • 물리적 주소에 바인딩된 논리적 주소

Dynamic Loading

• The entire program does need to be in memory to excute
• Routine is not loaded until it is called
• Better memory-space utilization; unused routine is never loaded
• All routines kept on disk in relocatable load format
• Useful when large amounts of code are needed to handle infrequently occurring cases
• No special support from the operating system is required
  • Implemented through program design
  • OS can help by providing libraries to implement dynamic loading

• 실행하려면 전체 프로그램이 메모리에 있어야 한다.
• 루틴이 호출될 때까지 로드되지 않는다.
• 메모리 공간 활용도 향상, 사용하지 않는 루틴은 로드되지 않는다.
• 재배치 가능한 로드 형식으로 디스크에 보관된 모든 루틴
• 자주 발생하지 않는 사례를 처리하기 위해 많은 양의 코드가 필요할 때 유용하다.
• 운영 체제의 특별한 지원이 필요하지 않다.
  • 프로그램 설계를 통해 구현된다.
  • 동적 로딩을 구현하기 위한 라이브러리를 제공함으로써 OS가 도움이 될 수 있다.

Dynamic Linking

• Static linking – system libraries and program code combined by the loader into the binary program image
• Dynamic linking –linking postponed until execution time
• Small piece of code, stub, used to locate the appropriate memory-resident library routine
• Stub replaces itself with the address of the routine, and executes the routine
• Operating system checks if routine is in processes’ memory address
  • If not in address space, add to address space
• Dynamic linking is particularly useful for libraries
• System also known as shared libraries
• Consider applicability to patching system libraries
  • Versioning may be needed

• Static linking – 로더에 의해 바이너리 프로그램 이미지에 결합된 시스템 라이브러리 및 프로그램 코드
• 동적 연결 – 연결이 실행 시간까지 연기됨
• 적절한 메모리 상주 라이브러리 루틴을 찾는 데 사용되는 작은 코드 조각 *stub
• 스텁은 자신을 루틴의 주소로 대체하고 루틴을 실행한다.
• 운영 체제가 프로세스의 메모리 주소에 루틴이 있는지 확인한다.
  • 주소 공간에 없는 경우 주소 공간에 추가
• 동적 연결은 특히 라이브러리에 유용하다.
• 공유 라이브러리로도 알려진 시스템
• 패치 적용 시스템 라이브러리에 대한 적용 가능
  • 버전 관리가 필요할 수 있다.

Contiguous Memory Allocation

• Main memory must support both OS and user processes
• Limited resource, must allocate efficiently
• Contiguous allocation is one early method
• Main memory usually into two partitions:
  • Resident operating system, usually held in low memory with interrupt vector
  • User processes then held in high memory
  • Each process contained in single contiguous section of memory

• 기본 메모리가 OS 및 사용자 프로세스를 모두 지원해야 함
• 제한된 리소스, 효율적으로 할당해야 함
• 연속 할당은 초기 방법 중 하나이다.
• 기본 메모리는 일반적으로 두 개의 파티션으로 구성된다.
  • 일반적으로 인터럽트 벡터가 있는 낮은 메모리에 보관되는 상주 운영 체제
  • 사용자 프로세스가 대용량 메모리에 저장됨
  • 메모리의 단일 연속 섹션에 포함된 각 프로세스

---

• Relocation registers used to protect user processes from each other, and from changing operating-system code and data
  • Base register contains value of smallest physical address
  • Limit register contains range of logical addresses – each logical address must be less than the limit register
  • MMU maps logical address dynamically
  • Can then allow actions such as kernel code being transient and kernel changing size

• 사용자 프로세스를 서로 보호하고 운영 체제 코드 및 데이터가 변경되지 않도록 하는 데 사용되는 재배치 레지스터
  • 기본 레지스터에 가장 작은 물리적 주소의 값이 포함되어 있다.
  • 제한 레지스터에는 논리 주소 범위가 포함된다. 각 논리 주소는 제한 레지스터보다 작아야 한다.
  • MMU가 논리적 주소를 동적으로 매핑한다.
  • 그런 다음 커널 코드가 transient가 되고 커널 크기가 변경되는 등의 작업을 허용할 수 있다.

Hardware Support for Relocation and Limit Registers

Variable Partition

• Multiple-partition allocation
  • Degree of multiprogramming limited by number of partitions
  • Variable-partition sizes for efficiency (sized to a given process’ needs)
  • Hole – block of available memory; holes of various size are scattered throughout memory
  • When a process arrives, it is allocated memory from a hole large enough to accommodate it
  • Process exiting frees its partition, adjacent free partitions combined
  • Operating system maintains information about:
    • a) allocated partitions
    • b) free partitions (hole)

• 다중 파티션 할당
  • 파티션 수에 따라 제한된 멀티프로그래밍 정도
  • 다양한 파티션 크기로 효율성 향상(특정 프로세스 요구에 맞게 크기 조정)
  • 구멍 – 사용 가능한 메모리 블록, 다양한 크기의 구멍이 메모리 전체에 흩어져 있다.
  • 프로세스가 도착하면 해당 프로세스를 수용할 수 있을 만큼 충분히 큰 구멍에서 메모리가 할당된다.
  • 프로세스를 종료하면 파티션이 해방되고 인접한 사용 가능한 파티션이 결합됨
  • 운영 체제는 다음에 대한 정보를 유지 관리한다.
    • a) 할당된 파티션
    • b) 자유 파티션(구멍)

Dynamic Storage-Allocation Problem

How to satisfy a request of size n from a list of free holes?

• First-fit: Allocate the first hole that is big enough
• Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
  • Produces the smallest leftover hole
• Worst-fit: Allocate the largest hole; must also search entire list
  • Produces the largest leftover hole
    First-fit and best-fit better than worst-fit in terms of speed and storage utilization

자유 구멍 목록에서 n 크기의 요청을 충족하는 방법은 무엇인가?

• 첫 번째 맞춤: 충분히 큰 첫 번째 구멍을 할당한다.
• 가장 적합: 충분히 큰 구멍을 할당한다. 크기순으로 정렬하지 않는 한 전체 목록을 검색해야 한다.
  • 남은 구멍이 가장 작다.
• 가장 적합하지 않음: 가장 큰 구멍을 할당합니다. 또한 전체 목록을 검색한다.
  • 가장 큰 남은 구멍을 생성합니다.
    속도 및 스토리지 활용률 측면에서 최악의 경우보다 가장 적합하고 가장 적합함

Fragmentation

• External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous
• Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
• First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation
  • 1/3 may be unusable -> 50-percent rule

• 외부 조각화 – 총 메모리 공간이 요청을 충족하기 위해 존재하지만 연속되지는 않는다.
• 내부 조각화 – 할당된 메모리가 요청된 메모리보다 약간 클 수 있다. 이 크기 차이는 파티션 내부의 메모리이지만 사용되지 않는다.
• 첫 번째 적합 분석에 따르면 N개의 블록이 할당되면 0.5N개의 블록이 단편화로 손실된다.
  • 1/3을 사용할 수 없음 -> 50% 규칙

---

• Reduce external fragmentation by compaction
  • Shuffle memory contents to place all free memory together in one large block
  • Compaction is possible only if relocation is dynamic, and is done at execution time
  • I/O problem
    • Latch job in memory while it is involved in I/O
    • Do I/O only into OS buffers
• Now consider that backing store has same fragmentation problems

• 압축을 통해 외부 단편화 감소
  • 메모리 콘텐츠를 셔플하여 사용 가능한 모든 메모리를 하나의 큰 블록에 함께 배치
  • 압축은 재배치가 동적인 경우에만 가능하며 실행 시에 수행된다.
  • 입출력 문제
    • I/O와 관련된 메모리에서 작업 래치
    • OS 버퍼에만 I/O 수행
• 이제 백업 저장소에 동일한 조각화 문제가 있다는 점을 고려해라.

Paging

• Physical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
  • Avoids external fragmentation
  • Avoids problem of varying sized memory chunks
• Divide physical memory into fixed-sized blocks called frames
  • Size is power of 2, between 512 bytes and 16 Mbytes
• Divide logical memory into blocks of same size called pages
• Keep track of all free frames
• To run a program of size N pages, need to find N free frames and load program
• Set up a page table to translate logical to physical addresses
• Backing store likewise split into pages
• Still have Internal fragmentation

• 프로세스의 물리적 주소 공간은 연속되지 않을 수 있으며 프로세스는 물리적 메모리를 사용할 수 있을 때마다 할당된다.
  • 외부 단편화 방지
  • 다양한 크기의 memory chunk 문제 방지
• 물리적 메모리를 frames라는 고정 크기 블록으로 분할
  • 크기는 2의 거듭제곱으로 512바이트에서 16MB 사이
• 논리 메모리를 pages라는 동일한 크기의 블록으로 분할
• 사용 가능한 모든 프레임 추적
• N 페이지 크기의 프로그램을 실행하려면 N개의 빈 프레임을 찾고 프로그램을 로드해야 한다.
• 논리적 주소를 물리적 주소로 변환하는 페이지 테이블 설정
• 백업 저장소도 마찬가지로 페이지로 분할됨
• 여전히 내부 조각화가 있음

Address Translation Scheme

• Address generated by CPU is divided into:
  • Page number (p) – used as an index into a page table which contains base address of each page in physical memory
  • Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit
    
  • For given logical address space 2m and page size 2^n

• CPU에서 생성되는 주소는 다음과 같이 구분된다.
• 페이지 번호(p) – 물리적 메모리에 있는 각 페이지의 기본 주소를 포함하는 페이지 테이블의 색인으로 사용된다.
• 페이지 오프셋(d) – 기본 주소와 결합하여 메모리 장치로 전송되는 물리적 메모리 주소를 정의한다.
• 지정된 논리 주소 공간 2m 및 페이지 크기 2^n에 대해

Paging Hardware

Paging Model of Logical and Physical Memory

Paging Example

• Logical address: n = 2 and m = 4. Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages)

Paging -- Calculating internal fragmentation

• Page size = 2,048 bytes
• Process size = 72,766 bytes
• 35 pages + 1,086 bytes
• Internal fragmentation of 2,048 - 1,086 = 962 bytes
• Worst case fragmentation = 1 frame – 1 byte
• On average fragmentation = 1 / 2 frame size
• So small frame sizes desirable?
• But each page table entry takes memory to track
• Page sizes growing over time
  • Solaris supports two page sizes – 8 KB and 4 MB

• 페이지 크기 = 2,048바이트
• 프로세스 크기 = 72,766바이트
• 35페이지 + 1,086바이트
• 2,048 - 1,086 = 962바이트의 내부 조각화
• 최악의 경우 조각화 = 1프레임 – 1바이트
• 평균 조각화 = 1/2 프레임 크기
• 프레임 크기가 작으면 좋은가?
• 그러나 각 페이지 테이블 항목은 추적하는 데 메모리가 필요하다.
• 시간이 지남에 따라 증가하는 페이지 크기
  • Solaris는 8KB와 4MB의 두 페이지 크기를 지원한다.

Free Frames

Implementation of Page Table

• Page table is kept in main memory
  • Page-table base register (PTBR) points to the page table
  • Page-table length register (PTLR) indicates size of the page table
• In this scheme every data/instruction access requires two memory accesses
  • One for the page table and one for the data / instruction
• The two memory access problem can be solved by the use of a special fast-lookup hardware cache called translation look-aside buffers (TLBs) (also called associative memory).

• 페이지 테이블이 메인 메모리에 유지된다.
  • 페이지 테이블 기본 레지스터(PTBR)가 페이지 테이블을 가리킨다.
  • 페이지 테이블 길이 레지스터(PTLR)은 페이지 테이블의 크기를 나타낸다.
• 이 체계에서 모든 데이터/명령어 액세스에는 두 개의 메모리 액세스가 필요하다.
• 하나는 페이지 테이블용이고 하나는 데이터/명령어용이다.
• 두 가지 메모리 액세스 문제는 translation Look-aside buffers(TLBs)(associative memory라고도 함)라는 특수한 빠른 검색 하드웨어 캐시를 사용하여 해결할 수 있다.

Translation Look-Aside Buffer

• Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
  • Otherwise need to flush at every context switch
• TLBs typically small (64 to 1,024 entries)
• On a TLB miss, value is loaded into the TLB for faster access next time
  • Replacement policies must be considered
  • Some entries can be wired down for permanent fast access

• 일부 TLB는 각 TLB 항목에 ASID(주소 공간 식별자)를 저장한다. 각 프로세스를 고유하게 식별하여 해당 프로세스에 주소 공간 보호 기능을 제공한다.
  • 그렇지 않으면 모든 컨텍스트 스위치에서 플러시해야 한다.
• 일반적으로 작은 TLBs(64~1,024개 항목)
• TLB 미스의 경우 다음 번에 더 빠른 액세스를 위해 값이 TLB에 로드된다.
  • 교체 정책을 고려해야 한다.
  • 영구적인 빠른 액세스를 위해 일부 항목을 유선으로 연결할 수 있다.

Hardware

• Associative memory – parallel search
  
• Address translation (p, d)
  • If p is in associative register, get frame # out
  • Otherwise get frame # from page table in memory

• 연상 메모리 – 병렬 검색
• 주소 변환(p, d)
  • p가 연상 레지스터에 있으면 프레임 번호를 가져온다.
  • 그렇지 않으면 메모리의 페이지 테이블에서 프레임 번호를 가져온다.

Paging Hardware With TLB

Effective Access Time

• Hit ratio – percentage of times that a page number is found in the TLB
• An 80% hit ratio means that we find the desired page number in the TLB 80% of the time.
• Suppose that 10 nanoseconds to access memory.
  • If we find the desired page in TLB then a mapped-memory access take 10 ns
  • Otherwise we need two memory access so it is 20 ns
• Effective Access Time (EAT)
  • EAT = 0.80 x 10 + 0.20 x 20 = 12 nanoseconds
  • implying 20% slowdown in access time
• Consider amore realistic hit ratio of 99%,
  • EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns
  • implying only 1% slowdown in access time.

• 적중률 – TLB에서 페이지 번호를 찾은 횟수(%)
• 적중률이 80%라는 것은 TLB에서 원하는 페이지 번호를 80%라는 것을 의미한다.
• 메모리에 액세스하는 데 10나노초가 걸린다고 가정한다.
  • 만약 우리가 TLB에서 원하는 페이지를 찾는다면, 매핑된 메모리 액세스는 10ns
  • 그렇지 않으면 메모리 액세스가 두 번 필요하므로 20ns이다.
• 유효 액세스 시간(EAT)
  • EAT = 0.80 x 10 + 0.20 x 20 = 12 나노초
  • 액세스 시간이 20% 단축됨
• 99%의 보다 현실적인 적중률을 고려해 보라.
  • EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns
  • 액세스 시간이 1%밖에 느려지지 않았음을 의미한다.

Memory Protection

• Memory protection implemented by associating protection bit with each frame to indicate if read-only or read-write access is allowed
  • Can also add more bits to indicate page execute-only, and so on
• Valid-invalid bit attached to each entry in the page table:
  • “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page
  • “invalid” indicates that the page is not in the process’ logical address space
  • Or use page-table length register (PTLR)
• Any violations result in a trap to the kernel

• 각 프레임에 보호 비트를 연결하여 읽기 전용 또는 읽기-쓰기 액세스가 허용되는지 여부를 표시함으로써 구현된 메모리 보호
  • 페이지 실행 전용 등을 나타내기 위해 비트를 추가할 수도 있다.
• Valid-invalid 비트가 페이지 테이블의 각 항목에 연결되었다.
  • "valid"는 연결된 페이지가 프로세스의 논리적 주소 공간에 있으므로 합법적인 페이지임을 나타낸다.
  • 페이지가 프로세스의 논리적 주소 공간에 없음을 나타낸다.
  • 또는 페이지 테이블 길이 레지스터(PTL)를 사용해라.
• 위반 시 커널에 트랩이 발생한다.

Valid(v) or Invalid(i) Bit In A Page Table

Shared Pages

• Shared code
  • One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems)
  • Similar to multiple threads sharing the same process space
  • Also useful for interprocess communication if sharing of read-write pages is allowed
• Private code and data
  • Each process keeps a separate copy of the code and data
  • The pages for the private code and data can appear anywhere in the logical address space

• 공유 코드
  • 프로세스 간에 공유되는 읽기 전용(reentrent) 코드 복사본 1개(예: 텍스트 편집기, 컴파일러, 창 시스템)
  • 동일한 프로세스 공간을 공유하는 여러 스레드와 유사하다.
  • 읽기-쓰기 페이지 공유가 허용되는 경우 프로세스 간 통신에도 유용하다.
• 개인 코드 및 데이터
  • 각 프로세스는 코드와 데이터의 별도 사본을 보관한다.
  • 개인 코드 및 데이터에 대한 페이지는 논리적 주소 공간의 모든 위치에 나타날 수 있다.

Shared Pages Example

Structure of the Page Table

• Memory structures for paging can get huge using straight-forward methods
  • Consider a 32-bit logical address space as on modern computers
  • Page size of 4 KB (2^12)
  • Page table would have 1 million entries (2^32 / 2^12)
  • If each entry is 4 bytes -> each process 4 MB of physical address space for the page table alone
    • Don’t want to allocate that contiguously in main memory
  • One simple solution is to divide the page table into smaller units
    • Hierarchical Paging
    • Hashed Page Tables
    • Inverted Page Tables

• 페이징을 위한 메모리 구조는 간단한 방법을 사용하면 커질 수 있다.
  • 최신 컴퓨터에서와 같이 32비트 논리적 주소 공간을 고려해라.
  • 페이지 크기 4KB(2^12)
  • 페이지 테이블에는 100만 개의 항목이 있다(2^32 / 2^12).
  • 각 항목이 4바이트인 경우 -> 각 프로세스는 페이지 테이블에 대한 4MB의 물리적 주소 공간만 처리한다.
    • 주 메모리에 연속적으로 할당하고 싶지 않음
  • 한 가지 간단한 해결책은 페이지 테이블을 더 작은 단위로 나누는 것이다.
    • 계층 페이징
    • 해시된 페이지 테이블
    • 반전된 페이지 테이블

Hierarchical Page Tables

• Break up the logical address space into multiple page tables
• A simple technique is a two-level page table
• We then page the page table

• 논리적 주소 공간을 여러 페이지 테이블로 분할한다.
• 간단한 기술은 2단계 페이지 테이블이다.
• 그런 다음 페이지 테이블을 호출한다.

Two-Level Paging Example

• A logical address (on 32-bit machine with 1K page size) is divided into:
  • a page number consisting of 22 bits
  • a page offset consisting of 10 bits
• Since the page table is paged, the page number is further divided into:
  • a 10-bit page number
  • a 12-bit page offset
• Thus, a logical address is as follows:

• 논리 주소(1K 페이지 크기의 32비트 시스템)는 다음과 같이 나뉜다.
  • 22비트로 구성된 페이지 번호
  • 10비트로 구성된 페이지 오프셋
• 페이지 테이블이 호출되므로 페이지 번호는 다음과 같이 추가로 나뉜다.
  • 10비트 페이지 번호
  • 12비트 페이지 오프셋
• 따라서 논리적 주소는 다음과 같다.

• where p1 is an index into the outer page table, and p2 is the displacement within the page of the inner page table
• Known as forward-mapped page table

• 여기서 p1은 외부 페이지 테이블의 인덱스이고, p2는 내부 페이지 테이블의 페이지 내 변위이다.
• forward-mapped page table로 알려져 있다.

Address-Translation Scheme

64-bit Logical Address Space

• Even two-level paging scheme not sufficient
• If page size is 4 KB (2^12)
  • Then page table has 2^52 entries
  • If two level scheme, inner page tables could be 210 4-byte entries
  • Address would look like
    
  • Outer page table has ^242 entries or 2^44 bytes
  • One solution is to add a 2nd outer page table
  • But in the following example the 2nd outer page table is still 234 bytes in size
    • And possibly 4 memory access to get to one physical memory location

• 2단계 페이징 체계도 충분하지 않다.
• 페이지 크기가 4KB인 경우(2^12)
  • 그러면 페이지 테이블에 2^52 항목이 있다.
  • 두 개의 수준 체계인 경우, 내부 페이지 테이블은 2104바이트 항목이 될 수 있습니다.
  • 주소는 다음과 같습니다. (그림)
  • 외부 페이지 테이블에는 2^42개의 항목 또는 2^44 바이트가 있다.
  • 한 가지 해결책은 두 번째 외부 페이지 테이블을 추가하는 것이다.
  • 그러나 다음 예제에서 두 번째 외부 페이지 테이블의 크기는 여전히 234바이트이다.
    • 또한 하나의 물리적 메모리 위치에 도달하기 위해 4개의 메모리 액세스가 가능하다.

Three-level Paging Scheme

Hashed Page Tables

• Common in address spaces > 32 bits
• The virtual page number is hashed into a page table
  • This page table contains a chain of elements hashing to the same location
• Each element contains (1) the virtual page number (2) the value of the mapped page frame (3) a pointer to the next element
• Virtual page numbers are compared in this chain searching for a match
  • If a match is found, the corresponding physical frame is extracted
• Variation for 64-bit addresses is clustered page tables
  • Similar to hashed but each entry refers to several pages (such as 16) rather than 1
  • Especially useful for sparse address spaces (where memory references are non-contiguous and scattered)

• 32비트 이상의 주소 공간에서 공통
• 가상 페이지 번호가 페이지 테이블에 해시된다.
  • 이 페이지 테이블에는 동일한 위치에 대한 요소 해시 체인이 포함되어 있다.
• 각 요소에는 (1)가상 페이지 번호(2)매핑된 페이지 프레임의 값 (3)다음 요소에 대한 포인터가 포함된다.
• 이 체인에서 일치 항목을 검색하는 가상 페이지 번호가 비교된다.
  • 일치하는 항목이 발견되면 해당 물리적 프레임이 추출된다.
• 64비트 주소의 경우 클러스터된 페이지 테이블이(가) 다르다.
  • 해시와 비슷하지만 각 항목은 1이 아닌 여러 페이지(예: 16)를 참조한다.
  • 특히 sparse 주소 공간(메모리 참조가 비연속적이고 흩어져 있는 경우)에 유용하다.

Inverted Page Table

• Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages
• One entry for each real page of memory
• Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page
• Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs
• Use hash table to limit the search to one — or at most a few — page-table entries
  • TLB can accelerate access
• But how to implement shared memory?
  • One mapping of a virtual address to the shared physical address

• 각 프로세스에 페이지 테이블이 있고 가능한 모든 논리 페이지를 추적하는 대신 모든 실제 페이지를 추적한다.
• 메모리의 각 실제 페이지에 대해 하나의 항목
• 항목은 실제 메모리 위치에 저장된 페이지의 가상 주소와 해당 페이지를 소유하는 프로세스에 대한 정보로 구성된다.
• 각 페이지 테이블을 저장하는 데 필요한 메모리를 줄이지만 페이지 참조가 발생할 때 테이블을 검색하는 데 필요한 시간을 늘린다.
• 해시 테이블을 사용하여 검색을 하나 또는 최대 몇 개의 페이지 테이블 항목으로 제한
  • TLB는 액세스를 가속화할 수 있다.
• 그러나 공유 메모리를 어떻게 구현할 것인가?
  • 공유 물리적 주소에 대한 가상 주소의 단일 매핑

Inverted Page Table Architecture

Oracle SPARC Solaris

• Consider modern, 64-bit operating system example with tightly integrated HW
  • Goals are efficiency, low overhead
• Based on hashing, but more complex
• Two hash tables
  • One kernel and one for all user processes
  • Each maps memory addresses from virtual to physical memory
  • Each entry represents a contiguous area of mapped virtual memory,
    • More efficient than having a separate hash-table entry for each page
  • Each entry has base address and span (indicating the number of pages the entry represents)

• 하드웨어가 긴밀하게 통합된 최신 64비트 운영 체제의 예를 생각해 보라.
  • 목표는 효율성, 낮은 오버헤드
• 해싱을 기반으로 하지만 더 복잡하다.
• 해시 테이블 두 개
  • 모든 사용자 프로세스에 대해 하나의 커널 및 하나
  • 각 메모리 주소를 가상 메모리에서 물리적 메모리로 매핑
  • 각 항목은 매핑된 가상 메모리의 인접 영역을 나타낸다.
    • 각 페이지에 대해 별도의 해시 테이블 항목을 갖는 것보다 효율적이다.
  • 각 항목에는 기본 주소와 범위(항목이 나타내는 페이지 수를 나타냄)가 있다.

---

• TLB holds translation table entries (TTEs) for fast hardware lookups
  • A cache of TTEs reside in a translation storage buffer (TSB)
    • Includes an entry per recently accessed page
• Virtual address reference causes TLB search
  • If miss, hardware walks the in-memory TSB looking for the TTE corresponding to the address
    • If match found, the CPU copies the TSB entry into the TLB and translation completes
    • If no match found, kernel interrupted to search the hash table
      • The kernel then creates a TTE from the appropriate hash table and stores it in the TSB, Interrupt handler returns control to the MMU, which completes the address translation.

• TLB는 빠른 하드웨어 조회를 위해 TTE(Translation Table Entry)를 보유한다.
  • TTE의 캐시는 TSB(Translation Storage Buffer)에 상주한다.
    • 최근 액세스한 페이지당 항목 포함
• 가상 주소 참조로 인해 TLB 검색이 발생함
  • 누락된 경우 하드웨어는 주소에 해당하는 TTE를 찾기 위해 메모리 내 TSB를 이동한다.
    • 일치하는 항목이 발견되면 CPU가 TSB 항목을 TLB로 복사하고 변환이 완료된다.
    • 일치하는 항목이 없으면 커널이 해시 테이블 검색을 중단했다.
    • 커널은 적절한 해시 테이블에서 TTE를 생성하여 TSB에 저장하고, 인터럽트 핸들러는 MMU로 제어권을 반환하여 주소 변환을 완료한다.

Swapping

• A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution
  • Total physical memory space of processes can exceed physical memory
• Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images
• Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed
• Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped
• System maintains a ready queue of ready-to-run processes which have memory images on disk

• 프로세스를 일시적으로 메모리가 부족한 상태로 백업 저장소로 swap한 후 계속 실행하기 위해 메모리로 다시 가져올 수 있습니다.
  • 프로세스의 총 물리적 메모리 공간이 물리적 메모리를 초과할 수 있음
• Backing store – 모든 사용자가 사용할 수 있는 모든 메모리 이미지의 복사본을 수용할 수 있을 만큼 충분히 큰 빠른 디스크. 이러한 메모리 이미지에 직접 액세스할 수 있어야 한다.
• Roll out, roll in – 우선순위 기반 스케줄링 알고리즘에 사용되는 스왑 변형. 우선순위가 낮은 프로세스가 스왑 아웃되므로 우선순위가 높은 프로세스를 로드하고 실행할 수 있다.
• 스왑 시간의 주요 부분은 전송 시간이며, 총 전송 시간은 스왑된 메모리 양에 정비례한다.
• 시스템은 디스크에 메모리 이미지가 있는 실행 준비 프로세스의 ready 큐를 유지 관리한다.

---

• Does the swapped out process need to swap back in to same physical addresses?
• Depends on address binding method
  • Plus consider pending I/O to / from process memory space
• Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)
  • Swapping normally disabled
  • Started if more than threshold amount of memory allocated
  • Disabled again once memory demand reduced below threshold

• 스왑 아웃 프로세스가 동일한 물리적 주소로 다시 스왑해야 하는가?
  • 주소 바인딩 방법에 따라 다름
• 또한 프로세스 메모리 공간에 I/O를 대기하는 것도 고려해 보라.
• 많은 시스템(예: UNIX, Linux 및 Windows)에서 스왑의 수정된 버전을 찾을 수 있다.
  • 스와핑이 정상적으로 비활성화됨
  • 할당된 메모리 양이 임계값을 초과할 경우 시작됨
  • 메모리 요구량이 임계값 미만으로 감소하면 다시 비활성화됨

Schematic View of Swapping

Context Switch Time including Swapping

• If next processes to be put on CPU is not in memory, need to swap out a process and swap in target process
• Context switch time can then be very high
• 100MB process swapping to hard disk with transfer rate of 50MB/sec
  • Swap out time of 2000 ms
  • Plus swap in of same sized process
  • Total context switch swapping component time of 4000ms (4 seconds)
• Can reduce if reduce size of memory swapped – by knowing how much memory really being used
  • System calls to inform OS of memory use via request_memory() and release_memory()

• CPU에 배치할 다음 프로세스가 메모리에 없는 경우 프로세스를 스왑 아웃하고 대상 프로세스에서 스왑 인해야 한다.
• 그러면 컨텍스트 전환 시간이 매우 길어질 수 있다.
• 전송 속도가 50MB/sec인 하드 디스크로 100MB 프로세스 스왑
  • 2000ms의 스왑 아웃 시간
  • 동일한 크기의 프로세스를 스왑 인
  • 총 컨텍스트 스위치 스왑 구성 요소 시간(4초)
• 실제로 사용 중인 메모리 양을 파악하여 스왑된 메모리 크기를 줄일 수 있다.
  • request_memory() 및 release_memory()를 통해 메모리 사용을 OS에 알리기 위한 시스템 호출

---

• Other constraints as well on swapping
  • Pending I/O – can’t swap out as I/O would occur to wrong process
  • Or always transfer I/O to kernel space, then to I/O device
    • Known as double buffering, adds overhead
• Standard swapping not used in modern operating systems
  • But modified version common
    • Swap only when free memory extremely low

• 스와핑에 대한 기타 제약 사항
  • 보류 중인 I/O – 잘못된 프로세스로 인해 I/O가 발생하므로 교환할 수 없다.
  • 또는 항상 I/O를 커널 공간으로 전송한 다음 I/O 장치로 전송한다.
    • 이중 버퍼링으로 알려진 오버헤드 추가
• 최신 운영 체제에서 사용되지 않는 표준 스왑
  • 그러나 수정된 버전 공통
    • 사용 가능한 메모리가 극도로 부족한 경우에만 스왑

Swapping on Mobile Systems

• Not typically supported
  • Flash memory based
    • Small amount of space
    • Limited number of write cycles
    • Poor throughput between flash memory and CPU on mobile platform
• Instead use other methods to free memory if low
  • iOS asks apps to voluntarily relinquish allocated memory
    • Read-only data thrown out and reloaded from flash if needed
    • Failure to free can result in termination
  • Android terminates apps if low free memory, but first writes application state to flash for fast restart
  • Both OSes support paging as discussed below

• 일반적으로 지원되지 않음
  • 플래시 메모리 기반
    • 공간이 적음
    • 쓰기 주기 수가 제한됨
    • 모바일 플랫폼의 플래시 메모리와 CPU 간 처리량 저하
• 대신 메모리가 부족한 경우 다른 방법을 사용하여 메모리를 확보하십시오.
  • iOS가 앱에 할당된 메모리를 자발적으로 포기하도록 요청합니다.
    • 필요한 경우 플래시에서 삭제되고 다시 로드되는 읽기 전용 데이터
    • 해제하지 않으면 종료될 수 있습니다.
  • Android는 사용 가능한 메모리가 부족할 경우 앱을 종료하지만, 빠른 재시작을 위해 먼저 응용 프로그램 상태를 플래시에 기록합니다.
  • 아래 설명된 대로 두 OS 모두 페이징을 지원한다.

Example: The Intel 32 and 64-bit Architectures

• Dominant industry chips
• Pentium CPUs are 32-bit and called IA-32 architecture
• Current Intel CPUs are 64-bit and called IA-64 architecture
• Many variations in the chips, cover the main ideas here

• 지배적인 업계 칩
• 펜티엄 CPU는 32비트이며 IA-32 아키텍처라고 불린다.
• 현재 Intel CPU는 64비트이며 IA-64 아키텍처라고 한다.
• 칩의 많은 변형, 여기서 주요 아이디어를 다룬다.

Example: The Intel IA-32 Architecture

• Supports both segmentation and segmentation with paging
  • Each segment can be 4 GB
  • Up to 16 K segments per process
  • Divided into two partitions
    • First partition of up to 8 K segments are private to process (kept in local descriptor table (LDT))
    • Second partition of up to 8K segments shared among all processes (kept in global descriptor table (GDT))

• 페이징을 통한 세분화 및 세분화 지원
  • 각 세그먼트는 4GB가 될 수 있다.
  • 프로세스당 최대 16K 세그먼트
  • 두 개의 파티션으로 분할
    • 최대 8K 세그먼트의 첫 번째 파티션은 비공개로 처리된다 (Local Descriptor Table(LDT)에 보관됨)
    • 모든 프로세스 간에 공유되는 최대 8K 세그먼트의 두 번째 파티션 (Global Descriptor Table(GDT)에 보관된)

---

• CPU generates logical address
  • Selector given to segmentation unit
    * Which produces linear addresses
    
• Linear address given to paging unit
  • Which generates physical address in main memory
  • Paging units form equivalent of MMU
  • Pages sizes can be 4 KB or 4 MB

• CPU가 논리적 주소를 생성한다.
  • 분할 장치에 지정된 선택기
    • 선형 주소를 생성한다.
• 페이징 장치에 지정된 선형 주소
  • 주 메모리에 물리적 주소를 생성한다.
  • MMU와 동등한 형태의 페이징 유닛
  • 페이지 크기는 4KB 또는 4MB일 수 있다.

Logical to Physical Address Translation in IA-32

Intel IA-32 Segmentation

Intel IA-32 Paging Architecture

Intel IA-32 Page Address Extensions

• 32-bit address limits led Intel to create page address extension (PAE), allowing 32-bit apps access to more than 4GB of memory space
  • Paging went to a 3-level scheme
  • Top two bits refer to a page directory pointer table
  • Page-directory and page-table entries moved to 64-bits in size
  • Net effect is increasing address space to 36 bits – 64GB of physical memory

• 32비트 주소 제한으로 인해 Intel은 페이지 주소 확장(PAE)을 생성하여 32비트 앱에서 4GB 이상의 메모리 공간에 액세스할 수 있게 되었다.
  • 페이징이 3단계 체계로 넘어갔습니다.
  • 상위 2비트는 페이지 디렉토리 포인터 테이블을 참조합니다.
  • 페이지 디렉토리 및 페이지 테이블 항목이 64비트 크기로 이동됨
  • 주소 공간을 36비트(64GB의 물리적 메모리)로 늘리는 순 효과

Intel x86-64

• Current generation Intel x86 architecture
• 64 bits is ginormous (> 16 exabytes)
• In practice only implement 48 bit addressing
  • Page sizes of 4 KB, 2 MB, 1 GB
  • Four levels of paging hierarchy
• Can also use PAE so virtual addresses are 48 bits and physical addresses are 52 bits

• 최신 세대 Intel x86 아키텍처
• 64비트는 엄청나다. (16엑사바이트 이상)
• 실제로는 48비트 주소 지정만 구현한다.
  • 4KB, 2MB, 1GB의 페이지 크기
  • 네 가지 수준의 페이징 계층
• PAE를 사용할 수도 있으므로 가상 주소는 48비트이고 물리적 주소는 52비트입니다.

Example: ARMv8 Architecture

• Dominant mobile platform chip (Apple iOS and Google Android devices for example)
• Modern, energy efficient, 32-bit CPU
• 4 KB and 16 KB pages
• 1 MB and 16 MB pages (termed sections)
• One-level paging for sections, two-level for smaller pages
• Two levels of TLBs
  • Outer level has two micro TLBs (one data, one instruction)
  • Inner is single main TLB
  • First inner is checked, on miss outers are checked, and on miss page table walk performed by CPU

• 지배적인 모바일 플랫폼 칩(예: Apple iOS 및 Google Android 장치)
• 최신의 에너지 효율적인 32비트 CPU
• 4KB 및 16KB 페이지
• 1MB 및 16MB 페이지(섹션으로 표현)
• 섹션의 경우 1단계 페이징, 작은 페이지의 경우 2단계 페이징
• 두 가지 수준의 TLBs
  • 외부 레벨에는 2개의 마이크로 TLB(데이터 1개, 명령 1개)가 있다.
  • 내부는 단일 메인 TLB이다.
  • 첫 번째 내부가 확인되고, 누락된 외부가 확인되며, 누락된 페이지의 테이블 워크가 CPU에 의해 수행된다.