1. RAID 구조

  • 디스크 시스템의 성능향상을 위해 여러개의 디스크를 논리적으로 하나의 디스크처럼 사용하는 방식
  • 접근 속도와 신뢰도를 향상시킬 수 있음
  • OS의 지원과 RAID 컨트롤러가 필요

 

 

2. RAID 0

  • 논리적으로 한 Block을 일정 크기로 나누어 각 디스크에 나누어 저장
  • 모든 디스크가 입출력 부하를 나누어 부담(빠른 접근속도)
  • 하나의 디스크에라도 문제가 발생하면 block 전체의 데이터가 손실됨(낮은 신뢰도)

 

 

3. RAID 1

  • 접근 속도의 향상보다는 신뢰도를 높이는데 치중한 RAID구조
  • 최소 두개 이상의 디스크로 구성, 데이터를 모든 디스크에 중복으로 저장
  • n개의 디스크지만 실제 사용 가능한 용량은 1개의 디스크만큼의 용량뿐
  • 어느 하나의 디스크에 문제가 발생해도 다른 디스크에서 데이터를 읽어올 수 있음(높은 신뢰도)

 

 

4. RAID 3

  • RAID 0 방식에서 신뢰도 향상을 위해 parity disk를 추가
  • 디스크에 문제가 발생할 경우 parity 비트를 사용하여 데이터를 복구
  • RAID 0의 빠른 접근속도에 parity bit를 통한 신뢰도 보장으로 높은 성능
  • write시 parity 계산으로 인한 오버헤드 존재

 

 

5. RAID 4

  • RAID 3와 유사하지만 블록단위로 데이터를 분산저장

  • 각 block에 독립적으로 접근 가능
  • 입출력 부하를 일부 디스크가 집중적으로 부담해야할 수 있음

 

 

6. RAID 5

  • RAID 3나 RAID 4는 parity 디스크에 문제가 생길 경우 신뢰도를 보장할 수 없게됨

  • parity 정보까지도 각 디스크에 분산저장
    • parity 디스크의 병목현상을 해소
    • 하나의 디스크에 문제가 생겨도 나머지 디스크의 데이터로 데이터를 복구 가능
  • 높은 신뢰도와 빠른 접근속도를 보여 실제로 많이 사용되는 아키텍처

  • 디스크 재구성 속도가 느리고 parity 정보를 계속해서 갱신해야하는 오버헤드 존재
  • 결합하는 디스크의 갯수가 증가할수록 parity 연산 오류가 발생하기 쉬워 신뢰도 저하

 

 

7. RAID 6

  • RAID 5의 신뢰도를 개선하기 위해 각 디스크의 parity 정보 또한 분산저장

  • 두 개까지의 디스크 고장도 복구가 가능

  • parity 정보 갱신의 오버헤드가 RAID 5보다 큼

  • 매우 중요한 데이터를 저장하기 위해 높은 신뢰도를 필요로 할 경우 사용할 수 있음

 

 

8. RAID 10( RAID 1 + RAID 0 )

  • RAID 0의 각 디스크를 RAID 1구조로 대체한 방식
  • RAID 5 나 RAID 6과 달리 parity 연산을 필요로하지 않기 때문에 오버헤드가 적음
  • RAID 0 의 빠른 접근속도와 RAID 1 의 신뢰도를 모두 얻음

  • 전체 디스크 용량의 절반만을 사용할 수 있기에 디스크 시스템 구성에 드는 비용이 큼

1. 디스크 스케줄링(Disk Scheduling)

  • 디스크 시스템의 성능은 처리율(Throughput)평균 응답시간(Average Response Time) 등을 기준으로 평가
  • disk access 요청의 처리 순서를 적절히 결정하는 것으로 header의 이동과 platter의 회전을 최소화할 수 있음
    => 최적의 성능

 

 

2. Seek Time 최소화

  • FCFS(First Come First Served)
    • 먼저 들어온 요청을 먼저 처리
    • 구현이 간단하고 오버헤드가 적으며 starvation 문제가 없음
    • 최적의 성능을 얻는데는 도움이 되지 않음
    • disk access 횟수자체가 많지 않은 시스템에 적합

  • SSTF(Shortest Seek Time First)
    • 현재 head 위치에서 가장 가까운 요청부터 처리
    • 처리율(Throughput)이 높음
    • 평균 응답시간이 작음(빠름)
    • 멀리 떨어져있는 위치에 대한 disk access 요청의 처리가 늦어질 수 있음(starvation)
    • 일괄 처리 시스템(Batch System)에 적합

  • Scan
    • 현재 head의 진행방향에서 가장 가까운 요청부터 처리
    • SSTF에서 starvation 문제를 해결한 방식
    • 단, 진행방향의 반대쪽의 위치에 대한 요청은 응답시간이 길어진다

  • CScan
    • Scan 방식과는 달리 진행방향을 바꾸지 않고 작업을 수행
    • 마지막 위치에 도달하고나면 시작 위치로 돌아와서 작업을 재시작
    • Scan 방식에서 진행방향의 반대쪽 위치에 대한 요청이 늦게 처리되는 문제 해결
    • 헤더가 초기위치로 돌아오는데 걸리는 시간만큼 오버헤드가 존재

  • Look Scheduling
    • Scan 에서 마지막 실린더까지 이동하지 않고 현재 진행방향에 요청이 없으면 방향을 전환
    • 실제로 Scan을 구현할 때는 이 방식을 사용
    • CScan에서도 같은 방식을 적용 가능(진행방향에 요청이 없을경우 바로 초기위치로)

 

 

3. Rotational Delay 최소화(Shortest Latency Time First)

  • platter 상의 모든 track에 고정된 head가 존재하는 Fixed Header System에서 사용

  • 각 sector마다 해당 sector에서 수행해야할 작업의 대기열(queue)을 유지하고 platter가 회전하면서
    각 sector의 대기열에 있는 작업을 모두 수행한 뒤 다음 sector로 넘어가는 sector queuing 방식 사용

  • head가 움직이는 방식의 디스크에서도 사용 가능
    • head가 특정 실린더에 도달했을 때 헤더를 고정한 뒤 해당 실린더의 모든 요청을 처리

 

 

4. SPTF(Shortest Positioning Time First)

  • Seek Time + Rotational Delay이 가장 작은 요청부터 처리하는 방식

  • 높은 처리율과 빠른 평균 응답시간을 보임

  • SSTF와 마찬가지로 starvation 문제가 발생할 수 있음

  • 에센바흐 알고리즘
    • 실린더 내 track, sector에 다수의 요청이 있다면 하나의 작업만을 수행하고
      나머지는 다음 회전에 처리하도록 요청을 재배열하는 방식

    • head의 이동방식은 CScan과 유사
    • 하드디스크의 물리적 특성상 비효율적인 방식이기에 실제로는 거의 사용되지 않음

1. Process Controlled Memory Access

  • 프로세서가 제어하는 메모리 접근 방식
  • Polling
    • 프로세서가 주기적으로 입출력장치의 상태를 확인
    • 송수신할 데이터가 있는 경우 I/O 실행
    • 단순하고 구현이 쉬움
    • 입출력장치의 처리속도는 프로세서에 비해 훨씬 느리기 때문에 프로세서의 낭비가 심함

  • Interrupt
    • 프로세스가 입출력 요청시 프로세서는 입출력장치에 요청을 전달하고 프로세스를 sleep 상태로 전환
    • 입출력장치는 입출력 작업 완료시 프로세스에게 작업이 완료되었음을 알림
    • 프로세스는 I/O 작업이 완료된 프로세스를 깨우고 ready queue에 다시 삽입
    • I/O 요청시 또는 작업 완료시에만 프로세서가 관여하기에 Pooling에 비해 프로세서의 부담이 훨씬 적음
    • 인터럽트 처리를 위한 오버헤드가 존재
    • 실제 OS들은 대부분 이 방식을 사용

 

 

2. Direct Memory Access(DMA)

  • 프로세서가 모든 입출력 요청을 직접 제어할 경우 오버헤드가 심함

  • 입출력 장치와 메모리를 직접 연결시켜두고 프로세서를 거치지 않아도 입출력장치와
    메모리간의 데이터 전송이 가능하도록 하는 방식

  • 프로세서는 DMA 컨트롤러에 전송방향(메모리 -> 입출력장치 or 입출력장치 -> 메모리)과
    전송 데이터 크기, 메모리 주소 등 작업 수행에 필요한 데이터를 전달하는 역할만을 하고
    실제로 데이터를 전송하는 작업은 DMA 컨트롤러가 수행하도록 함

 

 

3. 운영체제가 지원하는 입출력 서비스

  • I/O 스케줄링
    • 입출력 요청에 대한 처리 순서 결정
    • 보다 효율적이고 공평한 입출력 처리 지원

  • 오류 처리
    • 입출력 도중 에러가 발생할 경우의 처리
    • 디스크 접근 오류, 네트워크 통신 오류 등

  • 입출력장치 관리
    • 입출력장치의 상태나 정보를 관리

  • 버퍼링(Buffering)
    • I/O 장치와 프로세스 사이에 전송되는 데이터를 Buffer에 임시로 저장해두는 방식
    • 전송속도 차이를 해소할 수 있음

  • 캐싱(Caching)
    • 자주 사용되는 데이터를 캐싱해두고 접근하려는 데이터가 캐시메모리에 존재할 경우 
      I/O를 건너뛰고 바로 작업을 수행할 수 있음

  • 스풀링(Spooling)
    • 각 프로세스의 입출력 요청을 디스크상에 파일의 형태로 기록 => Spool 생성
    • 입출력장치는 기록해둔 파일(Spool)을 순차적으로 전송받아 작업을 처리
    • 디스크를 입출력 요청의 버퍼처럼 사용하는 방식

1. 공간 할당 방식(Allocation Methos)

  • 연속 할당(Continuous Allocation)
    • 한 File을 디스크상의 연속된 공간에 저장
    • file이 물리적으로 연속된 공간에 존재하기 때문에 순차접근, 직접접근 모두 효율적으로 가능
    • 구현이 간단하고 관리가 쉬움
    • 외부 단편화(external fragmentation) 문제가 발생할 수 있음
    • 파일의 크기가 변화할 경우를 고려하기 어려움

  • 비연속 할당(Non-Continuous Allocation)
    • 파일을 연속되지 않은 여러 블록에 나누어 저장

    • 연결 할당(Linked Allocation)
      • 파일을 구성하는 블록들을 순서대로 linked list 의 형태로 관리
      • 구현이 간단하고 외부 단편화가 발생하지 않으며 파일의 크기가 변화해도 문제가 없음
      • 포인터를 관리하기 위한 공간이 추가적으로 필요
      • 블록이 linked list 형태로 관리되기 때문에 직접 접근이 비효율적
      • 저장된 포인터에 문제가 생길경우 파일에 치명적인 문제가 발생
      • FAT 포맷이 대표적인 Linked Allocation 방식의 파일시스템

    • 색인 할당(Indexed Allocation)
      • 파일이 저장된 블록의 위치정보를 index 블록에 저장해두는 방식
      • index를 참조하여 원하는 블록에 바로 접근할 수 있기 때문에 직접 접근이 효율적
      • 블록 하나에 접근할 때마다 index 블록을 참조해야하기 때문에 순차접근은 비효율적
      • 파일마다 index 블록을 유지할 추가공간이 필요
      • 파일의 최대 크기가 index블록의 크기에 종속적
      • UNIX 등에서 사용

 

 

2. 빈 공간 관리(Free Space Management)

  • Bit Vector
    • 디스크 내 모든 블록의 사용중 여부를 bit 로 표시 (0: free / 1: allocated)
    • 구현이 간단하며 n개의 연속된 빈공간을 탐색하는데 효율적
    • bit vector 가 모두 메모리에 적재되어있어야 함 => 대규모 시스템엔 부적합
    • 규모가 작은 마이크로 컴퓨터에 적합

  • Linked List
    • 빈 블록을 linked list 형태로 관리
    • 포인터를 관리할 추가 공간을 필요로함 => 공간적으로 비효율적
    • n개의 빈 공간을 찾기 위해 n번의 참조가 필요함 => 시간적으로 비효율적

  • Grouping
    • 몇개의 빈 블록을 그룹으로 묶고 그룹단위로 linked list를 구성하여 관리
    • linked list 방식에 비해서 관리해야할 포인터의 갯수나 빈공간 탐색 시간을 많이 줄일 수 있음
    • n개의 연속된 빈 블록 탐색이 효율적

  • Counting
    • 연속된 빈 블록의 첫 번째 주소와 연속된 빈 블록의 갯수를 테이블로 관리
    • 빈 블록들이 서로 연속되지 않을수록 테이블의 크기가 늘어나 비효율적일 수 있음
    • 연속 할당 기법을 사용하는 시스템에 유리

'CS > 운영체제' 카테고리의 다른 글

#24 디스크 스케줄링(Disk Scheduling)  (0) 2022.02.07
#23 입출력 시스템(I/O System)  (0) 2022.02.05
#21 파일 보호(File Protection)  (0) 2022.02.02
#20 디렉토리(Directory)  (0) 2022.01.31
#19 파일 시스템(File System)  (0) 2022.01.28

1. 파일 보호(File Protection)

  • 파일에 대한 부적절한 접근을 방지하는 것
  • 삭제(Delete), 읽기(Read), 쓰기(Write), 실행(Execute), 추가(Append) 등의 연산을 보호
  • 다중 사용자 환경에서 매우 중요한 개념

 

 

2. 보호 기법

  • 명명(Naming)
    • 파일의 이름을 알지 못하는 사용자는 파일에 접근하지 못하도록 함

  • 암호(Password)
    • 암호를 아는 사용자만 파일에 접근 가능하도록 함
    • 효과적이지만 모든 파일에 접근권한별로 암호를 거는 것은 비현실적
    • 일부 중요한 파일에만 적용하는 방식

  • 접근 제어(Access Control)
    • 사용자, 혹은 사용자 그룹의 파일에 대한 접근 권한을 명시한 테이블을 관리
    • 테이블에 명시된 권한에 따라 접근을 제어함

 

 

3. 접근 제어 구현(Access Control Implementation)

  • 전역 테이블(Global Table)
    • 파일시스템 전체에 대한 접근 제어 테이블을 저장해두고 사용
    • 파일시스템의 규모가 커질수록 테이블의 크기도 너무 커지고 공간낭비도 심해짐

  • 접근 제어 리스트(Access Control List) & 권한 리스트(Capable List)
    • 그래프의 인접 리스트 표현 방식처럼 접근 제어 테이블의 강 행과 열을 리스트형태로 관리
    • 접근 제어 리스트는 각 파일에 접근가능한 도메인(사용자, 그룹)과 각 도메인의 접근권한을 저장
    • 권한 리스트는 각 도메인이 접근 가능한 파일과 그 파일에 대한 권한을 저장
    • 대부분의 OS에서는 접근 제어 리스트 방식을 사용
      => 각 파일에 대한 접근권한 관리가 용이

  • Lock & Key 기법
    • 각 파일은 lock을 가지고 각 도메인은 key를 가짐
    • lock과 key는 접근 권한을 비트로 표현한 형태
    • 파일의 lock 과 도메인의 key를 알면 둘 사이의 접근 제어 관계를 알 수 있음
    • 시스템에서는 key 의 리스트를 관리해야함

  • 접근 제어 리스트 방식의 문제점과 해결
    • 파일에 접근할 때마다 권한 확인이 필요하기 때문에 같은 사용자가 하나의 파일에
      여러번 접근할 때도 매번 권한을 확인하는 비효율적인 동작을 하게됨
    • 도메인이 파일에 접근했을 때 접근 제어 리스트를 통해 권한을 확인하고나면
      도메인에게 접근권한(Capability)을 부여하고 이후 그 프로세스의 접근시에는
      접근 제어 리스트 확인 절차를 진행하지 않도록 하고 도메인이 파일에 마지막으로
      접근했을 때 Capability를 삭제하는 방식으로 문제를 해결

1. 디렉토리(Directory)

  • 파일(File)을 특정한 기준으로 분류(Categorize)해둔 네임스페이스
  • UNIX 계열 운영체제에서는 디렉토리도 파일의 일종으로 취급

 

 

2. 디렉토리의 구조(Structure)

  • 평면 구조(Flat Directory Structure)
    • 파일시스템 내에 하나의 디렉토리만이 존재하는 구조
    • 모든 파일이 하나의 디렉토리 내에 위치함
    • 구조가 간단하여 구현이 쉽고 파일 생성, 삭제, 탐색, 갱신도 쉬움
    • 파일의 수가 늘어날수록 관리에 드는 비용이 증가
    • 하나의 디렉토리 내에 모든파일이 존재하기에 모든 파일 이름이 서로 달라야함
    • 파일의 분류가 불가능(다중 사용자 환경에서 문제가 생김)

  • 2-level 구조(2-level Directory Structure)
    • 사용자마다 하나씩의 디렉토리를 배정
    • 루트에 해당하는 MFD(Master File Directory)와 유저디렉토리인 UFD(User File Direcotry)로 구성
    • 기존 평면 구조에서의 문제점을 어느정도 완화
    • 그러나 결국 각 유저가 평면구조를 사용하는 형태일 뿐이기에 근본적인 문제는 해결되지 않음
    • 서브 디렉토리를 임의로 생성할 수 없기에 파일 분류나 이름 충돌 문제는 여전히 존재
    • 사용자간 파일 공유 또한 보안문제나 이름 충돌 문제로 불가능
  • 계층 구조(Hierarchical Directory Structure)
    • Tree 형태의 계층적 디렉토리 구조
    • 사용자가 디렉토리 내에 서브 디렉토리를 생성하고 관리
    • 디렉토리 연산은 OS가 system call의 형태로 지원
    • 대부분의 OS는 이 구조를 사용

  • 비순환 그래프 구조(Acyclic Graph Directory Structure)
    • 루프가 발생하지 않는 그래프 형태의 디렉토리 구조
    • link 개념의 사용으로 디렉토리 구조가 그래프 형태를 보임 => UNIX의 Symbolic Link가 대표적
    • 루프가 발생하는것을 허용하지 않기 때문에 루프가 발생하는 링크의 생성을 허용하지 않음

  • 일반 그래프 구조(General Directory Structure)
    • 비순환 그래프 구조에서 링크로 인한 루프 발생을 허용한 디렉토리 구조
    • 탐색시 링크로 인한 무한루프를 고려해야함

1. 파일 시스템(File System)

  • 운영체제가 파일을 제어하기 위해 사용하는 방식이나 자료구조 등을 의미

 

 

2. 구성

  • 파일(File)
  • 디렉토리(Directory)

  • 파티션(Partition)

 

 

3. 파일(File)

  • 서로간에 연관성이 있는 데이터들의 집합
  • 이름, 타입, 크기, 위치, 소유자, 생성시간, 수정시간, 접근시간,  권한정보 등의 속성을 가짐
  • 사용자는 파일에 대해(권한이 있다면) 생성, 읽기, 쓰기, 이동, 삭제 등의 작업을 수행할 수 있음
  • OS는 사용자가 위의 작업들을 수행하기 위한 system call을 제공해야함
  • 접근 방식
    • 순차 접근(Sequential Access)
      • 파일의 내용에 처음부터 끝까지 순차적으로 접근하는 방식

    • 직접 접근(Directed Access)
      • 파일의 원하는 부분에 바로 접근하는 방식

    • 색인 접근(Indexed Access)
      • index를 통해 파일의 원하는 부분에 접근하는 방식
      • 접근 속도는 빠르지만 index를 관리하기 위한 공간이 추가적으로 필요

 

 

4. 디렉토리(Directory)

  • 파일을 분류(Categorize)하여 보관하기 위한 자료구조
  • 파일 또는 디렉토리에 대한 참조(reference)를 포함

  • 지원하는 연산
    • 파일 탐색
    • 파일 생성
    • 파일 제거
    • 파일 이름변경
    • 디렉토리 내 존재하는 파일과 디렉토리 목록 확인3
    • 이 연산들 또한 파일의 연산처럼 OS가 system call로 지원

  • UNIX 운영체제의 경우 디렉토리도 파일의 일종으로 취급

 

 

5. 파티션(Partition)

  • 하나의 디스크 내에서 공간을 여러 영역으로 분할한 것
  • 각 파티션은 별개의 영역이기에 별도로 관리할 수 있음

 

 

6. 마운팅(Mounting)

  • 파일시스템은 기본적으로 트리구조로 구성되기 때문에 다른 파일시스템을
    기존의 파일시스템에 연결하여 하나의 파일시스템처럼 사용할 수 있음

  • 마운트 포인트에 다른 파일시스템의 루트를 이어붙이는 것을 마운팅이라 한다.

1. 디스크의 구성

출처: https://www.datarecoverytools.co.uk/2009/12/22/chs-lba-addressing-and-their-conversion-algorithms/

  • 섹터(Sector)
    • 디스크에 데이터를 읽고 쓰는 물리적 단위
  • 트랙(Track)
    • 중심으로부터 같은 거리에 위치한 섹터들의 집합. 즉, 섹터로 이루어진 동심원을 의미

  • 플래터(Platter)
    • 데이터를 읽고 쓸 수 있는 기록매체
    • 여러장의 Platter가 모여 디스크 팩을 구성한다.
  • 실린더(Cylinder)
    • 각 플래터에서 같은 반지름을 가지는 트랙의 집합

  • 표면(Surface)
    • 플래터의 표면

  • 헤드(Head)
    • 디스크 표면에서 데이터를 읽거나 쓰기 위한 부분
    • 전축의 바늘과 유사

  • 암(Arm)
    • Head를 지탱하고있는 부분

  • 암 이동장치(Boom)
    • 암을 이동시켜 원하는 트랙으로 헤드를 이동시키는 장치
  • 회전축(Spindle)
    • 디스크를 회전시켜 트랙 내의 원하는 섹터로 이동하기 위한 회전축
    • 분당 회전수(RPM)가 높을수록 플래터를 회전시키는 속도가 빨라 데이터의 읽고 쓰기가 빨라진다.

 

 

2. 디스크 주소

  • 디스크에서 원하는 섹터를 찾아가기 위해서 필요한 값
  • 물리 주소(실제 주소)
    • 실린더 번호(트랙번호와 같음)
    • surface 번호(몇번째 판의 어느 면인지)
    • 섹터 번호(해당 surface의 해당 트랙에서 몇번 섹터인지)

  • 논리 주소
    • 하드디스크의 종류는 다양하고 OS가 그 모든 디스크의 물리적 특성을 이해하고 사용할 수는 없음
    • OS는 하드디스크상의 모든 데이터를 단순히 block의 배열로 취급
    • 디스크를 블록 단위로 분할하여 각 블록에 번호를 부여하고 그 번호를 통해 블록에 접근
    • OS의 요청을 실제 디스크에 처리할 디스크 드라이버가 필요

 

 

3. 데이터 액세스(Data Access)

  • Seek Time
    • 디스크의 헤더를 목적 cylinder, surface로 이동시키는데 걸리는 시간

  • Rotational Delay
    • 플래터를 회전시켜 해당 섹터를 header에 위치시키는데 드는 시간
    • RPM이 높을수록 줄어듬

  • Data Transmission Time
    • 헤더가 섹터에서 데이터를 읽어서 전송하거나 쓰는데 걸리는 시간

1. 고정 할당 방식(Fixed Allocation)

  • 각 프로세스에게 고정된 갯수의 페이지 프레임을 할당하는 방식

  • OPT(Optimal) 알고리즘
    • 앞으로 가장 오랫동안 교체되지 않을 page를 교체하는 최적의 기법
    • page reference string을 미리 알고있지 않으면 불가능한 방법
    • 현실적으로 사용 불가능한 기법이지만 교체 알고리즘의 성능 평가를 위해 사용됨

  • Random 알고리즘
    • 무작위로 교체할 page를 선택
    • 오버헤드가 없으며 정책도 없음
    • Random 알고리즘보다 성능이 나쁜 알고리즘이라면 고려할 가치가 없음(성능평가의 기준)

  • FIFO(First In First Out) 알고리즘
    • 가장 오래된 page를 교체
    • page가 적재된 시간을 알아야함
    • Locality를 고려하지 않은 알고리즘이기에 좋은 성능을 보이긴 어려움
    • 메모리를 더 많이 할당했는데도 page fault 발생률이 증가할 수도 있음

  • LRU(Least Recently Used) 알고리즘
    • 가장 오래동안 참조되지 않은 page를 교체
    • 각 페이지를 마지막으로 참조한 시간을 기록해야함(오버헤드 있음)
    • Locality를 고려한 알고리즘이기에 OPT 알고리즘에 근접하는 성능을 보임
    • 실제로 가장 많이 사용되는 기법

    • 문제점
      • 반복적으로 참조되는 page 갯수보다 할당받은 page frame 수가 적을 경우
        사실상 FIFO와 같아져 성능이 급격히 하락

      • 할당 전략에서 충분한 메모리를 할당하는 것으로 해결 가능

  • LFU(Least Frequently Used) 알고리즘
    • 참조된 횟수가 가장 적은 page를 교체
    • 각 페이지를 참조할 때 마다 참조횟수를 증가시켜야함(오버헤드 있음)
    • 최근에 적재된 page의 경우 참조횟수가 적어 이후에 참조될 가능성이 높음에도 교체될 수 있음

  • NUR(Not Used Recently) 알고리즘
    • 유사 LRU 알고리즘

    • Bit Vector를 사용하는 방식
      • 참조 비트(Reference Bit)와 갱신 비트(Update Bit)를 참조하여 최근에 참조되지 않은 비트일수록,
        참조 여부가 같다면 최근에 수정되지 않은 비트일수록 교체 우선도를 높게 본다.

      • Bit Vector의 주기적인 초기화가 필요

  • Clock 알고리즘
    • NUR을 현실적으로 구현한 예시
    • Reference Bit를 사용하지만 주기적인 초기화는 필요하지 않음
    • page frame을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 페이지를 결정

    • 동작 방식
      • 시계바늘이 특정 page의 reference bit를 체크했을 때 1이라면 0으로 초기화
      • 0이라면 그 페이지를 교체

  • Second Chance 알고리즘
    • Clock 알고리즘과 유사
    • Clock 알고리즘에서 Update Bit을 추가적으로 고려하는 방식
    • 참조나 수정 전적이 둘 중 하나라도 있다면 한번의 기회를 더 주는 알고리즘

    • 동작 방식
      • 시계바늘이 특정 page의 reference bit, update bit 쌍을 확인하여 (0, 0)이라면 교체
      • (0, 1)이라면 write back 하여 변경사항을 반영한 뒤 (0, 0)으로 초기화
      • (1, 0)이라면 (0, 0)으로 초기화
      • (1, 1)이라면 (0, 1)로 초기화

 

 

2. 가변 할당 방식(Variable Allocation)

  • 프로세스에게 할당하는 메모리 크기가 변할 수 있는 경우

  • WS(Working Set) 알고리즘
    • 현재 작업에 필요한 페이지의 집합 => 프로세스가 특정 시점에 자주 참조하는 page의 집합
    • working set의 페이지들을 메모리에 적재된 상태로 유지하는 방식
    • 시간적 지역성(locality)에 기반한 방식이기에 page fault 발생률이 감소하며 시스템 성능 향상을 기대할 수 있음
    • working set의 크기는 시간에 따라 변하지만 window_size 는 고정된 값을 가짐
    • window_size가 커질수록 working set의 크기도 커진다.(프로그램이 참조하는 페이지의 갯수 이하)
    • window_size를 적절한 크기로 설정하는 것이 working set 알고리즘의 성능에 큰 영향을 미침
    • 메모리의 반납이 새로운 page의 적재와는 관계없이 이루어짐(window의 상태에 따라 이루어짐)
    • page fault가 없더라도 working set을 지속적으로 관리해야한다는 오버헤드가 존재함

    • W(current_time, window_size)
      • current_time - window_size 부터 current_time 까지 참조된 페이지의 집합

    • Working Set Transition
      • loop중에는 working set이 loop에 필요한 만큼으로 유지
      • loop를 빠져나오는 순간에는 working set이 일시적으로 증가하는 경향을 보임(새로운 페이지를 참조하기 때문)
    • 성능평가
      • 단순히 page fault만 보기엔 할당한 페이지 프레임의 수가 다름
      • page fault의 처리비용과 page frame 할당 및 관리 비용을 복합적으로 고려하여 평가해야함

  • PFF(Page Fault Frequency) 알고리즘
    • Working Set 알고리즘의 단점인 page fault가 발생하지 않아도 지속적으로 working set을 관리해야하는
      오버헤드를 해결하기 위한 알고리즘

    • working set의 크기를 page fault 발생률에 따라 조정
      • page fault 발생률이 높다면 working set의 크기를 증가, 낮다면 working set의 크기를 감소

    • page fault가 발생할 때만 working set을 갱신하고 메모리를 할당하기 때문에 오버헤드가 적음

    • page fault 간의 발생시간이 일정 수치를 넘어서면 page fault 발생률이 적다고 판단하고
      반대로 일정 수치보다 낮다면 page fault 발생률이 높다고 판단한다.

  • Variable OPT 알고리즘
    • 가변 할당 방식에서의 최적 알고리즘

    • 평균 메모리 할당량과 page fault 발생 횟수를 모두 고려한 최적

    • 고정 할당방식의 OPT 알고리즘과 마찬가지로 page reference string을 미리 알고있어야 사용 가능하기에
      현실적으로 구현 불가능한 방식 

    • current_time 부터 current_time + window_size 까지의 page reference string에서 참조되지 않는 page를
      메모리에서 해제하고 참조되는 page만을 유지하는 방식

    • window_size의 최적값?
      • window_size가 커지면 page fault 발생률은 줄어들지만 메모리 유지비용이 증가한다.
      • window_size가 작아지면 page fault 발생률은 늘어나지만 메모리 유지비용은 감소한다.
      • (page fault 처리비용 / 단위 시간당 메모리 관리비용) 으로 정하는 것이 효율적

    • 실현 불가능한 알고리즘이지만 페이지 교체 알고리즘의 성능 평가를 위해 사용할 수 있음

1. Cost Model

  • 가상 메모리의 성능을 저하시킬 수 있는 요인들을 수치화하는 모델 => 비용(cost) 산출
    • Page Fault 발생빈도
    • Page Fault 발생률

  • 비용을 최소화하는 기법을 통해 가상메모리를 관리, 성능을 최적화할 수 있음
    => Page Fault 발생률을 최소화하는 전략이 필요

  • Page Reference String(d)
    • 프로세스 실행 중 참조한 페이지 번호 순서
    • 페이지의 총 갯수 N
    • 페이지 번호 r(1) ~ r(n)

  • Page Fault Rate
    • F = (발생한 페이지 폴트 발생 횟수) / (참조했던 페이지 수)

 

 

2. Hardware Components

  • 가상메모리 성능 향상을 위해 사용하는 하드웨어 장치

  • Address Translation Device
    • 주소 변환 장치
    • 주소 매핑 과정을 빠르고 효율적으로 수행하기 위해 사용
    • TLB(Translation Lookaside Buffer)나 Page Table 전용 레지스터 등

  • Bit Vectors
    • Page의 사용 상황에 대한 정보를 기록하는 비트
    • PMT 내부에 존재

    • Reference Bits(user bit)
      • 참조 비트
      • 해당 페이지 프레임이 최근에 참조되었는지를 기록
      • 프로세스에 의해 참조되면 1로 설정, 주기적으로 0으로 초기화
      • 참조 비트를 확인하는 것으로 해당 페이지가 최근에 참조된적이 있는지 확인 가능
      • 페이지 교체 알고리즘에서 교체할 페이지를 선택하기 위한 정보로 활용 가능

    • Update Bits(modified bits, write bits, dirty bits)
      • 갱신 비트
      • 해당 페이지 프레임의 데이터가 변경된 적이 있는지 기록
      • 변경사항이 있는 데이터는 swap device에 변경 내용을 반영해야하기 때문에 필요한 비트

 

 

3. Software Components

  • 가상 메모리 성능 향상을 위한 관리 기법

  • 할당 전략(Allocation Strategies)
    • 프로세스에게 얼마만큼의 메모리를 할당할 것인가
      • 고정 할당(Fixed Allocation)
        • 고정된 크기의 메모리를 할당

      • 가변 할당(Variable Allocation)
        • 프로세스 실행중에 할당된 메모리의 크기가 변경될 수 있음

    • 프로세스의 실행에 필요한 메모리 크기의 예측
      • 너무 큰 메모리를 할당하면 메모리가 낭비됨
      • 너무 작은 메모리를 할당하면 page fault 발생률이 증가하여 성능이 저하된다(Thrashing)

  • 적재 전략(Fetch Strategies)
    • 특정 페이지를 어느 시점에 메모리에 적재할 것인가

    • 요구 페이징(Demand Paging)
      • 프로세스가 페이지를 참조하려고할 때 적재
      • page fault 발생으로 인한 오버헤드 존재

    • 예측 페이징(Pre-Paging)
      • 참조될 가능성이 높은 page를 예측
      • 가까운 미래에 참조될 가능성이 높은 page를 미리 적재
      • 예측에 성공한다면 page fault로 인한 오버헤드가 없지만 실패하면 더 큰 오버헤드가 발생
      • 참조 가능성이 높은 page를 예측하기 위한 오버헤드가 존재
    • 실제로는 대부분 요구 페이징을 사용
      => 예측 페이징은 예측 자체의 오버헤드도 크고 예측에 실패했을 때의 리스크가 크기 때문

  • 배치 전략(Placement Strategies)
    • 비어있는 공간 중 어느 위치에 적재할 것인가
    • Paging System의 경우 페이지단위로 할당하기에 불필요한 기법
    • Segementation System의 경우 First-fit, Best-fit, Worst-fit, Next-fit 등의 기법이 존재

  • 교체 전략(Replacement Strategies)
    • 새로운 페이지를 메모리에 적재할 때, 메모리에 공간이 없다면 어느 페이지와 교체할 것인가
      => 어느 페이지를 해제할 것인가

  • 정리 전략(Cleaning Strategies)
    • 변경사항이 발생한 페이지(Dirty Bit이 1인 페이지)를 어느 시점에 write-back 할 것인가

    • Demand Cleaning
      • 해당 page가 메모리에서 해제될 떄 write-back 하는 방식

    • Pre Cleaning
      • 더이상 변경될 가능성이 없다고 판단되는 시점에 write-back 하는 방식

    • 적재 전략에서와 마찬가지로 실패했을 때의 리스크와 예측의 오버헤드로 인해
      Demand Cleaning 방식을 주로 사용한다.

  • 부하 컨트롤 전략(Load Control Strategies)
    • 시스템의 다중 프로그래밍 정도(multi-programming degree) 조절
    • 사실상 할당 전략과 같음(멀티프로그래밍 정도에 따라 할당할 수 있는 메모리 크기도 달라지기 때문)

    • 적정 수준의 multi-programming degree 를 유지
      • 부하가 너무 적은 상태일 경우 시스템 자원이 낭비되고 성능이 저하
      • 부하가 너무 큰 경우 자원에 대한 경쟁이 심화되고 성능이 저하
      • 과도한 page fault 로 인한 성능 저하가 발생할 수 있음(Thrashing)

 

 

4. 기타 고려사항

  • Page 크기
    • page 크기가 작을수록 보이는 경향
      • page 갯수증가 => page table 크기 증가 => page 관리 오버헤드 증가
      • 내부단편화 감소
      • 프로그램당 page 갯수가 증가하여 I/O 시간 증가
      • 서로 무관한 데이터가 하나의 페이지에 들어갈 가능성이 줄어들어 Locality 향상
      • page 갯수가 많기에 page fault 발생률도 증가

    • page 크기가 클수록 보이는 경향
      • page 갯수감소 => page table 크기 감소 => page 관리 오버헤드 감소
      • 내부단편화 증가
      • 프로그램당 page 갯수가 감소하여 I/O 시간 감소
      • 서로 무관한 데이터가 하나의 페이지에 들어갈 가능성이 늘어나 Locality 저하
      • page 갯수가 적기에 page fault 발생률 감소

    • 최근 시스템에서 page 크기가 갈수록 커지는 경향을 보이는 이유?
      • CPU의 처리속도는 빠른속도로 발전하고있지만 디스트(swap device)의 I/O 속도는 이를 따라가지 못함
      • 메모리의 크기 또한 빠르게 커지면서 page fault 처리비용도 빠르게 증가
      • 보다 적은 I/O시간, 보다 적은 page fault 가 최적의 성능을 내기 위해 가장 중요해짐

  • 프로그램 재구성(Program Restructuring)
    • 가상 메모리 시스템의 특성에 맞게 프로그램을 재구성
    • 사용자가 메모리 관리 기법에 대해 이해하고있다면 보다 효율적인 구조의 프로그램을 작성할 수 있음

  • TLB reach
    • TLB를 통해 접근 가능한 메모리의 크기
    • TLB entry number * page size
    • TLB reach가 커질수록 hit ratio는 증가, 성능도 증가한다.

+ Recent posts