운영체제 정리 (8)

• 서적소개: 링크
• 운영체제 정리 (7): 링크
• 9~13 챕터는 정리 X
  1. 입출력 시스템과 디스크 관리
  2. 파일관리
  3. 분산 및 다중 처리 시스템
  4. 시스템 보안과 보안 운영체제
  5. 유닉스 운영체제

8-1. 가상 메모리의 이해

virtual memory

• 개념
  • 가상 메모리 주소를 주는 방법
  • 사용자와 논리적 주소를 물리적으로 분리
  • 메인 메모리 용량을 초과한 프로세스에 주소를 지정해서 메모리를 제한 없이 사용할 수 있게 함
• 활용
  • 필요할 때, 디스크와 메모리 사이에 프로세스 코드와 데이터 저장
  • 디스크에 저장된 주소 공간은 캐시로 처리 (메인 메모리 효율적 사용)
  • 페이징을 이용하여 가상 메모리 시스템 구현
• 주소
  • 가상 주소(논리적): 실행 중인 프로세스가 참조
  • mapping: 가상 주소를 물리적 주소로 변환
  • DAT(dynamic address translation): 인위적으로 연속적, 가상 주소에서 연속적 + 메인 메모리에서는 연속 필요 X

가상 주소와 테이블 항목

• 메인 메모리는 가상 page와 동일한 크기의 page frame으로 분할

8-2. 요구 페이징

요구 페이징

• 가상 메모리에서 가장 많이 사용하는 메모리 관리 방법
• 순차적인 프로그램의 모듈을 처리할 때, 다른 부분은 실행하지 않는다는 특성 이용
• 지연 기술/lazy swapper
  • 실행 중인 process의 요구 page만 memory에 fetch
  • 모든 페이지를 동시 적재 X
  • 페이지 테이블 유지 필요
• page fault (페이지 부재)

page fault

• 프로그램이 메모리에 저장되지 않은 페이지에 엑세스
• 타당 비트/비타당 비트로 처리 가능
• 비타당 비트를 발견하면 무효 주소 오류로 처리
• 페이지 부재로 트랩이 발생한 경우
  • 해당 페이지를 메모리에서 가져옴
  • 메모리에서 빈 프레임 중 하나 결정
  • 할당된 프레임에 요구된 페이지를 디스크에서 적재
  • 적재되었음을 알리기 위해 페이지 테이블의 비트를 타당으로 변경
  • 주소 트랩으로 인터럽트된 명령어 다시 시작
• 과도한 페이지 교체로 인한 오버헤드는 시스템 성능을 저하시킴
• COW(copy-on-write)기술로 더 많은 자원 저장
  • 페이지 효율성을 올림

페이지 성능

• MAT(memory access time): 메모리 액세스 시간
• EAT(effective access time): 유효 액세스 시간, 페이지 부재가 없다면 MAT와 동일
• 페이지 부재 비율을 낮추는 것이 중요: 알고리즘과 정책이 필요

페이지 대치

• 페이지 부재가 발생한 경우 발생
• 메인 메모리에 있으면서 사용하지 않는 페이지를 없애고 새로운 페이지로 교체

8-3. 페이지 대치 알고리즘

• 내보낼 페이지를 고르는 방법을 위한 알고리즘
• 보통은 페이지 부재 비율이 낮은 알고리즘을 기본으로 선택

선입선출 대치 알고리즘(FIFO)

• queue 구조로 유지
• Belady’s anomaly 발생: 할당하는 프레임 수가 증가하면 페이지 부재 비율도 증가

최적 페이지 대치 알고리즘

• 페이지 부재 비율이 낮은 페이지 대치 알고리즘을 찾기 위함
• 최적 페이지 대치 알고리즘(Optimal replacement algorithm)은 밸래디의 알고리즘으로도 알려져있음
• 앞으로 가장 오래 사용하지 않을 페이지를 대치
• 참조 문자열을 언제 사용할 것인지에 대한 정확한 정보를 요구

최근 최소 사용 대치 알고리즘

• 최근 최소 사용(Least Recently Used)
• 미래를 예측하려는 통계적 개념임
• 마지막으로 사용한 시간이 멀 수록 대치 대상
• 최종 참조로 정의되는 프레임 순서 결정이 필요
  1. 카운터(계수기)를 이용
     • 프로세서에 논리 클록을 추가
     • 모든 참조의 프로세서 클록을 각 페이지 테이블 항목에 업데이트
     • 참조할 떄 마다 클록 증가 (최후 참조 시간을 가짐)
     • 시간 값이 작은 페이지는 대치
  2. 스택을 이용
     • 페이지 번호를 스택에 넣어 관리
     • 페이지를 참조하면 페이지 번호를 스택의 top으로 이동

최근 최소 사용 근접 알고리즘

• 저렴한 비용으로 최근 최소 사용 알고리즘 구현
  • 이를 위해 system이 참조 비트의 형태를 지원
• 프로세스를 수행할 때 참조된 각 페이지와 관련된 비트를 1로 변환
• 어느 페이지를 사용했는지 조사하여 부분적인 순서 정보로 LRU에 근접한 알고리즘
  1. 참조 비트 알고리즘
     • 각 페이지의 8 bit 정보에 참조 비트를 기록
     • 최근 8번의 페이지 기록 정보를 유지
  2. 시계(2차적 기회 대치) 알고리즘
     • 가장 오랫동안 메인 메모리에 있던 페이지 중, 자주 사용하는 페이지의 대치를 방지
     • 각 프레임의 사용 여부를 나타내는 참조 비트를 추가
     • 원형 버퍼로 구성, 각각 포인터를 가짐
     • 참조하면 해당 비트를 1로 변경
     • 검사 중, 1을 발견하면 0으로 변경 (한 번의 기회를 더 줌)
     • 검사 중, 0을 발견하면 대치
  3. NUR(not used recently) 알고리즘
     • 최근 사용하지 않는 페이지를 교체
     • 수정 비트
       • 모든 페이지의 참조 비트와 수정 비트를 (0, 0)으로 설정
       • (최근에 사용, 최근에 수정)
  4. 최소 사용 빈도수 알고리즘
     • LFU (least frequently used)
     • 각 페이지마다 참조 횟수 카운터가 존재
     • 수가 가장 작은 페이지를 대치
     • 일반적이지 않음
  5. 최대 사용 빈도수 알고리즘
     • MFU (most frequently used)
     • 위와 반대
  6. 페이지 버퍼링
     • 교체 대상으로 선책한 페이지를 즉시 교체하지 않은 채 잠시 메인 메모리에 유지
     • 메모리에 원하는 페이지가 없으면 가용 페이지 리스트의 첫 프레임에 적재
     • 입출력 연산 횟수가 크게 감소 → 디스크 액세스 시간 감소

8-4. 프레임 할당 알고리즘

• 페이지 부재 횟수를 줄이기 위한 알고리즘
• 최소 프레임 수는 명령어 구조로 정의
• 명령어가 참조하는 모든 페이지를 수용할 수 있는, 충분한 프레임이 있어야 명령어 하나를 실행할 수 있음

균일/비례 프레임 할당 알고리즘

• 균일 할당
  • 프레임 m개를 프로세스 n개에 나눠주는 가장 쉬운 방법
  • 프로세스가 페이지 프레임을 낭비하거나 페이지 부재가 빈번한 문제 발생
• 비례 할당
  • 사용 가능한 메모리를 각 프로세스의 크기에 비례하여 할당하는 것
  • 크기나 우선순위를 결합하여 할당하는 방법
• 주로 혼합하여 사용

8-5. 메모리를 관리하는 프로세스 적재 정책

• 메모리에 상주할 프로세스 수를 결정

스레싱(thrashing)

• 페이지 교환이 계속 일어나는 현상
• 프로세스가 페이지 교환에 보내는 시간 > 프로세스 수행에 보내는 시간인 상태
• 발생 원인
  • 너무 많은 다중 프로그래밍으로 새로운 프로세스 증가
  • 프로세스에 고정된 프레임 수가 현재 활동에 충분하지 않음
  • 서로 프레임을 뺏는 과정(지속적인 페이지 부재) 발생
• 프러세서의 이용률은 감소하고 이를 위해 다중 프로그래밍의 정도가 올라가지만 악효과
• 예방
  • 다중 프로그래밍 수준과 프로세서 사용률의 수준을 비교 평가
  • 프로세스에 많은 프레임을 제공
    • 작업 집합(워킹 셋) 모델: 프로세스가 얼마큼 프레임을 많이 사용하는지 검사 후, 지역 모델 정의
    • 지역 모델: 한 지역에서 다른 지역으로 이동하는 과정, (지역: 동시에 사용하는 페이지 집합)
  • Denning은 50% 수준의 다중 프로그래밍 정도를 제안

지역성(locality)

• 동일한 값이나 관련 저장 위치를 자주 액세스하는 현상
• 정보를 균일하게 액세스하지 않고, 선호하는 특정 페이지만 집중적으로 참조
• 분류
  • 시간 지역성: 특정 자원들을 상대적으로 짧은 시간 안에 재사용
  • 공간 지역성: 프로세스가 메모리의 어떤 위치를 참조하면 그 근처를 이후에도 계속 참조

작업 집합 모델(WSM: Working Set Model)

• 프로그램 수행 과정을 지역성으로 설명
• 프로세스가 많이 참조하는 페이지 집합을 메모리 공간에 계속 상주시킴
• 작업 집합 크기(WSS)
  • 작업 집합 창을 이용해서 구함
  • D = 모든 WSS의 합 (D: 전체 요구 프레임)
  • D > m (m: 총 유효 프레임)의 경우 스레싱 발생
  • 스레싱 발생 시, 중지할 프로세스 선정 후 페이지 회수
• 작업 집합 창: 매개 변수를 이요해서 정의, 시간 단위에 의힘
• 새로운 프로세스는 메인 메모리에 자신의 작업 집합을 적재할 수 있는 공간이 있을 때만 시작

페이지 부재 비율(PFF: page fault frequency)

• 스레싱을 예방하는 직접적인 액세스 방법
• 페이지 환경에서 프로세스의 실행을 측정하는 기준
• 프로세스를 중지 후, 페이지 부재 비율이 높은 프로세스에 중지된 프로세스에 할당된 프레임 분배
• 페이지 부재 비율 > 상한 값 : 프로세스에 다른 프레임을 더 할당
• 페이지 부재 비율 < 하한 값 : 프레임 회수

8-6. 메모리 관리와 관련된 기타 이슈

대치 범위

• 대치할 희생 페이지 결정 방법

1. 전역 대치
   • 프레임 할당 기준으로 페이지의 대치 범위를 모든 프로세스에 적용
   • 교체할 프레임을 다른 프로세스에서 획득 (메인 메모리에서 자유롭게 선택)
   • 각 프로세스의 부재 비율을 조절할 수 없음
   • 페이지 테이블이 소프트웨어로 유지/관리 됨
2. 지역 대치
   • 프로세스를 개별적으로 제한
   • 프로세스에 할당된 페이지만 선정 가능
   • 프로세스의 상대적인 중요도에 따라 메모리 할당 조정
   • 일관된 성능
   • 프로세스 끼리의 경쟁 X

프리 페이징

• 예상되는 모든 페이지를 사전에 한꺼번에 메모리 내로 가져옴
• 실제 사용 확률 a(0 <= a <= 1)일 경우, a가 1에 가까울 수록 좋음

페이지 크기

• 페이지 크기는 하드웨어 디자인에서 중요한 요소
• 메인 메모리 크기와 프로그램 크기 자체에 영향을 받음
• 페이지 크기와 페이지 테이블의 크기
  • 페이지 크기가 감소하면 페이지 수가 증가하여 테이블이 커짐
• 작은 크기의 페이지
  • 페이지 테이블 증가
  • 내부 단편화 감소
  • 디스크 IO 증가
  • 지역성 증가, 페이지 부재 비율 증가
• 큰 크기의 페이지
  • 페이지 테이블 감소
  • 내부 단편화 증가
  • 디스크 IO 감소
  • 지역성 악화, 페이지 부재 비율 감소

페이지 테이블의 구조

• 가상 주소를 프레임 번호와 오프셋으로 구성된 물리적 주소로 변환
• 역 페이지 테이블
  • 프로세스들이 물리적 페이지를 공유할 때 필요한 전역 페이지 테이블
  • 페이지 테이블 일부를 메인 메모리에 적재해야하는 문제 해결
  • 물리적 주소로 정렬
  • 전체 탐색 탓에 페이지 테이블 탐색은 비효율적 → 해싱 사용
• 변환 우선참조 버퍼(Translation Look-aside Buffer)
  • 가상 메모리를 참조하는 메모리 엑세스 시간을 줄이기 위함
  • 페이지 테이블의 항목들에 특별한 캐시 사용
  • 지역성에 따름 : 최근 참조한 페이지 일부를 저장