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

23 Apr 2024 in Studying CS Basic

운영체제 스터디 기록

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

• 물리적 메모리의 주소 변환은
  OS가 관여하지 않는다!!
• Logical vs. Physical Address
  • 주소 바인딩 - 하드웨어의 도움이 있다
    • Compile Time binding
    • Load Time Binding → 실행시작 단계
    • Run Time binding
• MMU
• 몇가지 용어
  • Dynamic Loading
  • Overlay
  • Swapping (여기서는 프로세스 통째로를 말함)
    • Paging Swapping
  • Dynamic Linking
    • Static linking
    • Dynamic Linking (DLL)
• 물리적 메모리의 관리
• 사용자 프로세스 영역의 할당 방법
• ✔︎ 연속 할당
  • Hole
  • Storage-Allocation Problem
  • compactation (압축)
• ✔︎ 불연속 할당
  • Paging
    • Page Table
    • Two Level Page Table
    • Bit in a Page Table
    • Inverted Page Table
    • Shared Page
  • Segmentation
  • Paged Segmentation

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

Logical vs. Physical Address

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

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

Compile Time binding

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

Load Time Binding → 실행시작 단계

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

Run Time binding

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

MMU

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

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

몇가지 용어

Dynamic Loading

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

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

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

Overlay

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

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

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

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

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

Paging Swapping

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

Dynamic Linking

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

Static linking

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

Dynamic Linking (DLL)

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

물리적 메모리의 관리

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

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

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

✔︎ 연속 할당

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

Hole

• 가용 메모리 공간
• 다양한 크기의 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

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

• 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) 하드웨어 캐시

• 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의 주소 공간 중 지극히 일부분만 사용하므로 페이지 테이블 낭비가 너무 심함

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

  ⇒ 아니다!!

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

Bit in a Page Table

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

보호 비트는 왜 필요한가?

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

Inverted Page Table

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

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

Inverted Page Table

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

단점

✔︎ 테이블 전체를 탐색

장점

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

Shared Page

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

Segmentation

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

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

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

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

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

Paged Segmentation

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

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

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