개발공부 기록지

작업을 수행할 디스크를  선택하는 결정 +
하나의 디스크에서의 입출력 요청의 처리 순서 결정

(목표)

1. 많은 요청을 동시에 처리 할 수 있는 확장성있는 서비스

-> 각 디스크간의 부하균형(load balancing)을 이루는 것이 중요

2. 전력 소모를 줄이는 것

마치 그룹 엘레베이터 시스템 과 유사

-> 여러 대의 엘레베이터가 하나의 시스템에서 공동으로 운영

(목표) 다수의 승객이 오래 기다리지 않고 빠른 서비스를 받을 수 있도록하는 시스템의 확장성(scalability)

디스크에 대한 접근시간(access time)은 

• 탐색시간(seek time) :  헤더가 실린더에 도착하기까지 걸리는 시간
• 회전지연시간(rotational latency) : 섹터가 헤더에 도착하기까지 걸리는 시간
• 전송시간(transfer time) : 섹터가 헤더에 도착 후 실제로 데이터가 읽고 쓰는데 걸리는 시간
• 기타 등등

에 의하여 결정된다.

이 중에서 회전지연시간과 전송시간은 통제하기 힘든 부분이므로

운영체제는 탐색시간을 줄이기 위해 헤드의 움직임을 최소화 하는 스케줄링 작업을 함

1) FCFS(First Come First Service) 스케줄링

디스크에 먼저 들어온 요청을 먼저 처리 하는 방식 -> 비 효율적

( 이유 ) 입출력 요청이 디스크의 한쪽 끝을 처리한 후 반대쪽 끝을 처리해야 하는 경우 발생 -> 탐색시간이 비효율적으로 증가

2)SSTF(Shortest Seek Time First) 스케줄링

현재 위치로부터 가장 가까운 위치에 있는 요청을 먼저 처리

(+) 헤드의 이동거리 감소 -> 효율성 증가

(-) 기아현상(starvation)발생

--> 헤드의 이동거리 측면에서 가장 우수한 알고리즘은 아님

3)SCAN 알고리즘

헤드가 원판의 안쪽 끝과 바깥쪽 끝을 오가며 그 경로에 존재하는 모든 요청을 처리

버스가 일정한 경로를 따라 정류장을 도는 것과 유사한 방식

지그재그 방식 

(+) 효율성과 형편성을 만족시키는 알고리즘

(+) 한쪽 끝에서 다른쪽 끝으로 한번 이동으로 현재 큐에 있는 모든 요청 처리 가능

(+) 이동 거리측면에서 효율적

(+) 기아현상 발생 방지

(-) 공평성을 만족 시키지 못하는 알고리즘 - 실린더 위치의 기다리는 시간

4) C-SCAN(Circular-SCAN) 알고리즘

SCAN과 같은 방식으로 요청을 처리하는 알고리즘이지만 움직이는 방향이  다름

한쪽끝에서 다른쪽 끝으로 이동 후 다시 한쪽 끝에서 이동 시작

(+) 균일한 탐색시간 : 탐색시간의 편차가 줄어듬

(-) SCAN 보다 이동거리 증가

5) LOOK 과 C-LOOK 알고리즘

SCAN, C-SCAN 과 헤드의 이동방식이 유사한 알고리즘

이동방향: LOOK ( = SCAN), C-LOOK(= C-SCAN)

차이점:  가는 방향에 대기 중인 요청이 없으면 이동방향을 바꾼다는 점

--> 디스크 입/출력이 많은 시스템에서 언급한 기법들 중 가장 효율적인 방식

디스크의 물리적 구조는 원판형이지만

디스크는  일정한 크기의 저장 공간들로 이루어진 1차원 배열로 취급

• 논리블록(logical block) : 일정한 크기의 저장 공간
        디스크에 저장될 때 논리블록 단위로 저장
               -> 저장시 해당 블록의 인덱스 색인(입/출력 작업을 위함)  <ex> 섹터 0
        디스크에서 입/출력할 때도 논리블록 단위로 전송
• 섹터(sector) : 하나의 논리블록이 저장되는 물리적 공간의 이름
      1 : 1 = 논리블록 : 섹터

프로세스가 원활하게 수행되기 위해서는 일정 수준이상(최소한)의 페이지 프레임 할당이 필요

최소한의 프레임을 할당 받지 못한 경우 -> 스레싱(thrashing)현상 발생

•  집중적으로 참조되는 페이지 부재율 상승 -> CPU 이용률 급격히 감소 

스레싱이 발생하는 시나리오

• CPU 이용률이 낮아서 준비 큐가 비는 경우가 발생
  • (의미) 메모리에 올라와 있는 프로세스의 수가 너무 적어
    모든 프로세스가 I/O 작업을 함으로써 준비 큐가 비는 현상이 발생
  • CPU의 이용률이 낮다 = 일을 안한다
    -> 운영체제가 메모리에 올라가는 프로세스의 수가 적다고 판단
    -> 메모리에 프로세스를 추가
    -> 동시에 올라가 있는 프로세스의 수(multi-programing Degree: MPD)가 증가
    ->  MPD가 과도하게 많아지면
    -> 각 프로세스가 최소한의 프레임을 할당받지 못함
    -> 페이지 부재가 발생
    -> 디스크 I/O 수행
    -> 문맥교환을 통해 다른 프로세스에게 CPU 이양
    -> 다른 프로세스도 최소한의 프레임을 할당 받지 못함
    -> 페이지 부재
    -> 디스크 I/O 수행
    -> 문맥교환을 통해 다른 프로세스에게 CPU 이양
    이런 식으로 준비 큐에 있는 프로세스가 CPU를 할당 받아도 페이지 부재처리하기에 바빠짐
    이 때문에 CPU의 이용률이 낮아짐

MPD를 조절하면서 CPU 이용률을 높이는 방법

1) 워킹셋 알고리즘 (working-set algorithm)

• 워킹셋 = 프로세스가 일정 시간동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 페이지들의 집합
• 워킹셋이 메모리에 올라갈 수 있는 경우에만 그 프로세스에 메모리 할당
• 불가능한 경우는 디스크로 스왑아웃
• 한꺼번에 메모리에 올라가야 할 페이지들의 집합을 결정하는 방법
  • 워킹셋 윈도우(△) 사용 
    • 페이지가 참조된 시점 부터 △ 시간 동안은 메모리에 유지하고, 그 시간이 지나면 메모리에서 지움
    • △ 의 크기를 잘 결정하는 것이 중요
      • 너무 작으면 - 지역성 집합을 모두 수용 못할 경우 발생
      • 너무 크면 - MPD가 감소해 CPU의 이용률 낮아지는 경우 발생
• 메모리 내에 있는 모든 프로세스에 프레임을 다 할당한 후 프레임이 남으면?
  • 스왑아웃 되었던 프로세스에게 프레임 할당

2) 페이지 부재 빈도 알고리즘 (page-fault frequency scheme)

• 페이지 부재율을 주기적으로 조사하고 이에 따라 각 프로세스에 할당할 메모리의 양을 동적으로 조절
  • 설정한 상한 값 이상 -> 해당 프로세스에 프레임을 추가로 할당
  • 설정한 하한 값 이하 -> 해당 프로세스에 필요이상으로 프레임이 할당 된것으로 간주하여 할당된 프레임의 수 줄임
• 메모리 내에 있는 모든 프로세스에 프레임을 다 할당한 후 프레임이 남으면?
  • 스왑아웃 되었던 프로세스에게 프레임 할당

전역교체

모든 페이지 프레임이 교체 대상

전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 이용하여 할당되는 메모리 양이 가변적으로 변하는 방법

ex) LRU, LFU, 클럭등의 알고리즘을 물리적 메모리내에 존재하는 전체 페이지 프레임들을 대상으로 적용

지역교체

현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정

프로세스마다  페이지 프레임을 미리 할당

ex) LRU, LFU 등의 알고리즘을 프로세스별로 독자적으로 운영