본문 바로가기
카테고리 없음

메모리 시스템 : 연속 할당 기법 ~ 홀 선택 알고리즘

by winter_sunshine 2023. 8. 13.

안녕하세요 여러분~

이번 시간에는 '연속 할당 기법'  '단편화'  '압축 기법'  '홀 선택 알고리즘'까지

알아보는 시간을 가지겠습니다!
그럼 시작합니다~!~! 

1.  연속 메모리 할당

  • 각 프로세스의 영역(코드와 데이터)을 연속된 메모리 공간에 배치
    • 메모리를 한 개 이상의 파티션으로 분할하고 프로세스당 하나의 파티션을 할당하는 기법
    • 할당 가능한 메모리 부족시 프로세스는 큐에서 대기
    • 연속 메모리 할당은 초기 운영체제에서 사용
      • MS-DOS와 같은 과거 운영체제
        • 단일 사용자 단일 프로세스 시스템
        • 한 프로세스가 전체 메모리 독점
      • 가상 메모리 지원하지 않음

 

2.  연속 메모리 할당 기법

  • 고정 크기(fixed size partition) 할당
    • 전체 메모리를 고정된 크기의 n개의 파티션으로 분할, 각 프로세스마다 하나씩 할당
      • 수용가능 프로세스의 수 n 고정
    • 작은 프로세스의 경우 메모리 낭비 발생 가능, 큰 프로세스의 경우 실행 불가

고정 크기(fixed size partition) 할당

 

  • 가변 크기(variable size partition) 할당
    • 각 프로세스마다 가변 크기(그 프로세스와 같은 크기)의 연속된 메모리를 할당
      • 수용가능 프로세스 수 가변

가변 크기(variable size partition) 할당

 

3.  단편화(fragmentation)

  • 요청을 만족하는 메모리 양이 존재하지만 프로세스에게 할당할 수 없는 메모리 조각(hole)이 생기는 현상
    • hole == 낭비되는 메모리
  • 홀이 생기는 위치에 따른 종류
    • 내부 단편화
    • 외부 단편화

 

4.  내부 단편화(internal fragmentation)

  • 할당된 메모리가 요구된 메모리보다 더 큰 경우
    • 프로세스에 할당된 메모리 내부에 사용할 수 없는 홀이 생기는 현상
    • 파티션의 크기를 줄임으로 완화될 수 있으나 메모리 관리의 효율성은 떨어짐

내부 단편화(internal fragmentation)

 

5.  외부 단편화(external fragmentation)

  • 요청을 만족하는 메모리 양이 존재하지만, 연속적이지 않은 경우
    • 각 프로세스에 할당된 메모리들 사이에 사용할 수 없는 홀이 생기는 현상
      • 가변 크기의 파티션이 생기고 반환되면서 여러 개의 작은 홀 생성
    • 메모리 압축 기법 적용 가능

외부 단편화(external fragmentation)

 

6.  압축(Compaction)

  • 불연속적인 hole들을 이동하여 외부 단편화 문제를 해결가능
  • 한계
    • 주소 relocation이 동적인 경우만 가능
    • 압축 시간으로 시스템 성능 저하될수도

압축(Compaction)

 

7.  연속 메모리 할당의 구현

  • 하드웨어의 지원
    • CPU의 레지스터 필요
      • base 레지스터 : 할당된 물리 메모리의 시작 주소
      • limit 레지스터 : 현 프로세스에게 할당된 메모리 크기
      • 주소 레지스터 : 현재 액세스하는 메모리의 논리 주소
    • 주소 변환 하드웨어(MMU) 필요
  • 운영체제의 지원
    • 각 프로세스별로 할당된 물리메모리의 시작 주소와 크기 정보 관리
      • 새 프로세스를 실행시킬 때마다 물리 메모리의 시작 주소와 크기 정보를 base 레지스터와 limit 레지스터에 적재
    • 비어있는 메모리 영역 관리

 

 

※  연속 메모리 할당: 주소 변환과 메모리 보호

연속 메모리 할당: 주소 변환과 메모리 보호

 

8.  연속 메모리 할당의 특징

  • 장점
    • 논리 주소를 물리 주소로 바꾸는 과정이 단순
      • CPU의 메모리 액세스 속도 빠름
      • 운영체제가 관리할 정보량이 적어서 부담이 덜함
  • 단점
    • 메모리 할당의 유연성이 떨어짐
    • 외부 단편화 발생

 

9.  홀 선택 알고리즘(동적 메모리 할당)

  • OS는 메모리가 요구될 때 적당한 홀을 선택해서 할당
    • 고정 크기 할당시
      • 가용 파티션에 대한 리스트를 관리하고 이중에서 할당
    • 가변 크기 할당시
      • 가용 메모리 리스트(홀 리스트)를 통해 각 홀 마다 시작 주소와 크기 정보를 유지
      • 이 홀 리스트에서 적절한 홀을 선택해 할당
        • 어떤 홀을 선택하느냐에 따라 성능이 달라짐

 

10.  홀 선택 알고리즘 종류

  • First-fit(최초 적합)
    • 가능한 크기를 가진 첫 번째 hole에 할당
      • 가정: 홀 리스트는 주소에 대해 오름차순 정렬
  • Best-fit(최적 적합)
    • 가능한 가장 작은 크기의 hole에 할당
      • 가정: 홀 리스트는 홀 크기에 대해 오름차순 정렬
    • 할당 후 남는 공간을 최소화할 수 있음
      • 메모리 사용 효율이 높으나, 할당 때마다 홀 리스트 정렬 필요
  • Worst-fit(최악 적합)
    • 가능한 가장 큰 크기의 hole에 할당
      • 가정: 홀 리스트는 홀 크기에 대해 내림차순 정렬
    • 할당 후 남는 공간에 다른 프로세스의 할당 확률 높음

 

※  일반적인 효율성 비교

  • Storage utilization
    • Best-fit ≥ First-fit > Worst-fit
  • Speed
    • First-fit > Best-fit > Worst-fit

 

 

지금까지 '연속 할당 기법'  '단편화'  '압축 기법'  '홀 선택 알고리즘'에 대해 알아봤습니당 ㅎㅎ
다음 시간에는 비연속 할당 기법인 '페이징'과 '세그먼테이션'과 'TLB', '역 페이지 테이블', '멀티 레벨 페이지 테이블'

에 대해 알아보는 시간을 가질 예정입니다!!
오늘 포스팅한 개념들은 운영체제 과목에서 상당히 중요한 개념이니까 반드시 정리하는 시간을 가졌으면 해요!
다들 고생 많으셨습니다 ㅎㅎ 다음 시간에 뵈어용~!!

 

저작자표시 비영리 변경금지

티스토리툴바