[운영체제]OS09_Main Memory - 메인 메모리

OS09_Main Memory

• 명령어 Cycle
• IF → ID → OF → EX → MA → WB
• CPU는 간접적으로 Main memory와 CPU 레지스터에 접근할 수 있지만, Disk에는 접근 불가
• CPU register → CPU 내에 존재 → 빠르게 access 가능
  • CPU가 당장 처리해야할 데이터를 가지고 있음.
• Main memory
  • 큰 bytes의 배열로 이루어져 있음
  • memory stall을 일으키며 많은 cycles 소요
• Cache는 메인 메모리와 cpu 레지스터 사이에 위치하는 저장 공간
• memory의 Protection은 OS 영역과 사용자 영역을 분리하고 사용자 프로그램 간에 서로 접근하지 못하도록 보호해야 함.

Protection

→ 어떤 프로세스가 있을때 그 프로세스에게 할당되어 있는 주소공간만 access하게 만드는 것.

• base와 limit 레지스터를 사용해 Protection
  

Address Binding

• Disk에 있는 프로그램은 실행하기 전에 메모리로 가져와야함.
• Source code 주소는 주로 symbolic하다
• 컴파일된 코드에서는 주소 relocatable addresses로 매핑된다.
• linker 또는 loader는 relocatable address를 절대 주소로 매핑한다.

Logical vs Physical Address Space

• Logical address: (virtual address와 유사)
  • CPU에 의해 생성되며 실행시간 주소 바인딩 방식에서 사용, 프로그램이 실행도는 동안 CPU가 생성하는 주소
• Physical address
  • 메모리 장치가 실제로 볼 수 있는 주소
• Logical and Physical address는 같은 시간에 컴파일 되고 load된다.
• Logical address Space
  • 프로그램에의해 생성되는 주소공간
• Physical address Space
  • logical address에 의해 대응되는 물리적 주소

Memory-Management Unit(MMU)

• H/W device는 virtual주소에서 physical 주소로 런타임에 map한다.

• relocation register는 user process에 의해 생성되는 주소에 더해진다.

Dynamic Loading

→ 한정된 메모리를 효율적으로 쓰기위해 필요한 것들만 메모리에 갖다두자.

(사용되지 않는 것들은 load X, ex) Error handling routine)

Dynamic Linking

→ Linker에 의해 동작

• Static linking → 프로그램의 컴파일 시점에 모든 라이브러리 코드가 실행 파일에 포함됨. 이로써 실행 파일의 크기가 커지고 라이브러리 코드가 중복으로 포함될 수 있음.
• Dynamic linking → 프로그램이 실행될 때 필요한 라이브러리 코드를 동적으로 load. 이로써 실행 파일의 크기가 줄어들고 메모리를 효율적으로 사용가능
• stub → 프로그램 내부에 동적링킹된 라이브러리를 호출하는 코드
• 다이나믹 링킹은 특히 라이브러리에 유용하다 - Shared library(.so) in Linux, Dynamic link library(dll) in Windows → 메모리를 효율적으로 사용

Contiguous Allocation

• Main memory는 OS와 user processes 둘 다에게 support해야만한다.
  • 지원된 자원때문에 효율적으로 할당해야함.
• Main memory는 주로 두 partitions으로 나뉜다.
  • Operating system → 주로 높은 메모리를 잡고 있다.
  • User processes → 낮은 메모리를 잡고 있음

• Relocation register: 가장 작은 물리적 주소
• Limit register: 논리적 주소의 범위
• MMU는 논리적 주소를 동적으로 map한다.

Fixed Partitions

• 물리적 memory는 fixed partitions으로 쪼개진다.
  • 각 partition은 같은 크기
  • partitions의 수 = 멀티프로그래밍의 수
  • H/W는 base register을 필요로한다.
    • 물리적 주소 = 논리적 주소 + base 레지스터
• 장점: 실행하기 쉽고 빠른 context switch
• 문제점:
  • Internal fragmentation(내부 파편화) → partition의 size를 fix했지만 프로그램의 길이는 다름.
  • 

• 개선점
  • 다양한 fixed-size partitions 사용
  • Allocation 전략
    • First fit: 메모리 할당 요청이 발생했을 때, 이를 수용할 수 있는 첫 번째 나오는 파티션에 할당
    • Best fit: 메모리 할당 요청이 발생했을 때, 요청된 크기와 가장 잘 맞는(가장 작은) 파티션을 찾아 프로세스를 할당

Variable Partition

→ 파티션의 크기를 맞게끔 할당

• Variable-partition size(가변 파티션 크기)
• Hole(구멍): 사용 가능한 메모리 블록을 의미합니다. 'Hole'은 메모리 전체에 다양한 크기로 흩어져 있을 수 있습니다.
• 운영 체제는 메모리의 할당 및 해제 상태를 추적. 이를 위해 다음 두 가지 주요 정보를 유지.
  1. 할당된 파티션: 현재 사용 중인 메모리 파티션에 대한 정보를 관리합니다.
  2. 빈 파티션 (Free Partitions / Hole): 사용 가능한 메모리 블록에 대한 정보를 관리합니다. 이 정보는 새로운 프로세스에 메모리를 할당할 때 중요합니다.단점:
  3. 
  • 외부 단편화: 사용되지 않는 메모리 블록들이 작고 산재해 있을 수 있으며, 이는 큰 프로세스를 수용하기에 충분하지 않을 수 있습니다.
  • 관리 복잡성: 메모리의 할당 및 해제 상태를 추적하고 관리하는 데 더 많은 노력이 필요

Dynamic Storage-Allocation Problem

→ 동적 메모리 할당 문제. 주어진 request를 어떻게 free hole에 할당한 것인가?

• First-fit: 충분히 큰 홀 중에 처음 만나는 곳에 할당
• Best-fit: 들어갈 수 있는 곳들 중 가장 작은 곳에 할당
• Worst-fit: 가장 큰 홀에 할당
• → First-fit과 best-fit이 worst-fit 보다 속도와 메모리 활용면에서 더 낫다.

Fragmentation

• External Fragmentation(외부 파편화)
  • 메모리 내용을 재구성하여 모든 여유 메모리를 하나의 큰 블록으로 결합하는 'Compaction'이라는 기법(디스크 조각 모음)
  • 이를 통해 외부 단편화를 줄이고, 큰 메모리 할당 요청을 수용할 수 있는 공간을 확보합니다.
  • 필요 조건*:
  • 동적 재배치(Dynamic Relocation): 프로그램이 실행 중에 메모리 내에서 이동될 수 있어야 합니다. 이는 주소 변환을 수행하는 하드웨어(예: MMU)가 필요합니다.
  • 실행 시간 재배치(Execution-time Relocation): 프로그램이 실행되는 동안 메모리 주소가 재배치될 수 있어야 합니다.
  • Compaction 과 관련된 문제
  • I/O 문제
    • Latch Job: I/O 작업 중인 프로세스는 메모리에서 이동되어서는 안 됩니다. 이는 I/O 작업 중에 메모리 위치가 변경되면 데이터 불일치 문제가 발생할 수 있기 때문입니다.
    • OS 버퍼를 통한 I/O: I/O 작업을 운영 체제의 버퍼를 통해 수행하여, 메모리 재구성 중에도 데이터 무결성을 보장할 수 있습니다.
  • Overhead?
    • 메모리 내용을 재배치하는 과정은 시간과 자원을 소모하는 작업이며, 시스템의 성능에 영향을 미칠 수 있습니다.
• 외부 파편화를 해결하는 방법:
• Internal Fragmentation(내부 파편화)

Paging

→ 외부 파편화를 없애면서 내부 파편화를 최소화 시킬 수 없을까 해서 나온 기법

• 물리적 메모리를 frames라고 불리는 fixed-sized blocks로 나눈다.
• 논리적 메모리를 pages 라고 불리는 프레임과 같은 사이즈의 블록으로 나눈다.
• page table: 프로그램은 페이지 단위로 메모리에 로드된다. 각 페이지는 물리적 메모리의 어느 프레임에 위치하는지를 나타내는 페이지 테이블을 통해 추적

페이징의 작동 방식

• 메모리 할당: 프로그램 실행을 위해 필요한 페이지 수만큼의 프레임을 물리적 메모리에서 찾습니다. 이 프레임들은 연속적일 필요가 없습니다.
• 주소 변환: 논리적 주소(페이지 번호 및 페이지 내 오프셋)는 페이지 테이블을 통해 물리적 주소(프레임 번호 및 프레임 내 오프셋)로 변환됩니다.
• 자유 프레임 관리: 운영 체제는 사용 가능한 모든 프레임을 추적하고 관리합니다.

→ 여전히 내부 파편화를 가지고 있지만 조금이다.

Address Translation Scheme

• 주소는 CPU에 의해 두가지로 나뉜다
  • Page number(p): 페이지 번호는 페이지 테이블에서의 인덱스로 사용되며, 각 페이지가 물리적 메모리의 어느 프레임에 위치하는지를 나타내는 기준 주소(base address)를 포함
  • Page offset(d): 페이지 내에서의 특정 위치를 나타냅니다. 기준 주소와 결합되어 최종적인 물리적 메모리 주소를 형성
• Page table
  • OS에 의해 관리된다
  • page number를 frame number에 Map
  • Page table entry(PTE): 각 논리적 페이지에 대응하는 항목으로, 해당 페이지가 물리적 메모리의 어느 프레임에 위치하는지를 나타냄

Paging Model and Example

Paging Example

Paging

• 사용장 관점
  • 메모리를 0부터 N-1까지 하나의 연속된 주소 공간으로 인식 → 이를 Logical address space(LAS)
• 실제로, pages는 물리적 memory에 전체적으로 분산되어 있다.
  • 논리적-물리적 매핑: 운영 체제는 페이지 테이블을 사용하여 논리적 주소를 물리적 주소로 매핑. 이 매핑 과정은 프로그램에게는 보이지 않으며 운영 체제에 의해 관리됨.
• 프로그램은 자신의 논리적 주소 공간 외부의 메모리에 접근할 수 없음 → 이는 다른 프로세스의 메모리 영역이나 운영 체제의 메모리에 무단으로 접근하는 것을 방지
  • 독립된 주소 공간: 같은 논리적 주소(예: 0xdeadcafe)가 다른 프로세스에서는 서로 다른 물리적 주소로 매핑될 수 있음. 이는 각 프로세스가 독립된 주소 공간을 가지며, 서로의 메모리 영역을 침범하지 않도록 하는 데 기여함

Free Frames

• OS는 물리적 메모리를 관리하기위해 frame table 을 유지함.(각 frame들이 할당 되었는지 free상태인지 기록)
  • 각 프레임에 하나의 entry
  • 프레임이 할당되었거나 free 상태인지 상관없이

Implementation of Page Table

→ Main memory에서 운영

• 페이지 테이블은 물리적 메모리에 저장된다. 이 테이블은 논리적 페이지 번호를 물리적 프레임 번호로 Mapping
• Page-table base register(PTBR) - 페이지 테이블의 위치를 가리킴
• Page-table length register(PTLR) - 페이지 테이블의 사이즈를 나타냄
• Translation look-aside buffer(TLB)
  • TLB는 페이지 테이블 엔트리의 캐시로, 고속의 연관 메모리(associative memory)를 사용한다. → 가장 최근 또는 자주 사용되는 페이지 매핑을 빠르게 찾을 수 있도록 도와줌
  • 일부 TLB는 address-space identifiers (ASIDs)를 포함하여 각 프로세스의 주소 공간을 구별할 수 있게 한다. (ASIDs를 PID처럼 생각하면 쉽다)
  • TLB *Miss *→ TLB에 해당 페이지 매핑이 없는 경우(TLB Miss), 페이지 테이블(Main memory)에서 매핑을 찾아 TLB에 로드. 이후의 접근에서 빨라짐

Paging H/W with TLB

Effective Memory Access Time

• Hit ratio: TLB가 요청된 페이지의 매핑 정보를 가지고 있는 비율
• Effective Access Time (EAT) 계산
  • 예시)
    1. 80% 히트율:
       EAT = 0.80×10 ns + 0.20×20 ns = 8 ns + 4 ns = 12 ns
       이는 메모리 접근 시간이 평균적으로 12 나노초임을 의미, 이는 20%의 성능 저하를 의미합니다.
    2. 99% 히트율:
       EAT = 0.99×10 ns + 0.01×20 ns = 9.9 ns + 0.2 ns = 10.1 ns
       이 경우 평균 메모리 접근 시간은 10.1 나노초로, 성능 저하는 거의 없다.
• EAT=(TLB 히트율×단일 메모리 접근 시간)+(TLB 미스율×TLB 미스 시 메모리 접근 시간)

Memory Protection

• Protection bits: Page table에다가 protection에 관련된 bit 추가
  • ex) 특정 프레임이 읽기 전용(read-only)인지, 읽기-쓰기(read-write)가 가능한지, 또는 실행 전용(execute-only)인지를 지정
• Valid-invalid bit
  • valid: 페이지가 프로세스의 LAS 내에 있고, 접근이 허용된 경우
  • invalid: 페이지가 프로세스의 LAS 내에 없는 경우. 이 페이지에 대한 접근은 불법
  • 또는, page-table length register(PTLR) 사용 → page table 사이즈를 제한하는데 사용
  • 

Shared Pages

Paging의 장단점

• 장점
  • 물리적 메모리를 할당하기 쉽다
  • External fragmentation이 없다
  • 프로그램의 일부를 디스크로 쉽게 page out(swap out)할 수 있음. 모든 청크(페이지)가 동일한 크기이기 때문
  • page를 불법적인 접근으로부터 보호하기 쉽다
  • page를 공유하기 쉽다
• 단점
  • 여전히 Internal fragmentation이 발생할 수 있음 → Page 크기가 클 수록 더 많은 fragmentation 발생
  • 메모리 참조 오버헤드: 논리적 주소에서 물리적 주소로의 변환을 위해 여러 메모리 참조가 필요
  • 페이지 테이블이 크고 복잡할 경우 상당한 양의 메모리를 요구할 수 있음.
    • 이를 해결하기 위해 다중 레벨 페이지 테이블, 역 페이지 테이블 등의 기법이 사용될 수 있음

Swapping

• 프로세스나 프로세스의 일부분이 임시적으로 메인 메모리로부터 backing store가 된다. → 그러면 메모리가 비게되고 다른 프로세스가 사용할 수 있음. 후에 필요할 때 다시 가져올 수 있음
  • Backing store(second storage라고 생각하면 쉽다)
    • 백업 저장소는 일반적으로 디스크와 같은 보조 저장 장치입니다.
    • 모든 사용자의 메모리 이미지를 저장할 수 있는 충분한 공간과, 이러한 메모리 이미지에 대한 직접 접근을 제공해야 합니다.
  • Swapping하면, 시스템의 물리적 메모리보다 더 많은 프로세스를 동시에 실행할 수 있음 → 이를 통해 멀티프로그래밍도를 높일 수 있다.
  • 

• Standard swapping
  • 전체 프로세스를 swapping
• Page swapping
  • Standard swapping의 수정된 버전
  • 자주쓰고 중요한 것은 swap out하지 않고 잘 사용하지 않는 것들만 swap out해서 빠르게 필요한 가용 메모리를 확보
  • 전체 프로세스 대신에 일부만 Swapping → swapping cost 절감