19. 디스크 스케쥴링4

4) SCAN 스케쥴링

 (1) SCAN 스케쥴링
    * 디스크 해드가 어느 한쪽 방향의 끝으로 이동하면서 요청한 트랙을 처리하고 다시 다른 방향으로 이동하면서 처리하는 스케쥴링이다.
    * 53 ---> 0 ---> 199 ---> 0     / 화살표시는 방향을 의미함

 (2) C-SCAN 스케쥴링
    * 디스크 해드가 어느 한쪽 방향의 끝으로 이동하면서 요청한 트랙을 처리하고 다시 반대 방향의 끝으로 한 번에 즉시 이동한 다음 다시  요청한 트랙을 처리하는 스케쥴링이다.
    *  53 ---> 199 =점프=> 0 ---> 199

 (3) LOOK 스케쥴링
    * SCAN 스케쥴링과 동일하지만 어느 방향을 끝까지 해드가 이동하지 않고 요청작업이 있는 곳까지만 이동한다음 다시 다른 방향으로 해드가 움직이는 스케쥴링이다.
    *  53 ---> 34 ---> 183 ---> 34

 (4) C-LOOK 스케쥴링
    * C-SCAN 스케쥴링과 LOOK 스케쥴링의 결합된 형태이다.
      어느 한족 방향으로 이동하면서 요청작업을 처리하지만 디스크의 끝까지 이동하는 것이 아니라 마지막 요청 트랙까지만 이동하고 반대방향의 최초 요청 트랙으로 즉시 이동한뒤 다시 해드가 디스크 요청을 처리하는 스케쥴링이다.
    *  53 ---> 183 =점프=> 34 --->183

참고) SCAN 스케쥴링은 이동 거리는 많을 수 있지만 탐색시간이 최소가 되어 빠른 처리가 가능하다.
      SCAN 스케쥴링은 엘리베이터 알고리즘이라고도 한다.
      엘리베이터와 흡사한 이동특성을 보이고 있기 때문이다.

19. 디스크 스케쥴링3

3) SSTF(Shortest Seek Time First, 최소 탐색시간 우선 스케쥴링)

  * 제일 가까운 트랙의 요청부터 처리하는 스케쥴링

  * 예시)
    디스크 트랙:  0 ~ 199
    현재 해드의 위치: 53 트랙
    디스크 요청 트랙:  98  183  37  122  14  124  65  67

    총 이동거리: 236 트랙

  * 기아(Starvation)이 발생할 수 있다.
  * 가장 효과적인 방법은 아니다.
   

19. 디스크 스케쥴링2

2) FCFS(First-Come, First-Served, 선입선처리 스케쥴링)

  * 제일 먼저 요청한 작업부터 처리하는 스케쥴링이다.

  * 예시)
    디스크 트랙:  0 ~ 199
    현재 해드의 위치: 53 트랙
    디스크 요청 트랙:  98  183  37  122  14  124  65  67

    총 이동거리: 640 트랙

  * 가장 단순하면서 공정하긴 하지만 성능이 좋지 않다.
    디스크 요청이 흩어져 있는 경우 탐색시간이 오래걸려 처리량이 감소한다.

19. 디스크 스케쥴링1

1) 디스크 스케쥴링이란?
  * 디스크 엑세스 시간
   : 탐색 시간(Seek Time) - 디스크 해드가 해당 트랙으로 이동하는 시간
   : 회전 시간(Rotational Delay) - 디스크 회전 시간
   : 전송 시간(Transfer Time) - 디스크의 데이타가 읽혀지고 메인메모리에 전달되는 시간

  * 멀티프로그래밍 환경에서는 많은 프로세스들이 디스크 서비스(I/O 처리)를 받기위해 I/O Queue(입출력 대기 큐)에 대기하게 된다.

  * 운영체제는 어떤 방식으로 I/O Queue를 처리할 것인가를 결정해야 한다.
    이를 처리하는 알고리즘을 디스크 스케쥴링이라고 한다.

  * 디스크 스케쥴링의 알고리즘의 종류
   : FCFS(First-Come, First-Served, 선입선처리 스케쥴링)
   : SSTF(Shortest Seek Time First, 최소 탐색시간 우선 스케쥴링)
   : SCAN 스케쥴링 (또는엘리베이터 알고리즘; Elevator Algorithm)
     - 순수 SCAN 스케쥴링
     - C-SCAN 스케쥴링
     - LOOK 스케쥴링
     - C-LOOK 스케쥴링

18. 파일 할당4

4) 색인 할당(Indexed Allocation)
  * 파일 1개당 1개의 인덱스 블럭을 지정한다.
  * 인덱스 블럭에 해당 파일에 대한 포인터 정보를 저장해 놓는다.
  * 디렉토리는 인덱스 블럭을 가리키고 있는다.
    (연결 할당에서는 최초 위치의 블럭을 가리키고 있음)
  * Unix, Linux 등에서 사용하고 있다.

  * 장점
   : 순차 접근(sequential access)이 가능하다.
   : 직접 접근(Direct access)이 가능하다.
   : 외부 단편화가 없다.

 * 단점
  : 파일 마다 인덱스 블록을 할당해야 하기 때문에 부수적 저장공간의 손실이 있다.
   1 byte 파일 저장하기 위해
    => 데이터 블록 1개 + 인덱스 블록 1개가 필요하다. 즉, 내부 단편화가 크다.

 * 파일의 최대 크기
   : 만약 1 block이 512 byte 이고 인덱스 1개가 4 byte 라면
     512 / 4 = 128개의 인덱스를 가질 수 있다.
    그렇다면 최대 파일 사이즈는 128 X 512 = 64 KB 가 된다.
   : 해결 방법: Linked, Multilevel index, Combined 등으로 인덱스 블럭을 다수개 두고 서로 연결 지어 놓는다.

18. 파일 할당3

2) 연결 할당(Linked Allocation)

  * 파일 => 데이터가 저장된 블럭들의 연결된 집함
  * 파일 디렉토리(directory)는 제일 처음(시작) 블록만 가리킨다.
   그리고 각 블록들은 다음 블럭의 위치(포인터)를 가지고 있다.

  * 장점
   : 새로운 파일 생성시 비어있는 임의의 블록을 첫 블록으로 결정한다.
   : 파일이 커지면 다른 블록을 할당하고 연결을 지어준다.
   : 따라서 외부 단편화가 없다.

  * 단점
   : 순차 접근(sequential access)만 가능하고 직접 접근(Direct access)은 불가하다.
   : 포인터 저장을 위해 4바이트 이상 손실이 있다.
   : 낮은 신뢰성 - 중간 블럭에 bad sector가 발생하여 포인터가 끊어지면 그 이하는 접근이 불가능 하다.
   : 느린 속도 - 디스크 헤더가 블럭들을 읽기 위해 많이 움직여야 한다.

 * FAT 시스템
   : MS사에서 연결할당을 응용하여 속도가 느리고 낮은 신뢰성을 보안하여 자체적으로개발한 파일 시스템이다.
   : MS-DOS, OS/2, Windows 등에서 사용
   : FAT = File Allocation Table
     즉, 파일의 pointer를 모아둔 테이블
   : 포인터들만 모은 테이블 (FAT) 을 별도 블록에 저장
   : 직접 접근(Direct access)이 가능하다.
     FAT의 포인터를 찾아서 해당 디스크위치로 해드를 이동해서 원하는 데이터를 읽는다.
   : FAT은 일반적으로 메모리 캐싱 즉, 부팅시에 FAT이 메모리에 로드된다.
    따라서 FAT을 읽는 속도는 빠르고 수시로 업데이트된다.
   : FAT 내용만 있으면 중간에 bad sector가 있어도 다 읽을 수 있습니다.
   : FAT이 소실될 것을 대비하여  FAT 복사 본을 따로 저장해 둔다.
     즉, 기본적으로 FAT은  2개 이다.
   : 파일을 디스크에서 읽는 속도는 느릴 수 밖에 없다. 그러나 외부 단편화는 해결된다.
   : FAT 을 위해 어느 정도 공간을 할당하느냐에 따라 FAT 12, FAT 16, FAT 32 로 구분

18. 파일 할당2

1) 연속 할당(Contiguous Allocation)

  * 각 파일에 대해 디스크 상의 연속된 블록을 할당
   즉, 같은 파일은 연속된 블럭에 저장이 되어진다.
  * 옛날 IBM 에서 사용

  * 장점
   : 디스크 헤더의 이동 최소화 = 빠른 i/o 성능
   : 동영상, 음악, VOD 등에 적합
   : 순차 접근 즉, 순서적으로 읽을 수 있음 (Sequential access)
   : 직접 접근 즉, 특정 부분을 바로 읽을 수 있음(Direct access)
     순서적으로 저장되어져 있기 때문에 바로 원하는 위치에 접근이 가능하다는 의미임.

 * 단점
   : First-fit, Best-fit, Worst-fit 문제 발생
   : 외부 단편화가 심하다. 사용할 수 없이 버려지는 공간이 많아지게 된다.
   : 압축(compaction) 가능하지만 시간이 오래 걸림(초창기 MS-Dos)
   : 파일의 사이즈가 계속 커질 경우 처리하기 어렵다.

 참고) 이러한 단점 때문에 대안으로 연결 할당 출현.