24.03.25 운영체제, PintOS

24.03.25 운영체제, PintOS

운영체제

27. I/O 장치

27.1 시스템 구조

• 시스템 설계자들은 계층 구조를 택하여 고성능 장치들을 CPU에 가깝게 배치하고 느린 성능의 장치는 그보다 멀리 배치했다. 디스크처럼 느린 장치를 주변 장치 I/O 버스에 연결하여 얻는 이득이 많은데, 그 중 하나는 많은 장치를 연결할 수 있다는 것이다.
• CPU는 인텔의 DMI(Direct Media Interface) 기술을 통해 I/O 칩에 연결되어 있으며, 나머지 장치들이 이 칩에 여러 다른 종류의 연결 방식을 사용하여 연결된다.

27.2 표준 장치

• 두 개의 중요한 요소가 있다.
  • 첫 번째는 시스템의 다른 구성 요소에게 제공하는 하드웨어 인터페이스다. 소프트웨어가 인터페이스를 제공하듯이 하드웨어도 인터페이스를 제공하여 시스템 소프트웨어가 동작을 제어할 수 있도록 해야한다. 그렇기 때문에 모든 하드웨어 장치들은 특정한 상호 동작을 위한 방식과 명시적인 인터페이스를 갖고 있다.
  • 장치가 갖고 있어야 하는 두 번째 요소는 내부 구조이다. 구현 방법에 따라 다르지만 장치의 기능을 추상화하여 시스템에 제공하는 책임을 가지고 있다. 매우 단순한 장치들은 하나 또는 몇 개의 하드웨어 칩으로 기능이 구현되어 있고, 좀 더 복잡한 장치는 단순한 CPU와 범용 메모리 그리고 장치에 특화된 칩들을 사용하여 목적에 맞게 동작한다. 최신 RAID 컨트롤러는 수십만줄에 달하는 펌웨어(firmware) 라는 소프트웨어가 하드웨어 내부의 동작을 정의하고 있다.

27.3 표준 방식

• 표준 장치의 인터페이스(단순화 된)는 세 개의 레지스터로 구성되어있다. 상태(status) 레지스터는 장치의 현재 상태를 읽을 수 있으며 명령어(command) 레지스터는 장치가 특정 동작을 수행하도록 요청할 때, 그리고 데이터(data) 레지스터는 장치에 데이터를 보내거나 받거나 할 때 사용한다. 이 레지스터들을 읽거나 쓰는 것을 통해 운영체제는 장치의 동작을 제어할 수 있다.
• 운영체제와 장치간에 일어날 수 있는 상호동작의 과정은 네 단계로 이루어진다.
  • 먼저 반복적으로 장치의 상태 레지스터를 읽어서 명령의 수신 가능 여부를 확인한다. 이 동작을 장치에 대해 폴링(polling)한다고 표현한다. 두 번째는 운영체제가 데이터 레지스터에 어떤 데이터를 전달한다. 데이터 전송에 메인 CPU가 관여하는 경우를 programmed I/O 라고 부른다. 세 번째로 운영체제가 명령 레지스터에 명령어를 기록한다. 이 레지스터에 명령어가 기록되면 데이터는 이미 준비되었다고 판단하고 명령어를 처리한다. 마지막으로 운영체제는 디바이스가 처리를 완료 했는지를 확인하는 폴링 반복문을 돌면서 기다린다(성공과 실패를 알리는 에러코드를 받게된다.)
• 이 기본 방식은 간단하지만 제대로 작동한다. 하지만 매우 비효율적이다. 이 방식이 갖고 있는 첫 번째 문제는 매우 비효율적인 폴링을 사용하고 있다는 점이다. 다른 프로세스에게 CPU를 양도하지 않고, 장치의 동작이 완료되기 전까지 계속 루프를 돌면서 장치 상태를 체크한다. 이를 폴링이라 한다. 입출력 장치는 무척 느리다. 그리고 대기하는 중에 특별히 따로 하는 일이 있는것도 아니다. CPU 시간을 많이 소모하게 된다.

27.4 인터럽트를 이용한 CPU 오버헤드 개선

• 디바이스를 폴링하는 대신 운영체제는 입출력 작업을 요청한 프로세스를 블록시키고 CPU를 다른 프로세스에게 양도한다. 장치가 작업을 끝마치고 나면 하드웨어 인터럽트를 발생시키고 CPU는 운영체제가 미리 정의해놓은 인터럽트 서비스 루틴(ISR : Interrupt Service Routine) 또는 간단하게 인터럽트 핸들러(Interrupt handler)를 실행한다. 이 핸들러는 운영체제 코드의 일부이다. 인터럽트 핸들러는 입출력 요청의 완료, I/O를 대기중인 프로세스 깨우기를 담당한다. 깨어난 프로세스가 작업을 계속할 수 있도록 한다.
• 사용률을 높이기 위한 핵심 방법 중 하나는 인터럽트를 활용하여 CPU 연산과 I/O를 중첩시키는 것이다.
• 인터럽트가 항상 최적의 해법은 아니라는 것에 유의해야 한다. 대부분 작업이 한 번의 풀링 만으로 끝날 정도로 매우 빠른 장치라고 해보자. 이 경우에 인터럽트를 사용하면 시스템이 느려지게 된다. 다른 프로세스로 문맥을 교환하고 인터럽트를 처리한 후 다시 I/O를 요청한 프로세스로 문맥 교환 하는 것은 매우 비싼 작업이다. 그러므로 빠른 장치라면 폴링이 최선이고, 느리다면 인터럽트를 사용하여 중첩 시키는 것이 최선이다. 만약 장치의 속도를 모른다거나, 빠를 때도 있고 느릴 때도 있는 장치라고 한다면, 짧은 시간 동안만 폴링을 하다가 처리가 완료되지 않으면 인터럽트를 사용하는 하이브리드 방식을 채용하는 것이 최선일 것이다. 이와 같이 두 단계 접근법으로 양쪽의 장점만 취할 수 있다.
• 인터럽트를 사용하지 않는 다른 이유는 네트워크 환경에서 찾아볼 수 있다. 패킷이 대량으로 도착할 때를 생각해보면, 각 패킷이 도착할 때만 인터럽트가 발생된다. 이 경우 인터럽트만 처리하다가 운영체제가 사용자 프로세스의 요청을 처리할 수 없도록 만드는 무한 반복(live lock)에 빠질 가능성 있다. 이 경우, 폴링을 사용하면 시스템의 상황을 보다 효율적으로 제어할 수 있다. 웹 서버가 새로운 패킷이 도착했는지 검사하기 전에 사용자 요청들을 좀 더 처리할 수 있기 때문이다.
• 또 다른 인터럽트 기반의 최적화 기법은 병합(coalescing)이다. 이 경우는 CPU에 인터럽트를 전달하기 전에 잠시 기다렸다가 인터럽트를 발생시킨다. 기다리는 동안에 다른 요청들도 끝나게되기 때문에 여러번 인터럽트를 발생시키는 대신 인터럽트를 한 번만 CPU에 전달하게 된다. 이 방법으로 인터럽트 처리의 오버헤드를 줄일 수 있다.

27.5 DMA를 이용한 효율적인 데이터 이동

• 많은 양의 데이터를 디스크로 전달하기 위해 programmed I/O(PIO)를 사용하면 또 다시 단순 작업 처리에 CPU가 소모된다. 다른 프로세스를 처리하기 위해 사용될 수 있는 많은 시간이 허비된다.
• 직접 메모리 접근 방식(DMA)를 통해 문제를 해결한다. DMA엔진은 시스템 내에 있는 특수장치로서 CPU의 간섭없이 메모리와 장치간에 전송을 담당한다.
• 데이터를 장치로 전송한다고 했을 때 운영체제는 DMA 엔진에 메모리 상의 데이터 위치와 전송할 데이터의 크기와 대상 장치를 프로그램 한다. 그 시점에 전송하기 위해 할 일은 끝나기 때문에 운영체제는 다른 일을 진행할 수 있다. DMA 동작이 끝나면 DMA 컨트롤러가 인터럽트를 발생시켜 전송이 완료되었다고 운영체제에게 알린다.

27.6 디바이스와 상호작용하는 방법

• 장치와 통신하는 두 가지 기본적인 방법
  • 첫 번째는 I/O 명령을 명시적으로 사용하는 것이다. 이 명령어들은 운영체제가 특정 장치 레지스터에 데이터를 전송할 수 있는 방법을 제공한다. 데이터를 장치에 보내야 하는 경우에는 호출자가 데이터가 저장된 레지스터와 장치를 지칭하는 포트를 지정한다. 명령어를 실행하면 원하는 동작이 실행된다.
  • 이 명령어들은 대부분 특권 명령어(Privileged instruction)들이다. 운영체제가 장치를 제어하는 역할을 한다. 때문에 운영체제만이 장치들과 직접 통신할 수 있다.
  • 두 번째는 맵 입출력(memory mapped I/O)을 사용하는 것이다. 이 접근법에서 하드웨어는 장치의 레지스터들이 마치 메모리상에 존재하는 것 처럼 만든다. 특정 레지스터를 접근하기 위해서 운영체제는 해당 주소에 load(읽기) 또는 store(쓰기)를 하면 된다. 하드웨어 load/store 명령어가 주 메모리를 향하는 대신 장치로 연결되도록 한다.

27.7 운영체제에 연결하기 : 디바이스 드라이버

• 최종적으로 다룰 문제는 서로 다른 인터페이스를 갖는 장치들과 운영체제를 연결시키는 가능한 일반적인 방법을 찾는 것이다.
• 추상화(abstraction)라는 고전적인 방법을 사용하여 이 문제를 해결할 수 있다. 운영체제 최하위 계층의 일부 소프트웨어는 장치의 동작방식을 반드시 알고 있어야 한다. 이 소프트웨어를 우리는 디바이스 드라이버(device driver)라고 부르며 장치와의 상세한 상호작용은 그 안에 캡슐화 되어있다.
• Linux의 파일 시스템 소프트웨어 계층에서 파일 시스템은 어떤 디스크 종류를 사용하는지 전혀 알지 못한다. 파일 시스템은 범용 블록 계층(generic block layer)에 블록 read/write 요청할 뿐이다. 범용 블록 계층은 적절한 디바이스 드라이버로 받은 요청을 전달하며, 디바이스 드라이버는 특정 요청을 장치에 내리기 위해 필요한 일들을 처리한다.
• 응용 프로그램(파일 시스템 검사기(file-system checker) 또는 디스크 조각 모음(disk defragmentation 도구 등)) 이 파일 추상화를 사용하지 않고 직접 디스크의 블록에 읽고 쓸 수 있도록 하는 미가공 인터페이스(raw interface)도 표시되어 있다. 대부분의 시스템들은 저수준의 저장장치 관리 응용 프로그램을 지원하기 위해 이러한 인터페이스를 제공한다.
• 이러한 캡슐화는 단점도 있다. 특수 기능을 많이 갖고 있는 어떤 장치가 있다고 했을 때, 커널이 범용적인 인터페이스만을 제공할 수 밖에 없다면 그 많은 특수 기능들을 사용할 수 없게 된다

PintOS

• 한 페이지는 VM_UNINIT , VM_ANON , VM_FILE 라는 세 가지 종류 중 하나이다. 하나의 페이지는 swap in, swap out, 그리고 페이지 삭제같은 여러 동작을 수행하게 된다.
• 페이지의 타입별로 이러한 동작을 하기 위해 요구되는 단계와 작업들이 다르다. 즉, VM_ANON 페이지와 VM_FILE 페이지는 서로 다른 destroy 함수를 호출한다. 이를 위해 switch-case 구문을 활용해서 각 케이스에 맞는 함수를 사용하는 방법이 하나 있다.
• 우리는 이 문제를 해결하는 방법으로 객체 지향 프로그래밍의 컨셉인 “클래스 상속”을 소개하려고 한다. 실제로 C 언어에서는 클래스와 상속이라는 개념은 없지만, 우리는 이 개념을 이해하기 위해 함수 포인터를 사용할 것이다. 이 방법은 리눅스같은 실제 운영체제 코드에서 사용되는 방법과 유사하다.
  • 객체 지향 프로그래밍의 클래스 상속의 개념을 이해하기 위해 함수 포인터를 사용한다.
• Supplemental page table을 설계해야한다.
  • 추가 페이지 테이블은 적어도 두가지 목적으로 사용된다. 가장 중요한 것은 페이지 폴트가 발생하면 커널이 추가 페이지 테이블에서 폴트가 발생한 가상 페이지를 조회하여 거기에 어떤 데이터가 있어야 하는지 알아내는 것이다. 둘째, 커널은 프로세스가 종료될 때 추가 페이지 테이블을 참조하여 어떤 리소스를 해제할지 결정한다.
  • 각각의 페이지에 대해서 데이터가 존재하는 곳(frame, disk, swap 중 어디에 존재하는지), 이에 상응하는 커널 가상주소를 가리키는 포인터 정보, active인지 inactive 인지 등
  • 각 요소에 어떤 정보가 포함되어야 하는지 결정해야 한다.
  • 데이터 구조의 범위를 로컬(프로세스 별) 또는 전역(전체 시스템에 적용)으로 결정하고 해당 범위 내에서 필요한 인스턴스 수를 결정해야 한다.
  • 설계를 단순화하기 위해 이러한 자료 구조를 페이징할 수 없는 메모리(calloc 또는 malloc 으로 할당된 메모리)에 저장할 수 있다. 즉, 자료 구조 내 포인터가 유효하게 유지될 수 있다는 것을 의미한다.
• 우리조는 구현에 해시맵을 사용하기로 결정했다. 뭐.. 나중에 어떻게 바뀔지는 모르지만 ㅎ…

Implement Supplemental Page Table

• struct page에 member를 추가해주었다.
• supplemental_page_table에 해시 자료구조로 hash_table을 만들어 주었다.
• void supplemental_page_table_init (struct supplemental_page_table *spt);
• struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
• bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

Frame Management

• static struct frame *vm_get_frame (void);
• bool vm_do_claim_page (struct page *page);
• bool vm_claim_page (void *va);
• 을 일단 구현했다. 아직 제대로 통과하는 것은 없지만 이 친구들도 userprog하면서 했듯이 한번에 쫙 되지 않을까 생각한다.

FAIL tests/userprog/args-none
FAIL tests/userprog/args-single
FAIL tests/userprog/args-multiple
FAIL tests/userprog/args-many
FAIL tests/userprog/args-dbl-space
FAIL tests/userprog/halt
FAIL tests/userprog/exit
FAIL tests/userprog/create-normal
FAIL tests/userprog/create-empty
FAIL tests/userprog/create-null
FAIL tests/userprog/create-bad-ptr
FAIL tests/userprog/create-long
FAIL tests/userprog/create-exists
FAIL tests/userprog/create-bound
FAIL tests/userprog/open-normal
FAIL tests/userprog/open-missing
FAIL tests/userprog/open-boundary
FAIL tests/userprog/open-empty
FAIL tests/userprog/open-null
FAIL tests/userprog/open-bad-ptr
FAIL tests/userprog/open-twice
FAIL tests/userprog/close-normal
FAIL tests/userprog/close-twice
FAIL tests/userprog/close-bad-fd
FAIL tests/userprog/read-normal
FAIL tests/userprog/read-bad-ptr
FAIL tests/userprog/read-boundary
FAIL tests/userprog/read-zero
FAIL tests/userprog/read-stdout
FAIL tests/userprog/read-bad-fd
FAIL tests/userprog/write-normal
FAIL tests/userprog/write-bad-ptr
FAIL tests/userprog/write-boundary
FAIL tests/userprog/write-zero
FAIL tests/userprog/write-stdin
FAIL tests/userprog/write-bad-fd
FAIL tests/userprog/fork-once
FAIL tests/userprog/fork-multiple
FAIL tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
FAIL tests/userprog/exec-missing
FAIL tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
FAIL tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
FAIL tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
FAIL tests/userprog/bad-read
FAIL tests/userprog/bad-write
FAIL tests/userprog/bad-read2
FAIL tests/userprog/bad-write2
FAIL tests/userprog/bad-jump
FAIL tests/userprog/bad-jump2
FAIL tests/vm/pt-grow-stack
FAIL tests/vm/pt-grow-bad
FAIL tests/vm/pt-big-stk-obj
FAIL tests/vm/pt-bad-addr
FAIL tests/vm/pt-bad-read
FAIL tests/vm/pt-write-code
FAIL tests/vm/pt-write-code2
FAIL tests/vm/pt-grow-stk-sc
FAIL tests/vm/page-linear
FAIL tests/vm/page-parallel
FAIL tests/vm/page-merge-seq
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
FAIL tests/vm/page-shuffle
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
FAIL tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL tests/vm/mmap-remove
FAIL tests/vm/mmap-zero
FAIL tests/vm/mmap-bad-fd2
FAIL tests/vm/mmap-bad-fd3
FAIL tests/vm/mmap-zero-len
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
FAIL tests/vm/lazy-anon
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL tests/vm/swap-fork
FAIL tests/filesys/base/lg-create
FAIL tests/filesys/base/lg-full
FAIL tests/filesys/base/lg-random
FAIL tests/filesys/base/lg-seq-block
FAIL tests/filesys/base/lg-seq-random
FAIL tests/filesys/base/sm-create
FAIL tests/filesys/base/sm-full
FAIL tests/filesys/base/sm-random
FAIL tests/filesys/base/sm-seq-block
FAIL tests/filesys/base/sm-seq-random
FAIL tests/filesys/base/syn-read
FAIL tests/filesys/base/syn-remove
FAIL tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
123 of 141 tests failed.

• 진행상황