운영체제 (10주차 - 디스크 스케줄링과 파일 시스템)

○ 디스크의 정보는 드라이버 번호, 디스크 번호, 표면 번호, 트랙 번호 등으로 나누는 디스크 주소로 참조

- 각 트랙은 다수의 섹터(sector)로 구성

     + 각 섹터들은 일정한 공간 (inter-sector gab)을 두어 구분한다.

 

 

• 디스크 주소 예제(문제)

 

어떤 자기 디스크 장치에 있는 양쪽 표면이 모두 사용되는 8개의 디스크가 있는데, 각 표면(2개)에 는 16개 트랙과 8개의 섹터가 있다. 트랙 내의 각 섹터에 하나의 레코드(1개) 가 있다면 디스크 내의 레코드에 대한 주소 지정에는 몇 비트가 필요한가?

 

레코드 총 수 = 디스크 수 x 면 수  x 면당 트랙 수 x 트랙 당 섹터 수  x 섹터당 레코드 수

= 8 x 2 x 16 x 8 x 1 = 2048개.

 

즉, 이 레코드에 대한 주소 지정을 하기 위해서는 2048개의 레코드가 저장 되어 있으므로

> 2048 = 2의 11승 => 11개 비트로 레코드 주소를 식별한다.

 

 

 

 

 

 

 

디스크 구조(디스크 접근 시간)

 - 읽은 데이터를 주기억장치에 전달하는데 소요 시간

- 탐색 시간, 회전 지연 시간 , 전송 시간의 총합

 

 

                                                                                                 

디스크 접근 시간 = 탐색 시간 + 회전 지연 + 데이터 전송시간

                                                                                                 

 

 

운영체제

 

- 디스크 엑세스 요청을 스케줄 하여 디스크 처리하는 평균 시간을 향상 시킴.

- 처리량을 최대화하고 평균 반응시간을 최소화하면서 탐색 시간 최소화하도록 해야 함.

 

즉,

 

 

 

디스크 스케줄링(disk scheduling)

 

 

★ ★ ★ ★ ★ 탐색 시간(seek time) ★ ★ ★ ★ ★

- 회전 지연 시간에 비하여 훨씬 많은 시간이 소요되기 때문

- 실제 회전 지연시간의 감소는 시스템 전체의 생산성을 증진시키는 데 크게 영향을 주지 못한다.

 

 

일반적으로 디스크 스케줄링 방법은 탐색 시간을 최소화 하는 방법을 이용한다.

 

★ ★ ★  디스크 스케줄링(disk scheduling)의 종류

 

• FCFS(First Come First Served) 스케줄링

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

• SCAN 스케줄링 및 LOOK 스케줄링

• C-SCAN 스케줄링 및 C-LOOK 스케줄링

 

 

 

 

FCFS 풀이 . 

 

진짜 제일 간단하다. > 그냥 큐에 올라가있는 순서대로 이동함.

 

초기의 헤드가 트랙 50에 있을 경우니까 = 현재 디스크 헤드 위치는 50번 트랙

 

시작은 50 에서 시작

 

큐 = 105, 180, 40, 120, 10 ,125, 65, 70 

 

FCFS 스케줄링를 이용한 총 이동 순서 : 50 -> 105 -> 180 -> 40 -> 120 -> 10 -> 125 -> 65 -> 70이다. 

 

50  > 105 를 가면 , 55를 갔으니까 이동거리 55

 

105  > 180 을 가면 75를 갔으니까 이동거리 75

 

180 > 40을 가면 140을 이동했으므로 이동거리 140

 

이렇게 계속하면 D = 55 + 75 + 140 + 80 + 110 + 115 + 60 + 5 = 640이므로, 이동거리는 D는 640이다.

 

 

 

- 현재 헤드의 위치에 가장 가까운 요청을 먼저 서비스하는 기법.

- SJF 알고리즘 형태

- 큐의 요구들을 처리하는 동안 헤드의 이동거리 극소화

- FCFS 보다 처리율이 높고 평균 응답시간이 짧음

 

 

SSTF 스케줄링 풀이.

 

이것도 간단하다.

현재 헤드의 위치에 가장 가까운 요청을 먼저 서비스하는 기법. 이니까

 

현재 위치 50에서 제일 가까운 40으로 출발.

40에서 제일 가까운 65로출발 > 70 > 105 > 120 > 125 > 180 > 10(남은 짬처리)

 

50에서 40이 10차이나는거리이고, 40에서 65는 25차이, 10으로 갈라면 30 거리가 차이나므로, 40 > 65가 맞다.

 

즉 이렇게 이동하여 순서는.

50 > 40 > 65 > 70 > 105 > 120 > 125 > 180 > 10 으로 간다.

 

총 이동거리 D : ( 50 - 40 ) + ( 40 - 65 ) + (65 - 70) + (70 - 105) + (105 - 120) + (120 - 125) + (125 - 180) + (180 - 10)

= 10 + 25 + 5 + 35 + 15 + 5 + 55 + 170 (-는 이동거리 이므로 +로 치환.) = 320 이 된다!!!

 

 

- 진행 방향 상의 가장 짧은 거리에 있는 요청을 서비스하는 기법

- 현재 큐에 대기중인 요구들 중에서, 현재 헤드의 진행 방향으로 현재 헤드의 위치와가장가까운 요구를 먼저 서비스하고, 마지막 실린더에 도착했을 때에 방향을 전환하는기법

 

현재 헤드의 진행 방향 -> 헤드의 위치와 가장 가까운 요구 -> 마지막 실린더 도착시 방향을 반대로 바꿔서 간다. <--

 

요게 중요함 ★ > –>

헤드가 디스크의 한쪽 끝에서 시작하여 반대편 끝까지 움직이고 끝에서 역으로 하여다시계속 처리하는 방식

 

SCAN 알고리즘은 엘리베이터 동작과 유사하기 때문에 '엘리베이터' 알고리즘이라고 부름

-SSTF 기법과 비슷하다.

• SSTF 기법 사용시 응답시간에 대한 예측성이 저하되는 단점 해결

• 대체적으로 단위 시간당 처리량, 평균 응답 시간의 면에서 우수함

• 실제 디스크 시스템에서 사용되는 스케줄링 기법들의 근간이 됨

 

 

 

SAN 스케줄링 풀이 .

 

이것 또한 간단하다.

 

큐 = 105 , 180 , 40 , 120, 10 , 125, 65 , 70

 

현재 큐 50이면,

진행 방향 상의 가장 짧은 거리에 있는 요청을 서비스하는 기법이므로,

50에서 가장 짧은 거리에 있는 40을 요청.

 

50 > 40으로 가고 진행 방향에있는 10으로 이동후 65로 꺾는 것이 아니라. 0을 찍어야된다.

 

<★ 기말고사에서 이동 순서 0 들어간거 본다고 함 조심!! ★>

 

0을 찍고 이동 방향을 <- 에서 -> 으로 전환후 0 에서 제일 가까운 65로 이동-> 가까운 70 -> 105 -> 120 -> 125 -> 180 으로 이동한다.

 

즉, 간단하게 정리하자면 초기 큐에서 제일 가까운 큐로 이동하면 그 이동방향 그대로 가까운 곳으로 이동

50 > 40 > 10 으로 이동후 10에서 제일 가까운 곳은 65가 아니라 0(벽)을 찍고 반대 방향으로 돌려, 65로 이동한다.

약간 벽돌깨기 게임처럼 팅겨져 나오고 -> 반대 방향에서 제일 가까운 65로 감.

 

 

즉, 이동 순서 = 50 > 40 > 10 > 0 > 65 > 70 > 105 > 120 > 125 > 180 끝.

이동 거리 D =

( 50 - 40 ) + ( 40 - 10 ) + (10 - 0) + (0- 65) + (65- 70) + (70- 105) + (105- 120) + (120- 125) + (125-180)

= 10+30+10+65+5+35+15+5+55=230 (-는 이동거리 이므로 +로 치환.) = 230 이 된다!!!

 

 

 

 

- C-LOOK은 한쪽 방향으로 헤드를 이동하면서 ‘진행 방향’상의 가장 짧은거리에 있는 요청을 처리

 

– 한쪽 끝에 다다르면 다시 처음 시작 방향으로 이동하여

서비스하는 기법으로 끝에서다시같은 방향으로 처리를 진행하는 방식

 

 

 

C-LOOK 스케줄링 풀이.

 

1. 한쪽 방향으로 헤드를 이동하면서 ‘진행 방향’상의 가장 짧은거리에 있는 요청을 처리

즉, 시작할때 진행방향은 -> 방향이니까 50 에서 앞에있는 65로 이동 뒤에 40으로 가지않음.

 

2. 한쪽 끝에 다다르면 다시 처음 시작 방향으로 이동하여 서비스, 끝에서 다시 같은 방향으로 처리를 진행하는 방식임.

-> 방향으로 앞에있는 모든 큐를 지나감. 50 > 65 > 70 > 105 > 120 > 125 > 180

근데?! 이제 앞에 더 없넹!?

그럼 C-SCAN은 199를 찍고 10으로 이동하겠지만! C-LOOK은 다시 처음시작으로 간다고함.

180을 찍고 제일 왼쪽(처음)에 있는 10으로 이동 후 40으로 마무리..

 

이동 순서 : 50 > 65 > 70 > 105 > 120 > 125 > 180 > 10 > 40

 

이동 거리 D :

( 50 - 65) + ( 65- 70 ) + (70- 105) + (105- 120) + (120- 180) + (180- 10) + (10- 40)

= 15+5+35+15+ 55 + 170 + 30 = 325 끝.

 

이미지도중에 125 -> 105로 다시 가는데 이유를 모르겠음..

 

 

10주차 - 1교시 학습점검!

 

 

 

 

1. SCAN = 70 > 60 으로 이동했으니까 방향성은 <-이쪽이다 그래서 60 보다 큰값보다는 작은 값중에서 가까운걸 고르면 디는데 20, 50 , 95, 100 이니까 50 즉, 2번이다.

 

2. SSTF = 그냥 가까운 애들 고르면됨. 현재 헤드위치 100번일때 큐에있는 값중 가까운건 105 > 90 > 89 >75 순서니까 네 번쨰 즉, 3번이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

굿,,,,