퇴근 후 운영체제 시리즈 - 메모리 관리

in Studying CS Basic
퇴근 후 운영체제 시리즈 - 메모리 관리

운영체제 스터디 기록

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

물리적 메모리의 주소 변환은
OS가 관여하지 않는다!!

image

Logical vs. Physical Address

image

  • 주소 바인딩 : 주소를 결정하는 것
    • Symbolic Address → Logical Address → Physical Address
  • CPU가 보는 건 logical address 임

주소 바인딩 - 하드웨어의 도움이 있다

image

Compile Time binding

  • 물리적 메모리 주소가 컴파일 시 알려짐
  • 시작 위치 변경 시 재컴파일
  • 컴파일러는 절대 코드 생성

Load Time Binding → 실행시작 단계

  • 로더의 책임하에 물리적 메모리 주소 부여
  • 컴파일러가 재배치 가능 코드를 생성한 경우 가능

Run Time binding

  • 프로그램이 실행되는 도중에 메모리 상 위치를 옮길 수 잇음
  • cpu가 주소를 참조할 때마다 binding을 점검
  • 하드웨어적인 지원이 필요
    • base & limit registers, MMU ⇒ OS가 하는 일 아님!!
      • os가 하는 건 말이 안됨
      • 메모리에 한번 접근한다고 했는데 os에 가는 거 자체가 오버헤드임
      • 그냥 빨리 주소 변환이 필요함
    • 실행될 때마다 Binding 위치를 확인해봐야됨

MMU

📡 논리 주소를 물리 주소로 매핑해주는 하드웨어 장치

image

  • CPU가 346번지의 프로그램을 요청함
  • 물리 메모리에는 14,000번지에 올라가있음
  • 따라서 이를 도와주는 레지스터 2개가 필요함
  • Base Register : 더해주는 값
  • limit register : 논리적 주소의 범위 (3,000)
    • 악의적인 프로그램들의 공격을 막기 위해

몇가지 용어

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것

✓ Loading : 메모리로 올리는 것 ⇒ 실행 가능한 상태로 만드는 것

  • memory utilization의 향상
  • 가끔씩 사용되는 많은 양의 코드의 경우 유용
    • 오류 처리 루틴
  • 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능
    • 현대적인 시스템에서는 dynamic loading은 아님
    • 지금은 운영체제가 처리함

Overlay

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림

  • 옛날 시스템에서 유용 ⇒ 프로세스의 크기가 메모리보다 클 때

Swapping (여기서는 프로세스 통째로를 말함)

프로세스를 일시적으로 메모리에서 swap area(디스크)로 쫓아내는 것

image

  • 일반적으로 중기 스케줄러(swapper) 에 의해 swap out 시킬 프로세스 선정
  • 우선순위 스케줄링 적용
  • 컴파일 타임 혹은 로드 타임 바인딩에서는 원래 메모리 위치로 swap in 해야 함
    • 이미 정해져있는 주소이기 때문 (비효율적)
  • Run Time 바인딩에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • 스왑 시간은 대부분은 스왑되는 양에 비례

Paging Swapping

프로세스 전체를 이동하는 시간이 엄청나기에 최신 운영체제는 페이징 단위로 스와핑을 진행함

Dynamic Linking

링킹을 실행 시간까지 미루는 기법

Static linking

  • 라이브러리가 프로그램의 실행 파일 코드에 포함
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
    • ex) printf

Dynamic Linking (DLL)

  • 라이브러리가 실행 시 연결됨
  • 공유를 하는 개념이기에 중복해서 메모리에 올리는것이 아니라 shared library로써 사용함
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • OS의 도움이 필요

물리적 메모리의 관리

image

메모리는 일반적으로 두 영역으로 나뉘어 사용

  • OS 상주 영역
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 사용

사용자 프로세스 영역의 할당 방법

✔︎ 연속 할당

  • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것 (프로세스를 안 쪼개고)
    • 고정 분할 방식
      • 메모리를 미리 나누어두는 것
      • 내부 조각 (internal fragmentation): 낭비되는 조각
      • 외부 조각 : 분할의 크기가 작아 아무 프로세스도 들어가지 못하는 공간
      • 융통성이 없음
        • 동시에 메모리에 load되는 프로그램의 수가 고정됨
        • 최대 수행 가능 프로그램 크기 제한
    • 가변 분할 방식
      • 프로그램의 크기를 고려해서 할당
      • external fragmentation
        • 말이 외부 조각이지 그에 맞는 프로세스 생기면 낭비가 아닐수도~?
  • 위에서 보았던 base, limit register를 활용해서 주소 할당이 가능하다

image

Hole

image

  • 가용 메모리 공간
  • 다양한 크기의 hole 들이 메모리 여러 곳에 흩어져있음
  • 프로세스가 도착하면 수용 가능한 hole을 할당
  • 운영체제는 다음의 정보를 유지
    • 할당 공간
    • 가용 공간

Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole 을 찾는 문제

  • First Fit
    • 최초로 찾아지는 hole에 할당
  • Best Fit
    • size가 n 이상인 가장 작은 hole 을 찾아서 할당
    • hole들의 리스트가 크기 순으로 정렬되어 있지 않다면 탐색 O(n)
    • 많은 수의 아주 작은 hole 들이 생성됨 (정확하게 맞추기 어렵기 때문)
  • Wort-fit
    • 가장 큰 hole에 할당
    • 그냥 제일 안 좋음 (시간적으로나 공간적으로나)

compactation (압축)

  • 외부 단편화 문제를 해결하는 한 가지 방법
  • 사용 중인 메모리 영역을 한군데로 몰고 hole 들을 다른 곳으로 옮겨 큰 block으로
  • high cost
  • 최소한의 메모리의 이동으로 compactiation하는 방법
  • run time 실행에서만 compactation 이 가능 → 메모리의 주소를 계속 변화시키기에

✔︎ 불연속 할당

📡 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

기존의 base, limit 레지스터로는 다 저장할 수 없기에 레지스터로는 감당이 안된다 → 페이지 테이블 필요

Paging

  • 프로세스의 가상 메모리를 동일한 사이즈의 page 단위로 나눔 (보통 4KB)
  • 페이지 단위로 불연속적으로 저장됨
  • 일부는 swap 영역, 일부는 물리 메모리에 저장

Basic Method

image

  • 물리적 메모리를 동일한 크기의 frame으로 나눔
  • 논리적 메모리를 동일한 크기의 page로 나눔 (frame과 같은 크기)
  • 모든 가용 frame들을 관리
  • page table을 사용하여 논리 주소를 물리 주소로 변환
  • 외부 단편화가 발생 안함
    • 당연한 것. 이미 다 나눠놨기 때문에 어떤 페이지든 다 넣을 수 있음
  • 내부 단편화 발생 가능
    • 4KB 씩 잘라나가다 보면 마지막 부분에 짜투리 부분이 남을 수 있기 때문에

image

  • P : 페이지 번호 (2^20 비트 필요)
  • D : 페이지 안에서 얼마나 떨어져 있는가를 나타내는 오프셋 크기 (2^12 비트 필요)
  • 32bit 환경에서 프로세스 가상 메모리가 가질 수 있는 크기는 4GB
  • 이때 한 주소당 Byte이고 페이지를 4KB로 나눠놨으니 약 100만 크기의 테이블이 잡힘

Page Table

  • 프로세스마다 page table을 가지고 있음
  • 페이지 테이블은 메인 메모리에 상주
    • Page-table base register (PTBR)가 page table을 가리킴
    • 따라서 페이지 테이블을 바꾸고 싶다면 이 레지스터의 값만을 변화시키면 됨
  • Page-table length register (PTLR)가 테이블 크기를 보관
  • 모든 메모리 접근 연산에는 2번의 메모리 접근 필요
    • page table을 위해 1번 (메인메모리-DRAM 안에 있음)
    • 실제 데이터/명령어 접근 1번
  • 이를 위해 속도 향상을 위한 캐시를 두고 있음
    • 주소 변환을 빠르게 해주기 위한 translation look-aside buffer (TLB) 하드웨어 캐시

image

  • frame 에 접근하기 위해 메인 메모리를 2번 접근하는 것을 캐시화
  • TLB에 미리 저장시켜두어 메인 메모리 접근 1번
    • TLB 접근 속도 > 메모리 접근
  • TLB는 일부분만 담고 있기에 miss가 뜨면 페이지 테이블을 봐야됨
  • TLB 에서는 p 에 관해 선형 탐색을 해야됨 → O(n)
    • 따라서 병렬 처리가 되는 하드웨어를 사용함
  • 각 프로세스마다의 페이지 테이블을 TLB에 담기에 context switch가 일어나면 flush 해줘야됨 (큰 오버헤드)

Two Level Page Table

📡 현대의 컴퓨터는 주소 공간이 매우 큰 프로그램 지원

32bit 주소 공간

  • page 크기가 4KB시 1M개의 페이지 테이블 필요
  • 각 페이지 엔트리가 4B시 프로세스 당 4M의 페이지 테이블 필요
  • 그러나 대부분의 프로그램은 4GB의 주소 공간 중 지극히 일부분만 사용하므로 페이지 테이블 낭비가 너무 심함

image

  • outer 페이지 테이블을 하나 더 두면 시간적으로나 공간적으로나 손해 아닐까?

    ⇒ 아니다!!

  • 바깥 페이지 테이블은 잘 사용하지 않는 부분에 대해서는 NULL 포인터를 가짐
  • 그러면 바깥 페이지 테이블이 가르키는 페이지 테이블의 크기는 얼마인가?
    • 4KB! ⇒ 즉 프레임 크기와 똑같이 되어서 direct pointer라고 봐도된다
    • 근데 엔트리는 4B라 1K개의 엔트리가 있음

image

Bit in a Page Table

image

image

  • 해당 영역이 실제 메모리에 있는가 아니면 스왑 영역에 있는가
  • valid : 메모리 위에 있다.
  • invalid : 메모리를 사용하지 않거나 필요 없거나

보호 비트는 왜 필요한가?

  • 접근 주체가 아니라 page 에 대한 접근 권한 (read / write ..)

Inverted Page Table

📡 페이지 테이블이 큰 이유는 무엇인가?

  • 모든 프로세스 별로 그 논리 주소에 대응하는 모든 페이지에 대해 페이지 테이블 엔트리 존재
  • 대응하는 페이지가 메모리에 있든 아니든 간에 페이지 테이블에는 엔트리로 존재

Inverted Page Table

  • 페이지 프레임 하나 당 페이지 테이블에 하나의 엔트리를 둔 것
  • 각 페이지 테이블 엔트리는 각각의 물리적 메모리의 페이지 프레임이 담고 잇는 내용 표시(process-id, process의 논리 주소)

단점

✔︎ 테이블 전체를 탐색

장점

✔︎ 협력 레지스터 사용(병렬 처리가 가능해짐 → 따라서 비쌈)

Shared Page

image

  • 동일한 프로그램인 경우, 코드 부분은 동일하고 데이터, 스택만 다를 것
  • 즉 동일한 코드의 카피가 너무 많이 올라가면 낭비!
  • 따라서 여러 카피를 올리지말고 하나만 올려서 공유를 하자! 라는 의미
  • 프로세스의 IPC 중 하나인 shared memory가 아니라 read only 만 가능한 코드를 공유하는 것!
  • shared code는 모든 프로세스의 동일한 논리 주소에 위치해야됨
    • 왜냐? Run time 바인딩이 아닌 이상 주소는 이미 정해짐 → 컴파일을 새로 해야됨

Segmentation

🛝 크기대로 자르는게 아니라 의미 단위(코드, 스택, 데이터~) : Segment 로 자르는 것

  • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
  • 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨

image

  • 각 segment 별로 그 크기가 다르기에 limit / base 두 개가 필요함
    • base : 물리 주소 시작 위치
    • limit : 세그먼트의 길이
  • 해당 세그먼트를 넘어서는 주소의 세그먼트를 요청한건지를 확인해야됨!

image

🕢 어디 hole 에 넣어야 할까? (각자 크기가 다르다!) ⇒ First fit / best fit

  • 의미 단위이기에 Protection 이 알아서 이루어짐 ⇒ 의미 단위이기에 보안이나 공유에 있어 페이징보다 훨씬 효과적
  • 근데 세그먼트가 그렇게 많지 않음(코드, 스택 데이터, 함수 등 다 합해봤자 얼마 안됨 - 엔트리 수)
    • 현실적 구현 측면에서는 페이징이 너무 공간 비효율
    • pure 세그멘테이션을 그대로 쓰는 시스템은 없음
    • 페이징 기법을 근간으로 구축하고 잇음 ⇒ paging + segmentation

Paged Segmentation

image

🕢 세그먼트의 길이 = 페이지의 배수

즉 한 세그먼트마다 페이지로 나눠둔다.

  • 결국은 페이지 단위대로 물리메모리에 배치되는 것이다
  • 하지만 관리는 segment table을 활용해서 다룬다.
  • 페이지 테이블 같은 경우 프로세스마다 존재하는 것이 아닌 세그먼트마다 존재
  • 할당 문제가 없어짐 ⇒ 페이지대로 그냥 배치하니
  • protection 문제도 해결 ⇒ 세그먼트 별로 나누어 놓았으니