운영체제 정리 (7)

• 서적소개: 링크
• 운영체제 정리 (6): 링크
• 운영체제 정리 (8): 링크

7-1. 메모리 관리

메모리 관리의 개념과 정책

• 다중 프로그래밍 환경에서는 한정된 메모리를 여러 프로세스가 함께 사용하므로 효율적인 관리 방법 필요
• 메모리 관리자: 운영체제의 관리 모듈과 메모리 관리장치(MMU: Memory Management Unit)가 협업하여 관리
• 주요 정책
  1. 적재 정책 (fetch policy)
     • 디스크에서 메모리로 프로세스 반입할 시기 결정
     • 요구 적재: 참조 요청에 따라
     • 예상 적재: 시스템의 요청을 미리 예측
  2. 배치 정책 (placement policy)
     • 프로세스를 메모리 어디에 저장할 것인지 결정
     • 최초 적합, 최적 적합, 최악 적합…
  3. 대치 정책 (replacement policy)
     • 메모리가 부족할 때, 적재된 프로세스 중 제거할 프로세스 결정하는 교체 방법
     • FIFO, LRU(Least Recently Used: 최근 최소 사용)

메모리의 구조와 매핑 (사상)

• 주소
  1. 논리적 관점
     • 가상 주소
     • object code가 저장된 공간이나 프로그램에서 사용하는 자료구조 등
  2. 물리적 관점
     • 논리적 주소에 대응하여 적재하는 실제 주소
     • 메모리 칩이나 디스크 공간에서 만듦
• 주소의 변환은 MMU이 처리
• 변환 방법에는 고정 분할, 페이징, 세그먼테이션, 페이지화된 세그먼테이션이 있음
• binding: 프로세서가 프로세스를 실행하기 위해, 논리적 주소와 물리적 주소를 연결(mapping)시켜 주는 작업
• 변환 시점에 따른 binding 구분
  1. 컴파일 시간
     • 프로세스가 메모리에 적재될 위치를 컴파일 과정에서 앎 → 물리적 주소 생성
     • 시작 위치가 변하지 않으면 코드 재컴파일 필요 X
  2. 적재 시간
     • 프로세스가 적재될 위치를 컴파일 과정에서 모름 → 컴파일러가 상대 주소 생성 (시작 주소 = 0)
     • 최종 바인딩을 적재 시간까지 연기
     • 정적 대치: 시작 주소가 변하면 변화된 값을 반영하기 위한 재적재
  3. 실행 시간
     • 프로세스가 동일 장소에서 작동하면 적재 시간 과정에서 바인딩 가능
     • 프로세스가 실행 도중 메모리의 세그먼트 사이를 이동함 → 바인딩은 수행시간 까지 연기
     • 특수 하드웨어(기본 및 경계 레지스터)의 지원이 필요
• compiler가 원시 코드 컴파일 → object 파일 생성 → linker가 object 파일에 라이브러리/다른 object 파일 결합 → loader가 지정 위치에서 시작 → 메모리에 배치

메모리 관리 관련 용어

1. 동적 적재(dynamic loading)
   • 실행 직전에 주소를 확정하면 메모리를 효율적으로 운영
   • 메인 프로그램만 먼저 메모리에 적재
   • 다른 루틴은 교체 가능한 형태로 디스크에 저장
   • 메인 프로그램이 다른 루틴이 필요함 → 루틴이 메모리에 없음 → 적재 → 프로그램 주소 테이블 갱신
   • 프로그램 양이 많을 때 유용
2. 중첩 (overlay)
   • 실행하려는 프로그램이 메모리보다 클 때
   • 당장 필요하지 않은 프로그램의 일부를 오버레이로 설정
   • 메모리의 일부 영역에 프로그램 실행에 꼭 필요한 명령어와 데이터 저장
   • 오버레이 영역에는 필요할 때 호출하여 적재
   • 마이크로 컴퓨터나 실제 메모리 크기가 제한된 HW에서만 사용
3. 스와핑 (프로세스 교체)
   • swap out: 프로세서 할당이 끝나고 수행이 완료된 프로세스는 보조기억장치로
   • swap in: 새롭게 시작하는 프로세스를 메모리에 적재
   • 디스크의 프로세스를 디스크에서 메모리로 옮기고, 메모리에 적재된 프로세스는 준비 큐에서 대기하도록 하는 과정
   • 실행 시간 바인딩에서 스와핑 가능
   • 각 프로세스를 실행하는 시간이 스와핑 시간보다 길어야 프로세서 효율적 사용 가능

메모리 적재 방법

1. 연속 메모리 적재 방법
   • 직접 배치, 오버레이, 고정 분할이 해당
2. 비연속(분산)메모리 적재 방법
   • 페이지나 세그먼트 단위로 나눠 여러 곳에 적재
   • 외부 단편화를 해결하고 내부 단편화를 최소화하기 위함
   • 고정 분할: 프로그램 하나를 분할하는 기준에 따라 동일 크기로 나눠 적재 (ex 페이징)
   • 가변 분할: 의미 단위(크기 일정X)로 나눠 메모리로 적재

7-2. 연속 메모리 할당

단일 프로그래밍 환경

• 메모리를 모니터(운영체제 상주 영역), 사용자 영역, 미사용으로 구분
• 메모리 제어 권한이 모두 사용자에게 있음 → 경계 레지스터를 두어 OS 손상 방지
• 사용자 프로그램 적재의 문제
  1. 사용자 프로그램을 기준 레지스터보다 상위 메모리에 적재
     • 사용하지 않는 공간이 OS와의 경계가 되어줌
  2. 주소 바인딩을 연기
     • 기준값에 의해 주소 접근을 동적으로 대체

다중 프로그래밍 환경

1. 고정 분할 방법
   • 메모리를 고정된 크기로 분할
   • 물리적 주소는 기준 레지스터(PBR)값에 논리적 주소 더해서 생성
   • 논리 주소 > 분할된 메모리 → 오류
   • 논리 주소 < 분할된 메모리 → 내부 단편화: 요구된 블록에 할당하고 공간이 남아 낭비가 일어남
   • 기준 레지스터와 경계 레지스터: 이용해 여러 프로세스가 메모리에 상주하는 상황에서 프로세스 보호가 가능
     1. 기준 레지스터
        • 가장 작은 물리적 주소
     2. 경계 레지스터
        • 프로그램 영역이 저장되어 있는 크기 저장, 논리적 주소
   • 분할 영역이 빔 → 프로세서가 프로세스 queue에서 하나 선택 → 비어있는 분할 영역에 적재
   • 성능 향상
     • 분할 영역의 개수와 각 크기 지정
     • 프로그램 작업을 어느 영역에 배치하는 지 결정, 작업 스케줄러 이용
2. 가변 분할 방법
   • 고정된 경계 X, 각 프로세스가 필요한 만큼 메모리 할당
   • 기준 레지스터와 경계 레지스터를 사용하여 분할 영역 표현
   • 논리 주소 > 경계 레지스터 → 오류
   • 메모리 사용 테이블을 유지해야 함
   • 사용 가능 공간 어디에 할당하는 것이 좋은가
     1. 최초 적합 방법 (first-fit)
        • 사용 가능 공간 중 첫 번째 공간
        • 공간 활용률이 떨어짐
     2. 최적 적합 방법 (best-fit)
        • 사용 가능 공간 중 가장 작은 공간에 할당
        • 공간 이용률은 향상 가능성 있음, 할당에 많은 시간 소요
     3. 최악 적합 방법 (worst-fit)
        • 가장 큰 공간에 할당
   • 외부 단편화 발생
     1. 메모리 통합 (coalescing)
        • 하나의 작업이 끝난 후 인접한 빈 공간과 병합
     2. 압축 방법 (compaction)
        • 메모리의 내용을 움직여 사용 가능한 큰 블록 생성
        • 대체가 동적이고 실행 시간이어야 함
        • 메모리 테이블 유지해야 함 → 오버헤드 발생
        • 압축하는 동안 모든 일 중지

다중 프로그래밍 환경의 버디(buddy) 시스템

• 단편화 문제를 해결하는 방법
• 큰 버퍼를 반복적으로 이등분, 가능하면 인접한 free buffer 합침
• L <= K <= U
  • L=할당 가능한 가장 작은 블록, K=사용할 수 있는 메모리 블록, U=가장 큰 블록
• 요청한 메모리가 작아 전체를 할당하지 않으면 2^(U-1)의 크기를 갖는 버디로 나눔
• 유닉스 커널 메모리 할당/병렬 처리 시스템에서 응용

7-3. 분산 메모리 할당 1: 페이징

페이징의 개념

• 메인 메모리를 페이지 프레임이라는 고정 크기 블록으로 나누고, 프로세스를 동일한 크기의 페이지로 나눠 적재
• 외부 단편화 발생 X
• 분산 적재로 인한 내부 단편화와, 운영체제의 페이지 관리 부담
• 페이지의 크기와 페이지 테이블 유지 비용은 반비례

페이징 시스템의 하드웨어 구조와 원리

• 프로세서가 만드는 논리적 구조: 페이지 번호 + offset(변위)
  1. p(페이지 번호)를 페이지 테이블 색인으로 사용
  2. p 위치에 저장된 f(메모리 페이지 기준 주소: 메인 메모리의 프레임 번호)
  3. f + d(offset) = 메인 메모리의 물리적 주소
• 페이지 테이블(Page map table)
  • 페이지 번호(논리)와 이에 대응하는 페이지 프레임 주소(물리) 포함
  • 물리적 구조로 바꾸기 위한 용도
• 논리적 구조가 클수록 페이지 테이블 크기 증가 → 메모리에 더 큰 적재 공간 필요

페이지 테이블의 구현

• 프로세스 하나에는 페이지 테이블이 하나 있음
• 페이지 테이블 관리
  • 크기가 커서 관리 방법이 중요
  • 전용 레지스터 사용: 페이지 테이블이 매우 커서 어려움
  • 페이지 테이블을 메모리에 적재
    • 페이지 테이블 기준 레지스터(PTBR: page Table Base Register)로 페이지 테이블 지시
    • 레지스터 값을 바꾸는 것이 문맥 교환 효과를 보임
    • 메모리 엑세스 시간이 문제: 연관 레지스터/변환 우선참조 버퍼(Translation Look-aside Buffer)로 해결
• 연관 레지스터를 이용한 논리적 주소 → 물리적 주소
  1. 직접 매핑 (direct mapping)
     • 완전한 페이지 테이블 유지
     • 페이지 테이블에 있는 메모리 주소를 PTBR에 적재
     • 변환 방법
       1. b (페이지 테이블의 시작 주소) + p (참조 페이지 번호)
       2. b에서 시작하여 페이지 번호 p에 대응하는 p’(프레임: 물리적 주소)
       3. p’ + d(offset) = 물리적 주소
     • 메모리 위치에 액세스하는 시간 소요
  2. 연관 매핑 (associative mapping)
     • 논리적 주소를 연관 레지스터의 집합으로 표현
       • 연관 레지스터에는 프로세서의 페이지 번호, 프로세서에 대응하는 프레임 번호가 존재
       • 각 레지스터는 key-value로 구성
     • 변환 방법
       1. p는 연관 메모리의 모든 항목을 조사하여 찾음
       2. p에 대응하는 p’ + d = 물리적 주소
     • 빠른 검색 가능, PTBR 필요 X
     • 하드웨어가 비쌈
  3. 연관+직접 매핑 결합
     • 최근에 사용한 페이지만 연관 레지스터에 유지
     • 연관 레지스터에 해당 페이지가 없으면 직접 매핑
     • 지역성을 활용
     • 적중률: 페이지 번호를 연관 레지스터에서 발견하는 비율

공유 페이지

• 페이징 시스템은 시분할 환경에서 중요한 공통 코드 공유가 가능
• 연속적 할당X → 여러 프로세스가 메모리 공유
• 공유 라이브러리 코드에도 사용 가능
  • 재진입 코드(reentrant code)/순수코드(pure code)라고도 부름: 공유 코드는 재진입을 허용
  • only-read
  • 프로세스는 재진입 코드에서 데이터 항목 지정 X, 수행 도중 변하지 않음 → 복수의 프로세스가 동시에 같은 코드 수행 가능
• 모든 프로세스에서 동일한 논리적 주소는 동일한 물리적 주소로 매핑
• 전체 메모리에서 요구하는 사항을 크게 줄일 수 있음

페이징에서 보호

• 프로세스 하나가 다른 프로세스의 데이터 영역에 액세스하여 무단으로 읽거나 쓰기 X
• 페이지별로 액세스 권한 다르게 부여할 수 있음 → 테이블 보호 비트를 추가 → 페이지 보호
• 타당(1), 비타당(0) 여부 확인하여 선택적 트랩
• 다중 처리 프로그래밍의 실현, 압축 기능 제거
• 하드웨어 비용 증가, 속도 저하, 내부 단편화 문제

7-4. 분산 메모리 할당 2: 세그먼테이션

세그먼트의 개념

• segmentation은 프로세스 관점을 지원
• 메모리를 크기가 변할 수 있는 세그먼트(segment)로 나눔
• 세그먼트
  • 서브루틴, 프로시저, 함수, 모듈 등으로 구성
  • 하나의 모듈 프로그램으로 생각
• 비연속 메모리 할당 방법, 논리적 영역을 세그먼트의 집합으로 인식

세그먼테이션에서 하드웨어 구조와 원리

• 논리적 주소는 s(세그먼트 번호)와 d(offset)로 구성
  • s는 2^8, d는 2^16
  • 예: IBM 370
  • s는 세그먼트 테이블의 색인으로 사용
  • d는 0 ~ SL 사이여야 함
• 각 프로세스는 고유의 세그먼트 테이블을 메모리에 유지
• 세그먼트 테이블의 기준 레지스터(STBR), 세그먼트 테이블 길이 레지스터(STLR)
  • 프로세스를 dispatch할 때 적재
  • s < STLR을 만족해야 함
  • s + STBR = 실제 메모리 주소
• 세그먼트 테이블
  • 항목은 해당 세그먼트가 적재될 메모리의 시작 주소, 세그먼트의 길이
  • SB(세그먼트 기준), SL(세그먼트 경계) 존재 → 세그먼트 길이
  • SB + d = 원하는 워드에서 메모리 주소

세그먼트 공유

• 공유한다고 선언만 하면 됨
• 동일한 메모리 주소를 지정하면 공유 가능

페이징과 세그먼테이션 비교

• 세그먼테이션은 프로그램을 나누는 크기가 가변적
• 모든 블록이 작아서 세그먼트 수용 불가 시, 외부 단편화가 일어날 수 있음
  • 기다리거나 압축 진행
  • 세그먼테이션은 동적 알고리즘이기 때문에 메모리 압축 언제나 가능
• 페이징: 물리적 주소 없이, 큰 가상 주소 공간이 가능하게
• 세그먼테이션: 프로그램과 데이터를 논리적으로 독립된 주소 공간으로 나누고, 쉽게 공유/보호

페이지화된 세그먼테이션

• 외부 단편화 문제를 제거하면서 할당 과정을 쉽게 함
• 멀틱스(Multics), 인텔 386계열에서 사용
  • 멀틱스에서는 논리 주소를 18비트의 s와 16비트의 d로 구성
  • d는 6비트의 p와 10비트의 d’(page offset)으로 구성
• 논리적 구조를 세그먼트로 나누고, 세그먼트를 크기가 고정된 페이지로 나눔
  • 프로세스에 세그먼트 테이블 하나, 세그먼트에 페이지 테이블 하나
• 주소 생성 과정
  1. 논리적 주소의 s와 STBR을 이용해 세그먼트 테이블 확인
  2. p를 찾아서 이에 대응하는 프레임을 찾음
  3. 페이지 프레임과 오프셋 결합하여 메모리 주소 생성