[OS] 10. 메모리 관리 - (1)

[이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.]

운영체제

운영체제 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각 www.kocw.net

운영체제

---

[그림과 함께 편하게 보려면 여기로]

https://adorable-aspen-d23.notion.site/OS-10-1-db207507b2634bd6bc16af399ff83be2

[OS] 10. 메모리 관리 - (1)

1. 메모리

1. 논리적 주소, 물리적 주소

• Logical Address
  • 프로세스가 가지는 독자적인 주소 공간
  • 0번지부터 시작한다.
  • CPU는 논리적 주소를 봄
    • 물리적 주소로 바이딩이 될 때 시작 위치는 바뀌지만, 그 안의 코드상의 주소(ex.20,30과 같은 애들)은 바뀌지 않음
    • 따라서 cpu가 메모리 몇 번지를 달라 → 매번 주소 변환을 해서 전달함
• Physical Address
  • 메모리에서 물리적으로 접근할 수 있는 주소
  • 메모리에 실제 올라가는 위치

2. 주소 바인딩

• 프로세스가 실행되기 위해서는 메모리에 프로세스가 올라가야하고, 논리적 주소가 물리적 주소로 바뀌어야 한다.
• Symbolic address → Logical address → Physical address

• Compile time binding
  • 절대 코드 생성(항상 주소가 동일)
  • 메모리에 올리고 싶은 위치를 바꾸고 싶으면 컴파일을 다시 해야 한다.
  • But, 뒤에 주소가 비었음에도 불구하고 0번지부터 주소를 결정하기 때문에 아주 비효율적인 방법
    • 예전에 컴퓨터에서 하나의 프로그램만 실행할 수 있었던 시절에 썼던 방법
• Load time binding
  • 컴파일을 하고 실행이 될 때 물리적인 주소 바인딩
  • 실행될 때마다 주소가 달라질 수 있음
    • 그때그때 비어있는 메모리에 올리기 때문
  • 재배치가능 코드 생성(relocatable code)
• Execution time binding(=Run time binding)
  • 실행 중간에도 바뀔 수 있음
  • 실행을 하는 중에 물리적인 주소 바인딩이 되지만 중간에 바뀔 수 있음
    • 프로세스가 Context Switching이 되는 경우(swapping)
      • CPU가 해당 프로세스의 주소를 참조할 때마다 바인딩을 address mapping table을 이용하여 점검해야 함
      • 하드웨어적인 지원 필요(MMU)

3. MMU (Memory-Management Unit)

• Logical address → Physical address로 매핑해주는 Hardware device
• relocation register(base register)
  • 물리적 메모리의 베이스 주소를 저장
• limit register
  • 프로그램의 최대 크기를 저장
  • 논리적 주소의 최대 범위
  • CPU가 물리적 주소를 요청하면 먼저 limit register 내에 있는지 확인한다.
    • 넘으면 addressing error trap걸어서 종료시킴 (cpu 제어권을 운영체제로 넘기게됨)
• MMU scheme
  • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register의 값을 더한다.
• 사용자 프로그램은 논리적 주소만을 다루고, 물리적 주소는 알 필요가 없다.
  • 주소를 요청하면 MMU가 알아서 바꿔주기 때문

4. 용어

1. Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라, 해당 루틴이 불려질 때 메모리에 load 하는 것
  • 프로그램 중에 예외 처리같은 것들은 거의 실행이 안되기 때문에 이런 부분들은 당장 안올려도 된다.
• memory utilization의 향상
• 운영체제의 특별한 지원 없이, 프로그램 자체에서 구현 가능
  • 프로그래머가 직접, 라이브러리를 이용해서
• 현재 운영체제가 SWAP해주는 페이징 시스템과 용어를 섞어서 사용하기도 함

2. Overlays (Manual Overlay)

• 메모리에 프로세스 중에서 필요한 정보만을 올리는 것
  • Dynamic Loading이랑 뭐가 달라? → 역사!
    • 초창기 컴퓨터의 메모리가 워낙 작다보니 프로그램 하나도 메모리에 못 올리던 시절
    • 프로그래머가 수작업으로 프로그램을 쪼개어서 메모리에 올려서 사용했다.
• 운영체제의 지원이 없고, 라이브러리도 없이
  • 프로그래머가 직접 모든 것을 구현해야 한다.

3. Swapping

• 메모리에 너무 많은 프로세스가 올라와 있으면 시스템은 비효율적이어진다. ⇒ Swapping
• 프로세스를 일시적으로 메모리에서 backing store(하드디스크)로 쫓아내는 것
  • backing store(swap area) : 많은 프로세스를 담을만큼 충분히 빠르고 큰 저장 공간
• Swap in/Swap out
  • 중기 스케줄러가 선정한다.
  • Priority-based CPU scheduling algorithm
    • cpu 우선순위가 낮은 애를 swap out
    • cpu 우선순위가 높은 애를 메모리에 올리기
• Run-time binidng에서 사용
  • 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • (compile time, load time binding에는 원래 메모리 위치로 swap-in 해야 하므로 맞지 않음)
    • ex) 500번지였으면 500번지로 올라와야함
• swap time
  • 대부분 transfer time(swap하는 양과 비례)
  • 용량이 방대하기 때문에 seek time < transfer time
    • 원래는 디스크 옮길 때 seektime 이 더 큼

4. Static Linking

• Linking : 여러 군데 존재하는 목적 파일들을 묶어서 하나의 실행 파일을 만드는 과정
• 링킹을 하면 라이브러리가 프로그램 실행 파일에 포함되고, → 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스 메모리에 전부 올리기 때문에 → 메모리 낭비
  • ex) iostream, stdio.h, printf

5. Dynamic Linking

• Linking을 실행시간까지 미루는 기법
  • 라이브러리가 실행 시 연결됨(link)
• 파일 자체에는 라이브러리를 포함시키지 않고, 라이브러리가 필요할 때 메모리에 올림
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
    • 메모리에 이미 해당 라이브러리가 있다면 → 그 루틴 주소로
    • 없다면 → 디스크에서 읽어옴
• 운영체제의 도움 필요
• shared library : Dynamic linking을 해주는 라이브러리

2. Physical Memory

물리적인 메모리를 우리는 어떻게 관리할 것 인가??

• 메모리
  • 낮은 주소 : 운영체제 커널 상주
  • 높은 주소 : 사용자 프로세스 영역

1. Fragment

• External Fragmentation(외부조각)
  • 올리려는 프로그램보다 비어있는 partition이 작아서 사용을 못한 것
• Internal Fragmentation(내부조각)
  • partition 크기보다 프로그램의 크기가 작아서 사용이 안된 부분

2. Contiguous allocation

1. Fixed Partition allocation (고정분할방식)

: 물리적 메모리를 미리 파티션을 나눠 놓는다.

• 융통성 없는 방식
  • 외부조각, 내부조각 발생

2. Variable Partition allocation (가변분할방식)

: 미리 나눠놓지 않고, 프로그램의 크기를 고려해서 할당한다.

• 분할의 크기, 개수가 동적으로 변한다.
• 실행될 때마다 차곡차곡 올림
• But, 프로그램이 끝나서 release됐을 때
  • 외부조각이 발생할 수 있다.
• Hole
  • 가용 메모리 공간
  • 운영체제는 할당 공간, 가용 메모리 공간(Hole) 정보를 가지고 있어야 한다.
• Dynamic Storage-Allocation Problem
  • 지금 실행중인 프로그램 size n인데, 어떤 hole에 넣어야 할까?
    • First-fit
      • 맨 처음 본 것
    • Best-fit
      • size가 n이상인 것 중에서 가장 작은 hole
      • 전체를 다 탐색해야 함
      • 아주 많은 수의 작은 Hole들이 생성됨
    • worst - fit
      • 가장 큰 hole에 할당
      • 전체를 다 탐색해야 함
      • 상대적으로 아주 큰 hole들이 생성됨
• Compaction
  • 외부단편화를 막기 위해 메모리를 한군데로 몰고, 큰 block을 만드는 것
  • 단점
    • Cost가 크다
    • Run time binding일 때만 사용 가능하다.

3. Noncontiguous allocation

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

3-1. Paging

1. paging

• 프로그램을 구성하는 주소 공간을 같은 크기의 page로 잘라서 물리적 메모리에 올리는 것
  • 일부는 physical memory에, 일부는 bacing store에 저장 가능
• 물리적 공간도 page크기로 미리 잘라 놓는다. (=page frame)
  • 보통 page크기는 4KB
  • 외부 단편화 문제가 해결된다.
    • 내부 단편화는 존재(프로세스의 크기가 반드시 페이지 크기의 배수가 된다는 보장이 없기 때문)

• Page Table을 사용한 주소 변환
  • <p,d>
    • p : 페이지번호 → f : frame번호
    • d : offset
• 용어
  • Page Hit : 메모리에 올라와 있는 경우
  • Page Fault : 메모리에 안올라와 있는 경우
• 장점
  • 단편화가 발생하지 않는다.
  • 페이지 공유가 가능하다.
  • 페이지 보호도 가능하다.
• 단점
  • 주소 변환이 복잡해진다. (address binding)
    • 오버헤드 발생
    • 속도 저하 → TLB로 속도 저하 방지
    • 페이지 테이블 용량 → 페이지 테이블 구조 개선(다단계 구성 등)

메모리 보호

• Valid-invalid bit
  • Valid : 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함
  • invalid : 해당 주소의 frame에 유효한 내용이 없음을 뜻함 → Trap을 이용한 오류 처리
• Read-only bit
  • 읽기 전용에 쓰기 막음
• Dirty bit
  • 프레임의 변경 여부 확인

2. TLB(Translation lookaside buffer)

• Page table은 물리적 메모리에 존재한다.
  • 한 프로세스를 구성하는 4KB의 페이지들의 page table entry
    • 32bit 컴퓨터라면 2^32 / 2^12 = 2^20 → 총 2^20 = 1MB*4byte(숫자크기) = 4MB의 크기를 차지
  • 그리고 모든 프로세스마다 page table entry가 존재하기 때문
  • MMU에 저장 하면 좋지만, 그렇게 되면 대빵 비싸짐
• 따라서, 메모리 1번을 접근하기 위해 메모리를 2번 접근해야 한다.
  • page table 접근 한 번, 실제 data 접근 한 번
  • 추가록, PTBR 레지스터 접근도 필요함 (페이지 테이블 시작 주소를 알아야 하기 때문)
• ⇒ Cache메모리를 사용하자!
  • 대부분의 프로그램은 2^20개의 페이지 테이블을 다 사용하는게 당근 아님
  • ex) 메모장 27KB인데, page 7개면 사실 충분
  • Locality(지역성)
    • 자주 쓰이는 애만 쓰인다.
• ⇒ TLB
  • Page table의 캐시 메모리

• 빈번히 사용되는 entry를 캐싱하고 있다.
• <p,f>
  • p : page number
  • f : frame number
• Parallel Search(병렬 탐색)
  • TLB에 존재하는지 보려면 전체를 다 탐색해봐야 한다. → 느림
  • 따라서 병렬 탐색으로 스피디하게 고고
    • cf) page table은 MMU 연산에 의해 hashSet처럼 O(1)시간으로 얻을 수 있음
• Context Switching이 되면 flush 해야 한다.
  • 다른 프로세스로 cpu가 넘어가면 page 정보도 달라지기 때문

3. Two-level page table

• 왜 멀쩡한 테이블을 쪼개는거야?
  • 프로세스마다 4MB의 page table을 필요로 하는데 너무 커!
  • 프로그램은 주소 공간 중에 일부 공간만 사용하기 때문에 낭비가 너무 심해!
• 당연히 속도는 동일하다(혹은 더 걸림)

4. Multilevel paging

• 2,3,4...단계로 사용할 수 있음

• TLB를 통해 메모리 접근 시간을 줄이면 다단계를 사용하더라도 오버헤드가 그렇게 많이 커지지는 않음

5. Hashed Page Tables

• 페이지 요청이 오면 hash 함수를 통해 해시값을 추출한다.
  • Hashed page table에서 연결 리스트를 따라가며
    • 첫번째 원소와 page번호를 비교한다.
      • 일치 → 두번째 필드를 가져와 물리적 메모리 get
      • 일치X → 다음 연결리스트로 고고

6. Clustered Page Table

• 해시형 페이지에서는 각 항목들이 한 개의 페이지만 가리키지만
  • 64bit 시스템에서 해시 알고리즘을 변경하여 각 항목들이 여러개의 페이지를 가리킬 수 있게 한다.
  • 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 매핑 정보를 지닐 수 있다.
• 메모리 접근이 불연속적이면서, 전 주소 공간으로 넓게 퍼져 나오는 경우 유용

7. Inverted Page table

• 지금까지 문제 → 페이지 테이블이 많은 공간을 차지함
• 전체 시스템 안에 페이지 테이블이 딱 하나가 존재
  • 페이지 테이블 안에 물리적 메모리의 frame 개수만큼 존재
  • 물리적 → 논리적으로 할 수 있게 inverted
    • 그럼 어떻게 논리적 → 물리적?
    • 페이지번호 p가 페이지 테이블 어디에 있는지 쭉 탐색 → physical 탐색 → frame 겟
      • 병렬적으로 동시에 검색할 수 있게 해서 시간 오버헤드를 줄임

8. Shared page

• Shared Code
  • Read-Only로 해서 프로세스 간에 하나의 코드만 올린다.
• Shared Code는 동일한 Logical address space에 위치해야 한다.
  • 따라서 2개 이상의 프로세스가 같은 코드에서 동시에 실행된다.

3-2. Segmentation

1. segmentation

• 의미 있는 단위로 자르는 기법 (논리적 내용을 기반으로)
  • 크기가 균일하지 않기 때문에 dynamic memory allocation problem같은 것이 발생할 수 있다.
• 장점
  • Protection
    • 어떤 부분은 read/write/execution 권한 bit를 따로 줄 수 있다.
  • sharing
    • 의미 단위이기 때문에 섞이지 않고 효율적으로 공유가 가능하다.
    • 페이징은 영역이 섞일 수 있음
• ex) code, data, stack을 잘라서 올림 / 함수별로 올림
• Paged Segmentation
  • <segment-number, offset>
  • segment table을 가지고 있음 (base, limit)
    • limit → 크기가 균일하지 않기 때문에 limit이 존재한다.
  • STBR : 물리적 메모리에서의 segment table 위치
    • 테이블도 물리적 메모리의 어딘가에 위치할거니까
  • STLR : 프로그램이 사용하는 segment의 수
• 
• 테이블을 위한 메모리 낭비는 페이징 > 세그멘테이션 이다. (보통 페이징은 작은 단위로 페이지를 나누기 때문)
• BUT, 요즘은 페이징을 주로 사용한다.
  • 세그먼트 크기가 일정하지 않고 다양해서 외부 단편화가 발생해 메모리 낭비가 발생하기 때문

2. Sharing of segments

• segment를 공유하기 위해서는 같은 논리 주소를 가져야 한다.
  • Segment 번호가 같아야 함

3. Paged Segmentation

• 페이징과 세그먼테이션 혼합
  • Segment 하나가 여러 개의 page로 구성된다.
    • 하나의 Segment가 하나의 page table을 갖는다.
  • 장점
    • 메모리에 올라갈 때는 페이지 단위로 쪼개져서 올라가기 때문에 Allocation 문제가 발생하지 않는다.
    • Sharing/Protection과 같은 의미 단위의 작업 수행 시 Segment Table의 entry에서 그 처리를 한다.

• • •