운영체제 파일시스템에서 접근 시간, 디스크 스케줄링을 위한 알고리즘, I/O 시스템이란?

2019. 5. 13. 22:31

안녕하세요? 허니입니다. 운영체제 파일시스템에서 Access time, 디스크 스케줄링을 위한 알고리즘, I/O 시스템에 대해서 포스팅 하도록 하겠습니다. 학생이나 연구원분들에게 많은 도움이 될 것이라고 생각하며 언제든지 질문은 환영입니다.

오늘의 주제

접근 시간(Access time)

seek time

rotational delay time

transfer time

디스크 스케줄링을 위한 알고리즘

FCFS

SSF(Shortest Seek Time First Scheduling) 최단 탐색 시간 우선 스케줄링

Scan algorithm

Look

I/O 시스템이란 무엇인가?

Access time

앞서 우리는 read/write 명령문을 통해 필요한 데이터가 어디에 위치해 있는지를 확인하게 되면 access arm에 부착된 read/write 헤드는 해당 데이터가 위치한 디스크공간을 찾아가 명령문을 처리하게 된다고 공부하었다. 그렇다면 read/write 명령을 받은 후 헤드가 이동하여 데이터를 전송하는데 쓰이는 시간, 즉 access time은 어떻게 계산되는 것일까. 이러한 access time은 탐색시간(seek time), 회전지연시간(rotational delay time), 전송시간(transfer time)의 각각의 3단계로 나뉘어지게 된다.

탐색시간(seek time)이란 read/write 헤드를 데이터가 저장되어 있는 트랙위치로 이동시키는데 소요되는 시간을 말한다. 디스크 상에 인접한 실린더를 탐색하게 되는 최소거리 이동시간과 최대거리 이동시간을 고려한 평균으로 탐색시간은 계산된다. 디스크마다 차이가 있지만 보통 20ms 정도의 시간이 걸린다.

회전지연시간(rotational delay time)이란 read/write 헤드를 데이터가 위치하는 트랙으로 이동시킨 순간부터 원하는 섹터에 헤드가 다다를 때까지 소요되는 시간을 의미한다. 즉 디스크가 도는 속도에 따라 회전지연시간은 차이가 나지만 보통 회전지연시간은 3200rpm이 소요된다.

전송시간(transfer time)이란 read/write 헤드가 찾은 데이터를 실제로 디스크로부터 사용자의 버퍼로 보내지는데 소요되는 시간을 의미한다. 보통 1바이트를 전송하는데 0.1마이크로 세컨이 걸린다.

디스크 스케줄링

앞서 access time의 3가지 각기 다른 구성시간을 살펴보았는데 이중 탐색시간이 가장 많은 시간을 소요한다는 것을 발견한 시스템 설계자들은 탐색시간을 최소화하기 위해 디스크 내부에서 헤드를 어떻게 스케줄링 할 것인지 연구하게 되었다. 바로 수십, 수백 개의 데이터를 찾는 요구가 떨어졌을 때 어떻게 디스크 스케줄링을 해야만 최소의 시간에 가장 많은 데이터를 처리할 수 있을까를 생각하게 된 것이다. 디스크 스케줄링은 FCFS (First Come First Service), SSF(Shortest Seek Time First Scheduling), Scan algorithm, Look등의 방법이 있다.

FCFS (First Come First Service) 선도착 선처리
FCFS는 요구가 들어온 순서대로 헤드를 움직이는 방법이다. 이 방법의 가장 큰 장점은 프로그래밍하기 간단하고 사용자들에게 공평하다는 것이다. 먼저 요구되어진 데이터를 가장 먼저 찾는다면 불만을 표시할 사람은 없을 것이다. 그러나 불만이 없다고 하여 그것이 최선의 방법일 수는 없다. FCFS의 방법은 데이터 처리 요구가 상호 연관성이 없기 때문에 임의로 해드가 움직여야 한다. 예를 들어 번호가 0부터 99인 100개의 트랙이 있다고 하자. 다음과 같은 순서로 (12, 45, 80, 16, 30) 데이터를 찾는 요구가 발생했을 때 헤드의 이동 거리를 계산해보자.

* 헤드의 이동거리
   12---45   33
   45---80   35
   80---16   64
   16---30   14

* 총 이동거리= 146
* 평균이동거리 = 146/4 =36.5

그림 64 FCFS

바로 요구 순서에 맞춘 두 개의 데이터 사이에 거리가 멀수록 디스크 헤드의 이동 거리가 멀어져 암의 이동시간도 회전지연시간도 길어질 수밖에 없는 것이다. 이러한 문제에 부딪힌 시스템 설계자들은 다음과 같은 방법을 고안해 내었다.

SSF(Shortest Seek Time First Scheduling) 최단탐색시간 우선스케줄링
SSF는 현재 헤드의 위치로부터 가장 가까운 실린더에 놓인 데이터를 먼저 처리하는 방법이다. 바로 FCFS의 커다란 단점이었던 헤드의 이동거리를 SSF 알고리즘에서는 최소화하게 되는 것이다. 12에서 45로 이동하기 전에 중간에 위치한 16과 30을 처리하게 되면 탐색시간(seek time)을 FCFS에 비해 단축할 수 있다.

FCFS에서와 같은 예를 이용해 실제 계산을 한번 해보자.
(12, 45, 80, 16, 30)

* 헤드의 이동거리
   12---16    4
   16---30   14
   30---45   15
   45---80   35

* 총 이동거리= 68
* 평균이동거리 = 68/4 =17

그림 65 SSF

FCFS와 SSF 두가지 방법의 헤드 이동거리 계산 결과를 비교해보면 그 차이를 실감할 수 있을 것이다. 그러나 SSF 방법도 하나의 커다란 문제점을 지니고 있다. 12로 부터 가장 멀리 떨어진 80은 가장 늦게 처리되었다. 80으로 헤드를 이동 시키기 전에 계속해서 요구되어진 데이터들이 22, 33, 7, 15, 4에 위치해 있다면 헤드가 80으로 향하는 시간은 계속해서 멀어질 수 밖에 없다. 바로 현재 헤드가 놓인 위치로부터 최단거리에 놓인 데이터들이 계속해서 요구되어지는 경우가 발생하면 무한정 기다림을 갖는 데이터가 생기게 되는 것이다.

Scan algorithm
스캔 알고리즘은 헤드가 한번은 디스크의 안쪽 끝에서 바깥쪽 끝으로 한번은 바깥쪽 끝에서 안쪽 끝으로 이동하면서 요구된 데이터를 처리하는 것이다. 만약에 새로운 데이터의 요구가 현재 헤드가 이동중인 방향으로 놓이게 되면 처리될수 있다. 그러나 헤드의 뒤쪽에 놓이게 되면 디스크 끝까지 헤드가 이동된후 다시 되돌아 올때까지 기다리게 된다. 우리가 엘리베이터를 이용할 때 1층에서 승차한 사람이 12층을 올라가기 위해 버튼을 눌렀다고 생각해보자. 그 이후 바로 5층에서 한사람이 내려가는 버튼을 눌렀다하더라도 엘리베이터는 5층을 무시하고 1층에서 12층까지 올라간다. 그리고 다시 12층에서 내려올때 5층에 서게 된다. 5층에서 엘리베이터를 기다리는 사람(데이터)은 12층까지 올라갔다 다시 내려오는 엘리베이터를 기다리야 하는 것이다. 이렇듯 엘리베이터 작동과 유사한 특성 때문에 스캔 알고리즘을 엘리베이터 알고리즘이라고도 부른다.

앞서 예를든 것과 동일한 경우를 생각해보자.
(12, 45, 80, 16, 30)

헤드가 가장 안쪽에서 바깥쪽으로 먼저 스캔하게 된다면 0부터 헤드가 이동하여 12, 16, 30, 45, 80의 데이터를 처리하고 트랙의 가장 바깥쪽까지 스캔하게 된다. 만약 30을 처리한 직후 28 위치에 데이터가 요구된다면 헤드의 이동방향과는 다른 요구이기 때문에 바깥쪽 끝까지 스캔이 끝난후 다시 안쪽끝으로 스캔할 때 처리되어 지는 것이다.

그림 66 Scan Algorithm

스캔 알고리즘은 탐색시간(seek time)의 단축을 가져왔다는 점과 SSF에서 발생한 무한정의 기다림을 갖는 데이터를 방지했다는 것이 장점이다. 그러나 헤드가 항상 디스크 안쪽끝과 바깥쪽 끝을 스캔하기 때문에 헤드의 이동거리가 요구된 데이터들의 간격보다 넓어지는 것이다. 바로 디스크 바깥쪽 끝에 요구된 데이터가 없을 경우 헤드는 괜한 걸음을 하게 되는 것이니까.

Look algorithm
스캔알고리즘이 갖고 있는 단점을 해결하기 위한 고안된 방법이 바로 룩 알고리즘이다. 주어진 데이터 요구값에 가장 작은 번호부터 가장큰 번호까지 처리하는 방법이다.
앞서 예를든 것과 동일한 경우를 생각해보자.
(12, 45, 80, 16, 30)의 데이터가 요구된다면 12부터 80까지 헤드가 이동되는 것이다. 바로 헤드가 12의 데이터 요구를 처리한 다음 무작정 이동방향을 따라 움직이는 것이 아니라 또다른 요구데이터가 있는지를 확인한 다음 이동하게 되는 것이다. 그렇게 되면 12, 16, 30, 45, 80까지 처리한 이후 이동방향으로 더 이상 요구데이터가 없음이 확인되면 더 이상 이동하지 않는다. 바로 요구된 데이터가 있는지 없는지를 계속해서 'Look'하며 이동하는 것이다.

그림 67 Look Algorithm

I/O시스템이란 무엇인가?

기존에 컴퓨터에 새로운 프린터를 추가해 연결 할 때 컴퓨터본체에 코드를 꽂는다고 작동될까. 윈도우 환경에서 사용할 경우 새 하드웨어 추가라는 목록으로 가서 새로운 프린터를 등록해야만 이용이 가능하다. 이런 것을 처음 경험한 사람들이라면 누구나 당혹스러워했을 것이다. 이러한 당혹스러움은 바로 I/O시스템을 공부함으로 해결 될 수 있다. 지금까지 우리가 배워온 모든 영역들은 시스템 내부적인 것 들 이었다. 그러나 I/O시스템은 사용자가 직접 접하게 되는 영역이다. I/O시스템이 작동되기까지는 다음과 같은 과정들을 거친다.

그림 68 I/O 시스템의 구조

I/O시스템은 커널을 통해 명령받게 된다. 이러한 명령들은 계속해서 쏟아져 나올 때 커널은 어느 명령을 먼저 처리할 것인지에 관해 조절기능을 하게 된다. 이렇게 하나의 명령이 주어지면 장치구동기(Device driver)를 통해 추가 명령이 실행될 주변장치를 제어, 관리하게 되고 이어 장치제어기(Device controller)를 통해 실행 하드웨어가 작동되는 것이다.

잠깐, 상식!

장치제어기(Device controller)란...
입출력장치를 컴퓨터시스템버스에 접속하기 위하여 사용하는 입출력장치의 인터페이스제어장치를 말하고 이것의 기능은 컴퓨터 시스템을 구성하는 각각의 장치에서 정상적인상태로 작업을 진행할 수 있도록 제어하고 관리하는 것이다

장치구동기와 장치제어기는 하나의 하드웨어에 각각 하나씩 존재한다. 모니터, 모뎀, 키보드, 프린터 등이 각자만의 장치구동기를 갖고 있다는 말이다. 그렇기에 새로운 프린터를 추가할 경우 단지 본체에 젝을 꽂는다는 것만으로 프린터가 작동되지 않는 것이다. 시스템내부에 새로운 프린터를 작동시키는 역할을 맡게될 장치구동기와 장치제어기를 설정해야하는 것이다. 이렇듯 여러 I/O장치들이 각각 장치구동기를 갖는 이유는 뭘까. 키보드가 1초에 처리하는 데이터양과 모뎀이 1초에 처리하는 데이터의 양이 같다면 이 둘은 하나의 장치구동기를 사용하여도 된다. 결국 각각의 I/O장치마다 서로 다른 특성을 가졌기에 그 특성을 뒷받침 해줄 장치구동기가 필요한 것이다. 새로운 하드웨어가 기존 시스템에 추가될 수 있는 것은 장치구동기를 커널과 연결시킬 수 있는 장치가 커널에 존재하기 때문이다. 바로 장치구동기와 커널 사이에는 연결을 위한 상호간에 대화통로인 디바이스인터페이스가 정의되어 있는데 지원되는 기능이 이미 정의되어 있다. 그렇기에 커널이 내부적으로 어떻게 운영되는지 모르는 사람도 I/O 시스템을 사용할 수 있는 것이다.

장치구동기(Device driver)를 특성에 따라 분류

block device driver란?

최소단위를 갖고 고정된 크기의 데이터를 읽고 쓰는 장치구동기를 말하는 것으로 디스크와 CD-ROM등이 이에 속한다.

character device driver란?

고정된 크기가 사용자의 자유에 따라 임의 크기의 데이터를 읽고 쓸 수 있는 장치구동기를 말한다. 터미널과 마우스등이 character device driver에 속한다.

요점 정리

Access time의 구성
1)탐색시간(seek time)이란 read/write 헤드를 데이터가 저장되어 있는 트랙위치로 이동시키는데 소요되는 시간을 말한다.
2)회전지연시간(rotational delay time)이란 read/write 헤드를 데이터가 위치하는 트랙으로 이동시킨 순간부터 원하는 섹터에 헤드가 다다를때까지 소요되는 시간을 의미한다.
3)전송시간(transfer time)이란 read/write 헤드가 찾은 데이터를 실제로 디스크로부터 사용자의 버퍼로 보내지는데 소요되는 시간을 의미한다.

디스크스케줄링의 방법
1) FCFS (First Come First Service) 선도착 선처리
FCFS는 요구가 들어온 순서대로 헤드를 움직이는 방법이다.
2)SSF(Shortest Seek Time First Scheduling) 최단탐색시간 우선스케줄링
SSF는 현재 헤드의 위치로부터 가장 가까운 실린더에 놓인 데이터를 먼저 처리하는 방법이다.
3)Scan algorithm
스캔 알고리즘은 헤드가 한번은 디스크의 안쪽 끝에서 바깥쪽 끝으로 한번은 바깥쪽 끝에서 안쪽 끝으로 이동하면서 요구된 데이터를 처리하는 것이다.
4)Look algorithm
주어진 데이터 요구값에 가장 작은 번호부터 가장 큰 번호까지 처리하는 방법이다.

I/O시스템이란?
I/O시스템은 커널을 통해 명령받게 된다.
이러한 명령들은 계속해서 쏟아져 나올 때 커널은 어느 명령을 먼저 처리할 것인지에 관해 조절기능을 하게 된다. 이렇게 하나의 명령이 주어지면 장치구동기(Device driver)를 통해 추가 명령이 실행될 주변장치를 제어, 관리하게 되고 이어 장치제어기(Device controller)를 통해 실행 하드웨어가 작동되는 것이다.

디바이스 커널 인터페이스란?
바로 장치구동기와 커널 사이의 연결을 위한 상호간에 대화통로로 지원되는 기능이 이미 정의되어 있다.

장치구동기(Device driver)의 분류
1)block device driver란 최소단위를 갖고 고정된 크기의 데이터를 읽고 쓰는 장치구동기를 말한다.
2)character device driver란 고정된 크기가 사용자의 자유에 따라 임의 크기의 데이터를 읽고 쓸 수 있는 장치구동기를 말한다.

퀴즈

퀴즈1) access time 중 탐색시간(seek time)이란 무엇을 의미하는가.

퀴즈2) 최단탐색시간 우선스케줄링은 현재 헤드의 위치로부터 가장 가까운 실린더에 놓인 데이터를 먼저 처리하는 방법이다. 이 스케줄링의 단점은 무엇인가.

퀴즈3) Look algorithm의 특성을 설명하시오.

퀴즈4) I/O시스템은 커널을 통해 명령받게 된다. 명령이 주어진 이후 필요한 각각의 장치와 기능을 설명하시오.

퀴즈5) 장치구동기(Device driver) 중 block device driver란 어떤 특성을 갖고 있나.

정답1) linked list allocation는 순차접근을 할 경우 연결된 포인터만 쫓아가면 되므로 효율적인 방법이 된다. 그러나 임의 접근을 시도할 경우 내가 찾고자 하는 데이터가 리스 트로 연결된 블록 가운데 마지막에 있다 하더라도 처음 블록부터 찾아야 하므로 비효율적인 방법이다.

정답2) read/write 헤드를 데이터가 저장되어 있는 트랙위치로 이동시키는데 소요되는 시간을 말한다.

정답3) 현재 헤드가 놓인 위치로부터 최단거리에 놓인 데이터들이 계속해서 요구되어지는 경우가 발생하면 무한정 기다림을 갖는 데이터가 생기게 된다.

정답4) 주어진 데이더 요구값에 가장 작은 번호부터 가장 큰 번호까지 처리하는 방법이다.
정답5) 하나의 명령이 주어지면 장치구동기(Device driver)를 통해 추가 명령이 실행될 주변 장치를 제어, 관리하게 되고 이어 장치제어기(Device controller)를 통해 실행 하드웨어가 작동된다.

정답4) block device driver는 최소단위를 갖고 고정된 크기의 데이터를 읽고 쓰는 장치구동기를 말하는 것으로 디스크와 CD-ROM등이 이에 속한다.

목 차

운영체제를 시작하는 분들을 위해

운영체제의 역사와 구체적으로 어떤 일들을 수행하나요?

운영체제의 목표와 역할이 미래에도 계속 증대될까요?

운영체제를 이해하기 위해 필요한 기본 개념들은 무엇인가요?

운영체제 프로세스 생애주기(Process Lifecycle)는 무엇인가요?

운영체제 프로세스 관리(Process Management)는 어떻게 하나요?

운영체제 프로세스(Process)의 처리 속도는 어떻게 높일까?

운영체제 스레드(Thread)는 무엇인가요?

운영체제 스케줄링 (Scheduling)은 어떻게 하나요?

운영체제 스케줄링 알고리즘의 비교 기준이 있나요?

운영체제 프로세스 동기화가 무엇인가요?

운영체제에서 세마포어(Semaphore)란?

운영체제 메모리 관리(Memory Management)는 어떻게 하나요?

운영체제 메모리 분할 방법은 어떻게 하나요?

운영체제 가상메모리(Virtual Memory)는 무엇인가요?

운영체제 Page in/out, Swapping 등이 Page Table Entry와 어떤 관계인가요?