[운영체제]메모리관리

메모리 관리

필요한 이유 : 프로그램을 메모리에 적재하는 과정 중 공간이 낭비되거나 메모리가 가득 차서 부족해지는 상황이 발생할 수 있다. 그렇기 때문에 메모리를 효율적으로 사용하기 위해 메모리 관리는 필수적이다.

 

논리적 주소(가상 주소)

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0 번지부터 시작
• CPU가 보는 주소는 logical address임

물리적 주소

• 메모리에 실제 올라가는 위치

주소 바인딩 : 주소를 결정하는 것

Symbolic Address->logicial Address-> Physical address

Symbolic Address:프로그래머 입장에서의 주소(숫자가 아닌 상징성 있는 주소를 사용한다)-> int a=8과 같은 것들

물리적인 메모리에 주소가 결정되는 것 -> 주소 바인딩 

Compile time binding

- 컴파일되는 시점에 결정되어지는 것.

- 지금은 주로 사용되어지지 않음

- Logical 이 그대로 사용됨 

- 컴파일하면서 생기기 때문에 절대 코드라고 불립니다.

- 주소를 바꾸고 싶다면 컴파일을 다시 해야 변환이 가능합니다.

Load time binding

- 프로그램이 시작되어 메모리에 올라갈 때 결정되어지는 것

- 물리적인 메모리 빈 곳부터 차근차근 들어가는 개념

 

Run time binding

- 실행 시에 주소가 결정되어지는 것은 Load time binding과 똑같음

- 실행 중에 물리적 메모리가 변경되어질 수도 있는 게 특징★★

 - 대부분이 Run time binding을 사용 

 

CPU가 바라보는 주소는 Logical address입니다.

올라가는 위치는 500번지 인지 300번지 인지는 계속 바뀌게 되지만 (메모리의 시작 위치는 변경되지만)

컴파일하면서 코드 상의 주소(Add 20, 30)는 Logical address에 남겨지게 됩니다.

그러면서 CPU는 실행을 하게 될 때 Loadtime binding 기준 500번지를 보는 것이 아니라 Logical address인 Add 20번지 30번지를 보게 됩니다.

 

Memory Management Unit(MMU주소변환을 위한 하드웨어)

- logical address를 physical address로 매핑해 주는 하드웨어 서비스

- 주로 register(limit, relocation) 두 개를 활용하여 변환

CPU가 메모리 346번지 내용을 달라고 하면 주소변환이 필요한데 주소변환을 해주는 것이 MMU를 통해 한다(relocation, limit regisgister를 통해)

relocation에 시작 위치를 저장하고

limit register는 악의적인 의도(남의 프로그램을 보려는)를 가지고 다른 프로그램을 실행하려고 하는 것을 방지.

limit은 프로그램의 크기가 정해져 있는데 그 이상을 보려고 한다면 제지시키는 역할.

Dynamic Loading

동적으로 올린다.(Loading:메모리 롤 올리는 것)

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load 하는 것
• 가끔씩 사용되는 많은 양의 코드의 경우 유용
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능

OS라이브러리를 통해 지원 가능합니다.

Overlay(다이나믹과 구분하여야 함)

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
• 초창기 메모리가 너무 작아 프로그램 전체를 못 올리고 필요한 부분만 올리는 것.

프로그래머가 수작업으로 처리 운영체제의 지원이 없음

Swapping

• Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
• Backing store(swap area) : 디스크, 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간
• Swap in/ Swap out
  • 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스 선정
  • priority-based CPU scheduling algorithm: 우선순위 낮은 프로세스 swap out, 높은 프로세스 swap in
  • Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 함(비효율적)
  • Run time binding에서는 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • swap time은 대부분 transfer time(swap 되는 양에 비례하는 시간) 임

Dynamic Linking

• Linking: 컴파일된 파일들을 하나로 묶는 작업 (ex. 라이브러리)
• Linking을 실행 시간까지 미루는 기법
• Static Linking
  • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
  • 실행 파일의 크기가 커짐
  • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비
• Dynamic Linking
  • 라이브러리가 실행시 연결됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴(Shared library)
  • 운영체제의 도움이 필요
  • 실행파일에 만들어질 때 라이브러리가 포함되지 않고 만들어지고, 라이브러리의 위치를 찾을 수 있는 코드(stub)만 남겨두어 실행하게 하는 개념

프로그램 안에 라이브러리가 포함 (프로그램 주소 안에서 실행)-> static 

별도의 라이브러리를 위치를 가지고 실행 -> Dynamic 

Allocation of Physical Memory

• 메모리는 일반적으로 두 영역으로 나뉘어 사용
  • OS 상주 영역(커널)
    • interrupt vector와 함께 낮은 주소 영역 사용
  • 사용자 프로세스 영역
    • 높은 주소 영역 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation(연속 할당)
    • 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
      • Fixed partition allocation
      • 융통성이 없음
      • Variable partition allocation
        • 외부 조각의 발생
  • NonContiguous allocation
    • 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
      • Paging
      • Segmentation
      • Paged Segmetation

연속 할당

연속 할당도 두 가지 방식으로 분리가 됩니다.

프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나누어 놓는 개념입니다.

가변 분할은 고정 분할과 반대입니다.

고정 분할에서의 외부 조각과 내부 조각

외부 조각:프로그램을 올리려는데 올리려는 프로그램보다 크기가 작은 조각

내부 조각:프로그램 B를 올려놨지만 사용하고도 남은 조각입니다.

가변 분할 방식

내부 조각을 없애기 위해 생겨난 방식 

프로그램의 크기에 맞게 분할하는 방식 

위의 사진에서 프로그램 B를 사용하고 끝나고 남는 조각 자리(외부 조각이 됨)

Dynamic Storage Allocation Problem

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

당연히 worst-fit이 제일 안 좋다.

불연속 할당

실제로 불연속 할당을 주로 사용한다.

크게 페이징과 세그멘테이션 기법으로 나눕니다.

페이징: 페이지를 같은 크기로 자르는 것(Hole 이런 문제는 발생 하진 않음)

세그멘테이션 기법: 의미 있는 단위로 자르는 것(크기가 균일하진 않음)

 

 

Paging

연속 할당의 경우 register를 통해 간단하게 주소 변환을 하였는데

페이징 경우 프로세스에서 페이지별로 나누어진 상태로 물리적 메모리에 올라가게 되는데 이경우는 간단하게 주소 변환을 하기가 어려워지는 상황이 발생합니다. 단순히 시작 위치만을 가지고 주소변환을 하기가 어렵습니다.

그리하여 page table을 활용하여 인덱스를 얻어 물리적 메모리에서의 값을 얻을 수 있습니다.

 

Page table은 main memory에 상주

page table 접근 1번, 실제  data/instruction 접근 1번 총 두 번의 메모리의 접근이 필요합니다.

상당한 비용이 발생하게 됩니다.

별도의 하드웨어인 TLB(translation look-aside buffer) 일종의 캐시를 사용하여(메인 메모리와 CPU사이에 존재) 비용 절감과 속도 향상을 위해 사용합니다.

TLB

주소변환을 위한 별도의 캐시 메모리 -> TLB(page number, frame number를 둘 다 가지고 있음)

page table에서 빈번하게 참조되는 일부 엔트리를 캐시를 하고 있습니다.

CPU가 논리 주소를 주게 되면 TLB먼저 검색하여 원하는 정보가 있는지 검색을 하게 됩니다. 이미 저장되어있다면 TLB를 통해 물리적 주소까지 알게 되어 1번의 접근으로 Data를 얻을 수 있습니다.

하지만 TLB는 모든 정보를 가지고 있는 것이 아니라 빈번하게 발생되는 것들만 가지고 있습니다.

그리하여 TLB에 검색해도 없다면 page table을 탐색하게 됩니다.

TLB의 경우 page table의 중 일부만 존재하기 때문에 병렬 검색을 수행합니다.

TLB의 정보는 만약 문맥 교환이 발생하게 된다면 모든 엔트리를 제거해야 합니다.(프로세스마다 주소 정보가 다르기 때문에)

 

Two-Level Page Table

2단계의 page-table을 거쳐 메모리 주소를 얻어오는 단계

이것을 사용하는 이유는 page table을 위한 공간 확보가 목적입니다.

 

32bit address를 사용 시에는 2의 32승 B (4GB)의 주소 공간 

page size가 보통 4KB로 가정 1M 개의 page table entry가 필요

각 page table의 entry크기가 보통 4B로 가정하는데 프로세스당 4M의 page table이 필요합니다.

그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨

code data stack이 있다고 가정하였을 때 code와 data는 초반 부분에 stack은 page의 마지막에 있을 때 중간 부분은 사용하지 않게 됩니다. 하지만 page table의 경우 중간을 사용하지 않는다고 하여 중간을 안 만들 순 없어, 상당 부분이 낭비하게 되는 현상이 발생하게 됩니다. 이러한 비용들을 절감하기 위해 2단계 페이지 테이블을 사용합니다.

다단계 페이징 기법(Multilevel paging)

• TLB를 통해 메모리 접근 시간을 줄일 수 있음
• TLB를 통하지 않는다면 상당히 비효율 적이지만 TLB를 활용한다면 효율적입니다.
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근 시간이 100ns, TLB접근 시간이 20ns이고
  • TLB hit ration가 98%인 경우
    • effective memory access time= 0.98x120+0.02x 520=128nanoseconds
    • 28ns만 소요 이렇다면 크게 오버헤드가 발생하지 않는다.

Inverted Page Table

• page table의 가장 큰 문제는 너무 큰 공간을 가지고 있는다.
• 물리적 주소를 통해 논리적 주소를 알아내는 방법?(논리적 메모리의 개수만큼 이 아니라 물리적 메모리 개수만큼 존재)
• 일일이 전부 확인해야 한다.
• 이러한 Page Table의 궁극적인 목적은 공간을 줄이고자 가 목적.
• 시간적 오버헤드가 큼. (극복하기 위해 병렬적 탐색을 가능하게 구현)

Segmentation

프로그램을 의미 단위로 나누는 것(code, data, stack)

• 프로그램은 의미 단위인 여러 개의 segment로 구성
  • 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
  • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
• Segment-table base register(STBR)
  • 물리적 메모리에서의 segment table의 위치
• Segment-table length register(STLR)
  • 프로그램이 사용하는 segment의 수

Logical address는 < segment-number, offset>으로 구성

CPU가 논리 주소를 준다면 논리 번호와 주소로 나눕니다.

limit(세그먼트의 길이)은 세그먼트는 길이가 다 다르기 때문에 limit도 나타내야 합니다.

의미단위로 자르기 때문에 길이가 다를 수 있다.

체크사항 2가지

• 세그먼트 번호가 STLR보다 크다면 트랩에 걸리게 된다.
• 주소 변환을 하는데 limit보다 offset이 크다면 트랩에 걸리게 되다.

segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적이다.

단점은 동일한 크기가 아니기 때문에 holl과 빈 공간이 나타날 수 있다.

 

세그먼트의 예시

위의 예시를 들어 설명을 하자면

segment 0의 경우 base는 1400이고 limit이 1000 임으로 1400 + 1000을 한 2400까지 메모리를 차지하고 있습니다.

 

Shared Segment(같은 논리적인 주소상에 있어야 한다 세그먼트 번호가 같아야 함)

editor는 공유하고 data1,2는 프라이빗으로 개인적으로 처리한 그림.

Paged Segmentation

올라갈 때는 페이지 단위로 올라가고, table은 segment로 관리

holl과 같은 공간 소비는 없어짐