[OS] GeekOS Projects!!

GeekOS : An Instructional Operating System for Real Hardware

Introduction

이 페이퍼는 GeekOS에 대해 설명한다. GeekOS는 실제 하드웨어(x86-based PC)에서 실행되는 작은 OS 커널이다. GeekOS는 Maryland 대학에서 학부 OS 수업에 프로젝트의 베이스로서 사용되었다.OS 커널 개발에는 두 가지 기본적인 접근이 있다.

1. 순수 하드웨어상의 실행, 하드웨어 디바이스에 직접적으로 노출시켰다.

2. host OS의 유저모드 내에서의 실행, 하드웨어 레벨의 시뮬레이팅

이 페이퍼에서 나는 순수 하드웨어 위에서 실행하는 것을 위한 의견 논쟁을 보여 줄 것이다. 그리고 GeekOS로부터 얻은 진짜 경험을 보충해 줄 것이다.

이 페이퍼의 개요는 다음과 같다. 첫째, GeekOS를 만든 자세한 동기를 의논할 것이다. 그 다음, GeekOS의 디자인과 구현을 말할 것이다. 마지막으로 현제의 결론을 포함하여 미래 작업에 대한 아이디어에 대해 언급하고 결론을 지을 것이다.

1 Motivation

이 섹션은 GeekOS를 만든 동기를 설명한다. 특히 왜 내가 새로운 교육용 OS를 시작했는지에 대해 설명한다.

첫 번째 동기는 순수 x86 PC에서 작동하는 부팅 프로그램에 대한 템플릿을 만들고자 하는 욕망이었다.

두 번째 동기는 Maryland 대학에서 학부 OS 수업을 위한 프로젝트를 업데이트 하기 위한 욕망이었다.

2 Alternative Instuctional OS Kernels

이 섹션에서는내가 왜 불만족스럽게 교육용 OS의 존재를 찾게 되었는지 설명한다.

2.1 Nachos

가장 넓게 하용되는 교육용 OS 중 하나는 Nacos이다. Nachos는 Unix 아래에서, 유저 레벨 프로세스를 실행하고, MIPS 프로세서를 위한 instruction-level 시뮬레이터를 거쳐서 유저 프로그램을 실행한다. OS 코드는 C++로 구현되었다( host Unix system을 위해 컴파일 / 실행). OS 커널은 CPU 시뮬레이터 옆에서 실행이 된다. 이런 접근 방법의 주요한 이정은 OS가 host system's debugger로 디버깅이 될 수 있으며, 충돌이 일어나도 하나의 사용자 프로세스에게만 영향을 미치게 된다. 또 다른 장점은 타임 쉐어링을 쉽게 할 수 있어 개인 컴퓨터에서도 쉽게 실행 될 수 있다. 마지막으로, Nachos는 low-level 하드웨어로부터 멀리 떨어져 있어 system call을 하는 interface의 host운영체제를 자신의 하드웨어로 생각할 수 있다.

나는 Nachos의 접근방식에 두 가지 불만족을 찾아내었다. 주요 이유는, OS는 유저 프로그램으로서 같은 CPU와 하드웨어에서 돌아가야 하는데, Nachos는 그렇지 않다. 학생들은 OS가 djEJgrp 유저 프로세스로부터 커널을 분리하는지 이해하기 어려울 것이다. 또 Nachos는 칩과 장치 레벨 프로그래밍의 추상력을 떨어뜨린다. 나는 OS가 실제 하드웨어의 로우 레벨 조직을 소개하는데 좋은 방법이라고 믿는다. 마지막으로 순수 하드웨어에서 동작시키기 위해 포티하는게 어렵다.

2.2 Minix

Minix또한 매우 널리 알려진 또자른 OS이다. Nachos와는 다르게 실제 하드웨어 상에서 실행된다. 그러나 Minix는 코드가 너무 복잡하고 방대하다. 처음부터 이런 방대한 소스에 뛰어드는 것은 위험하다. 그리고 Minix가 이미 실제 OS의 많은 부분을 구현하고 있어 학생용 프로젝트로 사용하기엔 알맞지 않다.

3 Design and Implementation

이 섹선에서는 나의 GeekOS 디자인 목표를 논의하고 현제 디자인과 몇몇 구체적인 구현을 설명한다.

3.1 Design Goals

GeekOS의 디자인에 세 가지 주된 목적이 있다 : 간소함, 현실적, 이해 가능.

GeekOS의 특징을 요약하면 다음과 같다.

- interrupt handling

- 힙 메모리 할당자

- 정적 우선 스케줄링 시분할 커널 스레드들

- 커널 스레드들의 동기화를 위한 mutexes 와 condition variables

- 유저 모드에서 세그멘테이션을 기본으로 한 메모리 보호, 간단한 system call interface

- 키보드와 VGA text모드 표현을 위한 장치 드라이브

그 외는 페이지 가상 메모리, 저장 장치 드라이브, 파일시스템 등.

3.2 Low-level Details

이 섹션은 GeekOS의 더 구체적인 디자인과 구현을 탐색하고 중요한 데이터 구조 와 함수에 대해 설명한다.

3.2.1 Loading and Runtime Environment

GeekOS는 플로피를 통해 부팅된다. 부트 섹터는 16비트 셋업 프로그램과 메모리 안에 있는 커널 이미지(from floppy)를 로드한다. 그리고 셋업 프로그램으로 점프한다. 셋업 프로그램은 32비트 protected 모드로 들어가기 충분한 하드웨어로 초기화하고, 초기 커널 thread의 스택을 셋업한다. 그리고 커널의 엔트리 포인트가 가리킨 Main() 함수로 점프한다.

Main() 함수는 다양한 커널 서브시스템을 위한 초기화 함수를 호출한다. 그리고 커널 안에 링크된 특별한 데이터 구조로 명명된 유저 프로그램을 시작한다.

3.2.2 Memory

GeekOS는 페이징을 사용하지 않기 때문에, 모든 커널 코드는 물리적 주소를 사용하여 수행한다.

부트섹터는 10000h(64k) 주소의 커널에 있다. 셋업 코드와 자료는 90000h 주소에 있다 : 하지만, 커널의 Main() 함수는 한번 들어가면, 셋업 프로그램을 다시 사용하지 못해서, 메모리는 다시 요구된다.

.bss 세크먼드가 0으로 채워진 후, VGA text display가 초기화 된 후, 커널은 페이지 리스트 데이터 구조를 만든다. 이것은 Page 자료형의 배열이고, 이 중 하나는 물리적 주소의 페이지이며, 커널 이미지 후 즉시 할당된다. Page 자료형의 정의는 다음과 같다.

#define PAGE_KERN 0x0001 // page used by kernel code or data

#define PAGE_HW 0x0002 // page used by hardware (e.g., ISA hole)

#define PAGE_ALLOCATED 0x0004 // page is allocated

#define PAGE_UNUSED 0x0008 // page is unused

#define PAGE_HEAP 0x0010 // page is in kernel heap

struct Page{

unsigned flags;

unsigned long nextFree;

};

flags : 페이지의 현재 상태를 나타낸다.

nextFree : page freelist로 사용됨. 그것은 페이지 할당자가 이용 가능한 페이지의 리스트이다. 앞으로, 다른 필드가 가상 메모리 페이지의 관련성을 다루기 위하여 추가 될 수 있다.

페이지 할당자(allocator)는 Alloc_Page() 와 Free_Page() 함수를 통해, 물리적 주소의 페이지로 할당된다. 페이지 할당자는 일반적으로 Kernel_Thread 객체와 그 스택을 생성하는 용도로만 쓴다.

A0000h ~ 100000h 는 VGA 메모리 같은 PC 하드웨어 장치를 위해 예약된 ISA hole이다. 일반적으로 GeekOS에 의해 사용된 이 영역의 한 부분은 VGA text screen인데, 이는 주소 B8000h에 위치해 있다.

즉시 따라오는 ISA hole 은 초기화된 커널 thread 와 그 스택을 위한 메모리의 두 페이지 이다. 모든 남아있는 메모리는 커널 힙 할당자에 의해 사용되어진다. Malloc()과 Free()를 통해 접근되어지는 힙 할당자는 일반적으로 임의의 크기의 객체를 위한 동적인 할당을 목적으로 한다. 일반적으로 힙 할당자는 오직 유저 프로그램을 위한 메모리의 할당을 위해 사용된다.

3.2.3 Kernel Threads

커널 thread는 GeekOS에서 스케쥴할 수 있는 엔티티를 위한 추상개념이다. GeekOS에서 thread 모델을 선택한 이유는, thread가 이해하기 간편하고 유저 레벨 thread를 사용한 경험을 가진 학생에게 친숙하기 때문이다. 커널 thread는 커널 모드에서만 전적으로 수행하거나 user context를 가지고 있을 것이다. Kernel_Thread 구조체는 다음과 같이 정의되어 있다.

struct Kernel_Thread{

unsigned long esp;

volatile unsigned long numTicks;

int priority;

DEFINE_LINK( Thread_Queue, Kernel_Thread );

void* stackPage;

struct User_Context* userContext;

struct Kernel_Thread* owner;

int refCount;

Boolean alive;

struct Mutex joinLock;

struct Condition joinCond;

};

esp : 쓰레드가 suspended 되었을 때, 쓰레드의 스택포인터를 저장하는데 사용된다.

stackPage : 커널 쓰레드의 스텍 페이지를 가리킨다.

numTicks, priority : 스케줄러에 의해 사용된다. 각각 선매와 우선권 스케쥴링을 기반으로 한 타이머를 구현.

DEFINE_LINK : 커널 쓰레드가 쓰레드 위에 있을 때 이전과 다음 필드를 정의한다.

userContext : 널값이 아니라면, 필수적으로 결합된 코드와 쓰레드가 유저 모드 프로그램을 실행하도록 하는 쓰레드의 유저 문맥을 가리킴

나머지 필드들은 종료를 하기 위해 부모 쓰레드가 자식 쓰레드를 기다리게 하는 Join() 함수 구현에 사용된다.

typedef void (*Thread_Start_Func)( unsigned long arg );

struct Kernel_Thread* Start_Kernel_Thread(Thread_Start_Func startFunc,

unsigned long arg, int priority, Boolean detached);

struct Kernel_Thread* Start_User_Thread(struct User_Context* userContext,

unsigned long entryAddr, Boolean detached);

void Exit( void );

Figure 2: Thread creation and destruction functions.

void Schedule( void );

void Yield( void );

void Wait( struct Thread_Queue* waitQueue );

void Wake_Up( struct Thread_Queue* waitQueue );

Figure 3: Voluntary thread scheduling functions.

Fig.2는 커널 쓰레드를 생성, 파괴하는 함수에 대한 원형을 나타낸다(Fig2는 원문참조).

커널 쓰레드는 2가지 방법으로 생성이 된다.

Start_Kernel_Thread() : 커널모드에서 독립적으로 실행되는 쓰레드는 이 함수를 통해 생성됨. 쓰레드의 바디에 구현된 start function 포인터가 가리킨다.

Start_User_Thread() : 유저 모드 프로그램에서 실행되는 쓰레드는 이 함수를 통해 생성됨. User_Context와 유저 문맥 메모리 내부의 코드 엔트리 포인트의 주소가 이것을 가리킨다.

커널 쓰레드는 Exit() 함수를 자발적으로 호출할 때 파괴된다. 왜냐하면 mutex에 의해 보호되는 치면적인 섹션을 수행하는 동안 쓰레드는 suspended가 된다. mutex lock 해제를 보장하는 메커니즘이 현재 없기 때문에 GeekOS는 한 쓰레드가 다른 것을 죽이는 것을 제공하지 못한다.

3.2.4 Interrupts and Scheduling

GeekOS에서 쓰레드 문맥 교환(thread context switch)은 두 가지 이유로 발생된다.

첫째로, thread는 Yield() 나 Wait() 함수를 부름으로 CPU를 자발적으로 포기한다. 각각의 함수들, 현재 쓰레드는 쓰레드 큐에 의해 자리 잡고, 새로운 쓰레드는 Schedule() 함수를 호출함으로 선택된다. Yield() 함수는 재스케쥴된 실행 큐에 있는 호출 쓰레드를 위치시킨다. Wait() 함수는 또 다른 쓰레드나 Wake_up() 함수를 사용하는 실행큐에서 되돌아온 interrupt handler가 자리할 때까지 남아있는 대기 큐에 호출 쓰레드를 위치시킨다.

둘째로, thread는 인터럽트가 가능케 될 때 어떤 포인트를 선매권에 의해 얻는다. timer interrupt handler 는 쓰레드의 numTicks 필드를 증가시키고, 만약 그것이 time slice를 초과한다면 그것은 suspended되고 새로운 쓰레드를 선택한다.

초기 긱오에스에서는 (시분할 기반 선점을 지원하지 않을 때) 나는 뚜렷한 데이터 구조를 사용하였다. 그 이유는 자발적인 컨텍스트 스위칭을 위해 중지된 쓰레드의 저장된 컨텍스트를 저장하기 위함이다.

단일화된 인터럽트 핸들링과 쓰레드 컨텍스트 스위칭에 의하여, 인터럽트 핸들러가 새로운 쓰레드가 선택되어야 인터럽트 리턴 코드를 알리게 한다.

현제의 스케쥴러인 Get_Next_Runnable() 함수는 정적 우선 계획을 사용하여 다음에 실행될 쓰레드를 선택한다.

3.2.5 Thread Synchronization

커널 쓰레드를 동기화 하기 위하여 GeekOS는 POSIX 쓰레드 모델에 기반한 mutexes 와 condition variables를 제공한다. Mutexes는 다중 쓰레드에 의해 공유되는 data 구조를 독립적인 접근으로 중개하는데 사용된다. Condition variables 는 쓰레드가 조건을 만족할 때까지 기다림을 허락한다. 쓰레드 동기화 함수의 원형은 Figure 4와 같다. 이러한 함수는 저레벨 Wait()와 Wake_UP() 함수를 사용함으로 구현되어 진다.

3.2.6 User Mode

궁극적으로 어느 OS 커널의 사용성은 다른 프로그램을 실행 시키는 능력에 달려있다. 유저 프로그램으로 부터의 커널을 보호하는 것과 서로의 유저 프로그램끼리 보호하는 것은 반드시 있어야만 한다.

무엇인가를 빠르게 실행시키기 위하여 난 유저모드 프로그램을 위한 제한적 환경을 만들기 위해 x86 세크멘테이션 하드웨어를 사용하였다. 유저 코드는 그들 소유의 데이터와 system call을 접근하고 수정하지만, 다른 모든 OS 자원은 제한이 없다.

user 프로세스는 user context를 커널 thread에 붙임으로써 생성된다. User_Context 구조체의 정의는 다음과 같다.

struct User_Context{

struct Segment_Descriptor ldt[2];

struct Segment_Descriptor* ldtDescriptor;

void* memory;

unsigned long size;

int refCount;

unsigned short ldtSelector;

unsigned short csSelector;

unsigned short dsSelector;

};

ldt : local descriptor table(LDT)로 유저 문맥의 코드와 data segment를 정의함.

ldtDescriptor : global descriptor table(GDT)에 있는 LDT의 descriptor를 가리킨다.

memory, size : context의 코드와 데이터를 포함한 메모리를 정의함

각각의 유저 문맥은 하나의 LDT를 가지고 있다. 그래서 GeekOS는 LDT들을 바꿀때마다 실행되는 새로운 유저 문맥이 자기 것 외의 것을 바꾸거나 침입하는 것을 막는다.

유저 프로그램은 system call 인터페이스를 통해 커널과 통신한다. 이 system callms eax 레지스터에 system call number를 로딩하여 만들고, 매개변수를 다른 레지스터에 로드하고, 소프트웨어 interrupt 144가 일어나길 바라는 방법이 있다. system call interrupt handler는 타당한 system call이 요청된 것인지를 검증하고, enable interrupts, calls the handler function, disable interrupt, 그 결과를 eax 레지스터에 리턴한다. Copyin 과 copyout 함수는 유저 공간과 커널 공간 사이를 움직이는 데이터를 위해서 제공된다. 그들의 유저모드 wrapper를 더하여 몇몇의 논증 system call은 그들 소유의 system call 구현에 필요한 학생에게 제공된다.

3.2.7 GeekOS Source Code

GeekOS는 현재 C로 된 3500줄 정도의 코드와 어셈블리로 된 1000줄 정도의 코드로 이루어졌다. GeekOS는 이해하기 쉽게 만들었다. 코멘트도 쉽게 달았다.

4. GeekOS as an Instructional Operating System

- slab 메모리 할당자 구현

- multi-level 과 round-robin 스케줄링 알고리즘 구현

- 적합한 mutex 구현

- fork() 와 exec() system call 구현

- 단방향 파이프를 사용한 IPC 구현

추가로 구현 할 것은 페이지 가상 메모리 구현, IDE 장치 드라이버 구현, 이더넷 장치 드라이버 구현

학생들을 대상으로 한 설문조사를 통해 GeekOS에 대한 적합성을 조사해본 결과 대체로 모두 긍정적이었다.

또한 Bochs 에뮬레이터의 성능과 적합성을 걱정하였지만, 조사결과 학습용으로 굉장히 적합하다는 결론을 얻었다.

마지막으로 GeekOS가 프로젝트 교육과정에 매우 좋다 라는 결과를 얻었다.

5. Future Work

GeekOS를 더욱 효과적인 교육용 툴로 만들기 위해서는, 이해하기 쉬운 참조 문서들이 많이 쓰여져야 한다.

하드웨어 레벨의 프로그래밍을 할 때 만나는 어려운 문제점은 에러를 만났을 때 좋은 진단 정보를 제공하는 것이다. Bochs 는 어셈블리 레벨 디버거를 포함한다. 그러나 GeekOS가 C로 작성된 이래로 컴파일러에 의한 어셈블리 코드는 특별히 도움을 주지 못한 것 같다. 복잡한 하드웨어 논쟁을 이해하는데 학생들의 짐을 덜어줄 것은 교육용 매체같은 하드웨어 에뮬레이션을 약속하는 것이다.

덧붙여 GeekOS에 어울리는 여러 가지 instructional tool을 계속적으로 개발하는 것이다. GeekOS에 가장 필요한 것은 paged 가상 메모리를 위한 지원이다.

디스크나 이더넷 같은 장치 드라이브는 매우 유용하게 할 것이다.

GeekOS는 현재 상호처리통신을 위한 그 어떤 메커니즘도 가지고 있지 않다. 물론 복잡하긴 하겠지만, 학생 프로젝트를 위해서는 매우 좋은 가능성을 줄 것이다.

6. Conclusions

GeekOS에서 보여준 순수 하드웨어를 위한 프로그래밍을 경험하는 것은 OS원리를 가르치는데 효과적인 방법이 된다.

 

hackingGeekOS_manual.pdf

Ubuntu_GeekOS_Bochs_update.pdf

projects(0~3).zip