티스토리 뷰

알고리즘 공부

[운영체제] 메모리

itsmekyum 2024. 2. 20. 13:14

연속 메모리 할당

 메모리에는 다양한 프로그램도 올라가지만 OS도 올라간다. 그래서 메모리는 OS를 위한 파티션과 프로그램을 위한 파티션이 존재한다. 이전 게시물에서 설명했듯이 loading time binding에서 MMU를 활용해 물리적 주소를 논리적 주소처럼 연속적으로 메모리를 할당하는 것을 가능하게 했다. 또한 MMU에는 메모리 보호 기능도 있어서, 메모리 가용 범위를 넘어가지 않도록 해준다. 하지만, MMU를 통해 연속 메모리를 할당하는 것은 외부 단편화가 발생 할 수도 있다는 단점이 있다. 

단편화(Fregmentation)

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할만큼의 작은 자유 공간들이 늘어나게 되는데 이를 단편화라고 한다

외부 단편화

MMU를 통한 연속 메모리 할당은 메모리 주소를 연속적으로 사용하기에 하나의 프로세스를 두개로 분할해서 올리는 것이 불가능하다.

그리고 메모리에는 수많은 프로그램들이 실행되고 종료되면서 새로운 프로세스가 들어가야되지만 메모리에 공간이 없는 경우가 있을 수 있다.

 

메모리에 있는 가용공간을 hole이라고 한다. 프로세스가 진행되는 도중 1과 5가 종료가 됐다고 하면, hole은 생겼지만, 충분한 공간이 나오지 않기 때문에 6이 들어갈 하나의 공간은 부족하다. 즉, 외부 단편화란 메모리 공간 중 사용하지 못하게 되는 일부분이다. 물리 메모리(RAM)에서 사이사이 남는 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을 때 발생한다.

 

해결방법

  • 압축(compaction) : 메모리의 모든 내용을 한군데로 몰고 모든 자유 공간들을 다른 한 군데로 몰아 클 블록으로 만드는 것
    • 재배치가 정적으로 이루어진다면 불가능. 동적으로 재배치가 가능한 경우에만 사용 가능
    • 압축 작업 중 시스템은 다른 작업을 할 수 없다
  • 통합(Coalescing) : 인접한 단편화 영역을 하나의 영역으로 통합하는 작업

내부 단편화

프로세스가 사용하는 공간에 포함된 남는 부분

예) 메모장을 켰는데 4KB만큼 할당해 주었지만 실제 1KB만 사용하고 있을 때 필요 이상으로 메모리를 할당받아 내부 단편화가 3KB만큼 발생

페이징(Paging)

가상 메모리를 사용. 외부 단편화를 해결

  • 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 기법
  • 외부 단편화를 방지하고 압축 작업을 불필요하게 함
  • 보조 기억장치를 이용한 가상 메모리(논리 메모리)를 같은 크기의 블록으로 나눈 것(페이지), RAM(물리 메모리)을 페이지와 같은 크기로 나눈 것(프레임)
  • 사용하지 않는 프레임을 페이지에 옮기고 필요한 메모리를 페이지 단위로 프레임에 옮기는 기법
  • 페이지와 프레임을 대응시키기 위해 page mapping 과정이 필요해 paging table을 만든다
  • 페이징 기법을 사용하면 연속적이지 않은 공간도 활용할 수 있어 외부 단편화 문제를 해결 가능
  • 코드가 reentrant code라면 공유가 가능(Shared Page)

 

 이 페이징 테이블을 본다면, P1프로세스의 0번째 페이지가 메인메모리의 5번째 프레임에 있다는 것을 알 수 있다.

 

단점 : 내부 단편화 문제의 비중이 증가

페이지를 너무 작게하면 내부 단편화 문제를 해결할 수 있지만 page mapping table이 많아져 효율이 감소

세그멘테이션(Segmentation)

가상 메모리 사용, 내부 단편화 해결, 외부 단편화 존재

  • 페이징에서 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌 서로 다른 크기의 논리적 단위(Segment)로 분할
    • main, function, method, object 등 인간적인 관점으로 나누는 것
  • 연속적인 공간에 저장되어 있다
  • 세그먼트 테이블에는 각 세그먼트 별 세그먼트 시작주소와 세그먼트 길이정보를 가지고 있다

단점 : 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 작은 조각들로 나누어져 못 쓰게 될 수도 있다(외부 단편화)

 

 


               

가상 메모리

메모리로서 실제 존재하지는 않지만 사용자에게 있어 메모리로서 역할을 하는 메모리

가상 메모리에 수용된 프로그램이 실행될 때에는 실제 메모리를 필요로 하기에,  프로세스들이 연속된 물리적 메모리 공간처럼 여기게 만든다. 필요한 부분만 메모리에 올림으로써 메인 메모리에 올라가는 프로세스의 크기를 줄일 수 있는 기법이다..

 

개발 배경

이전에는 실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 따라서 메모리 용량보다 큰 프로그램은 실행불가

또한, 여러 프로그램을 동시에 메모리에 올리면 용량의 한계와 페이지 교체 등의 성능 이슈가 발생

가끔 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서 불필요하게 전체가 메모리에 올라와 있어야하는게 아님을 알게됨

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려야한다

가상메모리는 프로세스 전체가 메모리 내에 올리지 않더라도 실행 가능하도록 하는 기법

프로그램이 물리 메모리보다 커도 된다는 장점

하는 일

가상 메모리는 실제 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리해, 작은 메모리를 가지고 얼마든지 큰 가상 주소 공간(한 프로세스가 메모리에 저장되는 논리적인 모습을 가상 메모리에 구현한 공간)을 프로그래머에게 제공하는 것이다.

 

ex) 프로그램이 실행되며 논리 메모리로 100kb가 요구되지만 실행까지 필요한 메모리 공간(heap, stack, code, data)의 합이 40kb라면 실제 물리 메모리에는 40kb만 올라가고 나머지 60kb만큼은 필요시 물리 메모리(보조기억장치 등)에 요구

 

가상 메모리 관리

요구 페이징(Demand Paging)

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신 초기에 필요한 것들만 적재하는 전략

가상 메모리 스세템에서 많이 사용되며 가상 메모리는 대게 페이지로 관리

요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재

 

프로세스 내의 개별 페이지들은 페이저(Pager)에 의해 관리

페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어와 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 감소

 

TLB(Translation Look-aside Buffer, 변환 우선 참조 버퍼)

MMU에서 사용하는 특정한 소형 하드웨어 캐시, 일종의 page cache


페이지 테이블은 메인 메모리(주 기억장치)에 저장되기 때문에 메모리를 액세스 할 때마다 물리 기억장치의 주소를 얻기 위해 테이블을 조회와 가상 기억장치에 필요한 데이터를 얻기 위한 접근, 총 두번을 접근해야 하기 때문에 액세스 시간이 길어져 문제를 해결하기 위해 프로세서 내장 캐시인 TLB를 사용한다.즉, 가상 메모리 주소가 한번 물리 주소로 변환되면 TLB에 기록하고 그 다음부턴 MMU가 페이지 테이블을 참조하는 것이 아닌 TLB를 통해 물리 주소를 먼저 찾는다. 이를 통하여 상대적으로 속도가 느린 메모리에 접근하는 횟수를 줄여 성능을 향상 시켜준다.

 

페이지 폴트(Page Fault)

프로그램이 자신의 주소공간에는 존재하지만 시스템의 RAM에는 현재 없는 데이터나 코드에 접근을 시도했을 때 발생하는 현상

프로세스에 필요한 데이터만 적재하기때문에 적재되지 않은 페이지를 요구하는 경우가 발생

 

과정

CPU가 원하는 주소를 MMU에 전송

→ MMU는 주소 변환 과정에서 페이지 테이블(table)에 주소에 대한 항목이 없다고 표시

→ MMU는 CPU를 인터럽트한 후 페이지 폴트 처리기라는 소프트웨어가 실행

→ 페이지 폴트 처리기가 원하는 페이지를 디스크 상 어디에 위치하는지 찾은 후 읽어옴

페이지 교체

프로그램 실행시 모든 항목이 물리 메모리에 올라오지 않기 때문에 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하면 원하는 페이지를 보조 기억장치에서 가져옴

하지만 물리 메모리가 모두 사용중인 상황이라면 페이지 교체가 발생해야 함!

 

기본적인 방법

  1. 디스크에서 필요한 페이지의 위치를 찾는다
  2. 빈 페이지 프레임을 찾는다
    1. 페이지 교체 알고리즘을 통해 희생(victim)될 페이지를 고른다
    2. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정
  3. 새롭게 비워진 페이지 테이블 내 프레임 새 페이지를 읽어오고, 프레임 테이블을 수정
  4. 사용자 프로세스 재시작

FIFO 페이지 교체

First In First Out

가장 간단한 페이지 교체 알고리즘, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 나가게 된다

큐를 만들어 구현이 가능하다

 

장점

  • 이해하기 쉽고, 프로그램하기 쉬움

 

단점

  • 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있음
  • 처음부터 활발하게 사용되는 페이지를 교체해 페이지 부재율을 높이는 부작용 초래
  • Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 페이지 부재가 더 많이 발생하게 되는 모순이 존재

최적 페이지 교체(Optimal Page Replacement, MIN)

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체, 가장 낮은 페이지 부재율을 보장

비교 연구 목적을 위해 사용

 

장점

  • 알고리즘 중 가장 낮은 페이지 부재율을 보장
  • Belady의 모순 현상을 야기하지 않음 ⇒ 스택 알고리즘

 

단점

  • 구현의 어려움
  • 모든 프로세스의 메모리 참조 계획을 파악할 방법 없음

LRU 페이지 교체(Least Recently Used)

최적 알고리즘의 근사 알고리즘. 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체

대체적으로 FIFO보다 우수하고 OPT보다는 그렇지 않은 모습

Belady의 모순 현상을 야기하지 않음(스택 알고리즘)

 

지원할 수 있는 컴퓨터 시스템은 거의 없고, 대부분 참조 비트(reference bit)형태로 지원

LFU 페이지 교체(Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 방법. 활발하게 사용되는 페이지는 참조 횟수가 많아질 것이라는 가정에서 만들어진 알고리즘

집중적으로 사용됨으로 참조 횟수가 커지지만 이후 사용되지 않더라도 계속 메모리에 머뭄

최적 페이지 교체(OPT)를 제대로 근사하지 못해 잘 사용하지 않는다

MFU 페이지 교체(Most Frequently Used)

참조 횟수가 가장 적은 페이지가 최근 메모리에 올라왔고 앞으로 계속 사용될 것이라는 가정에 기반

최적 페이지 교체를 제대로 근사하지 못해 잘 사용하지 않는다

NUR(Not Used Recently)

최근 사용되지 않은 페이지를 교체하는 것

최근 사용된 메모리 페이지를 유지하는 것을 선호하는 것이다

'알고리즘 공부' 카테고리의 다른 글

프로그래머스 스택/큐  (1) 2024.07.01
[네트워크] HTTP/HTTPS  (1) 2024.03.12
[백준 11399] ATM  (0) 2024.01.12
[백준 1912] 연속합 - 자바  (0) 2024.01.08
[백준 9095] 1,2,3 더하기 - 자바  (0) 2024.01.08
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함