[2022-2] 운영체제 - 221117

1) 페이지 교체 알고리즘
→ 새로 적재될 페이지 공간 확보를 위해 가상공간으로 내보낼 페이지를 결정하는 것
▶ 페이지 부재 (page fault) : 가상 주소를 호출된 페이지가 페이지 프레임에 없어 가상공간에서 불러와야 하는 경우
   → 새로 불러온 페이지를 탑재하기 위해 기존의 페이지를 제거(희생)해야 함.

2) 알고리즘 종류 → 2022-2 기말고사 출제
  ① FIFO (First In First Out) 알고리즘
- 각 페이지가 주기억장치에 적재될 때, 타임스태프 기록
- 교체 대상 선정시, 가장 먼저 들어온 페이지를 결정
- 이해하기 쉽고 설계가 간단 
- | 그림 4-17 | FIFO 알고리즘 참고

  ② 최적 교체 (Optimal Replacement) 알고리즘
- 가장 오랫동안 사용되지 않을 페이지를 교체
   → 가장 효율적이지만 구현하기에 비현실적
- | 그림 4-19 | 최적 교체 알고리즘 참고

  ③ LRU (Least Recently Used) 알고리즘
- 교체할 시점에서 가장 오래전에 사용된 페이지를 교체
- 오래되었다는 이유만으로 교체 대상이 되는 것은 경우에 따라 불합리 할 수 도 있음.
- | 그림 4-20 | LRU 알고리즘 참고

  ④ 2차 기회 (Second Chance) 알고리즘
- 한 번 참조된 페이지는 다음 희생 대상에서 살아 남을 수 있는 기회를 부여
- 각 페이지의 참조 여부를 기록하는 참조 비트(reference bit)를 운영
- | 그림 4-21 | 2차 기회 알고리즘 참고

  ⑤ LFU (Least Frequently Used) 알고리즘
- 사용 빈도 수가 낮은 페이지를 교체 

3) 스레싱 (thrashing)
- 페이지 부재 증가에 따른 페이지 교체 비용 증가로 시스템 효율이 낮아지는 경우
- | 그림 4-22 | 스래싱 참고
- 스래싱을 방지하기 위해서는 효율적 수행을 위한 적절한 페이지 프레임 수 (작업세트 : working set)를 알 필요가 있음.
- 작업 세트 (working set) : 프로세스에 의해 자주 참조되는 페이지 집합체로 메모리 참조 패턴 분석이 필요하다. (| 그림 4-23 |, | 그림 4-24 | 참고)
- 구역성 (locality) : 프로세스가 기억장치 내의 모든 정보를 균일하게 참조하지 않는 성질
     ▶ 시간 구역성 (temporal localtiy) : 최근에 참조된 기억장소가 가까운 미래에도 계속 참조될 가능성 높음 (loop, stack, counting 변수 등)
     ▷ 공간 구역성 (spatial locality) : 어떤 기억장소가 참조되면 그 근처의 기억장소가 참조될 가능성이 높음 (배열, 순차 코드 실행, 서로 관련된 변수들)
- 페이지 부재율 : 적절한 페이지 부재율을 유지하는 것이 효율적인 운영에 도움 (| 그림 4-25 | 페이지 부재 빈도 참고)
    ▶ 높은 부재율 : 프로세스에 더 많은 페이지 프레임 할당 필요
    ▷ 낮은 부재율 : 페이지 프레임을 줄여 다른 프로세스에 할당 필요

=========== ↑ 4장 (가상 메모리) 마무리 ↑ ===========

=========== ↓ 5장  (디스크 스케줄링 파일 시스템) ↓ =========== 

1) 개요 
- 다중 프로그래밍 시스템(운영체제)에서 보조기억장치의 효율적 운용은 매우 중요
- 파일시스템 - 운영체제의 동작을 관찰하기 좋은 부분
   → 파일 : 프로그램과 데이터 저장이 되는 하나의 형식

2) 디스크 구조
- 트랙(Track) : 중심축에서 동심원으로 나누어진 것
- 실린더(Cylinder) : 여러 플래터의 같은 트랙들을 가상적으로 묶은 것 (원통형의 모습)
- 섹터(Sector) : 디스크의 각 면을 부채꼴 모양으로 나눈 것 / 디스크 섹터라고도 함
- 블록(Block) : 트랙과 섹터가 교차하여 생기는 단위 / 섹터 또는 트랙 섹터 이라고도 함
- 탐색 시간 (seek time) : 헤드가 읽기/쓰기를 원하는 실린더로 이동하는 시간 
- 회전 지연 시간 (rotational latency time) : 해당 실린더로 헤더가 이동 후에, 원하는 블록(섹터)가 헤드까지 오는 시간
→ | 그림 5-1 | 이동 헤드 디스크의 구성도 / | 그림 5-2 | 디스크 접근의 구성 단계  참고
- 등각 속도 (CAV : Constant Angular Velocity : 30회전/초)

3) CD-ROM 
- 저렴한 비용으로 많은 데이터 저장 (650MB)
- CD-ROM 안쪽에서 시작하여 바깥쪽으로 계속 이어지는 나선형 트랙 (동심원 아님)
- 등선 속도 (CLV : Constant Linear Velocity : 10~30회전/초) 
→ 바깥쪽은 느리게, 안쪽은 빠르게 회전
→ | 그림 5-3 | CAV와 CLV의 구조 참고

4) 디스크 스케줄링
- 디스크 입출력 시간 동안 프로세스는 대기상태이므로 최대한 효율적 운용이 중요
→ 다중 프로그래밍 시스템에서는 특히 중요
- 회전지연시간보다 탐색 시간이 훨씬 많이 걸리므로 탐색 시간 최소화가 관건
  ① FCFS (First Come First Served) 스케줄링
     - 가장 간단하며, 요청 순서대로 서비스하며 일반적으로 효율이 낮음.
     - | 그림 5-4 | FCFS 스케줄링 참고

  ② SSTF (Shortest Seek Time First) 스케줄링
     - 현재 헤드 위치에서 가장 가까운 요청을 먼저 서비스
     - 가장 자리(안쪽, 바깥쪽)보다는 가운데 트랙이 유리 → 응답 시간 편차 발생 가능
     - FCFS보다 높은 처리율, 평균 응답시간 짧음 → 기근 (starvation) 현상 발생 가능
     - | 그림 5-5 | SSTF 스케줄링 참고

  ③ SCAN 스케줄링
     - SSTF와 기본적으로 비슷하지만, '진행방향' 상의 가장 가까운 요청을 먼저 서비스
     - 엘리베이터 동작과 유사하여 '엘리베이터 알고리즘'이라고도 함.
     - | 그림 5-6 | SCAN 스케줄링 참고

  ④ LOOK 스케줄링
      - SCAN과 비슷하지만, 진행 방향의 끝까지 가지 않고 진행 방향의 마지막 요청까지만 이동
      - 요청과 무관한 이동을 하지 않은 만큼 SCAN에 비해 효율적

  ⑤ C-SCAN (Circular-SCAN) 스케줄링
       - SCAN과 유사, 한쪽 끝에 다다르면 반대방향으로 서비스하며 이동하지 않고 다시 처음에서 시작
       - 요청을 서비스 하는 방향은 고정
       - SCAN의 불공정대한 대기시간을 개선하여 균등화 하는 방식
       - Circular 환형 ?
      - | 그림 5-7 | C-SCAN 스케줄링 참고

   ⑥ C-LOOK 스케줄링
      - | 그림 5-8 | C-LOOK 스케줄링 참고

※ 한 면의 수와 실린더의 수는 같음.