Appendix A: Reference Guide

pc가 이 로더를 메모리에 적재하면, 이 로더는 디스크에서 kernel을 찾아서 메모리에 적재하고, start로 넘어간다. 어떻게 돌아가는지를 완벽하게 이해하는 것은 별로 중요하지 않지만, 관심 있으면 읽어봐라. 로더의 소스랑 같이 읽어보는 걸 추천한다. 너는 또한 80x86 아키텍쳐에 대한 이해가 있어야한다.

PC BIOS 는 로더를 첫번째 하드디스크의 첫번재 섹터(master boot record라고 부름)에서 로드한다.

PC는 MBR의 64바이트를 partition table로 예약해놓고, pintos는 추가적인 128바이츠를 kernel command-line arguments에 사용한다. 이것은 300 바이트 조금 넘는 크기가 로더의 own code를 위해 남는다는 소리다. 이건 곧, 어셈블리 언어로 쓰여야한다는 의미이다.(대충 300바이트 크기가 필요하니까 어셈블리로 작성되야한다는 소리인듯.)

로더의 첫 일은, 각 하드디스크의 파티션 테이블을 읽고, pintos kernel을 위한 부팅 가능한 파티션을 찾음으로써, 커널을 찾는 것이다.

로더가 부팅 가능한 커널 partition을 찾으면, paritions의 컨텐츠를 128kB 주소 번지로 들고온다. 파티션의 시작 부분에 있는 커널은 필요한 것보다 커지게 된다(partition boundary alignment convention 때문에), 그래서 로더는 512KB 이상을 읽지 않고, pintos 빌드 과정은 커널을 이것보다 크게 빌드하는 것을 허용하지 않는다. 이것보다 많은 양을 읽는 것은 BIOS와 하드웨어를 위해 PC 아키텍쳐에서 남겨놓은 640KB 부터 1메가 까지의 공간을 침법하게 되고, 이건 standard PC BIOS 는 1MB이상의 커널을 로드하는 방법을 제공하지 못한다는 뜻이다.

로더의 마지막 일은, 로드된 커널 이미지에서 첫 진입 포인트를 찾고, 글로 제어를 넘기는 것이다.

핀토스 커널 command line은 boot loader에 저장되어있다. pintos 프로그램은 커널을 실행시킬 때마다 디스크에 있는 부트 로더를 복사해서 들고온 다음, 유저가 커널에 제공하는 어떤 command-line arguments를 insert하고, 그 arguments들을 메모리 상에서 부트 로더 바깥에서 읽는다.

Low-Level Kernel 초기화

로더의 마지막 액션은 커널의 진입 포인트로 제어권을 넘기는 거다. 이 진입 포인트는 threads/start.S에 있는 start()함수임. 이 코드의 역할은 CPU를 legacy 16-bit “real mode”에서 주로 80x86 OS에서 사용되는 32비트 “protected mode”로 전환시킨다.

이 startup code의 첫번째 태스크는 머신의 메모리 사이즈를 획득하는 것이다. 이것을 위한 simplest BIOS function은 오직 64MB의 RAM을 감지하기 때문에, 이게 pintos가 지원하는 practical limit이다. 이 함수는 메모리 사이즈를 페이지로 저장하고, global variable인 init_ram_pages에 저장한다.

A20 line을 가능하게 한다는데... 무슨 말인지 잘 모르겠다.

basic page table을 생성한다. 이건 virtual memory의 64MB를 동일한 물리 주소로 사상시킨다. 또한 그건 0xc0000000 (3 GB)인 LOADER_PHYS_BASE이라는 가상 주소에 시작하는 물리 주소 또한 사상한다.

pintos 커널은 사실 후자만 있으면 되지만, 우리가 전자를 하지 않는다면, chicken-egg 문제를 가지고 있다. 우리의 현재 가상 주소는 roughly 0x20000(로더가 우리를 집어 넣는 주소)인데, 우리가 page table을 키기 전까지는 0xc0020000으로 jump하지 못한다. but if we turn on the page table without jumping there, then we’ve just pulled the rug out from under ourselves.

그리고 페이지 테이블이 initialized 되면, 우리는 CPU의 control register와 paging을 protected 모드로 키고, segment register를 setup 한다. protected mode에서 interrupt를 다룰 준비가 안됬기 때문에, 우리는 interrupts를 diable 시켜놨다. 마지막 step은 main을 호출하는 것이다.

요약

High-Level Kernel 초기화

main()함수는 C언어로 이루어져 있는데, pintos에서 마주치는 모든 코드는 여기 있다.

main()이 시작되면, system은 raw state를 가진다. 32bit protected mode에 paging이 가능한 상태지만, 아무것도 된게 없다. 이 때 main 함수는 pintos의 다른 모듈의 초기화 함수를 우선적으로 부른다. (module_init()이라는 함수에 주로 있는데, 여기서 module은 모듈 이름이고, module.c는 그것에 대한 구현체이며, module.h는 헤더이다)

맨 처음에 호출하는 것은 bss_init()이다. 이건 kernel’s BSS를 0으로 초기화한다. C에서, 함수 밖에서 선언한 변수를 초기화하지 않으면, 해당 변수는 BSS로 간다.

그 다음은 read_command_line을 호출한다. 이건 kernel command line을 arguments로 부수고, parse_options()를 통해 command line에서 옵션이 있는지를 검사한다.

thread_init()은 쓰레드 시스템을 initialize한다. pintos threads에 대해서는 나중에 후술. 이런 작업은 먼저 되는 편인데, 왜냐면 가능한 thread structure가 lock을 하는데 prerequisite하기 때문이다. 그리고 lock acquisition은 pintos subsytem에 굉장히 중요하다.

그 다음은 kernel의 메모리 시스템을 init하는 것들이다.

palloc_init()은 커널의 page allocator를 setup하는 것인데, 한 번에 메모리에 여러 개의 페이지를 나눠주는 것이다(A.5.1을 참고하길).

malloc_init은 임의 사이즈의 메모리 블록의 allocation을 핸들하는 allocator를 세팅한다.(A.5.2를 참고)

paging_init()은 kernel을 위한 page table을 세팅한다.(A.7을 참고)

프로젝트 2에서 main함수는 tss_init()과 gdt_init()을 또 호출할 거다.

그 다음 initialize는 interrupt 시스템이다.

intr_init()은 interrupt handling을 위해 CPU의 interrupt descriptor table을 셋업하고, timer_init(), kbd_init()을 호출한다(timer와 keyboard interrupt를 대비하기 위함). input_init()은 serial과 키보드 인풋을 하나의 스트림으로 합치기 위해 셋업된다.

project2의 뒷쪽에서, 우리는 exception_init이나 syscall_init을 사용하는 user program에 의해 생기는 interrupt를 핸들하기 위해 준비해야한다.

이제 우리는 스케쥴러를 thread_start()를 통해 시작할 수 있는데, 이것 idle thread를 만들고, interrupt를 가능하게 한다. 인터럽트가 가능해지면서, interrupt-driven한 serial port I/O 가 가능해지고, 따라서 우리는 serial_init_queue()를 통해 모드를 변경할 수 있다. 마지막으로 timer_calibrate()는 정확한 short delays를 위한 타이머를 calibrate한다.

프로젝트2에서 파일 시스템이 compiled된다면, 우리는 IDE disks를 ide_init()을 통해 intialize 하고 파일 시스템을 filesys_init()을 한다.

boot가 다 됬으니, message를 던진다.

run_cations()는 이제 kernel command line으로 들어온 액션들을 parse하고 execute한다(test를 위한 run과 같이) 마지막으로 ‘-q’가 kernel command line에 specified된다면, 우리는 shutdown_power_off()를 머신 시뮬레이터를 끄기 위해 호출한다. 반면에 main함수는 thread_exit()을 호출하는데, 이건 다른 running threads가 계속 running할 수 있도록 한다.

요약

https://poalim.tistory.com/23

https://lacti.github.io/2008/04/01/pintos-boot/

A.2 Threads

struct Thread

이 프로젝트에서, 너는 너의 own member를 여기 추가해야한다. 기존에 있는 멤버들에 대한 정의를 change하거나 delete할 수 있다.

모든 struct thread는 각자의 메모리 페이지의 시작을 점유한다. 나머지 영역은 thread’s stack을 위해 사용되는데, 이건 page의 끝에서 자라난다.

				4 kB +---------------------------------+
             |          kernel stack           |
             |                |                |
             |                |                |
             |                V                |
             |         grows downward          |
             |                                 |
             |                                 |
             |                                 |
             |                                 |
             |                                 |
             |                                 |
             |                                 |
             |                                 |
             +---------------------------------+
             |              magic              |
             |                :                |
             |                :                |
             |               name              |
             |              status             |
        0 kB +---------------------------------+
JavaScript
복사

위 그림처럼 생겼는데, 0kB부터 자라는거다. 나머지 영역은 thread만의 stack영역을 위해 자라난다.

전체 메모리에서 나머지는 kernel영역이다.

이건 두 가지 결론을 낳는다.

struct thread는 너무 커질 수 없다. 만약 너무 커지면, 커널 stack을 위한 충분한 room이 없다. 따라서 struct thread는 결국 few bytes이다. 주로 1kB이내로 유지된다.

kernel stacks 또한 너무 커지지 못한다. 너무 커지면, thread state와 겹친다. 그래서 kernel functions은 large structures 나 array를 non-static local variable로 배치하지 못한다. 대신 malloc이나 palloc_get_page를 대신 써라.

멤버들

•

tid_t tid

thread identifier. 모든 쓰레드는 unique한 tid를 가진다. tid_t 는 int에 대한 typedef이고, 새로운 스레드는 1부터 시작해서 높은 tid를 하나씩 받는다.

•

enum thread_status status

state를 나타내는데, THREAD_RUNNING, THREAD_READY, THREAD_BLOCKED를 나타낸다.

THREAD_RUNNING은 지금 딱 실행되고 있는 하나의 스레드를 얘기한다. thread_current()를 통해 얻는다.

ready to run 한 애들이지만, 지금 실행되지 않는 것들. thread는 그 다음에 실행되도록 선택될 수 있다. ready thread는 double linked list로 구현된 ready_list로 관리된다.

THREAD_BLOCKED은 어떤 것을 기다리고 있는 거다. lock이 가능하다면, interrupt가 필요하다. thread는 THREAD_READY 상태가 될 때까지 스케쥴링 되지 않는다.(즉 thread_unblock() 이 필요하다.). 이것은 thread를 자동으로 unblock, block 시킬 수 있는 편한 방법이다.

THREAD_DYING은 스케쥴러에 의해 파괴될 예정이고, 그 다음 thread로 스위칭 될 예정이다.

즉, 이 때 THREAD_READY 상태인 애들을 ready queue에 넣고 뺄 때의 순서를 정하는 것이 scheduling의 주된 작업이다. 현재는 round-robin 상태로 구현됨. queue에서 순서대로 실행되는 순서.

•

char name[16]

thread의 이름이다.

•

uint8_t *stack

모든 스레드는 각자의 상태를 관리하기 위한 스택이 있다. 스레드가 running 중일 때, CPU의 스택 포인터 레지스터는 stack의 top을 가리키고, 이 멤버(stack)은 사용되지 않는다. 그러나 CPU가 다른 thread로 switch될 때. 이 멤버들은 thread’s stack 포인터를 저장한다. 다른 멤버들은 thread’s register에 저장될 필요가 없는데, 왜냐면 다른 저장되어야하는 register들은 stack에 저장되기 때문이다.

interrupt가 발생할 때, 커널 또는 user program인지에 따라, struct intr_frame이 stack에 푸쉬된다. interrupt가 만약 user program에서 발생하면, struct intr_frame은 항상 페이지의 최상단에 위치해있다.

•

priority

PRI_MIN(0) 부터 PRI_MAX(63)로 범위가 잡혀있다. 낮은 숫자는 lower priorities에 대응되기에, priority 0은 가장 낮은 우선순위이고 63은 가장 높은 거다. pintos는 현재 thread priorities를 무시하도록 제공되었지만, project1에서 구현해내야한다. (Section 2.2.3을 살펴보시길)

•

struct list_elem allelem

“list element”는 모든 쓰레드의 list에 쓰레드를 링크하는데 사용된다. 각 쓰레드는, 만들어질 때 이 리스트에 삽입되고, exit했을 때, 제거된다. thread_foreach() function은 이 전체 쓰레드를 돌 때 사용된다.

An empty list looks like this:

                      +------+     +------+
                  <---| head |<--->| tail |--->
                      +------+     +------+

   A list with two elements in it looks like this:

        +------+     +-------+     +-------+     +------+
    <---| head |<--->|   1   |<--->|   2   |<--->| tail |<--->
        +------+     +-------+     +-------+     +------+
JavaScript
복사

이런 식으로 관리되고, double linked list로 관리된다.

각각의 노드의 타입은 list_elem이며, list 타입은 head와 tail만을 가지고 있다.

이 때, ready 상태에서 꺼내서 running 시켜주는 함수 = next_thread_to_run()이라는 함수 인데

이 함수는 ready_list에 있는 맨 앞 노드를 반환한다.

이 때, list_elem은 오직 앞 뒤 노드의 주소만을 가지고 있으므로, 그 노드를 반환해봐야 쓰레드를 실행시키는데 아무 도움이 안 되기에, pintos는 list_entry라는 함수를 제공한다.

이 함수가 어떻게 구현됬는지는 알기가 어렵지만, 주석에 따르면, 꺼내온 list_elem을 포함하는 전체 struct에 대한 포인터를 반환한다.

list_entry(LIST_ELEM, STRUCT, MEMBER)
JavaScript
복사

이렇게 생겼는데, 보면 embedding하는 타입이 어떤 형태인지와, list_elem이 해당 타입에서 어떤 멤버로 저장되어있는지를 식별해서 들고온다.

•

struct list_elem elem

한 개의 list elem는 ready_list나 sema_down()안의 semaphore를 기다리는 쓰레드 리스트에 들어갈 수 있다. 이중 의무를 가지는데, 왜냐면 semaphore를 기다리는 쓰레드가 ready가 안됬거나, ready가 됬는데, semaphore가 안 됬거나 하는 경우에 대해서...(???)

→ 대충 뭐 다양하게 쓰일 수 있다는 뜻 같음.

→ 보니까 thread_block(), thread_unblock(), next_thread_to_run()과 같은 함수에서 전부다 thread→elem을 사용하네.

•

uint32_t * pagedir

project2 그 이후에서나 쓰일거다. Section 4.1.2.3[Page Table]을 보자.

•

unsigned magic

항상 THREAD_MAGIC이 선언되는데, thread.c에 있는 임의이 숫자이고, stack overflow를 감지하기 위해 쓰인다. thread_current()는 이 변수를 체크한다. stack overflow는 이 값을 바꾸기 때문에, assertion에서 걸리게 된다. 이 혜택을 보려면, struct thread에 멤버를 추가할 때, magic 변수는 맨 마지막에 놔두기 바란다.

함수들

•

void thread_init(void)

main()에 의해서 thread system을 initalize하는 역할을 한다. 주요한 목적은 pintos의 initiail thread를 위한 struct thread를 생성하는 것이다. pintos loader가 페이지의 최상단에 initial thread의 stack을 put 해놓았기에 가능하다.

thread_init()이 실행되기 전에, thread_current()는 running thread의 magic 값이 정확하지 않기 때문에 실패한다. thread_current()에 대한 직접적이든, 간접적이든 수많은 function call들이 pintos initialization 중에 실행된다.

•

thread_start(void)

main()함수에 의해, 스케쥴러를 실행하기 위해 시작한다. idle thread를 만드는데, 이거는 ready인 다른 쓰레드가 없을 때 스케쥴 되는 쓰레드이다. 그리고 interrupt를 가능하게 만드는데, 이것은 부가적으로 스케쥴러가 동작하게끔 하는데, 왜냐하면 intr_yield_on_return()이라는 함수를 사용해 timer interrupt에서 오는 return에 대해서 스케쥴러가 돌기 때문이다.

•

thread_tick(void)

timer interrupt에 의해 호출된다. 매 시간 tick 마다. 이것은 쓰레드의 statistics를 확인하고, time slice가 expired됬을 때, scheduler를 trigger 시킨다.

•

thread_print_stats(void)

pintos가 shutdown 될 때, thread statistics를 프린트하기 위해 사용된다.

•

thread_create(const char *name, int priority, thread_func *func, void  *aux)

주어진 이름과 priority를 가지고 새로운 thread를 만들고 시작하는 거로, 새로운 tid를 반환한다. 이 쓰레드는 func을 실행하고, 넘어온 aux를 function의 single argument로 실행하게 한다.

thread_create()는 쓰레드의 struct thread를 위한 페이지를 allocate하고 그것의 멤버를 stack & initialize하며, 그리고 그것을 위한 fake stack frame을 set up한다. (thread switching에서 자세히 보기). 이 쓰레드는 blocked 상태에서 initialized 되고, return 직전에 unblocked 되는데, 이에 따라서 새로운 쓰레드는 schedule 가능한 상태가 된다.

•

thread_func(void *aux)

이건 thread_create()에 passed되는 함수 타입인데, aux argument는 function의 argument로 passing 된다.

•

thread_block(void)

◦

running 쓰레드를 running state에서 blocked state로 전환시키는 역할. 이렇게 되면 thread_unblock()이 호출되기 전까지, 이 쓰레드는 다시 돌지 않는다. thread_block()이 low-level이기 때문에, synchronization primitives 대신에 쓰는 것이 좋겠다.

•

thread_unblock(struct thread *thread)

◦

blocked 상태에 있는 thread를 ready state로 변경시키고, 이를 통해 running이 가능하게 한다. 이건 어떤 이벤트를 기다리고 있는 쓰레드가 다시 사용가능할 때 호출된다.

•

struct thread * thread_current(void)

◦

running thread를 return한다.

•

tid_t thread_tid(void)

◦

running thread의 tid를 반화한다.

•

const char* thread_name(void)

◦

running thread의 name을 반환한다.

•

thread_exit(void)

◦

current thread를 exit 시키고, 다시 안돌아온다.

•

thread_yield()

◦

CPU를 스케쥴러에 양보하고, 스케쥴러는 실행할 새 쓰레드를 고른다. 새 쓰레드는 current thread가 될꺼다. 그렇기에 이 쓰레드가 특정 시간동안 실행되는 것을 막기 위해 이 함수에 의존할 수는 없다.

•

thread_foreach(thread_action_func *action, void *aux)

◦

모든 thread t를 돌면서 action(t,aux)를 실행시킨다. action은 thread_action_func()으로 주어지는 시그니쳐와 형식이 맞아야한다. 

◦

thread_action_func(struct thread *thread, void *aux)

•

int thread_get_priority(void)

•

void thread_set_priority(int new_priority)

◦

thread priority를 get,set할 수 있는 stub이다. 섹션 2.2.3을 보자

•

thread_get_nice, thread_set_nice, thread_Get_recent_cpu, thread_get_load_avg

◦

advanced 스케쥴러를 위함. Appendix B를 보자

Thread Switching

schedule()은 쓰레드를 switching 하는 것에 책임이 있다. 이것은 thread.c에 있으며, 쓰레드를 switch 시키는 세 가지의 public thread function에 의해 호출된다. - thread_block(), thread_exit(), thread_yield()

이 함수가 schedule()함수를 호출하기 전, 얘네들은 interrupt를 disable 시키거나, 이미 disable되있다는 것은 보장해야하고, 그리고 나서야 running 쓰레드의 상태를 다른 걸로 바꾼다.

schedule()은 짧지만 tricky하다. 이것은 현재 쓰레드를 local variable 인 cur,에 저장하고, 그 다음에 실행한 쓰레드를 next라는 local variable에 저장한다.(next_thread_to_run()이라는 함수를 통해). 그리고 나면 switch_threads()를 호출해서, 실제 thread switch를 실행한다.

The thread we switched to was also running inside switch_threads(), as are all the threads not currently running, so the new thread now returns out of switch_threads(), returning the previously running thread.

→ 대충 옛날꺼를 뱉는 다는 거 같음.

switch_threads()는 어셈블리 언어이다. 이건 stack에 register를 저장하고, cpu의 현재 stack 포인터를 현재 쓰레드의 stack 멤버 변수에 추가한후, 새로운 쓰레드의 stack 변수를 cpu의 stack포인터에 다시 넣는다. → 대충 어셈블리로 되있어서, 알아서 된다는거 같음

스케쥴러의 나머지는 thread_schedule_tail()에 구현되어있다. 이건 running하는 새로운 쓰레드를 marks한다. 우리가 스위치 되서 나온 쓰레드가 dying state라면, 그것의 페이지를 free 시켜준다. 이 영역은 쓰레드 스위치 전에는 free 되지 못하는데, 왜냐면 스위치가 그 쓰레드 자체를 필요로하기 때문이다.

처음으로 실행되는 running thread는 특별한 케이스다. thread_create()가 새로운 쓰레드르 만들면, 정상적으로 실행되기 위해서 몇 가지 문제에 부딫힌다. 특히, 새로운 쓰레드가 아직 running을 실행하지 않았다면, 스케쥴러가 예상하듯이 switch_threads()안에서 running 상태로 바꿀 방법이 없다.

이 문제를 해결하기 위해, thread_create()는 새로운 쓰레드를 위해서 fake stack frame을 만든다.

The topmost fake stack frame is for switch_threads(), represented by struct switch_threads_frame. The important part of this frame is its eip member, the return address. We point eip to switch_entry(), indicating it to be the function that called switch_entry(). • The next fake stack frame is for switch_entry(), an assembly language routine in ‘threads/switch.S’ that adjusts the stack pointer,1 calls thread_schedule_tail() (this special case is why thread_schedule_tail() is separate from schedule()), and returns. We fill in its stack frame so that it returns into kernel_thread(), a function in ‘threads/thread.c’. 1 This is because switch_threads() takes arguments on the stack and the 80x86 SVR4 calling convention requires the caller, not the called function, to remove them when the call is complete. See [SysV-i386] chapter 3 for details. Appendix A: Reference Guide 66 • The final stack frame is for kernel_thread(), which enables interrupts and calls the thread’s function (the function passed to thread_create()). If the thread’s function returns, it calls thread_exit() to terminate the thread.

https://poalim.tistory.com/26

A.3 Synchronization

쓰레드 간의 공유되는 자원을 조심스럽게 다루지 않으면, 결과는 엉망이 된다. 이건 특히 커널 시스템에서 심한데, 잘못되면 전체 머신이 고장나기 때문이다. pintos는 몇 가지 synchronization할 수 있는 방법을 준다.

Disabling Interrupts(인터럽트 비활성화)

가장 쉬운 방법은 interrupt를 끄는거다. 이러면 CPU가 인터럽트에 응답하는 것을 일시적으로 막을 수 있다. 인터럽트가 꺼지면, 다른 쓰레드는 running thread를 선점하지 못한다. 왜냐하면 쓰레드 선점은 timer interrupr에 의해 발생하기 때문이다. 만약 인터럽트가 켜지면, 다시 정상적으로 running thread가 언제든지 선점될 수 있다.

그런데, 이 말은 pintos가 preemptible kernel이라는 뜻인데, 이 말은 kernel thread는 언제든지 선점당할 수 있다는 뜻이다. 전통적인 UNIX 시스템은 선점 불가능한데, 이 말은 커널 쓰레드는 오직 스케쥴러에 의해 명시적으로 불러졌을 때에만 선점 당할 수 있다. 너가 예상하듯, preemptible kernel은 좀 더 명시적인 synchronization이 필요하다.

너는 인터럽트 상태를 좀 더 directly하게 설저할 필요가 있다. 대부분은 아래에서 설명할 다른 동기화 방법을 사용할테지만, disable interrupts를 사용하는 가장 큰 이유는 external interrupt handler와 함께 kernel thread를 동기화시켜야하기 때문이다. 이 external interrupt handler는 재울 수 없기에, 다른 형태의 synchronization은 할 수 없다. A.4.3 External Interrupt Handling 참조

어떤 외부 인터럽트들은 disabling interrupt를 하더라도, 연기될 수 없다. 이런 인터럽들을 non-maskable interrupts라고 하며, 급할 때만 주로 사용된다. 예를 들어 computer is on fire. 핀토스는 Non-maskable interrupt를 다루지 않는다.

•

enum intr_level

◦

INTR_OFF이거나 INTR_ON임. 인터럽트가 가능한지 불가능한지를 나타낸다.

•

enum intr_level intr_get_level(void)

◦

현재 인터럽트의 상태를 나타낸다.

•

enum intr_level intr_set_level(enum intr_level level)

◦

인터럽트를 레벨에 따라서 껐다 켰다 할 수 있다. 이전 상태를 반환

•

enum intr_level intr_enable(void)

◦

인터럽트를 키고, 이전 상태를 반환

•

intr_level intr_disable(void)

◦

인터럽트를 끄고, 이전 상태를 반환

세마포어

세마포어는 음이 아닌 정수이고, 각각 원자적으로 조작이 가능한 두 가지 연산을 제공한다.

Down , P : 양이 될 때까지 기다리고 감소시킨다.

Up , V: 값을 증가시키고, 기다리는 쓰레드 중 하나를 깨운다.

세마포어는 맨 처음에 0으로 초기화되고, 딱 한번 일어나야할 이벤트를 위해 기다린다. 예를 들어 쓰레드 A가 쓰레드 B를 시작시키고, B의 활동이 끝날때까지 기다려야한다고 해보자. A는 0으로 초기화된 세마포어를 만들고, 그것을 B가 시작할 때 pass시키고, down한다. 그리고 B가 활동이 끝난다면, up시킨다. 이건 down이나 up 중 어떤게 먼저 실행되냐와 무관한다.

세마포어가 1로 초기화된다면, 보통 자원 접근에 대한 조작을 하기 위해 사용된다. 이 자원을 사용하는 코드가 시작되기 전에, down을 하고, 시작되고 나면 up하는 방식으로 진행. lock의 경우에는 좀 더 정확하다. 세마포어는 1보다 큰 숫자로도 초기화될 수 있는데, 거의 사용하지 않는다. 다익스트라에 의해 처음 발명됬고, THE 운영체제에 처음 사용된다. threads/synch.h에 있다.

•

struct semaphore

◦

세마포어를 표현함

•

void sema_init(struct semaphore *sema, unsigned value)

◦

sema를 새로운 세마포어로 주어진 값으로 초기화한다.

•

void sema_down(struct semaphore *sema)

◦

down이나 P 연산을 수행하고, 그것의 값이 양이 될 때까지 기다린다. 그리고 그 값을 하나 차감한다.

•

bool sema_try_down(struct semaphore *sema)

◦

down이나 P 연산을 시도한다. 기다리지 않고. 만약 성공적으로 decremented 됬다면 true를 리턴하고, 이미 0이라서 감소되지 않으면 waiting 없이, false를 반환한다. tight loop에서 이 함수를 돌리는 것은 CPU 타임을 잡아먹으므로 sema_down()을 쓰던가, 다른 방법을 찾아봐라.

•

void sema_up(struct semaphore *sema)

◦

up이나 V연산을 시도하고, 값을 올린다. 만약 이 sema를 기다리는 함수들이 있다면, 그 중에 하나를 wake up한다.

◦

대부분의 synchronization primitives와 다르게 sema_up()은 external interrupt handler안에서 호출될 수 있다. (???)

세마포어는 내부적으로 disabling interrupt 와 thread_block과 thread_unblock 없이 구현되어있다. 각 세마포어는 waiting thread의 리스트를 유지하고 있다.

Lock

락은 세마포어와 비슷한 것이다. up에 해당하는 게 release이고 down에 해당하는게 acquire이다.

세마포어와 비교해서, 한 가지 추가된 restriction이 있다. 락을 획득한 쓰레드만, 그것은 release할 수 있다. 만약 이 제한이 문제라면, 이것은 락 대신에 세마포어가 사용되야한다는 좋은 신호이다.

핀토스에서 락은 recursive하지 않다. 이 말은, 현재 락을 들고 있는 쓰레드가 이 락을 획득하려고 하는 것은 에러라는 뜻이다. 락의 타입과 함수는 synch.h에 있다.

•

struct lock

◦

lock을 나타낸다.

•

void lock_init(struct lock *lock)

◦

새로운 lock을 init한다. 어떤 쓰레드에 의해서도 소유되지 않는다.

•

void lock_acquire(struct lock *lock)

◦

current thread에서 락을 획득하려고 하고, 필요하다면 current owner가 release해주기를 기다리낟.

•

void lock_try_acquire(struct lock *lock)

◦

current thread에 의해 사용될 락을 획득하려고 하는데, 기다리지 않는다. 성공하면 true를 리턴하고 만약 이미 소유 중이라면 false를 뱉는다. tight loop 안에서 이 함수를 호출하는 것은 CPU시간을 소비하기에 좋지 않다. 따라서 lock_acquire()를 대신 사용해라.

•

void lock_release(struct lock* lock)

◦

lock을 풀어준다. current thread가 가지고 있는

•

bool lock_held_by_current_thread(const struct lock *lock)

◦

running thread가 해당 락을 가졌는지를 리턴한다. 임의의 쓰레드가 해당 락을 가졌는지 테스트하는 함수가 없기 때문에, caller가 행동하기 전에 답이 바뀔 수 있다.(???)

Monitors

모니터는 세마포어나 락보다 좀 더 추상적인 개념이다. 모니터는 동기화되야하는 데이터와 lock을 가지고 있고, 이 락을 monitor lock이라 부른다. 그리고 condition variable이라는 걸 들고 있다.

보호된 데이터에 접근하기 전에, 쓰레드는 모니터 락을 획득해야한다. 이거를 ‘in the monitor’라고 표현한다. 모니터 안에 있는 동안, 쓰레드는 모든 보호된 데이터를 조작할 수 있다. 다했을 때, Monitor lock을 release한다.

condition variable은 모니터 락에 있는 코드가 컨디션들이 참이기를 기다리도록 할 수 있다. 각 condition variable은 추상적인 컨디션과 관련이 있다. 예를 들어 ‘어떤 데이터가 처리를 위해 도착해야한다.’ 든지 ‘사용자 키스트로크가 있은 뒤에 10초 뒤에 패스한다.’ 든지. 만약 모니터 안의 코드가 컨디션이 참이 될때까지 기다려야한다면, 그것은 관련된 condition variable을 기다리고, 락을 풀어주면서 조건이 signaled될 때까지 기다린다. 만약 반대로, 모니터의 조건이 참이 된다면, waiter 하나를 깨우든가, 그 와 관련된 모든 애들에게 ‘broadcast’한다.

모니터를 위한 이론적인 framework는 C.A.R Hoare에 의해 설명된다. 실제 사용은 나중에 Mesa operating system에서 사용됨. synch.h에 정의되어있다.

•

struct condition

◦

condition variable을 나타낸다.

•

void cond_init(struct condition * cond)

◦

새로운 컨디션 변수를 초기화한다.

•

void cond_wait(struct condition *cond, struct lock *lock)

◦

원자적으로 Lock을 release하고, 다른 코드에 의해서 cond가 signaled되기를 기다린다. 만약 cond가 signaled되고 난 뒤에, return 하기 전에 lock을 reacquire한다. lock은 이 함수를 호출하기 전에 held되어있어야한다.

◦

signal을 보내고 wait에서 깨우는 것은 atomic operation이 아니기에, cond_wiat()’s caller는 wait가 끝나고 나서 다시 한번 컨디션을 체크해야하고, 필요하다면 wait해야한다. 

•

void cond_signal(struct condition *cond, struct lock *lock)

◦

만약 어떤 쓰레드가 cond(protected by monitor lock lock)를 기다리고 있다면, 이 함수는 그 중 하나를 깨운다. 만약 기다리는 쓰레드가 없다면, 아무 행동도 하지 않고 리턴한다.

◦

락은 이 함수가 실행되기 전에 held되있어야한다.

•

void cond_boadcase(struct condition *cond, strcut lock *lock)

◦

모든 쓰레드를 wake up한다. lock은 이 함수가 호출되기 전에 held되있어야한다.

Monitor Example

https://firecatlibrary.tistory.com/58

Optimization Barriers

optimization barrier는 컴파일러가 barrier를 넘어서 메모리 상태에 대한 추측을 하는 것을 막는다. 컴파일러는 barrier를 넘어서는 변수에 대한 읽기와 쓰기 순서를 재정렬하지 않거나, barrier 사이에서는 변수들의 값이 변하지 않는다고 가정한다. 주소값이 절대 얻어질 수 없는 지역 변수를 제외하고는. barrier()라는 매크로를 제공한다.

이거를 사용하는 이유는 데이터가 비동기적으로 바뀔 때이다. too_many_loops() 함수가 그 예시이다. 이 함수는 타이머 틱이 발생할 때까지 busy-waiting loop가 실행된다.

optimization barrier 없이는, 컴파일러는 그 반복문이 절대 종료되지 않을거라 결론내린다, 왜냐하면 start와 ticks는 무조건 같게 시작하고, 달라지지 않을꺼기 때문이다. 그래서 이 함수를 무한 루프로 최적화하는데, 이건 우리가 원하는 방향은 아니다.

optimization barrier는 다른 컴파일러 최적화를 피할 수 있다. busy_wait()함수가 또다른 예시이다.

이 함수의 주 목적은 loops가 0이 될때까지 busy-wait하는 것이다. barrier() 없이는, 컴파일러는 이 루프를 완전히 삭제할 수 있다. 왜냐면 그것이 아무런 useful output과 부작용이 없기 대문이다. barrier는 컴파일러에게 loop의 몸체가 굉장히 중요하다는 것을 얘기한다.

그 결과, optimization barrier는 메모리의 읽기와 쓰기를 ordering하기를 강제시킬 수 있다. 예를 들어 우리가 새로운 기능을 추가한다고 하자. 만약 타이머 인터럽트가 발생하면, 전역변수 timer_put_char에 있는 문자가 콘솔에 출력되도록 하자. 하지만 timer_do_put이 true일 때만이어야한다. 이럴 때 barrier()를 쓸 수 있다.

barrier 없이는 컴파일러가 코드의 순서를 마음대로 바꿔도 되기 때문에, 이 케이스에서는 컴파일러는 순서가 얼마나 중요한지 모르기에, 그냥 그 순서를 바꾸도록 허용한다. 실제로 그럴지는 모르지만, 그럴 가능성을 남겨놓는거다.

다른 해결책은 이 구문 주변에 인터럽트를 disable해놓는 것이다. 이것 또한 reordering을 막기는 하지만, 이것은 구문들 사이에서 일어나는 인터럽트 핸들러 또한 막는다. 이건 extra runtime cost를 야기한다.

??? 어따 쓰지 이건....

A.4 Interrupt Handling

인터럽트는 CPU에게 이벤트를 알려준다. 운영체제의 대부분의 일은 인터럽트랑 관련이 있다. 우리의 목적에 맞게, 우리는 인터럽트를 두 가지 큰 카테고리로 분류한다.

•

internal interrupt

◦

내부 인터럽트는, CPU instructions에 이해 직접적으로 불러진 것을 의미한다. invalid memory access를 시도한다든가, 아니면 0으로 나누기를 한다든가 등의 활동은 internal interrupt를 발생시킨다. 이것은 CPU instruction에 의해 생기기 때문에, internal interrupt는 synchronous 하거나 CPU instruction에 synchronized 되어있다.

◦

intr_disable()은 내부 인터럽트를 비활성화 시키지 못한다.

•

external interrupt

◦

외부 인터럽트는 CPU 바깥에서 발생한 것들이다. 이 인터럽트는 system timer, keybord, serial ports, disk 등과 같은 하드웨어 장치에서 발생한다. 외부 인터럽트는 asynchronous한데, 이건 인터럽트의 전달이 instruction execution과 동기화되있지 않다는 뜻이다. external interrupt는 intr_disable()을 통해 연기 될 수 있다.

CPU는 두 가지 분류를 같은 방법으로 처리한다, 따라서 pintos는 두 가지 클래스를 다루기 위한 공통 infrastructure를 가지고 있다. 앞으로 나올 내용에서 이것에 대해 설명한다. 아직 IA32-v1의 chapter3, Basic Execution Environment를 읽지 않았다면, 읽기를 바란다. 5장도 대충 읽어보면 좋음

Interrupt Infrastructure

인터럽트가 발생하면, CPU는 스택의 필수적인 정보를 저장하고, interrupt handler routine으로 넘어간다. 80x86 아키텍처에서는 256가지 인터럽트를 지원하고, 0부터 255까지 있다. 각가은 서로 독립적인 핸들러를 interrupt descriptor table이라 불리는 핸들러에 가지고 있다.

핀토스에는 intr_init()함수가 IDT를 세팅해서, 각각의 엔트리가 threads/intr-stubs.S에 intrNN_stub()에 고유한 entry point를 가리키고 있는데, NN은 hexadecimal 한 인터럽트 넘버이다. CPU가 우리에게 interrupt 숫자를 알아낼 방법을 알려주진 않기에, 각 entry point는 interrupt number를 숫자에 밀어넣는다. 그리고 intr_entry()로 점프하는데, 이건 프로세서가 아직 밀어넣지 못한 레지스터들을 스택에 밀어넣어주고, intr_handler()를 호출하면, 이제 다시 interrupt.c에 있는 코드로 이동한다.

intr_handler()의 주요한 일은 특정 인터럽트를 handling하기 위해 등록된 함수들을 call하는 것이다. 만약 아무 함수도 등록되어있지 않다면, panic을 띄운다.

intr_handler()에서 돌아오면, intr-stubs.S의 어셈블리 코드는 모든 CPU레지스터들을 회복시키고, 인터럽트에서 CPU로 돌아온다.

•

void intr_handler_func(struct intr_frame *frame)

◦

인터럽트 핸들러 함수가 선언되는 방식이다. frame argument는 인터럽트의 원인과 인터럽트 된 쓰레드의 상태를 설명하도록 해준다.

•

struct intr_frame

◦

인터럽트 핸들러의 stack frame이고, CPU와 인터럽트 스텁 그리고 intr_entry()에 의해 저장된다. 

◦

각종 register들의 value

◦

uint32_t vec_no : 인터럽트 벡터의 숫자이다. 0~255

◦

uint32_t error_code: CPU에 의해 스택에 집어넣지는 error Cdoe

◦

void (*eip) (void) : 그 다음 명령이 실행될 주소.

◦

void * esp: 인터럽트된 쓰레드의 stack pointer

◦

const char * intr_name(uint8_t vec): 인터럽트 숫자인 vec의 이름을 return 한다. 이름이 없으면 ‘unknown’ 리턴

Internal Interrupt Handling

내부 인터럽트는 CPU 연산에 의해 발생하는 것으로 kernel thread나 사용자 프로그램을 실행시키는 중에 일어난다. internal interrupt는 그러면 process context 안에서 일어난다고 말할 수 있겠다.

내부 인터럽트 핸들러 안에서, struct intr_frame을 평가하고 interrupt handler로 패싱하며, 수정할 수도 있다.

인터럽트에서 돌아오면, struct intr_frame의 수정사항은 process state 또는 불러낸 쓰레드에 변화가 된다.

예시로, pintos 시스템 call handler는 저장된 EAX register의 값을 수정함으로써 user program에게 값을 전달한다.

internal interrupt가 뭘 할 수 있을지 없을지가 딱 정해진게 없다. 일반적으로 다른 모든 코드처럼 인터럽트가 켜진 상태에서 실행이 되고, 그렇기에 다른 kernel thread에 의해 선점될 수 있다. 따라서 다른 쓰레드나 shared data, 그리고 자원들과 synchronized 되야한다.

internal interrupt 핸들러는 recursive하게 호출될 수 있다. 예를 들어 시스템 콜 핸들러는 user memory를 읽는 와중에 page fault를 발생시킬 수 있다. deep recursion은 한정된 커널 스택을 넘길 위험이 있다.

•

void intr_register_int(uint8_t vec, int dpl, enum intr_level level, intr_handler_func *handler, const char *name)

◦

vec으로 명명된 내부 인터럽트가 발생될 때 호출될 handler를 등록한다. 디버깅 목적으로 name으로 인터럽트에 이름을 붙여줄 수 있다.

◦

만약 level이 INTR_ON이라면, interrupt handler의 실행 중에 외부 인터럽트가 적절히 처리될 수 있다. INTR_OFF로 명시하면, external interrupt가 interrupt handler를 호출할 때 CPU가 external interrupt가 불가능하도록 막는다. 이 효과는 intr_disable()과는 핸들러 안에서 약가 다른데, 왜냐면 intr_disable()은 하나 이상의 CPU 연산의 window를 남겨놔서, external interrupts가 가능하도록 한다. 이것은 page fault handler에 중요하다. userprog/exception.c의 주석을 봐라.

◦

dpl은 인터럽트가 어떻게 호출될지를 결정한다. 0이면 인터럽트는 오직 kernel thread에 의해 호출된다. 반면 3이면, 사용자 프로세스가 명시적으로 INT instruction 과 함께 interrupt를 발생시킬 수 있다. dpl의 값은 user process가 인터럽트를 간접적으로 호출하는 것에 영향을 주지 않는데, 예를 들면 invalid memory reference 는 dpl과 상관없이 발생할 수 있다.(뭔소리지...)

external interrupt handling

외부 인터럽트는 CPU밖에서 일어나는 이벤트이다. asynchronous하기에, 언제든지 발생할 수 있으며 따라서 disable할 수 없다. external interrupt는 interrupt context에서 실행된다.

외부 인터럽트에서, struct intr_frame은 크게 의미가 없다. 그것은 쓰레드나 프로세스의 상태를 설명하지만, 어떤 것인지 예측할 방법이 없다(???) 가능하다면, 거의 필요 없겠지만, 그것을 평가하고 수정하는 것은 재앙으로 가는 지름길이다.

오직 하나의 외부 인터럽트만 at a time에 Processed 될 수 있다. 내부든 외부든 간에 외부 인터럽트에는 nested 될 수 없다. 따라서 외부 인터럽트 핸들러는 무조건 interrupts가 disabled된 상태에서 실행된다.

외부 인터럽트 핸들러는 sleep하거나 yield하지 못한다, 이 말은 lock_acquire(), thread_yield()가 안 먹힌다는 거다. interrupt context안에서 자는 것은 인터럽트 핸들러가 다시 스케쥴되고 리턴될 때까지 인터럽트된 쓰레드를 재우는 좋은 방법이다. 운이 안좋은 쓰레드에게는 Unfair할 수도 있고, 핸들러가 다른 자는 쓰레드를 기다리고 있다면 deadlock이 걸릴 수도 있다.

external interrupt handler는 효과적으로 머신을 독점하고 다른 활동을 delay시킨다. 따라서 외부 인터럽트 핸들러는 가능한 빨리 완료되야한다.

Anything that require much CPU time should instead run in a kernel thread, possibly one that the interrupt triggers using a synchronization primitive.(????)

외부 인터럽트는 CPU의 밖에 있는 장치들에 의해서 조작될 수 있다. intr_init()이 될 때, 이 PIC도 같이 셋업된다. PIC는 개별 외부 인터럽트를 위한 처리 마지막에 인식된다. intr_handler()는 pic_end_of_interrupt()를 부르는데 신경쓰는데, 이것은 PIC에 적절한 신호를 준다.

•

intr_register_ext(uint8_t vec, intr_handler_func *handler, const char *name)

◦

vec으로 numbered된 외부 인터럽트가 호출될 때 불러질 핸들러를 등록한다. 이름은 디버깅 목적으로 사용된다. the handler will run with interrupts disabled

•

bool intr_context(void)

◦

인터럽트 컨텍스트 안에서 실행중이라면 true를 뱉고, 아니라면 false를 준다. 주로 자고 있는 함수 안에서나 interrupt context에서 호출되면 안되는 애들일 경우 Assert(!intr_contex())이런 식으로 사용된다.

•

intr_yield_on_return(void)

◦

interrupt context에서 호출되면, thread_yield()를 인터럽트 리턴이 되기 직전에 호출한다. timer interrupt handler에서 주로 사용하고, 쓰레드의 time slice가 expire됬을 때, 새 쓰레드르 스케쥴하기 위해 사용한다.