[운영체제] 메모리 관리

주소 바인딩

• 논리적 주소 = 가상 주소 : 프로세스의 주소공간
  • 가상 메모리 : 메모리 관리 기법. 컴퓨터가 실제 이용가능한 메모리자원을 추상화하여 매우 큰 메모리로 보이게 만드는것
• 물리적 주소 : 물리적 메모리에 실제로 올라가는 위치

cpu가 기계어를 수행하기 위해 논리적(가상) 주소를 통해 물리적 메모리의 어느 위치에 있는 지 확인해야함. 이렇게 논리적 주소를 물리적 주소로 연결해주는 작업을 주소바인딩이라고함.

1) 컴파일 타임 바인딩 : 프로그램을 컴파일 할 때 물리적 메모리 주소가 결정되는 방식

• 물리적 메모리가 컴파일 시 알려짐
• 시작 위치 변경 시 재컴파일
• 절대주소로 적재된다는 뜻에서 절대코드를 생성하는 바인딩 방식
• 비현실적이고 현대의 시분할 컴퓨팅 환경에선 잘 사용안함

2) 로드 타임 바인딩 : 프로그램의 실행이 시작될 때 물리적 메모리 주소가 결정되는 방식

• Loader(사용자 프로그램을 메모리에 적재시키는 프로그램)의 책임 하에 물리적 메모리 주소 부여
• 프로그램이 종료될때까지 물리적 메모리 상의 위치 고정
• 컴파일러가 재배치 가능 코드를 생성한 경우에 가능

3) 실행 시간(런타임) 바인딩 : 프로그램 실행 도중에도 물리적 메모리상의 주소가 변경될 수 있는 방식

• cpu가 주소를 참조할 때마다 물리적 메모리의 어느 위치에 존재하는 지 주소 매핑 테이블로 확인
• 하드웨어 자원 필요 → , 재배치 레지스터(=기준 레지스터), 한계 레지스터, MMU
• 재배치 레지스터(= 기준 레지스터) : 접근할 수 있는 물리적 메모리 주소의 최소값. → 논리적 주소 + 재배치 레지스터 값 = 물리적 메모리 시작 주소
• 한계 레지스터 : 프로세스의 논리적 주소의 범위(= 프로세스 크기). 프로세스가 자신의 주소 공간을 넘어서는 메모리 참조를 하려고 하는지 체크하는 용도
• 메모리 관리 장치(MMU) : 가상 주소를 실제 물리적 주소로 변환시켜줌 → 사용자 프로그램이나 cpu는 실제 물리적 주소는 알지 못하고 알 필요없음
• 페이지 테이블 : 가상 주소와 실제주소가 매핑되어 잇고, 프로세스 주소 정보가 들어있음
  • TLB : 메모리와 cpu 사이에 있는 주소변환을 위한 캐시. 페이지 테이블에 있는 리스트를 보관하며 cpu가 페이지 테이블까지 가지 않도록 속도 향상 시켜주는 캐시계층.

 

스와핑(swapping)

메모리에 올라온 프로세스의 주소공간 전체를 디스크의 스왑 영역에 일시적으로 내려놓는 것

• 스왑 영역 : 디스크 내 파일 시스템과는 별도로 존재하는 일정 영역(휘발성 공간)

특정 이유로 수행중인 프로세스 주소공간을 일시적으로 메모리에서 디스크로 내려놓는 것 (프로세스가 종료되어 그 주소 공간을 디스크로 내려놓는 게 아님.)

• 스왑 인 : 디스크 → 메모리
  • 컴파일 타임 바인딩이나 로드 타임 바인딩에서는 스왑 아웃된 프로세스가 다시 스왑인될때는 원래 메모리 위치로 스왑 인 해야함
  • 실행 타임 바인딩에서는 추후 빈 메모리 영역 아무곳에나 올릴 수 있음
• 스왑 아웃 : 메모리 → 디스크 (suspend 상태가됨)

스와핑을 통해 다중 프로그래밍 정도 조절(프로세스 수 조절)

어떤 프로그램을 사용하고자 하는데 그에 대한 메모리 공간이 충분치 않을 경우, 메모리 내에 이미 존재하는 프로세스를 통째로 스왑 영역으로 내쫓아(스왑 아웃) 공간 확보 후, 사용하고자하는 프로그램을 스왑 인

스와퍼라고 불리는 중기 스케줄러에 의해 스왑 아웃 시킬 프로세스 선정

스와핑에 소요되는 시간은 디스크의 탐색 시간이나 회전지연 시간보다는 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송시간(transfer time)이 대부분 차지

 

페이지 폴트(page fault)

가상메모리에는 존재하지만 실제 메모리인 램에는 없는 데이터에 접근했을 경우 발생

valid/invalid 비트를 사용 (사용되지 않는 주소영역이거나 페이지가 물리적 메모리에 없을 경우에는 페이지 테이블에 invalid bit로 설정되어있음)

1. invalid 페이지를 접근하면 MMU가 페이지에 부재 트랩을 발생시킨다.
2. cpu 제어권이 커널모드로 전환된 후, 페이지 부재 처리루틴 호출
3. 페이지가 적법한지를 먼저 확인. 사용되지 않는 주소 영역에 속한 페이지에 접근하려했거나 해당 페이지에 대한 접근 권한 위반을 했을 경우 프로세스 종료.
4. 적법한 경우는 물리적 메모리에서 비어 있는 프레임을 할당받아 그 공간에 해당 페이지를 읽어옴.
5. 비어 있는 프레임이 없으면 프로세스 하나를 스왑 아웃.
6. 디스크로부터 메모리로 적재. 페이지 테이블 최신화(이 떄, 페이지 부재를 발생시킨 프로세스는 cpu를 빼앗기고 봉쇄 상태임)
7. 페이지 테이블 엔트리 기록, valid/invalid 비트를 valid로 변환
8. ready 큐에 프로세스를 넣고, 나중에 dispatch
9. 이 프로세스가 cpu를 선점하고 다시 실행

• 페이지 : 가상 메모리를 사용하는 최소크기 단위
• 프레임 : 실제 메모리를 사용하는 최소 크기 단위

 

스레싱(thrashing)

스레싱은 페이지 폴트율이 높은 것을 의미 → 성능 저하 초래

요구 페이징 기법의 성능에 가장 큰 영향을 미치는 요소는 페이지 폴트(부재) 발생 빈도 (디스크 → 메모리가 막대한 오버헤드 발생하기 때문)

cpu 이용률이 낮아지게 되면 운영체제는 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올리게되며 악순환 발생 → 스레싱 발생

해결하려면 메모리를 늘리거나, HDD → SSD 변경

운영체제의 해결방법 : 작업 세트, PFF

• 작업 세트(working set) : 과거 사용 이력인 지역성으로 결정된 페이지 집합을 만들어 미리 메모리에 로드
• PFF(Page Fault Frequency) : 페이지 폴트 빈도를 조절하는 방법으로 상한선과 하한선을 만들어, 상한선에 도달한다면 프레임을 늘리고, 하한선에 도달하면 프레임을 줄이는 것

 

물리적 메모리 할당 방식

물리적 메모리의 낮은 주소 영역은 운영체제 및 커널, 높은 주소 영역은 사용자 프로세스

사용자 프로세스 영역의 관리 방법은 두가지

1) 연속 할당

메모리에 연속적으로 공간을 할당하는 것. 물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스가 적재되도록함

분할 관리 방식

• 고정 분할 방식
  • 고정된 크기의 분할로 미리 나누어두는 방식 (분할의 크기는 모두 동일하게 할 수도 있고 서로 다르게 할 수도있음)
  • 하나의 분할에는 하나의 프로그램만 적재 가능하여, 동시에 메모리에 올ㄹ릴 수 있는 프로그램 수가 고정 되어있음 → 융통성이 떨어짐
  • 외부 단편화 : 프로그램 크기 > 분할의 크기. 분할이 비어있어도 적재를 못하는 공간
  • 내부 단편화 : 프로그램 크기 < 분할의 크기. 적재는 가능하나 메모리 공간이 남아 메모리가 낭비됨
• 가변 분할 방식
  • 미리 나누어놓지 않고 프로그램이 실행되고 종료되는 순서에 따라 분할을 관리하는 방식
  • 내부 단편화 발생 x : 프로그램 크기를 고려해서 동적으로 메모리 할당
  • 외부 단편화 : 메모리에 이미 있는 프로그램이 종료되어 빈 공간 발생했는데, 새로운 프로그램 크기보다 작으면 발생
  • 동적 메모리 할당 문제 : 프로세스를 메모리 내 가용공간 중 어디에 올릴 지 결정하는 문제
    • 최초적합(first-fit) : 위쪽이나 아래쪽부터 시작해서 홀을 찾으면 바로 할당. (시간적 측면에서 효율적)
    • 최적적합(best-fit) : 프로세스 크기 이상의 공간 중에 가장 작은 공간에 할당. (시간 오버헤드, 공간적 측면에서 효율적)
    • 최악적합(worst-fit) : 가용 공간 중에 가장 크기가 큰 곳에 할당 (시간 오버헤드, 공간 비효율적)

2) 불연속 할당

하나의 프로세스를 물리적 메모리의 여러 영역에 분산해 적재하는 방식

분할 기준 방식

• 페이징 기법 (현대 운영체제가 사용)
  • 프로세스 주소공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른위치에 페이지들을 저장하는 방식
  • 물리적 메모리도 페이지와 동일한 크기의 프레임으로 나누어두기 때문에 빈 프레임 있으면 아무곳이나 할당 가능 → 동적 메모리 할당 문제 발생 X
  • 주소 변환이 복잡 → 모든 프로세스가 각각의 페이지 별 주소 변환을 위한 페이지 테이블 가짐
  • 외부 단편화 x, 프로그램 크기가 항상 페이지 크기의 배수가 된다는 보장이 없어 주소 공간 중 마지막에 위치한 페이지에서는 내부 단편화 발생 가능성 있음
• 세그멘테이션(segmentation)
  • 페이지 단위가 아닌 의미 단위로 분할. 코드, 데이터, 스택, 힙 영역 등의 기능 단위로 나누거나 함수 하나하나를 각각 나누기도 함. → 크기가 균일하지 않음
  • 세그먼트 테이블 사용 : 각 항목은 기준점(세그먼트 위치 정보)과 한계점(세그먼트 길이)을 가지고 있음
  • 공유와 보안 측면에서 강점을 가지고 있음. 의미 단위이기 때문
    • 페이징 기법 같은 경우에는 페이지를 동일한 크기로 나누기 때문에, 공유 코드와 private한 데이터가 한 페이지에 섞일 수 있는 문제가 있음.
  • 세그먼트의 길이가 일정하지 않아 외부단편화 발생, 동적 메모리 할당 문제 발생.(최초 적합 방식, 최적 적합 방식)
• 페이지드 세그멘테이션(paged segmentation)
  • 세그먼트가 동일한 크기 페이지의 집합으로 구성되어 페이지 크기의 배수가 됨, 물리적 메모리에 적재하는 단위는 페이지 단위.
  • 페이징 기법의 장점(동일한 크기의 페이지) + 세그멘테이션의 장점(의미 단위로 분할)
  • 페이징 약점 해결(공유나 보안) + 세그멘테이션 약점 해결(외부 단편화 해결)
  • 주소 변환을 위한 외부 세그멘트 테이블과 내부의 페이지 테이블 (하나의 세그먼트가 여러개의 페이지로 구성되므로 각 세그먼트마다 페이지 테이블을 가짐)

💡 공유 페이지란?
공유 코드는 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드.
재진입 가능 코드나 순수 코드라고도 불리고 read-only 다.
이런 공유코드를 가지고 있는 페이지가 공유페이지.
공유페이지는 물리적 메모리에 하나만 적재되어 메모리를 좀더 효율적으로 사용할 수 있게함.
이는 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 존재해야함
반대의 의미는 private 페이지로 각자의 데이터를 말한다.

 

페이지 교체 알고리즘

메모리는 한정되어 있어 스와핑이 많이 일어남. 일어나는 기준이 페이지 교체 알고리즘

페이지 폴트율을 최소화하는 것이 목표

 

1) 오프라인 알고리즘 (최적의 알고리즘)

가장 먼 미래에 참조될 페이지를 삭제. 즉, 가장 최적의 알고리즘.

빌레디의 최적 알고리즘이라고 하고, 미래에 어떤 페이지가 어떤 순서로 참조될지 미리 알수 없어서 실제로는 사용못하는 알고리즘

 

2) FIFO (First In First Out)

가장 먼저 온 페에지를 교체 영역에 가장 먼저 놓음

 

3) LRU (가장 오래전에 참조된 페이지 삭제)

시간 지역성 이용. (최근에 참조된게 또 참조될 가능성이 높다)

현재 시점을 기준으로 가장 오래전에 사용된 참조 페이지를 삭제한다.

→ 오래전에 사용된 페이지는 미래에 다시 사용안될 가능성이 높다고 판단

구현 : 링크드리스트로 O(1)의 시간복잡도

 

4) NUR (Not Used Recently)

Clock 알고리즘. LRU에서 발전한 알고리즘.

하드웨어 자원을 사용하여 LRU, LFU에서 생기는 알고리즘의 운영 오버헤드를 줄임

프레임마다 0과 1을 가진 참조 비트를 둠. 0은 최근에 참조되지 않은것, 1은 최근에 참조된것.

시계방향으로 돌면서 참조 비트가 1인 경우는 0으로 바꾸고 지나가고, 0인 경우는 교체하고 해당 부분을 1로 바꿈 → 즉, 최근에 참조되지 않은 페이지를 교체하는 것

 

5) LFU (참조횟수가 가장 적은 페이지 삭제)

현재 시점을 기준으로 가장 적게 참조된 페이지를 삭제한다.

→ 인기가 없는 페이지는 미래에 다시 사용안될 가능성이 높다고 판단

구현 : 힙으로 구현하여 O(logN)의 시간복잡도