운영체제

[Operating System] I/O 관리 및 디스크 스케쥴링

짱일모 2023. 5. 20. 03:39

컴퓨터에는 여러 I/O Device 를 연결할 수 있습니다. 예를 들어, 데이터를 저장하기 위한 SSD, HDD 도 I/O Device 이고, 마우스, 키보드, 모니터 등도 I/O Device 입니다.

 

이번 포스팅에서는 위와 같은 I/O Device 를 운영체제가 어떻게 관리하는 지 알아보겠습니다.

 

I/O Device

I/O Device 는 전자장치로 구성되어 있는 Controller 부분과 Mechanical 하게 구현된 Machine 부로 구현되어 있습니다.

 

HDD 를 예시로 살펴보겠습니다.

 

(좌) Mechanical 하게 구현된 디스크 부분, (우) 컨트롤러 부분

 

HDD 의 디스크 부분은 Machine Arm 이 이동하여 데이터를 읽고 쓸 수 있습니다.

HDD 의 컨트롤러 부분은 다음과 같이 구성되어 있습니다.

  • 컨트롤러는 Control Register, Status Register, Internal Buffer 로 구성되어 있습니다.
  • 커널 내의 디바이스 드라이버는 I/O Device Controller 의 Control Register 중 특정한 bit 하나를 1로 세팅함으로써 Command (ex. Read/Write) 를 전달할 수 있습니다.
  • 디바이스 드라이버는 Device Controller 의 Status bit 을 체크함으로써 디바이스 상태를 확인합니다.
  • I/O Device Controller 는 디바이스 드라이버의 Polling 방식 또는 Interrupt 방식을 통해 Control 됩니다.

 

I/O Management, 커널은 디바이스를 어떻게 제어하는가에 관한 아키텍쳐

 

I/O Management Architecture

먼저 위 그림의 구조에 대한 설명을 하겠습니다. 회색 부분은 Hardware 즉, I/O Device 부분을 의미합니다. 보다시피 장치와 컨트롤러로 구성되어 있습니다. 그 위의 흰색 부분은 Software 부분입니다. Kernel I/O Subsystem (= I/O Management) 는 커널의 일부분입니다. 그리고 Device Driver 의 경우, 디바이스 제조사가 만든 소프트웨어이지만, 커널의 일부로서 동작을 해야 하드웨어에 직접 접근하여 디바이스를 조작할 수 있습니다.

 

따라서, 흰색 부분은 모두 커널 그리고 회색 부분은 하드웨어 부분을 의미합니다.

 

커널은 I/O 를 수행해야하는 명령을 받으면 커널에서 I/O 를 담당하는 부분인 I/O Subsystem 에게 I/O 명령을 넘깁니다. 그러면 I/O Subsystem 은 적절하게 명령을 수행합니다. 이 때, Device Driver 는 Device Driver Interface (DDI) 에 의해 호출됩니다. 마치, 유저 모드의 프로세스가 커널에 명령을 내릴 때 System Call 이라는 Interface 를 통해 호출하는 것과 유사한 구조입니다.

 

왜 이런 구조를 띌까요?

 

장치마다 Device Driver 가 수행하는 행동이 제각기 다르다는 가정하에 다음과 같은 상황을 생각해봅시다.

 

2015 년에 출시한 윈도우 10에 2016년에 출시한 새로운 SSD 장치를 연결하여 사용하고자합니다. 2015년 이전에 출시한 모든 장치에 대한 디바이스 드라이버를 내장하여 윈도우를 출시했다고 하더라도, 나중에 출시된 장치는 지원하지 못합니다. 즉, 범용성이 떨어집니다.

 

하지만, 표준적인 Interface 를 미리 정의해두고 장치 제조사가 이 규격에 맞추어 제작한다면, 나중에 출시된 장치도 문제없이 2015년의 윈도우에서 동작할 수 있습니다.

 

예를 들어, 2015년에 업데이트 된 윈도우10이 범용적인 마우스 드라이버를 내장한 상태에서 2016년에 출시한 마우스를 연결하여 사용하더라도, 마우스가 범용적인 드라이버 규격을 지키고 있다면 별도의 디바이스 드라이버 설치 필요없이 마우스를 조작할 수 있습니다. 물론 특정 제품에 대한 세세한 조작을 지원하기 위해서는 그 장치만을 위한 드라이버의 추가 설치가 필요하겠습니다.

 

그렇다면, Kernel I/O Management (=I/O Subsystem) 은 어떤 방식으로 동작할까? 

커널  I/O Management 는 다음과 같은 동작을 수행합니다.

 

  • Device Reservation
  • Device Scheduling
  • Error Handling
  • Buffering
  • Caching
  • Spooling

 

하나씩 살펴보겠습니다.

 

Device Reservation

  • 말 그대로 장치 점유에 관한 예약입니다. Device Reservation 은 장치에 대한 Exclusive 한 접근을 제공합니다.
  • 장치 점유에 관한 할당/반납을 제어하고 데드락이 발생했는지 관찰합니다.

 

Device Scheduling

  • Kernel I/O Management 는 I/O 요청에 대한 순서를 관리합니다.

 

Error Handling

  • 운영체제는 디스크 읽기,  장치 사용불가, 일시적인 쓰기 실패 등의 오류로부터 복구할 수 있습니다.
  • 대부분은 I/O 요청에 실패하면, 에러코드를 반환합니다.
  • 시스템 에러로그에 이러한 문제들에 대한 리포트가 기록됩니다.

Buffering

  • Buffering 은 디바이스로 데이터를 전송할 때 메모리 내에 일시적으로 데이터를 저장하는 것을 의미합니다.
  • 일반적으로 Device 는 RAM, CPU 에 비해서 동작속도가 느립니다. 따라서 Device 와 RAM, CPU 간의 동작속도 괴리를 극복하기 위해 버퍼링을 수행합니다.
  • 또한, Device 는 RAM. CPU 에 비해 한 번에 전송할 수 있는 데이터의 크기가 작습니다. 한 번에 전송할 수 있는 데이터 양의 괴리를 극복하기 위해 버퍼링을 수행합니다. (ex. Device Controller 에 존재하는 Internal Buffer 의 크기가 작아서, 컴퓨터 시스템의 메인 메모리에 담아 뒀다가 조금씩 꺼내서 전송)
  • Copy Semantics 를 유지하기 위해서 버퍼링을 수행합니다. Copy Semantics 란 프로세스 사이에서 데이터가 어떤 방식으로 복사되는지를 의미합니다. 예를 들어, 문서 편집기에서 문서 작성을 하다가 프린트를 합시다. 프린터가 프린트를 진행하고 있는 동안에 추가로 문서 수정을 진행하면 출력되는 결과물에는 수정한 내용이 반영되지 않고 프린트를 누른 그 순간의 내용이 출력이 됩니다. 즉, 프린트를 누른 순간의 데이터가 Deep Copy 되어 커널의 I/O버퍼에 저장되어 출력이 수행됩니다.

Caching

  • Cache 란 메모리 공간입니다. 어떤 메모리 공간이냐면, 저속 입출력 장치에서 데이터를 가져오려면 Performance 가 떨어지기 때문에 자주 사용하는 데이터의 경우 속도가 빠른 메인 메모리 공간에 저장해두고 사용합니다. 이를 위해 Cache 를 사용합니다.
  • Kernel I/O Management 가 Caching 도 수행합니다.

 

Spooling

  • 일반적으로 I/O Device 는 CPU, RAM  에 비해서 속도가 느리다고 언급한 바 있습니다. 스풀링은 이러한 동작속도의 괴리를 극복하기 위해 사용하는 방법입니다.
  • Buffering 과 유사하지만 큰 차이점이 있습니다. Spooling 은 처리할 데이터를 보조 기억장치 (Secondary Disk) 에 저장합니다.
  • 예를 들어, 하나의 서버 컴퓨터가 한 대의 프린터와 연결되어 있다고합시다. 서버 컴퓨터에는 많은 사람들이 연결되어 작업을 하고 있을 것입니다. 이 서버에 연결된 모든 사람들이 프린터에 프린트 요청을 하면, Buffer 에도 프린트할 데이터가 저장되겠지만 이 양이 매우 방대해 Buffer 를 초과하는 양이 있다면 누락되는 데이터가 발생할 것입니다. 이러한 한계를 극복하기 위해 Spooling 을 사용합니다. 보조 기억장치에 I/O 를 위한 데이터를 저장해두었다가, Buffer 가 적절하게 비면 버퍼에 다시 데이터를 Load 하고 데이터의 I/O 를 처리합니다.

 

 

지금까지 I/O Device 가 동작하는 구조와 I/O Management 가 수행하는 일에 대해 알아보았습니다. 지금부터는 I/O 를 제어하는 구체적인 방법에 대해 알아보겠습니다.

 

I/O Control

I/O 를 제어하는 방법은 다음과 같습니다.

 

  • Polling
  • Interrupt-driven I/O Control
  • Direct Memory Access (DMA)

 

하나씩 차례대로 살펴보겠습니다.

 

Polling (Software 기반의 I/O Control)

Polling 의 사전적 의미는 다음과 같습니다.

 

  1. 투표
  2. 여론 조사

 

폴링은 디바이스에 계속해서 동작 가능한지 물어보는 방식으로 이루어집니다.

Polling 은 Programmed I/O 라고도 불리며 I/O 가 실행 중인 Program Code 에 의해 Monitoring 됩니다.

즉, 프로세스는 작업을 마치기 위해서 I/O 를 Busy-waiting 하며 대기합니다.

 

폴링의 동작구조는 아래 그림과 같습니다.

 

 

위 그림을 바탕으로, Host 가 Device 에 데이터를 Write 하는 예시를 살펴보겠습니다.

 

  1. 유저 모드의 프로세스가 I/O Request System Call 을 호출하면, Kernel 은 이 System call 을 처리해야합니다. System Call 이 I/O 에 관한 호출이므로, 커널 내의 I/O 를 담당하는 부분인 Kernel I/O Management 에게 이 명령을 전달합니다.
  2. Kernel I/O Management 는 이 명령이 어떤 Device 에 대한 요청인지를 파악하고 맞는 Device Driver 에 Device Driver Interface 를 호출하여 Device Driver 로 하여금 명령을 처리하도록 시킵니다.
  3. Device Driver 는 Device Controller 의 Status Register 를 확인하며 I/O Request 를 처리할 수 있는 상태인지 계속 확인합니다. 만약 Device 가 다른 I/O Request 를 처리하고 있는 상태라면 Busy bit 이 1 일 것입니다. Device Driver 가 Driver 의 Status 의 Busy bit 이 0 으로 Clear 될 때까지 계속, 반복적(Busy Waiting)으로 확인합니다.
  4. Busy bit 이 0 으로 Clear 되었다면, Host (Device Driver) 는 Device Controller 의 Control Register 에 Write bit 을 set  합니다. 그리고 Data-out Register 를 통해서 데이터를 Write 합니다. 그리고 Host 는 Device Controller 의 Command-Ready bit 을 set 합니다.
  5. Command-Ready bit 이 set 되었으면 Device Controller 는 이제 I/O Request 를 처리하는 상태에 들어갑니다. Busy bit 을 set 하고 Control Register 를 읽어 받은 Request 가 Write 임을 파악합니다. 그리고 Data-out Register 에 저장된 데이터를 읽어 I/O Request 를 처리합니다.
  6. I/O Request 를 정상적으로 처리를 완료했다면 Device Controoler 는 Command-Ready bit 과 busy bit 을 모두 clear 합니다.

 

이처럼 폴링 방식은 Busy Waiting 과 유사합니다. 계속해서 사용 가능한지 여부를 체크합니다. 그렇다면 Busy Waiting 형태로 I/O 를 처리하는 것은 좋지 않은 방식일까요? 그렇지 않습니다.

 

Polling 의 장점 (또는 Busy-Waiting 의 장점으로 볼 수도 있음)

I/O 처리가 빠르게 일어난다면, 폴링 방식으로 동작 시 (인터럽트로 처리할 때에 비해) 빠르게 동작한다.

후술할 내용이지만, 인터럽트 및 프로세스 상태조작 방식으로 I/O 를 처리하는 방법도 있습니다. I/O 가 매우 빠르게 일어나는 과정에서 인터럽트 및 프로세스 상태조작 방식으로 I/O 를 처리하면, Mode Change 와 같은 Overhead 에 의해 폴링 방식보다 느리게 동작합니다.

 

 

Interrupt-driven I/O

인터럽트를 기반으로 동작하는 I/O 방식에 대해 살펴보겠습니다. 이에 앞서 Interrupt 란 무엇인지, 어떻게 동작하는지 살펴봅시다.

 

인터럽트란 ?

Interrupt : a mechanism for the OS to inform a process of the occurrence of an event 이라고 기술한 적 있습니다.

I/O 에서 인터럽트의 정의는 다음과 같습니다. A mechanism that peripheral devices inform an asynchronous event to an operating system 

 

둘이 다른 정의처럼 보이지만, Peripheral Devices 가 OS 에게 비동기적인 이벤트가 발생했다는 것을 알리고, OS 는 이를 Process 에게 알리는 것입니다.

 

인터럽트를 통해 User Mode 에서 Kernel Mode 로의 Mode Change 를 수행할 수 있습니다. 이외에도 Kernel Mode 로 Mode Change 를 수행하게 해주는 Entry Point 에 대해 살펴봅시다.

 

커널로 진입하는 방법. Interrupt, Trap, System Call

 

Trap

Interrupt 와 동일한 방식으로 동작함. Interrupt Vector Table 을 찾아 Interrupt Service Routine 을 수행. Trap 은 Synchronous (동기적) 으로 발생하는 이벤트라는 점에서 Interrupt 와 구분됨.

System Call

System Call 은 Interrupt Vector Table 에서 system_call 의 ISR 을 찾아 System Call Request 에 해당하는 명령을 수행함.

 

인터럽트의 동작구조

 

CPU 는 Real-time Clock 과 PIC 와 연결되어 있습니다. Real-time Clock 을 이용하여 Time Slice 가 경과하였는지를 확인할 수 있습니다.

 

PIC 와 Peripheral Device 가 연결되어 있습니다. 디바이스에서 I/O 가 발생하면, PIC 는 CPU 에 Interrupt 가 발생해야 함을 알립니다. 

 

그리고 OS 는 다음과 같은 동작을 수행합니다.

  • 만약 유저 모드에서 동작하고 있었다면, 커널 모드로 Mode Change 를 수행
  • OS 는 실행 중이던 작업의 Context 를 Kernel Stack 에 저장합니다. (유저 모드에서 동작 중이었다면, 유저 모드의 프로세스 Context 에서의 Register 값들을 Kernel Stack 에 저장합니다. 만약 커널 모드에서 동작 중이었다면, 커널모드에서 수행 중이던 task 의 Context 에서의 Register 값들을 Kernel Stack 에 저장합니다.)
  • OS 의 Interrupt Handler 는 PIC 에게 어떤 Device 로 부터 Interrupt 요청이 왔는지 물어보고 확인합니다.
  • 이를 바탕으로 OS 는 Interrupt Vector Table 에서 해당 Device 의 Interrupt Service Routine 을 찾아 수행합니다.
  • 이 때, Interrupt Service Routine 은 급한 부분과 급하지 않은 부분으로 구성됩니다. Interrupt Service Routine 은 급한 부분을 먼저 수행한 후 급하지 않은 부분은 나중에 처리합니다.
  • 인터럽트를 수행하던 도중 새로운 인터럽트가 발생하면 위 과정을 반복합니다. 이 때, 기존의 인터럽트의 급한 부분을 수행하고 있더라도 새로 호출된 인터럽트가 수행이 됩니다. 새로 호출된 인터럽트의 급한 부분이 마무리 되면, 기존 인터럽트의 급한 부분을 마저 수행합니다.
  • 모든 인터럽트가 수행되었다면, 커널은 Special Code Block 을 Execution 합니다.
  • Special Code Block 이란 Interrupt Service Routine 의 급하지 않은 부분을 모두 처리하고, 인터럽트에 진입하기 전 수행되고 있던 프로세스의 State 를 Ready 로 바꾸고 Scheduler 를 부르는 코드 부분을 의미합니다.
  • 호출된 Scheduler 는 다음에 실행할 프로세스를 선택합니다. (즉, Context Switching 을 합니다., 반드시 하는 것은 아니고 인터럽트 된 프로세스를 다시 Run 시킬 수도 있습니다.)

 

아래 그림을 통해 위 동작을 이해할 수 있습니다.

 

Interrupt 발생 시, Kernel Stack 안에 Context Saving 이 이루어진다.

 

 

인터럽트 수행 중 새 인터럽트가 발생하면 새 것의 급한 부분을 처리하고 기존의 급한 부분을 모두 처리한다. 급하지 않은 부분은 모두 빨간색 영역 (Special Code Block) 에서 처리한다.

 

커널 모드에 들어갔다가 다시 나오려면, 커널이 항상 해야하는 Routine 이 있는데 그것이 바로 Special Code Block 의 수행입니다. Special Code Block 은 Interrupt 의 Remainder Part 를 모두 수행하고, Scheduler 를 호출하여 다음으로 실행시킬 프로세스를 결정합니다.

 

이제 Interrupt 의 동작방식에 대해 이해하였으니, Interrupt-driven I/O 에 대해서 알아봅시다.

 

Interrupt-driven I/O 의 동작 방식

 

Interrupt-driven I/O 의 동작방식

 

Interrupt-driven I/O 는  위 그림과 같이 동작합니다. 하나하나 자세히 살펴보겠습니다.

 

  1. 유저 모드의 프로세스가 System Call 을 통해 I/O Request 를 합니다.
  2. I/O Management 는 어떤 Device 로 I/O 를 수행해야하는지 파악하고 Device Driver Interface 로 Device Driver 로 하여금 I/O Request 를 처리하도록 요청합니다.
  3. Device Driver 는 Device 의 Busy Bit 을 체크하여 현재 사용 가능한 상태인지 확인합니다.
  4. 현재 Device 가 다른 I/O Request 를 처리 중이라면 (Busy bit 이 set 되어있다면) Device Driver 는 Process Management 로 하여금 현재 실행 중인 프로세스 (I/O Request 가 일어난 프로세스) 를 Run -> Blocked State 을 요청합니다.
  5.  Process Management 는 현재 프로세스가 I/O Request 를 처리하지 못하므로 Process State 을 Run -> Blocked 로 전환합니다.
  6. 인터럽트 된 프로세스가 Blocked 상태로 바뀌었으므로, 커널은 스케쥴러를 호출해 실행할 새 프로세스를 찾아 Context Switching 을 수행합니다.
  7. 스케쥴러에 의해 새 프로세스 B 가 Ready -> Run 상태로 바뀌고 실행됩니다.
  8. 이 때, Process A 가 기다리던 I/O 가 Device 에서 일어나면, PIC (Programmable Interrupt Controller) 가 CPU 에 인터럽트가 발생했다고 알립니다. 그러면, OS 는 Mode Change 를 수행합니다. 
  9. 커널의 I/O Management 가 PIC 로부터 어떤 장치로부터 인터럽트가 발생했는지 확인하고 Interrupt Vector Table 에서 적절한 Interrupt Service Routine 을 찾아 수행합니다.
  10. Interrupt Service Routine 을 수행합니다.
  11. 인터럽트를 수행하고, 커널은 Special Code Block 도 수행합니다. 이 때, 정상적으로 수행했다면 Process A 는 Blocked 상태에서 Ready 상태로 전환이 됩니다.
  12. 그리고 커널은 다음 실행시킬 프로세스를 고르기 위해 스케쥴러를 호출합니다. 이 때, Process A 가 B 보다 더 높은 우선순위를 가지고 있다면 A 로의 Context Switching 을 수행합니다. 그렇지 않다면 커널 스택에 저장된 Register 값들을 복원하여 다시 Process B 의 Instruction 을 수행합니다.

 

이제 인터럽트 기반 I/O 동작까지 살펴보았습니다. 이를 바탕으로 예시를 하나 생각해봅시다.

 

우리가 메모장을 띄워놓고 있다가 키보드에 글자 ㄱ 을 입력하다고 생각해봅시다.

 

CPU 는 메모장 프로세스를 계속 실행 (메모장 프로세스는 사용자의 키보드 입력을 대기하고 있다.) 시키고 있습니다. 이 때 우리가 키보드에 ㄱ 을 누릅니다. 그러면 PIC 가 CPU 에 인터럽트가 발생했음을 알립니다. 인터럽트를 처리해야 하니 메모장 프로세스는 커널 모드로 모드 체인지가 됩니다. 그리고 메모장 프로세스를 실행하던 CPU Register 값들은 Kernel Stack 에 Save 됩니다. 그 다음 커널의 I/O Management 는 이것이 키보드에서 요청한 Interrupt 임을 파악하고 Interrupt Vector Table 에서 키보드에 입력된 값을 Read 하는 Interrupt Service Routine 을 호출합니다. 이 Read 의 급한 부분을 처리하고 새로운 인터럽트가 없으면 Read ISR 의 급하지 않은 부분을 모두 처리하고, 메모장 프로세스의 Context 를 커널 스택에서 다시 꺼내 복구한 뒤, 키보드에서 가져온 데이터를 프로세서가 메인 메모리에 존재하는 메모장 프로세스의 data 영역 안에 저장할 것임을 생각해볼 수 있습니다.

 

정리해보면, I/O Control 이 Main Memory <-> I/O Device 사이에서 일어나고 있습니다. 물론, 직접 메모리가 버스에 데이터를 실어서 I/O Device 로 보내는 것이 아니라, 중간에 CPU (Processor) 를 경유하여 데이터를 전송합니다.

 

즉, 메모리가 버스에 데이터를 실어 프로세서에 보내고, 프로세스는 버스에 데이터를 실어 I/O Device 에 보냅니다.

 

입출력하는 데이터의 양이 많지 않다면 지금과 같은 방식으로 Processor 를 거쳐 I/O Control 을 수행해도 문제가 되지 않습니다. 하지만 I/O Request 가 수천, 수만개로 매우 많을 때 Interrupt-Driven I/O 방식으로 I/O Control 을 수행한다면 어떤 Side Effect 가 있을까요?

 

수천, 수만가지의 I/O Request 요청을 받을 때마다 커널은 모드 체인지 후 Interrupt Handling 을 수행해야 합니다. 모드 체인지를 하는 행동은 유저 모드 프로세스의 Context 를 Save 하고 인터럽트 처리를 한 뒤 Special Code Block 까지 처리해야하는 Overhead 가 큰 동작입니다. 따라서 수천, 수만가지의 I/O Request 를 인터럽트 방식으로 처리하면 유저 프로세스를 처리하는 Throughput 이 굉장히 낮아지는 문제가 발생합니다.

 

이러한 문제점을 해결하기 위해 DMA (Direct Memory Access) 방식이 등장합니다.

 

DMA (Direct Memory Access)

DMA 가 있는 컴퓨터 구조

 

DMA 방식은 I/O Request 를 처리할 때 메모리에 대한 접근을 DMA Controller 가 수행합니다. DMA Controller 는 I/O 를 처리하기 위한 별도의 보조 Processor 입니다.

 

DMA 방식에서 Output Request 를 처리하는 예시를 살펴보겠습니다.

 

  1. CPU 가 DMA 로 하여금 Output Command 를 내립니다.
  2. DMA 는 Output 할 데이터를 Main Memory 에 접근하여 DMA 로 가져옵니다.
  3. 그리고 I/O Device 를 통해 Output 을 수행합니다.
  4. I/O Request 처리가 끝나면, DMA 가 CPU 에 인터럽트를 겁니다.
  5. 인터럽트를 받은 CPU 는 모드 체인지를 수행한 뒤, DMA 가 I/O Request 를 처리했음을 인지하고, Interrupt Handling 을 수행합니다.

 

이렇게 DMA 방식으로 I/O Request 를 처리하면, CPU 는 DMA 에게 I/O Command 만 내리고, DMA 가 I/O Request 를 처리하는 동안 유저 프로세스를 처리할 수 있습니다. 즉, CPU 의 Utilization 이 좋아집니다.

 

지금까지 배운 I/O Control 방식의 특성을 요약하면 다음 Table 과 같습니다.

Direct 의 의미는 프로세서를 거치지 않는다는 이야기지, 직접적으로 I/O Device 와 Main Memory 가 데이터를 주고 받는다는 이야기는 아니다. DMA 방식은 DMA 가 Main Memory 와 I/O Device 사이에 놓여져 있다.

 

 

 

지금까지 이 포스팅의 두가지 주제 중 I/O 관리에 대해 알아보았습니다. 이제 Disk Scheduling 에 대해 알아보겠습니다.

 

 

Disk Scheduling

디스크 스케쥴링이란 컴퓨터 시스템에서 디스크 접근 작업을 관리하고 조정하는 방법을 의미합니다. 조금 더 자세히 말하면

여러 개의 디스크 접근 작업이 동시에 요청될 때, 이 작업들을 어떤 순서로 처리할지 결정하는 알고리즘을 의미합니다.

 

디스크 접근 작업이란 무엇인지 알아보고, 어떻게 이를 효율적으로 운용할 수 있는지 살펴봅시다.

 

디스크 접근 작업에 대해 알아보기 전에 디스크의 구조에 대해 알아봅시다. 위에서 I/O Device 의 구조를 살펴볼 때 I/O Device 는 Mechanical 한 부분봐 전자적인 Controller 부분이 존재한다고 하였습니다.

 

저장장치인 HDD 의 Mechanical 한 부분은 회전하는 Disk 와 이를 Read 하기 위한 Disk Arm 으로 구성되어 있습니다.

 

Disk 의 구조, 좌측 상단의 그림에서 방사형태의 선은 실제 물리적으로 존재하는 것은 아니다.

 

  • 섹터 : 디스크를 구성하는 가장 작은 단위. 섹터의 번호는 0번 트랙부터 매기며, 한 디스크의 앞 뒷면의 0번 트랙에 번호를 다 매기면 그 다음 디스크의 앞면의 0번 트랙에 존재하는 섹터에 번호를 순서대로 부여한다. 즉, 실린더 단위로 번호를 부여한다.
  • 트랙 : 같은 반지름 상에 존재하는 섹터의 집합. 가장 바깥쪽의 트랙부터 번호를 매긴다.
  • Surface : 디스크의 면 단위, 디스크는 앞면과 뒷면을 모두 사용하므로 3장의 디스크에는 6개의 Surface 가 존재함.
  • Cylinder : 여러개의 디스크에 걸친 트랙의 집합
  • Head : Disk Arm 의 끝부분으로, Sector 에 저장되어 있는 0, 1 데이터를 읽는 센서이다.
  • Disk Arm : Disk Arm 의 축이 Rotate 하여 Disk 안쪽과 바깥쪽을 이동하며 Head 가 필요한 Sector 를 읽을 수 있도록 한다.

 

다음은 일반적인 Disk 의 Structure Spec. 입니다.

 

1개 Sector 의 크기는 일반적으로 32bytes ~ 4096bytes 로 2의 배수 형태이다. 따라서 File System 의 Block 이 n 개의 Sector 로 구성될 수 있다.

 

운영체제는 Disk 에 접근할 때 Block 단위로 접근한다고 File System 에서 배운 바 있습니다. 즉, 운영체제를 Disk 를 Block 의 1차원 배열로 바라봅니다.

 

아까 Disk Structure 에 대해 알아볼 때, 섹터의 번호를 실린더 단위로 부여한다고 하였습니다. 이 부여된 번호를 기반으로 n 개의 섹터를 모아서 1개의 block 을 만들 수 있으며 이러한 매핑을 모아둔 것을 바탕으로 운영체제는 Disk 에 접근하여 I/O 를 수행할 수 있습니다.

 

Timing of a Disk I/O Transfer

디스크에 접근하여 I/O 를 수행하기 위해서는 I/O 를 어느섹터에 수행할 것인지를 정하고, 그 섹터에 물리적으로 헤드가 직접 접근해야합니다.

 

이렇게 Disk Head 가 섹터로 접근하기 위한 Mechanical 하게 소요되는 시간과 Data Transfer 에 소요되는 시간의 합이 Disk 를 읽는데 걸리는 시간이 됩니다.

 

  • Seek Time : Disk Arm 의 축을 움직여 Head 가 읽고자 하는 Sector 가 존재하는 Track 에 위치하도록 하는 시간
  • Rotational Delay : Head 가 Sector 가 존재하는 Track 에 위치하고 있을 때, 해당 Sector 가 Head 아래로 오기 까지 디스크가 회전하는 시간
  • Data Transfer Delay : Head 가 섹터로부터 데이터를 읽고 Device 가 컴퓨터 시스템 내부로 데이터를 전송하는데 걸리는 시간

 

이 중 Seek Time + Rotational Time 을 Access Time 이라고 지칭합니다.

 

이 Access Time 중에서도 Seek Time 이 차지하는 비중이 Rotational Time 보다 훨씬 큽니다. 따라서 Disk I/O 의 Performance 를 결정하는 Factor 는 Seek Time 이라고 할 수 있습니다.

 

그러므로, 이 Seek Time 을 최소화하는 것이 디스크 스케쥴링의 핵심입니다.

 

구체적인 디스크 스케쥴링 방법

 

구체적인 디스크 스케쥴링 방법에는 다음과 같은 것들이 있습니다.

 

  • FIFO (Queue)
  • Shortest Seek Time First (SSTF)
  • SCAN (Elavator Algorithm or Look Policy 라고도 불림)

 

FIFO

디스크 스케쥴링 방식으로 FIFO 를 채택하면, I/O Request 가 요청된 순서대로 수행됩니다. 이는 많은 프로세스가 동작하고 있는 상황에서 Disk I/O Performance 가 뒤죽박죽이 됩니다. 빠를 수도, 느릴 수도 있습니다.

 

 

Shortest Seek Time First (SSTF)

Shortest Seek Time First 방식으로 디스크 스케쥴링을 수행하면, 현재 Disk Arm 의 위치에서 최소의 움직임으로 찾아갈 수 있는 Track 에 위치한 섹터를 읽는 I/O Request 를 우선적으로 처리합니다. 마치 그리디 알고리즘처럼 동작합니다.

 

SSTF 방식의 스케쥴리은 현재 Disk Arm 의 위치에서 어떤 것이 가장 가까운 I/O Request 인지 계산해야하는 Overhead 가 존재하며, 그리디하게 I/O Request 를 선택한다하더라도, Optimal 한 Result 를 가져오지 않을 수도 있습니다.

 

그리고 가장 가까이에 있는 섹터에 접근하는 I/O Request 를 우선적으로 처리하기 때문에 멀리 떨어진 I/O Request 가 먼저 들어왔더라도 오랫동안 요청이 처리되지 않는 Starvation 문제가 발생할 수 있습니다. (Priority 가 존재하면 Starvation 이 발생하는 것은 자연스럽습니다.)

 

 

SCAN (Elavator Algorithm or Look Policy)

Elavator Algorithm 이라고도 불리는 SCAN 알고리즘은 초기에는 디스크 가장자리부터 안쪽까지 쓱 훑어가며 I/O Request 를 처리하고, 다시 안쪽부터 가장자리로 I/O Request 를 처리하는 방법으로 고안되었습니다. (0번 트랙 ~ N번 트랙 - N번 트랙 ~ 0번 트랙)

 

이를 조금 더 개선하여 현재 위치에서 안쪽으로 Disk Arm 을 이동하며 I/O Request 를 처리하고, 더 안쪽에 처리할 I/O Request 가 없으면 다시 가장자리 쪽으로 Disk Arm 을 이동하며 I/O Request 를 처리하는 방법이 되었습니다.

 

 

 

각 디스크 스케쥴링의 성능을 정리한 예시 표는 다음과 같습니다.

SSTF 와 SCAN 은 유사한 Performance 를 보이나, SSTF 는 Starvation 문제가 존재하므로, SCAN 방법이 더 유용한 방법이라 할 수 있다.

 

지금까지, Disk Scheduling 방법에 대해 살펴보았습니다. 요약하자면, Disk Scheduling 은 Disk Arm 을 어떻게 움직여야 빠르게 I/O 를 처리할 수 있는지에 대한 내용이었습니다.

 

 

이어서 추가적으로, Disk I/O 를 더 빠르게 수행하기 위해 사용하는 Disk Cache 방법에 대해 살펴보겠습니다.

 

Disk Cache (Buffer Cache, Page Cache)

Disk 와 같은 I/O Device 는 CPU, RAM 에 비해 속도가 매우 느립니다. 따라서 Disk 에 접근하여 I/O Request 가 많을 경우 컴퓨터의 Performance 가 저하될 수밖에 없습니다.

 

이를 해결하기 위해, Disk 에 있는 데이터를 Kernel 에 가져옵니다. 커널 내의 Disk Data (혹은 Data Block 으로 지칭할 수도 있겠습니다.) 를 저장하는 공간을 Disk Cache 라고 칭합니다.

 

 

Main Memory 는 Disk 에 비해 용량 당 가격이 비싸고, 또 보통은 Disk 의 용량이 Main Memory 의 용량보다 훨씬 큽니다. 따라서 Disk 에 있는 데이터를 모두 Main Memory 에 Disk Cache 로 저장할 수 없습니다.

 

따라서 Disk Cache 가 꽉 찼을 때, Disk Cache 에는 없는 데이터를 Disk 로부터 읽어오고 Disk Cache 에 저장하려면, 이미 존재하고 있던 Disk Cache 중 일부를 제거하고, 추가해야합니다.

 

이 때 Disk Cache 에 저장된 데이터 중 어떤 것을 제거해야 할지에 대한 기준이 있습니다. 아래와 같습니다.

 

LRU, LFU

 

 

 

이 글의 초기에 말씀드렸듯, I/O Device 를 Control 하기 위해서는 커널의 I/O Management 부분의 Device Driver 를 통해서 Device Controller 에 접근해야 한다고 했습니다. 이 Device Driver 구조에 대해 자세히 살펴봅시다

 

Device Driver 의 구조

 

위 설명에 나타나 있듯, 디바이스 드라이버는 세 부분으로 나뉩니다.

 

1. Interface for initialization : 디바이스 드라이버를 초기화하고, 커널에 디바이스 드라이버 함수를 등록하는 역할을 합니다.

2. Interface for File System : 파일 시스템과 상호작용하는 부분으로, 문자형 장치, 블록형 장치, 네트워크 장치인지에 따라 수행하는 file_operations (파일 시스템에서 다뤘던 그것과 동일합니다.) 가 다릅니다.

3. Interface for hardware : 하드웨어와 상호작용하는 부분으로, 블록형 장치의 경우 In, Out 을 호출합니다.

 

커널과 장치의 통신은 Switch Table 을 통해서 수행됩니다. 문자형 장치의 경우 chrdevs(Switch), 블럭형 장치의 경우 blkdevs 라는 스위치 테이블이 존재합니다.

 

register_chrdev (문자형 장치의 등록), register_blkdev (블럭형 장치의 등록) 함수를 통해서 디바이스 드라이버를 커널에 등록시킬 수 있습니다. major_number, device name, file_operations 를 인자로 받으며 예를 들어 tty (터미널 장치) 드라이버를 커널에 등록할 경우, 다음과 같이 작성할 수 있습니다.

 

register_chrdev(4, "tty", &tty_fops)

 

tty driver 와 tty device 의 상호작용 구조

 

위 그림에서 tty_init() 함수를 통해 tty 디바이스 드라이버를 초기화하고 커널에 등록합니다.

 

그 다음, Application 에서 I/O System Call 을 호출하면, 커널의 I/O Subsystem 이 적절한 Device Driver 에 file operations 를 호출하라고 명령합니다.

 

tty_open(), tty_read(), tty_wirte() ... 등이 위에서 설명한 Device Driver 의 Interface for File System 입니다. 이 Interface 를 실행하면, Interface for Hardware 함수들 (rs_interrupt(), receive_chars(), transmit_chars()) 이 호출이 됩니다.

 

예를 들어, tty_write() 를 호출하면, transmit_chars() 가 호출되어 터미널에 output 이 출력됩니다.

 

rs_interrupt() 는, IDT (Interrupt Descriptor Table) 에 등록된 Interrupt Service Routine 입니다. 만약 키보드와 같은 I/O Device 에 입력이 일어난다면, ISR 을 통해 문자를 receive 하는 과정이 수행될 것입니다.

 

tty_init() (디바이스 드라이버의 초기화 및 커널에 등록)

 

Init Process 가 실행될 때,  tty_init() 함수에 의해서 register_chrdev 함수가 호출이 되고, 이를 통해 tty 디바이스 드라이버를 초기화하고 커널에 등록할 수 있습니다.

 

디바이스 드라이버가 커널에 등록이 된다는 것은, chrdevs 즉, 스위치 테이블에 등록이 되는 것을 의미합니다. 아래 그림은 스위치 테이블의 모습을 보여줍니다.

 

예를 들어, Major_number 가 4번인 tty는 스위치 테이블의 인덱스 4번에 저장되게 됩니다.

 

tty_open() 이 일어날 떄 동작

tty_open 이 일어날 때 동작

만약 어떤 프로세스가 파일을 open 하기 위해서 sys_open() 시스템 콜을 호출하면, sys_open 은 filep.open() 을 호출합니다. filep_open() 은 PCB 의 files 에 file struct 를 추가하고 (초기화 작업, 이 때, 문자형 디바이스를 사용할 것임을 커널이 인지하고 초기화함.) open_namei() 를 호출합니다. 

 

open_namei() 는, open 하고자 하는 device 의 major_number 와 minor_number 를 확인하여, 루트 디렉토리부터 재귀적으로 찾고자하는 디바이스 파일 (장치 파일) 이 존재하는 지 확인합니다. 예를 들어, /dev/tty0 를 찾습니다.

 

장치 파일을 찾으면, filep_open 은 file 이라는 자료구조를 초기화하고, 그것으로부터 file operation open() 을 호출합니다.

 

처음에 file operation open() 은, chrdev_open 입니다. chrdev_open() 은, 장치의 메이저 번호와 마이너 번호를 확인하여 구체적인 file operation tty_open() 으로 교체됩니다.

 

file 자료구조의 f_op 가 tty_fop 로 구체화된다.

 

 

마지막으로, 저장장치를 여러개 연결하여 사용할 수 있는 방법인 RAID 에 대해 알아보겠습니다.

 

RAID (Rendundant Array of Inexpensive (Independent) Disks)

 

RAID 란, 위 설명 그대로 값싼 디스크의 연속입니다. 물리적인 여러개의 디스크를 운영체제를 통해 하나의 논리적인 드라이브처럼 보이게 하는 기술입니다.

 

RAID 를 사용하면 다음과 같은 이점을 가질 수 있습니다.

 

  • 병렬적 데이터 처리가 가능해져, 속도가 향상됨
  • 작은 용량의 물리적 디스크를 연결하여, 큰 용량의 드라이브를 가질 수 있음
  • 데이터를 분산 저장하여, 안정성 (신뢰성) 이 향상됨

 

RAID 0

 

n개의 디스크에 데이터를 분산 저장하는 방법

strip 이란 ? : 파일 (블록들의 집합) 을 디스크에 분산하여 저장하기 위한 논리적 단위 = n 개의 블록 (n>=1)

 

RAID 0 방식은, N개의 디스크에 파일 데이터를 분산하여 저장하는 방식입니다. 데이터를 읽어올 때, N개의 디스크에서 병렬적으로 읽어올 수 있기 때문에 극단적인 성능 향상을 얻을 수 있습니다.

 

RAID 1

 

Mirrored, 안정성의 극대화

 

RAID 1 방식은 Mirrored 방식이라고도 불립니다. 위 예시처럼 만약 8개의 물리적 디스크를 사용한다면 4개는 데이터를 저장하는데 사용하고, 나머지 4개는 그 백업본을 저장하는데 사용됩니다. 이 경우에도, 읽기 속도의 성능 향상을 얻을 수 있습니다. 왜냐하면, 파란색 부분에서 데이터를 읽으면서, 회색 부분에서도 데이터를 읽어들일 수 있기 때문입니다.

 

하지만, 쓰기 속도에서는 RAID 0 에 비해 느립니다. 왜냐하면 Mirroring 을 하기 위해서 하나의 strip 을 두 디스크에 적어야하기 때문입니다.

 

Mirrored 방식을 사용하면, 데이터가 더 안정적으로 유지될 수 있지만, 실제 물리적 디스크 용량의 절반밖에 사용하지 못한다는 단점 또한 존재합니다.

 

RAID 3 (수정 필요)

 

Bit Interleaved 로 저장되면서, parity 를 저장하는 공간 또한 갖고 있음

 

RAID 3 방식은 bit-interleaved parity 방식이라고도 불립니다. 먼저 bit-interleaved 가 무엇인지 살펴봅시다.

 

비트 단위로 저장

 

이전 RAID 0, RAID 1 방식에서는 데이터를 디스크에 Strip 단위로 저장하였습니다. bit-interleaved 방식에서는 데이터를 bit 단위로 저장합니다. 이 때, 데이터를 구성하는 연속된 비트들이 각 디스크의 같은 위치에 저장되는 특징이 있습니다. 당연히 Parity Bit 도, 각 디스크의 같은 위치에 존재하는 bit 들에 대한 Parity 입니다.

 

그리고, 데이터의 오류를 복구하기 위한 Error Correction Code 인 Parity Bit 을 저장할 디스크가 요구됩니다.

 

이로 인해, RAID 3 방식은 다음과 같은 특징을 갖습니다.

 

  • 여러 개의 디스크에서 병렬적으로 I/O 가 수행가능 함. 읽기 속도에서는 성능 향상을 기대할 수 있음
  • 그러나, 데이터의 수정이 일어날 때마다 Parity Bit 을 계산하고 Update 해주어야 하므로, 쓰기 속도에 병목현상이 발생함. 또, Parity Bit 을 저장하는 디스크는 I/O 가 특히 자주 일어나 내구성이 감소할 수 있음.
  • Parity bit 을 이용해, 한 개의 디스크에 오류가 나더라도 오류를 정정할 수 있으나, 두 개 이상의 디스크 오류는 복구할 수 없음

 

RAID 4

 

 

RAID 4 는 RAID 3 를 개선한 방법입니다. RAID 4 와 3 의 가장 큰 특징은, interleaved 하게 저장되는 데이터의 단위가 bit 에서 block 으로 바뀌었다는 점입니다.

 

예를 들어, 한 블럭의 크기가 8bits 인 파일 시스템에서, 데이터의 크기가 한 블럭인 파일을 읽어오려면 디스크를 5개 사용하는 RAID 3 방식에서는 4개의 디스크로부터 데이터를 읽어와 모으는 과정을 두 번을 거쳐야 합니다. 반면, RAID 4 를 사용하면 데이터를 블럭 단위로 읽기 때문에 속도가 더 빠릅니다.즉, 블럭 단위로 읽을 수 있기 때문에 Parallel 하게 I/O Request 를 수행할 수 있다고 하는 것입니다.

 

또 Parity Bit 의 계산은, 디스크의 물리적인 위치가 같은 것들만 모아서 만듭니다. 이 부분은 RAID 3 과 동일하나 차이점은 RAID 3 에서는 디스크의 물리적인 위치가 같은 위치의 비트들은 하나의 파일에 대한 데이터를 이루지만, RAID 4 에서는 블럭 단위로 저장하기 때문에 디스크의 물리적인 위치가 같다고 해서 같은 파일의 데이터라는 보장이 전혀 없습니다.

 

RAID 5

 

 

RAID 5 는 RAID 4 와 거의 유사하나, Parity Bit 들을 한 디스크에 몰아서 저장하지 않고 여러 디스크에 분산시켜 저장하는 차이점이 존재합니다.

 

이렇게 구성하면, RAID 4 와 달리 Parity Bit 를 담고 있는 디스크가 손상이 있어도, 더 안정적으로 데이터를 유지할 수 있습니다.

 

RAID 6

 

RAID 6 는 RAID 5 와 유사하지만, 서로 다른 Check Alogrithm 을 이용하여 데이터 정합성을 유지하도록 합니다.