Pintos-kaist Guide - PROJECT 1: THREADS - Introduction

Project1: Threads

이번 과제에서는 최소한의 기능만 있는 스레드 시스템을 제공합니다. 여러분은 이 시스템의 기능을 확장하여 동기화 문제에 대한 이해도를 높여야 합니다. 주된 작업 디렉토리는 threads이지만, devices 디렉토리에서도 부수적인 작업이 필요합니다. 컴파일은 threads 디렉토리에서 수행해야 하며, 프로젝트 설명을 읽기 전에 동기화 관련 자료를 먼저 살펴보는 것이 좋습니다.

 

Background

Understanding Threads

첫 번째 과제는 초기 스레드 시스템 코드를 읽고 이해하는 것입니다. Pintos에는 이미 스레드 생성과 종료, 스레드 간 전환을 위한 간단한 스케줄러, 그리고 세마포어, 잠금, 조건 변수, 최적화 장벽 등의 동기화 프리미티브가 구현되어 있습니다.

 

일부 코드는 다소 미스터리하게 보일 수 있습니다. 아직 소개에 설명된 대로 기본 시스템을 컴파일하고 실행해보지 않았다면 지금 해보세요. 소스 코드를 읽어보면 무슨 일이 일어나는지 알 수 있습니다. 원한다면 printf()를 적절한 위치에 추가하여 재컴파일 및 실행해 보세요. 그러면 무슨 일이 일어나는지와 그 순서를 확인할 수 있습니다. 또한 디버거를 사용하여 커널을 실행하고, 관심 있는 지점에 중단점을 설정한 후 단계별로 코드를 실행하고 데이터를 검사해볼 수도 있습니다.

 

스레드가 생성되면 새로운 실행 컨텍스트가 만들어져 스케줄링됩니다. thread_create() 함수의 인수로 이 컨텍스트에서 실행될 함수를 제공합니다. 스레드가 처음 스케줄링되어 실행되면 해당 함수의 시작 부분부터 실행되며, 함수가 반환되면 스레드는 종료됩니다. 따라서 각 스레드는 Pintos 내부에서 실행되는 미니 프로그램과 같이 동작하며, thread_create()에 전달된 함수가 main() 역할을 합니다.

 

주어진 시점에는 오직 하나의 스레드만 실행되며, 나머지 스레드는 비활성 상태가 됩니다. 스케줄러가 다음에 실행할 스레드를 결정합니다. 만약 주어진 시점에 실행 가능한 스레드가 없다면, idle() 함수에 구현된 특수 idle 스레드가 실행됩니다. 한 스레드가 다른 스레드의 작업을 기다려야 할 경우, 동기화 프리미티브를 통해 컨텍스트 전환이 강제될 수 있습니다.

 

컨텍스트 전환의 핵심 동작은 threads/thread.c 파일의 thread_launch() 함수에 구현되어 있습니다. (자세한 내용을 이해할 필요는 없습니다.) 해당 함수는 현재 실행 중인 스레드의 상태를 저장하고, 전환할 대상 스레드의 상태를 복원하는 역할을 합니다.

 

GDB 디버거를 사용하여 컨텍스트 전환 과정을 천천히 추적해보세요(GDB 설명서 참조). schedule() 함수에 중단점을 설정한 후 단계별로 실행해 나가세요. 각 스레드의 주소와 상태, 그리고 호출 스택에 어떤 프로시저가 있는지 주의 깊게 확인하세요. 한 스레드가 do_iret()에서 iret을 실행하면 다른 스레드로 실행이 전환되는 모습을 확인할 수 있습니다.

 

경고: Pintos에서는 각 스레드에 4KB 미만의 작은 고정 크기 실행 스택이 할당됩니다. 커널은 스택 오버플로를 감지하려 하지만 완벽하지 않습니다. 따라서 큰 데이터 구조를 non-static 지역 변수로 선언하면(예: int buf[1000];) 예기치 않은 커널 패닉 등의 문제가 발생할 수 있습니다. 스택 할당 대신 페이지 할당자나 블록 할당자를 사용하는 것이 좋습니다(메모리 할당 섹션 참조).

 

source Files

threads와 include/threads 디렉토리에 있는 파일들에 대한 간단한 개요입니다. 대부분의 코드는 수정할 필요가 없지만, 이 개요를 통해 어떤 코드를 확인해야 할지 파악하는 데 도움이 되기를 바랍니다.

 

threads 코드

• loader.S, loader.h
  • 커널 로더 코드입니다. PC BIOS가 메모리에 로드하는 512바이트 크기의 어셈블리 코드와 데이터로 구성되어 있습니다. 이 코드는 디스크에서 커널을 찾아 메모리에 로드한 후 start.S의 bootstrap() 함수로 점프합니다. 이 코드를 직접 보거나 수정할 필요는 없습니다. 반면 start.S는 메모리 보호 설정과 64비트 긴 모드 전환을 위한 기본 설정 코드로, 실제 커널의 일부입니다.
• kernel.lds.S
  • 커널을 연결하는 데 사용되는 링커 스크립트입니다. 커널의 로드 주소를 설정하고 start.S가 커널 이미지의 시작 부분 근처에 위치하도록 정렬합니다. 다시 말하지만, 이 코드를 보거나 수정할 필요는 없지만 궁금한 경우를 대비하여 여기에 있습니다.
• init.c, init.h
  • 커널의 메인 프로그램인 main()을 포함한 커널 초기화. 최소한 main()을 살펴보고 무엇이 초기화되는지 확인해야 합니다. 여기에 자신만의 초기화 코드를 추가할 수도 있습니다.
• thread.c, thread.h
  • 기본 스레드 지원. 대부분의 작업은 이 파일에서 이루어집니다. thread.h는 네 개의 프로젝트 모두에서 수정할 가능성이 높은 구조체 스레드를 정의합니다. 자세한 내용은 Threads를 참조하세요.
• palloc.c, palloc.h
  • 페이지 할당기는 시스템 메모리를 4kB 페이지의 배수로 나눠주는 페이지 할당기입니다. 자세한 내용은 Page Allocator를 참조하세요.
• malloc.c, malloc.h
  • 커널용 malloc() 및 free()의 간단한 구현입니다. 자세한 내용은 Block Allocator를 참조하세요.
• interrupt.c, interrupt.h
  • 기본 인터럽트 처리 및 인터럽트를 켜고 끄는 기능.
• intr-stubs.S, intr-stubs.h
  • 낮은 레벨의 인터럽트 처리를 위한 어셈블리 코드입니다.
• synch.c, synch.h
  • 기본 동기화 기본 요소: semaphores(세마포어), locks, condition variables(조건 변수), optimization barriers(최적화 배리어). 네 가지 프로젝트 모두에서 동기화를 위해 이 기본 요소를 사용해야 합니다. 자세한 내용은 동기화(Synchronization)를 참조하세요.
• mmu.c, mmu.h
  • x86-64 페이지 테이블 작업용 함수. 실습1 이후에 이 파일을 자세히 살펴보겠습니다.
• io.h
  • I/O 포트 액세스를 위한 함수입니다. 이 함수는 대부분 devices 디렉터리에 있는 소스 코드에서 사용하므로 건드릴 필요가 없습니다.
• vaddr.h, pte.h
  • 가상 주소 및 페이지 테이블 항목 작업을 위한 함수 및 매크로입니다. 이는 프로젝트 3에서 더 중요해질 것입니다. 지금은 무시해도 됩니다.
• flags.h
  • x86-64 flags 레지스터에서 몇 비트를 정의하는 매크로. 딱히 흥미롭진 않습니다.

 

devices 코드

기본 스레드 커널에는 이러한 파일도 devices 디렉터리에 포함되어 있습니다:

• timer.c, timer.h
  • 기본적으로 초당 100회 ticks하는 시스템 타이머입니다. 이 프로젝트에서 이 코드를 수정합니다.
• vga.c, vga.h
  • VGA 디스플레이 드라이버. 화면에 텍스트를 쓰는 일을 담당합니다. 이 코드를 볼 필요는 없습니다. VGA 디스플레이 드라이버에서 printf() 함수를 대신 호출하므로 이 코드를 직접 호출할 이유는 거의 없습니다.
• serial.c, serial.h
  • 직렬 포트 드라이버. 다시 말하지만, 이 코드는 printf()가 대신 호출하므로 직접 호출할 필요가 없습니다. 이 코드는 직렬 입력을 입력 계층으로 전달하여 처리합니다(아래 참조).
• block.c, block.h
  • 블록 디바이스, 즉 고정 크기 블록의 배열로 구성된 랜덤 액세스 디스크와 같은 디바이스를 위한 추상화 계층입니다. 기본적으로 Pintos는 두 가지 유형의 블록 장치를 지원합니다: IDE 디스크와 파티션. 블록 장치는 유형에 관계없이 프로젝트 2까지는 실제로 사용되지 않습니다.
• ide.c, ide.h
  • 최대 4개의 IDE 디스크에서 섹터 읽기 및 쓰기를 지원합니다.
• partition.c, partition.h
  • 디스크의 파티션 구조를 이해하여 단일 디스크를 여러 영역(파티션)으로 분할하여 독립적으로 사용할 수 있도록 합니다.
• kbd.c, kbd.h
  • 키보드 드라이버. 키 입력을 처리하여 입력 레이어에 전달합니다(아래 참조).
• input.c, input.h
  • 입력 레이어. 키보드 또는 직렬 드라이버가 전달한 입력 문자를 대기열에 넣습니다.
• intq.c, intq.h
  • 커널 스레드와 인터럽트 핸들러가 모두 액세스하려는 순환 큐를 관리하기 위한 인터럽트 큐. 키보드 및 직렬 드라이버에서 사용합니다.
• rtc.c, rtc.h
  • 커널이 현재 날짜와 시간을 확인할 수 있도록 하는 실시간 시계 드라이버. 기본적으로 이 함수는 난수 생성기의 초기 시드를 선택하기 위해 thread/init.c에서만 사용됩니다.
• speaker.c, speaker.h
  • PC 스피커에서 톤을 생성할 수 있는 드라이버.
• pit.c, pit.h
  • 8254 프로그래밍 가능 인터럽트 타이머를 구성하는 코드. 이 코드는 각 장치가 PIT의 출력 채널 중 하나를 사용하기 때문에 devices/timer.c와 devices/speaker.c에서 모두 사용됩니다.

 

lib 코드

마지막으로, lib와 lib/kernel에는 유용한 라이브러리 루틴이 포함되어 있습니다. (lib/user는 프로젝트 2부터 사용자 프로그램에서 사용되지만 커널의 일부가 아닙니다.) 다음은 몇 가지 자세한 내용입니다:

• ctype.h, inttypes.h, limits.h, stdarg.h, stdbool.h, stddef.h, stdint.h, stdio.c, stdio.h, stdlib.c, stdlib.h, string.c, string.h
  • 표준 C 라이브러리의 하위 집합.
• debug.c, debug.h
  • 디버깅을 지원하는 함수 및 매크로. 자세한 내용은 디버깅 도구(Debugging Tools)를 참조하세요.
• random.c, random.h
  • 의사 난수 생성기. 실제 난수 값의 시퀀스는 핀토스 실행마다 달라지지 않습니다.
• round.h
  • 반올림을 위한 매크로.
• syscall-nr.h
  • 시스템 호출 번호. 프로젝트 2까지는 사용되지 않습니다.
• kernel/list.c, kernel/list.h
  • 이중 링크된 리스트 구현. 핀토스 코드 전체에 사용되며 프로젝트 1에서 몇 군데 직접 사용하게 될 것입니다. 시작하기 전에 이 코드를 훑어보는 것이 좋습니다(특히 헤더 파일에 있는 주석).
• kernel/bitmap.c, kernel/bitmap.h
  • 비트맵 구현. 원한다면 코드에 사용할 수 있지만 프로젝트 1에서는 필요 없을 것입니다.
• kernel/hash.c, kernel/hash.h
  • 해시 테이블 구현. 프로젝트 3에 유용할 것 같습니다.
• kernel/console.c, kernel/console.h, kernel/stdio.h
  • printf() 및 기타 몇 가지 함수를 구현합니다.

 

 

Synchronization(동기화)

적절한 동기화는 이러한 문제들을 해결하는 데 중요한 부분입니다. 인터럽트를 비활성화하면 동시성이 없어져 동기화 문제를 쉽게 해결할 수 있습니다. 하지만 이렇게 하면 안 됩니다. 대신 세마포어, 락, 조건 변수와 같은 동기화 프리미티브를 사용하여 대부분의 동기화 문제를 해결해야 합니다. 어떤 상황에서 어떤 동기화 프리미티브를 사용해야 할지 잘 모르겠다면 동기화 투어 섹션(Synchronization 참조)이나 threads/synch.c 파일의 주석을 참고하세요.

 

Pintos 프로젝트에서 인터럽트를 비활성화하는 것이 가장 적절한 문제 유형은 커널 스레드와 인터럽트 핸들러 간에 공유되는 데이터를 조정하는 경우입니다. 인터럽트 핸들러는 Sleep할 수 없기 때문에 잠금을 획득할 수 없습니다. 따라서 커널 스레드와 인터럽트 핸들러 간에 공유되는 데이터는 커널 스레드 내에서 인터럽트를 비활성화하여 보호해야 합니다.

 

이 프로젝트에서는 인터럽트 핸들러에서 스레드 상태의 일부만 액세스하면 됩니다. 알람 클락을 위해서는 타이머 인터럽트가 Sleep 중인 스레드를 깨워야 하며, 고급 스케줄러에서는 타이머 인터럽트가 몇 가지 전역 및 스레드별 변수에 액세스해야 합니다. 커널 스레드에서 이러한 변수에 액세스할 때는 타이머 인터럽트의 간섭을 방지하기 위해 인터럿트를 비활성화해야 합니다.

 

인터럽트를 비활성화할 때는 가능한 최소한의 코드에 대해서만 그렇게 해야 합니다. 그렇지 않으면 타이머 틱이나 입력 이벤트 등 중요한 것들을 잃을 수 있습니다. 인터럽트 비활성화 시간이 길어지면 인터럽트 처리 대기 시간이 증가하여 기계가 느려지는 것처럼 느껴질 수 있습니다.

 

synch.c의 동기화 프리미티브 자체는 인터럽트를 비활성화하여 구현됩니다. 여기서 인터럽트가 비활성화된 상태로 실행되는 코드의 양을 늘려야 할 수도 있지만, 최소한으로 유지하는 것이 좋습니다.

 

디버깅 목적으로 특정 코드 섹션에 인터럽트가 발생하지 않도록 하고 싶다면 인터럽트 비활성화가 유용할 수 있습니다. 프로젝트 제출 전에는 디버깅 코드를 반드시 제거하세요. (단순히 주석 처리하지 마세요. 그렇게 하면 코드 가독성이 떨어집니다.)

 

제출물에는 busy waiting이 없어야 합니다. thread_yield()를 호출하는 타이트 루프는 busy waiting의 한 형태입니다.

 

Development Suggestions

과거에는 많은 그룹이 과제를 여러 부분으로 나누고, 각 그룹 멤버가 마감일 직전까지 자신의 부분만 작업한 후 모여서 코드를 결합하고 제출했습니다. 이런 방식은 바람직하지 않습니다. 우리는 이렇게 하지 말 것을 권장합니다. 이렇게 하면 종종 두 가지 변경 사항이 서로 충돌하여 마지막에 많은 디버깅이 필요한 경우가 생깁니다. 이런 방식으로 작업한 그룹 중에는 컴파일조차 되지 않거나 부팅되지 않는 코드를 제출한 경우도 있었습니다.

 

대신 git 등의 소스 코드 관리 시스템을 사용하여 팀의 변경 사항을 자주 통합하는 것이 좋습니다. 이렇게 하면 다른 사람의 코드를 완성된 후가 아니라 작성 중에 볼 수 있어 예기치 않은 일이 적습니다. 또한 변경 사항을 검토할 수 있고, 변경 사항에 버그가 있는 경우 작동하는 버전의 코드로 되돌릴 수 있습니다.

 

이번 및 후속 프로젝트를 작업하는 동안 이해할 수 없는 버그를 만날 것으로 예상해야 합니다. 그럴 때는 유용한 디버깅 팁이 가득한 디버깅 도구 부록(디버깅 도구 참조)을 다시 읽어보세요. 커널 패닉이나 어설션 실패 시 백트레이스를 최대한 활용할 수 있도록 백트레이스 섹션(백트레이스 참조)도 반드시 읽어보세요.