OS - (7) Main memory

Main Memory

Background

• HW : 메인메모리와 레지스터
  CPU에 직접 접근할 수 있는 장치는

  • main memory
  • 각 processor core에 내장된 register.

  이므로, 실행되어야 하는 코드, 명령어들은 cpu가 접근할 수 있도록 main memory에 로드되어야한다.

• Cache
  CPU와 메모리 사이에 존재하는 속도가 빠른 fast memory.

  CPU에 내장된 레지스터들은 일반적으로 1 CPU clock내에 접근 가능하다.

  클럭?

  CPU의 속도 단위(1초 동안 CPU 내부에서 몇 단계의 작업이 처리되는지를 측정한, 파장이 움직이는 속도 단위)

  그러나 메인메모리 접근에는 많은 CPU 클록 틱 사이클이 소요된다.
  필요한 데이터가 없는 processor들은 실행중인 연산을 완료할 수 없기에 일반적으로 정지(stall)하고,
  메모리 접근의 빈도가 매우 높다면 어느 순간 정지 시간이 견딜 수 없게 지연될 수 있다.
  이러한 CPU와 접근할 수 있는 장치들의 속도차이로, 생길 수 있는 문제를 해결하기 위해
  CPU와 메모리 사이에 속도가 빠른 fast memory 하나를 추가해 메모리의 접근을 줄이고 캐시로 접근하도록 한 것.

• 프로세스의 주소공간

  • 메모리 위치 방식 : 독립된 공간 보장 (Base & Limit)
    프로그램은 실행을 위해 메모리로 옮겨져 독립된 공간에 위치한다.
    프로세스들이 각자 메모리에 고유 공간을 차지할 수 있도록 프로세스 별
    base register(가장 작은 물리 메모리 주소(프로세스 시작점)를 가짐)와
    limit resgister(프로세스 주소 공간의 크기를 가짐)에 값을 저장해놓는다.
    : 이 register들이 물리 메모리 내 프로세스 주소 공간을 결정하는데 사용된다.
    
  • 메모리 공간 보호
    CPU hw가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교하고, (사용자모드에서 만들어진 모든 주소는 레지스터 범위 안에 존재해야햠)
    사용자 모드에서 수행되는 프로그램이 OS의 메모리공간이나 다른 user program 메모리 공간에 접근하면 trap을 발생시켜 보호한다.(legal,유효한 메모리 접근 범위 정할 수 있음.) -> 사용자 프로그램이 허가되지 않은 메모리영역의 코드나 데이터 구조를 변경할 수 없게 함.
    
    base와 limit register값은 OS 커널모드에서만 동작하는 전용 연산에 의해 적재되고, OS만이 커널모드를 수행할 수 있기 때문에 OS만이 해당 값을 변경할 수 있다.

Adress Binding

• 프로세스 주소
  • 논리적 주소(logical address)
    가상주소. (virtual address). CPU가 생성하며 프로세스마다 독립적으로 가지는 주소 공간이기 때문에 프로세스 내부에서 사용.
  • 물리적 주소
    프로세스가 실행되기 위해 실제로 메모리에 load되는 위치.
  • adress binding
    프로세스의 logical 주소를 물리적 메모리 주소로 연결시켜주는 작업(cpu가 보는 주소인 logical address와 메모리hw의 위치인 물리적주소 연결)

• Access Binding 과정
  프로그램은 보통 실행가능한 이진 파일(binaryfile)형태로 디스크에 저장 -> 실행되기 위해 메모리로 로드.

  0. 프로세스는 실행 동안 disk,memory를 옮겨다닐 수 있는데 이 때 memory로 옮겨지기 위해(실행) 기다리는 프로세스들은 Input Queue에서 대기하게 된다.
  1. input queue에서 process 선택해 메모리에 적재
  2. 프로세스 실행 시 메모리의 연산과 데이터들에 접근
  3. 프로세스 종료 시 사용하던 메모리 영역은 다시 사용 가능한 메모리 영역이 됨.
  • symbolic 주소, 재배치 가능 주소, 절대 주소
    • 원시 주소 : 프로그램 주소는 일반적으로 symbloic 주소 형태이다.(count등 변수 형태)
    • 컴파일러 : compiler는 심볼릭 주소 형태를 'module 시작 주소(B4CE04C)로부터 16바이트(+2)' 라는 실제 주소로 bind
    • 링커/로드 : linker나 loader는 이 주소(재배치 가능 주소)를 절대 주소로 바인딩.
      

• 컴파일 시간, 적재 시간, 실행 시간
  바인딩 과정은 이루어지는 시간에 따라 3가지로 나눌 수 있다.

  • Compile Time : 프로세스의 물리적 주소가 컴파일 때 정해진다.
    process가 메모리에서 차지할 영역을 컴파일 시간에 알고있다면 절대 주소(고정 주소)생성한다. (시작 주소가 변경될 경우 코드를 재컴파일)
    컴파일 타임 주소 할당은 프로세스 내부에서 사용하는 논리적 주소와 물리적 주소가 동일하다.
  • Load time : 프로세스가 메모리의 어느 위치에 들어갈지 미리 알 수 없다면 컴파일러는 이진 코드를 재배치 가능 코드로 만든다. 재배칭 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.
    -> load time 주소는 논리적 주소와 물리적 주소가 다르다. 실제 address와 바인딩은 프로그램이 메인 메모리로 실제 적재되는 시간에 이루어진다.
  • Execution Time(Run Time)
    프로세스가 수행된 이후 프로세스가 실행 중 메모리 주소를 바꾸는 방법. Runtime때 물리적 주소가 결정되며 실행 도중 주소가 바뀔 수 있음. CPU가 주소 참조 시 마다 address Mapping Table을 이용하여 binding 점검.
    런타임 주소 할당은 MMU(memory Management Unit)이라는 하드웨어 장치를 사용하여 논리적 주소를 물리적 주소를 바꿔준다.(process cpu 수행되며 생성해내는 주소값들에 대해 base register의 값을 더해줘 물리적 주소를 생성하는 방식. -> base register는 1개 뿐이므로 프로세스끼리 공유)
    

  컴파일/ 로드 타임에 주소를 바인딩하면 논리주소(CPU가 생성한 주소)와 물리주소(메모리에 올라간 주소)가 같고, Runtime(실행시간) 바인딩에서는 논리 주소와 물리 주소가 다르며, 이 때 논리 주소를 가상주소라고 지칭한다.

• MMU ( Memory Management Unit, 메모리 관리 장치)
  가상 주소를 물리 주소로 변환해주는 'HW'장치
  
  사용되는 방법들은 CPU에서 논리적 주소를 받아 고정분할,동적분할, 페이징, 세그멘테이션 등 변환방법을 사용하여 물리적 주소로 변환시킨다.

Swapping

메모리를 임시에 디스크에 보내거나(swap-out) 다시 로드(swap-in)하는 것. (한정된 메모리 자원을 효율적으로 쓰기 위하여)
일반적으로 mid-term scheduler가 swap out할 프로세스를 선정, 우선순위에 따라 swap-in , out한다.
메모리(주기억장치) - 디스크(보조기억장치)간 프로세스를 옮기는 시간이 swapping시간의 대부분을 차지한다. 또한 swap-in할 때 이전과 같은 주소로 가져와야하는 것만은 아니다. Runtime binding을 지원한다면 상관 없다.

Contiguous Memory Allocation

: 연속 할당 방식. 각 프로세스들이 연속적인 메모리 공간을 차지하게 된다.

고정 분할 방식 (fixed partition allocation)

각 프로세스를 메모리에 담기 위해 메모리는 미리 공간을 분할해둔다.
고정 분할 방식은 사용자가 쓸 수 있는 메모리 범위 내에서 고정된 특정 크기로 잘라 분할된 메모리 partiation을 생성한다. (각 분할의 크기가 모두 같지 않을 수도 있다). 분할 당 하나의 프로세스가 적재되므로 메모리에 load되는 프로세스 수가 고정, 수행가능 프로세스 최대 크기가 제한된다.

가변 분할 방식 (variable partition allocation)

각 프로세스가 필요한 만큼 메모리를 할당한다. 기준(base) 레지스터와 경계(limit) 레지스터를 사용하여 각 프로세스 분할 영역을 나타낼 수 있게 되고 생성한 논리적 주소가 경계 레지스터 값보다 커지면 오류.
각 메모리 분할 단위를 Block이라고 하고 프로세스가 사용 가능한 block을 hole이라고하는데, 프로세스가 도착하면 수용 가능한 hole을 할당시켜준다. 이 때 가변 분할 방식에서 크기가 n인 프로세스들이 들어갈 가장 적절한 hole을 찾는 문제를 Dynamic Storage Allocation Problem이라고 한다.

• Dynamic Storage-Sllocation Problem

1. First Fit
   최초로 발견한 수용가능 Hole에 할당.
2. Best Fit
   크기가 n 이상인 가장 작은 Hole에 할당. 모든 Hole을 탐색(정렬X경우)
3. Worst Fit
   가장 큰 hole에 할당. 모든 Hole탐색, 상대적으로 할당 후 발생하는 Hole 크기가 크다
   .

Internal Fragmentation

• 단편화 : 프로세스들이 적재되고 제거되는 일이 반복되다보면 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼 작은 자유공간들이 늘어나게되는 것. (할당하지 못할 만큼 작은 hole들이 생겨나는 것.)
• 내부 단편화 : 프로세스가 사용하는 메모리 공간 중 남는 부분. 메모리 분할(고정) 자유공간이 1000이 있고, 프로세스 A가 900을 사용한다면 고정된 공간과 프로세스 요구크기 간 100이라는 차이가 발생하고 이를 내부 단편화라고 한다.
  고정 분할 방식에서 논리적 주소가 분할된 메모리보다 작을 때 문제가 발생한다는 개념이 내부 단편화.

External Fragmentation

• 외부 단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분.
  가변분할방식 사용 시 프로세스가 계속해서 적재-제거 됨에 따라 외부 단편화가 생기게 된다.

• Compaction(압축)
  외부 단편화를 해결할 수 있는 방법. 프로세스가 사용하는 공간들을 한쪽으로 몰아서 공간을 확봐는 방법. 그러나 비용이 많이 들어 효율적이지 않다. 메모리의 재배치가 runtime에 동적으로 동작할 경우에만 가능하다.
  -> paging, segmentation은 이러한 문제점을 해결하기 위해 논리적 주소공간을 비연속적(Noncontiguous)가 되도록 하여 사용 가능한 물리적 메모리 어디든 사용가능하게 한다.

Noncontiguous Allocation

: 비연속 할당 방식. 하나의 프로세스가 메모리 여러 영역에 분산되어 올라가게 된다.

Paging

외부 단편화의 압축 작업 비효율성을 해결하기 위한 방법.
물리 메모리를 frame, 논리 메모리(프로세스 점유)를 page라는 이름으로 고정크기 블록으로 분리한다.
한 프로세스가 사용하는 공간은 여러 page로 나누어서 관리되고, page는 순서와 관계없이 frame에 mapping되어 저장된다.

하나의 프로세스가 사용하는 공간을 여러개 페이지(논리메모리상)로 나누기 때문에, 논리 메모리는 물리 메모리에 저장될 때 연속되어 저장될 필요가 없고, 물리 메모리의 남는 프레임에 적절하게 배치되어 불연속적으로 원하는 크기만큼 할당받으면 된다.

동작 원리

CPU에 의해 생성된 모든 주소들은

• 페이지번호(Page number p)와
• 페이지 간격(Page Offset d)로
  

구성되며 페이지 번호는 페이지 테이블의 인덱스로 사용된다.

• 페이지 테이블 : 물리적 메모리의 각 페이지 Base 주소(시작주소, f=프레임번호)를 저장하고있다. -> 페이지와 대응하는 물리적 메모리의 프레임 주소를 가리킨다. 시작 주소를 페이지 간격(offset)과 더해 메모리 단위의 물리적 메모리 주소를 정의할 수 있다.
  이 때 변환은 MMU(memory management unit)이 수행하며,
  1. 프로세스 실행 시 주소에서 페이지 번호 p를 가져와 페이지 테이블 인덱스로 사용
  2. 페이지 테이블에서 매팽되는 프레임번호 f를 얻어옴
  3. 논리 주소 페이지번호 p를 프레임 번호 f(실제 물리 주소)로 바꾼다

페이지 테이블은 프로세스마다 존재하여 메인 메모리에 상주한다.

• TLB ( Translation Look Aside-Buffer)
  : 소형 하드웨어 캐시
  • PTBR(Page table base register)
    : 페이지 테이블 기준 레지스터. page table은 메인 메모리에 상주하지만, PTBR라는 레지스터가 page table을 가리키도록 하여 context switching을 빠르게 할 수 있다.(레지스터 내용만 변경하면 되며 레지스터는 빠르다, 레지스터는 비용이 비싸므로 큰 페이지 테이블을 적재하는 것은 비효율적이며 저장은 메인메모리에 하되 테이블 주소값을 레지스터에 저장,매핑해 빠르게 접근 및 변경 가능하도록 한다) 이 때 실질적으로 원하는 물리 메모리에 접근하는 방법ㅇ느
    페이지 번호를 기준으로 PTBR 오프셋 값을 사용해 페이지 테이블의 항목을 찾고,(첫 번째 메모리 access)
    얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소에 접근한다(두 번째 메모리 access)
    -> 두 번의 접근으로 메모리 접근이 느려진다. 이러한 문제를 해결하기 위한 것이 TLB이다.
    

TLB는 메모리 주소 변환을 위한 별도의 캐시 메모리로, page table에서 빈번히 참조되는 일부 엔트리를 캐싱하고있다.
key-value쌍으로 데이터를 관리하는 associative memory.

• key : page number,
• value : frame number

구조를 갖는다.
CPU는 TLB를 우선 참조해 원하는 page가 TLB에 존재하면 바로 frame number를 얻을 수 있고 그렇지 않다면 메모리에 있는 page table로부터 frame number를 얻을 수 있다.

context switching이 일어날 경우에는 TLB 전체를 비우는 방법은 비용이 비싸다는 단점이 있으므로 TLB의 각 엔트리가 어느 프로세스를 위한 것인지 추적하여 이용하지 않는 엔트리만 비운다. (Address space identifier , ASID)
ASID란 프로세스 아이디와 유사하지만 8bit로 32인 pid보다 비용이 저렴하다. 동일 ASID인 프로세스끼리는 TLB를 공유.

segmentation

: 프로세스 가상메모리를 '의미'단위인 세그먼트로 나누어 물리 메모리에 적재하는 방식.
사용자 관점의 메모리를 지원하는 메모리 관리 기법.
작게는 함수 하나하나를, 크게는 프로그램 전체를 segment로 정의할 수 있고, 일반적으로는 code, data, staack부분이 하나의 세그먼트로 정의된다.
segment의 논리적 주소는

• segment number
• offset

으로 구성되며 각 segment는 base, limit, protection bit를 가지고있다.
segmentation 장점은 paging과 마찬가지로 연속적 할당 필요가 없고 stack, heap이 독립적으로 커질 수 있다.
segmentation 또한 segment table에 의해 사용자 관점 주소들을 물리 주소로 매핑한다.

segment의 논리적 주소인 segment number s와 offset d는 segment table에서 s에 해당하는 segment의 base와 limit 값을 찾고, d가 limit보다 작은 값인지 검사 후 이상이 없다면 base+d가 물리적 주소로 매핑된다.

역시 외부 단편화 존재 가능

paged segmentation

페이징, 세그멘테이션 장점만을 취하는 주소 변환 기법이다.
segmentation을 먼저 수행하고 각 segment별로 paging을 수행한다.
프로그램을 의미 단위인 segment로 나누지만 segment가 동일 크기 페이지들 집합으로 구성되는 것.

기존 segment table 구조에서 base 주소값 대신 해당 segment의 page table 위치를 저장하고, limit(bound) 값 대신 segment의 page 개수를 저장한다.
물리 메모리에 적재하는 단위는 페이지 단위이다.
기존 paging 기법만 사용했을 때 보다 page의 크기를 줄일 수 있지만, 메모리 참조가 한번 더 증가해3번으로 증가되는 속도 저하의 문제점이 있음.
하나의 세그먼트 크기를 페이지 크기의 배수로 함으로써 외부 단편화를 해결한다.

Structure of the Page Table

페이지 테이블의 문제점

현대 컴퓨터들은 매우 큰 주소공간을 지원한다. 2^32(32bit주소공간)부터 2^ 64까지 큰 논리적 주소공간을 지원.
32bit 주소체계를 사용할 때 주소공간의 크기는 2^32이다.
페이지 하나의 크기가 4kb라면 2^12이다. (1kb=1024byte=8192bit=2^12)
페이지 테이블에 2^20(2^32/2^12)개 정보가 저장되어야하고 항복 당 4byte가 사용된다면 각 프로세스는 2의 22승인 4mb의 page table공간을 물리 메모리에 요구하게된다. 페이징 자체가 연속된 메모리에 공간을 할당하는 것이 불합리하기 때문에 고안된 것이나 페이지 테이블때문에 4mb라는 공간을 연속해서 할당해야하므로 개선이 필요한 사항이며 테이블 자체도 쪼개서 메인메모리에 탑재한다.

Hierarchical Paging:계층적 페이징( 2 level paging )

: 페이징 테이블을 다시 페이징.
논리 주소를 구성하는 값 중 페이지 번호를 의미하는 p를 분할한다. 분할한 p1,p2중 p1을 위해서 outer(바깥)페이지 테이블을 구성하고, p2를 위해서 inner(안쪽)페이지 테이블을 구성한다. 바깥 에서 안쪽 페이지 테이블을 인덱싱하고, 안쪽 페이지 테이블은 최종적으로 frame으로 mapping 되도록 하는 것.
outer의 페이지 시작주소로부터 p1값을 더해 접근,참조해 해당 항목 값을 얻고, inner에서 얻어낸 해당 값에 p2값을 더한 값을 참조해 값을 얻어낸다. 이 때 얻어낸 값으로부터 해당 페이지에 mapping되는 프레임 번호를 얻고 거기에 d(offeset)값을 더해 최종 물리주소를 얻어냄.



단점으로는 물리메모리 접근횟수가 증가해 속도저하될 수 있다는 문제.

Hashed Paged Tables:해시 페이지 테이블

: 논리주소에 대한 해시값을 이용해 바로 물리주소로 mapping한다.
일반적으로 hash기법 사용 시 입력 도메인 크기가 출력 도메인보다 훨씬 크므로 has collision이 발생하는데(해쉬값이 겹침)
이러한 문제를 해결하기 위해서 Hash Table 각 항목에 연결 리스트를 두어 충돌이 일어난 주소(가상 페이지 번호)에 대한 물리주소 값 쌍을 리스트로 관리한다.

해시테이블의 각 항목은 3개의 필드를 가지게 되고, 논리페이지로부터 프레임 번호가 매핑된다.

• 논리 페이지 번호
• 매핑되는 페이지 프레임 번호
• 연결리스트 상 다음 원소 포인터
  해시 페이지 테이블에서는 논리 주소값이 들어오면 hash값으로 변환, hash page table로 부터 연결리스트의 가상페이지번호들과 비교, 매치되는 가상페이지번호와 동일 항목의 페이지 프레임번호로 변환한다.

Inverted Page Table:역 페이지 테이블

: 메모리 프레임마다 한 항목(entry)씩을 할당한다.
페이지 테이블을 위한 메모리가 많이 요구되는 이유는 프로세스 당 하나의 페이지 테이블을 보유하기 때문이므로 페이지 테이블을 하나만 두고 메인메모리 각 프레임마다 페이지 테이블의 한 항목을 할당하되, 각 항목에 PID와 페이지번호(논리공간 순번)을 함께 기록해 동일 프레임이 프로세스간 매핑되는 것을 방지.
각 필드는 다음과 같이 구성

• 프레임에 올라와있는 페이지 주소
• 페이지를 소유하고 있는 프로세스ID
  
  페이지 테이블에 프로세스 정보를 포함시킴으로서 프로세스별 페이지 테이블을 만들지 않는다
  -> 기존 페이지 테이블은 논리 주소로부터 페이지에 접근하여 많은 양의 물리 메모리를 소비한다.
  그러나 역 페이지 테이블 방법에서는 적재된 물리 메모리 프레임마다 하나의 페이지 엔트리를 할당해 각 엔트리에는 프레임에 올라와 있는 페이지 주소와 소유자 PID를 표시 -> 시스템에 페이지 테이블을 하나만 유지할 수 있게 해준다.
  -> 실제 물리 frame에 대응하는 엔트리(페이지주소와 PID)만 저장하면 되기 때문에 메모리를 적게 사용하게된다. (물리프레임에 대응되는 항목만 테이블에 저장)

단점으로는 공유되는 가상 주소(공유 메모리 사용 불가)를 가질 수 없고, 물리주소에따라 역페이지테이블이 정렬되어있으므로 주소 변환 시 테이블 전체를 탐색, 오래걸린다.

스와핑

스와핑은 전체 프로세스를 메인 메모리와 디스크사이에서 이동시키는 것인데, 이 때 프로세스 단위로 스와핑을 하게되면 시간이 오래 걸린다.
그러므로 거의 모든 운영체제는 페이지 단위의 스와핑을 적용한다.