[PROJECT 1 : THREADS]과제 설명

PROJECT 1 : THREADS

---

introduction 소개

👉🏻이 과제에서 최소한의 기능을 갖춘 스레드 시스템이 주어진다. 우리의 임무는 이 시스템의 기능을 확장하여 동기화 문제에 대한 더 나은 이해를 얻는것, 이 과제에서 주로 스레드 디렉토리에서 작업하게 될텐데, 옆에 devices 디렉토리에서도 작업을 해야한다. 컴파일은 주로 스레드 디렉토리에서 해야한다. 이 프로젝트에 대한 설명을 읽기 전에 동기화에 관한 자료를 최소한 훑어보는 것이 좋다.

Background

✏️Understanding Threads 쓰레드 이해하기

🤔 먼저 과제에서 제공되는 쓰레드 시스템 코드를 읽고 이해합시다. Pintos에는 이미 쓰레드 생성, 쓰레드 종료, 쓰레드 간에 스위치를 하는 간단한 스케쥴러, 그리고 동기화 함수(semaphores, locks, condition variables, and optimization barriers)가 구현되어있습니다.

🤔일부 코드는 좀 낯설게 느껴질 수 있어요. 이미 소개에서 설명한대로 기본 시스템을 컴파일하고 실행하지 않았다면, 지금 그렇게 해보세요. 소스 코드 일부를 살펴보면 어떤 일이 일어나는지 이해하는 데 도움이 될 거예요. 만약 원한다면 거의 어디든 printf()를 추가해보고, 다시 컴파일하고 실행하여 어떤 일이 어떤 순서로 일어나는지 확인해보세요. 또한 디버거에서 커널을 실행하고 흥미로운 지점에 중단점을 설정하고, 코드를 단계별로 실행하고 데이터를 검사하는 등의 작업도 할 수 있습니다

🤔쓰레드가 생성될 때, 스케쥴링의 대상이 되는 새로운 문맥(context)이 생성됩니다. 만약 이 문맥에서 어떤 함수를 실행하고자 하는 경우,thread_create()의 인자로 실행하고자 하는 함수를 넣으면 됩니다. 쓰레드가 처음 스케쥴링되고 실행될 때, 쓰레드는 해당 문맥에서 함수의 맨 처음부터 실행합니다. 함수가 리턴될 때 쓰레드도 종료됩니다. 그러므로 각각의 쓰레드는 Pintos 내부에서 실행되는 미니 프로그램 같이 동작한다고 생각하면 됩니다. 마치 프로그램을 실행하면 main() 함수가 실행되는 것처럼, thread_create()가 실행되면 쓰레드에 전달된 함수가 실행됩니다. 

😒언제나, 한 번에는 하나의 쓰레드만이 실행되고 나머지들은 (만약 있다면) 모두 비활성화 됩니다. 스케쥴러는 다음 실행할 쓰레드를 결정합니다. 만약 다음으로 실행할 쓰레드가 없다면 idle 쓰레드라는 특별한 쓰레드를 실행합니다. (idle 쓰레드는
idle()로 실행됩니다.) 동기화 함수는 하나의 쓰레드가 다른 쓰레드가 뭔가를 하는 것을 기다려야 할 때 문맥교환(context switch) 을 강제 진행합니다.

🤔문맥교환이 일어나는 방식은 threads/thread.c의thread_launch() 에 정의되어 있습니다. (이 방식을 이해할 필요는 없다)
문맥 교환은 현재 실행중인 쓰레드의 상태를 저장하고, 스위칭 할,즉 다음으로 실행할 쓰레드의 상태를 복원합니다. 

🤔GDB 디버거를 사용해서 문맥교환에서 어떤 일이 일어나는 지를 천천히 추적해보세요. (GDB정보는 여기)schedule()
함수에 breakpoint를 설정하는 것부터 시작해서 한 단계씩 나아가보세요. ❗️각각의 쓰레드 주소와 상태, 그리고 각각의 쓰레드에 대해 어떤 프로시저가 콜 스택에 있는 지를 주의깊게 추적해보세요❗️. 하나의 쓰레드가 iret 과 do_iret()을 실행할 때, 또 다른 쓰레드가 실행을 시작한다는 것을 알아채게 될 거에요.

⚠️ 경고: Pintos에서 각각의 쓰레드에는 작은 고정 사이즈(4kB 이하의) 실행 스택이 할당됩니다. 커널이 스택 오버플로우를 잡아내려고 노력은 하겠지만 완벽하게 잡아내지는 못해요. 그래서int buf[1000];와 같이 큰 자료 구조를 non-static 지역 변수로 선언한다면 kernel panic과 같은 이상한 문제들을 만들어낼 수 있습니다. 대신에 💜스택에 할당하는 대신 page allocator와 block allocator 을 사용해보세요. (Memory Allocation참고!)💜

 

Source Files 소스 파일

threads 디렉토리와 include/threads 내 파일들의 개요입니다. 이 코드 중의 대부분은 수정할 필요가 없겠지만, 이 개요가 어떤 코드부터 봐야 할지를 알려줄 수 있기를 바랍니다.

✏️threads codes

• loader.S, loader.h 

🤔 kernel loader 파일입니다. PC BIOS가 메모리로 로드한 코드와 데이터를 512바이트로 합치고, 이것을 통해 디스크에서 커널을 찾아 메모리에 올린 후, start.S파일에 있는bootstrap()을 실행합니다. ❗️이 코드를 들여다보거나 수정할 필요는 없습니다. start.S파일은 메모리 보호를 위한 기본 셋팅을 수행한 다음,64비트 롱 모드로 들어갑니다. loader와는 다르게, 이 코드는 실제로 커널의 한 부분입니다.

• kernel.lds.S

❗️이 코드를 들여다보거나 수정할 필요는 없습니다.

• init.c , init.h

🤔커널을 초기화하는 커널의 메인 프로그램 입니다. 적어도 어떤 것들이 초기화되는지를 알기 위해 main() 함수를 살펴보세요. 여러분만의 초기화 코드를 추가하고 싶어질거에요. 

• thead.c , thread,h

🤔기본적인 쓰레드 함수입니다. 이 프로젝트의 대부분의 작업은 이 파일에서 발생할것입니다.thread.h는 thread 구조체를 정의하는데, 4개의 프로젝트에서 모두 이 구조체를 수정하게 될겁니다. 더 많은 정보를 보려면 Threads를 읽어보세요.

• palloc.c , palloc.h

🤔페이지 할당기입니다. 

•  malloc.c , malloc.h

🤔malloc()과 free() 함수를 간단하게 구현한 파일입니다. 블록 할당기가 궁금한다면 Block Allocator 를 참고하세요.

• interrupt.c , interrupt.h

🤔기본적인 인터럽트 핸들링, 인터럽트를 키고 끄기 위한 함수들 입니다.

• intr-stubs.S , intr-stubs.h

🤔저수준의 인터럽트 핸들링을 위한 어셈블리코드 입니다.

• sysch.c , synch.h

🤔기본적인 동기화 함수들 : semaphores, locks, condition variables, optimization barriers 입니다. 네 번의 프로젝트에서 모두 이 동기화를 사용해야 합니다. 더 많은 정보는 Synchronization 를 참고하세요.

• mmu.c , mmu.h

🤔 x86-64의 페이지 테이블 연산을 위한 함수들입니다. lab1이 끝나면 이 파일을 자세히 보게 될 것입니다.

• io.h

🤔I/O 포트 접근을 위한 함수들입니다.devices디렉토리 내 소스에서 주로 사용됩니다. 

• vaddr.h , pte.h

🤔가상 메모리와 페이지 테이블 엔트리와 함께 사용하는 함수와 매크로들입니다. project 3에서 중요하게 다루어질 것이고 현재로서는 무시하셔도 됩니다. 

• flags.h

🤔x86-64의 flags 레지스터의 일부 입니다.

 

 

✏️devices codes

• timer.c m timer.h

🤔초당 100번 똑딱거리는 시스템 타이머입니다. 이번 프로젝트에서 이 코드를 수정하게 될 것입니다. 

• vga.c , vag.h

🤔VGA는 화면에 텍스트가 나타나게 하는데, printf() 를 호출하면 VGA 디스플레이 드라이버가 호출되므로 직접 이 코드를 호출해서 쓸 일은 없을 겁니다. 

• serial.c , serial.h

🤔마찬가지로 호출할 일이 없을 겁니다..

• block.c , block.h

🤔블록 디바이스의 추상화입니다. 블록 디바이스는 고정된 크기의 블록들 배열 형태로 조직된 램이나 디스크 같은 장비들을 의미합니다. 기본 기능으로서 Pintos는 두 종류의 블록 디바이스를 제공합니다. IDE disks와 partition 입니다. 둘 중 어떤 종류도 project 2 이전까지는 사용되지 않습니다. 

• ide.c , ide.h

🤔최대 4개의 IDE 디스크에서 섹터를 읽고 쓸 수 있습니다. 

• partition.c , partiton.h

🤔디스크의 파티션 구조를 이해하세요. 파티션 구조는 하나의 디스크를 독립적으로 사용할 수 있는 여러 개의 region(파티션)으로 나눕니다.

• kbd.c , kbd.h

🤔키보드 드라이버입니다. 

• intq.c , intq.h

🤔인터럽트 큐입니다. 이는 커널 쓰레드와 인터럽트 핸들러가 모두 접근하려고 하는 원형 큐를 관리합니다. 키보드와 직렬 드라이버에 의해 사용됩니다.

• rtc.c , rtc.h.  - clock

🤔실시간 clock 드라이버 입니다. 이는 커널이 현재 날짜와 시간을 결정하도록 해줍니다. 이는 thread/init.c 에 의해서만 난수 생성기를 위한 초기 값을 고를 목적으로 사용됩니다.

• speaker.c , speaker.h

🤔스피커로 음향을 만들어내는 드라이버입니다.

• pit.c  , pit.h 

🤔8254 Programmable Interrupt Timer를 설정하는 코드입니다. 타이머와 스피커는 PIT의 출력 채널 중 하나를 사용하기 때문에 이 코드는 devices/timer.c 와devices/speaker.c 에 의해 사용됩니다.

 

✏️lib codes

lib 와 lib/kernel 은 유용한 라이브러리들을 포함하고 있습니다. lib/user는 프로젝트2부터 시작할 디렉토리로 user programs 에 의해 사용되지만 커널의 일부는 아닙니다.

• 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 이전까지는 쓰이지 않습니다. (2부터 쓰입니다)

• kenel/list.c , kerner/list.h

🤔이중 연결 리스트의 구현입니다. pintos 코드 전체에서 사용되고, 프로젝트1을 진행할 때 이 코드를 몇 군데에서 사용하는 게 좋을 겁니다. 시작하기 전에 이 코드를 한번 훑어보기를 추천합니다. 특히 헤더 파일의 주석들을 잘 보세요!

• kernel/bitmap.c , kenel/bitmap.h

🤔비트맵 구현입니다. 원한다면 코드에서 써도 되지만 프로젝트 1에서는 쓸 필요가 없을 겁니다.

• kernel/hash/c , kernel/hash.h

🤔해시 테이블 구현입니다. 프로젝트3에서 유용할 거에요.

• kernel/ console.c , kernel/console.h, kernel/stdio.h

🤔printf() 및 다른 함수들을 구현합니다.

 

Synchronization

 적절한 동기화는 이 문제의 풀이 중 중요한 부분 입니다. 동기화 문제들은 인터럽트를 비활성화 시키면 쉽게 해결할 수 있습니다 : ❗️인터럽트가 비활성화 되어 있으면, 동시성이 없어집니다. 즉 경쟁 조건의 가능성이 없어집니다. 이런식으로 모든 동기화 문제들을 해결하는건 매우 유혹적이지만, 그렇게 하지 마십시오. ❗️❗️대신 세마포어, 락, 컨디션 변수를 사용해서 동기화 문제들을 해결하세요. ❗️❗️어떤 동기화 함수가 어떤 상황에 쓰여야하는지 잘 모르겠다면,동기화← 이 섹션을 읽거나 threads/synch.c 의 코멘트를 참고하세요.

👉🏻 Pintos 프로젝트에서 인터럽트 비활성화가 최선의 해결책이 되는 문제는 딱 하나, 커널 쓰레드와 인터럽트 핸들러사이에 공유된 데이터를 조정해야 할 때 입니다. 인터럽트 핸들러는 잠들지 않기 때문에 lock을 소유할 수 없습니다. 이 말은 커널 쓰레드와 인터럽트 핸들러 사이에 공유되는 데이터는 인터럽트를 비활성화 시켜서만 커널 쓰레드에서 보호 받을 수 있다는 뜻 입니다.

👉🏻이 프로젝트에서는 인터럽트 핸들러가 쓰레드 상태에 접근하는게 조금은 필요할 것 입니다. 알람 시계가 동작하려면 타이머 인터럽트가 자고있는 상태의 쓰레드를 깨워야 합니다. 더 발전된 스케쥴러에서는 타이머 인터럽트가 전역 변수와 쓰레드마다의 변수에도 조금은 접근해야 합니다. 이런 변수들을 커널 쓰레드에서 접근하려면, 타이머 인터럽트가 방해하지 못하게 인터럽트를 비활성화 시켜야 할 것 입니다.

👉🏻인터럽트를 비활성화 시킬 땐 최대한 적은 코드에게 적용되게 해주세요. 주의하지 않으면 timer ticks나 input event 같은 중요한 내용을 잃게 됩니다. 또한 인터럽트를 비활성화 시키는 것은 인터럽트를 다루는 작업을 지연시킵니다. 이런 일이 많이 생기면 결국엔 머신이 너무 느려진 것을 느낄 것입니다.

👉🏻synch.c에 있는 동기화 함수들은 인터럽트 비활성화하는 방식으로 구현되었습니다. 아마 인터럽트 비활성화로 돌아가는 코드의 양을 추가하게 될 텐데, 최소한으로 유지해주세요.

👉🏻만약에 어떤 섹션의 코드가 인터럽트 당하지 않는걸 확실하게 하고 싶다면, 인터럽트를 비활성화시키는 것이 디버깅에 유용할 수 있습니다. 디버깅 코드들은 프로젝트에 합칠 때에는 꼭 없애 주세요. (주석처리만 하시면 코드 가독성이 너무 떨어지게 됩니다)

👉🏻제출물에는 바쁜 대기(busy waiting)가 없어야 합니다.thread_yield()를 호출하는 밀집한 루프는 바쁜 대기의 한 형태입니다.

 

 

Development Suggestions 개발제안

👉🏻예전엔 멤버들끼리 과제를 나눠서하는 그룹이 많았습니다. 그렇게 하면 각 멤버들은 모든 코드를 모아서 합쳐 제출하는 데드라인 직전까지 자기가 맡은 부분만 작업하게 됩니다. 나쁜 아이디어 입니다. 이런 접근법은 추천드리지 않습니다. 이렇게 하는 그룹들은 서로의 코드가 충돌이나면 서로 고치고, 디버깅하는데에 시간이 엄청 필요하게 됩니다. 이런식으로 합쳐서 작업한 그룹들은 컴파일이나 부팅자체가 안되는 경우도 있고 심지어 어떤 테스트조차 통과하지 못하기도 합니다.

👉🏻대신에 추천드리는 방법은 git 과 같은 소스코드 관리 시스템을 사용해서 코드 변경사항이 생기면 빨리, 자주 합치는 것입니다. 이렇게 해야 놀랄 일이 적게 생기고, 다 만든 이후가 아니라 코드가 쓰여질 때 서로의 코드를 볼 수 있습니다. 이런 시스템을 사용하면 코드 변경사항을 리뷰할 수 있고, 변경사항이 버그를 만들면 쉽게 코드의 버전을 되돌릴 수 있습니다.

👉🏻이 프로젝트나 이 이후의 프로젝트를 작업하는 동안 간단하게 이해할 수 없는 버그들에 뛰어들게 될 겁니다. 그때, 다시 작업 속도를 내게해줄 유용한 디버깅 팁이 가득한 디버깅 ❗️tools의 appendix를 다시 읽으세요. Backtraces 섹션을 확실히 읽으세요. 이 섹션을 읽으면 대부분의 커널 패닉이나 assert 실패 상황에서 정신을 다잡는 데 도움이 됩니다.

 

 

Alarm Clock

🙈 devices/timer.c 에 있는 timer_sleep()을 다시 구현해봅시다.

🔥이미 잘 작동하는 timer_sleep()이 구현되어있지만 이는 busy wait 방식입니다. 즉 이는 계속해서 반복문을 돌면서 현재 시간을 확인하고 충분한 시간이 경과할 때까지 thread_yield()를 호출합니다. busy waiting 을 피하도록 다시 구현합니다.

void timer_sleep (int64_t ticks);

🔥 이 함수는 호출한 스레드를 x 타이머 틱 만큼 대기한 후 다시 실행 대기 큐에 넣어 두고, 이후에 시스템이 스케줄링에 따라 스레드를 실행시킬 것입니다. 스레드가 정확히 x 타이머 틱 후에 깨어나지 않더라도, 시스템이 유휴 상태가 아니라면 해당 스레드를 다시 실행 대기 큐에 넣을 것입니다.

🔥timer_sleep()함수는 실시간 작업을 수행하는 스레드에 유용합니다. 예를 들어, 1초마다 커서를 깜박이게 만드는 작업 등에 사용될 수 있습니다.timer_sleep()함수의 인자는 타이머 틱(timer ticks) 단위로 표현되며, 밀리초나 다른 단위가 아닙니다. 1초에
TIMER_FREQ개의 타이머 틱이 있으며, 이 TIMER_FREQ는 devices/timer.h에서 정의된 매크로입니다. 기본값은 100입니다. 이 값을 변경하지 않는 것이 좋습니다. 왜냐하면 이 값을 변경하면 많은 테스트가 실패할 가능성이 있기 때문입니다.

🔥timer_msleep(), timer_usleep(), timer_nsleep()와 같이 밀리초, 마이크로초 또는 나노초 동안 sleep하는 별도의 함수가 존재하긴 합니다. 하지만 이 함수들은 필요시 자동으로timer_sleep()을 호출합니다. 이 함수들은 수정할 필요가 없습니다. project 1에서 구현한 alarm clock 기능은 (프로젝트 4에서는 유용할 수는 있지만) 이후 프로젝트에서는 필요로 하지 않습니다.

 

 

Priority Scheduling

"Pintos"는 컴퓨터 운영 체제 개발 및 교육을 위한 프로젝트로, 스레드 스케줄링 및 관련 기능을 구현하는 것을 포함하고 있습니다.

🔥현재 실행중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 ready list에 추가되면 현재 쓰레드는 즉시 프로세서를 새 쓰레드에게 양보해야합니다.

마찬가지로 쓰레드가 락, 세마포어 또는 조건변수(참고:https://ju-hy.tistory.com/39)를 대기할 때, 우선순위가 가장 높은 대기 스레드를 먼저 깨워야합니다. 쓰레드는 언제든지 자신의 우선순위를 올리거나 내릴 수 있지만, 우선순위를 내렸을 때 해당 쓰레드의 우선순위가 가장 높은 우선순위가 아니게 된다면 CPU를 즉시 양보해야 합니다.

🔥쓰레드 우선순위의 범위는 PRI_MIN (0) 부터PRI_MAX (63)까지입니다.
숫자가 작을수록 우선순위가 낮으므로 우선순위 0이 가장 우선순위가 낮고, 우선순위 63이 가장 우선순위가 높습니다.
초기 쓰레드의 우선순위는thread_create()에 대한 인수로 전달됩니다. 이때 다른 우선순위를 선택할 이유가 없으면 PRI_DEFAULT (31)를 사용하세요.PRI_매크로는 threads/thread.h 에 정의되있고, 이 값들을 변경하면 안됩니다.

🔥우선순위 스케줄링에서 중요한 사항은 “우선순위 역전(priority inversion)”입니다.

우선순위가 높은 쓰레드 H, 중간 M 그리고 낮은 L가 있다고 생각해보세요. 만약 L이 락을 갖고있어서 H가 L을 기다려야하고 M이 ready list에 있다면, H는 절대로 CPU를 사용하지 못할 것입니다. 왜냐면 낮은 우선순위의 스레드가 CPU시간을 얻지 못할 것이기 때문입니다. 이 문제에 대한 부분적으로 해결하는 방법은 L이 락을 갖는 동안 H가 L에게 우선순위를 기부(donate)한 다음, L이 잠금을 해제하면 (따라서 H가 획득) 이 기부를 회수하는 것입니다.

🔥 우선순위 기부를 구현해봅시다. 우선 우선순위의 기부가 필요한 모든 상황을 고려해야합니다. 하나의 쓰레드에 여러 우선순위가 기부되는 multiple donation 상황을 처리할 수 있어야 합니다. 또한 nested donation 즉 H가 M이 가진 락에서 대기하고있고, M은 L이 가진 락에서 대기하고 있다면 M과 L이 모두 H의 우선순위로 상승해야합니다. 필요하다면 8 단계와 같이 nested priority donation의 깊이에 대해 적당한 제한을 둘 수도 있습니다.

🔥락에 대한 우선순위 기부(priority donation)를 구현해야 합니다. 다른 Pintos 동기화 생성자에 대한 우선순위 기부를 구현할 필요는 없습니다. 모든 경우에서 우선 순위 스케쥴링을 구현해야 합니다. 마지막으로 다음의 함수들을 구현하세요. 이 함수들은 쓰레드가 자신의 우선순위를 검사하고 수정하도록 합니다. 이러한 함수에 대한 골격은threads/thread.c에 제공되어 있습니다.

void thread_set_priority(int new_priority)

🔥현재 스레드의 우선순위를 새 우선순위로 설정합니다. 만약 현재 스레드의 우선순위가 더 이상 높지 않으면 우선순위를 양보합니다.

void thread_get_priority(int new_priority)

🔥현재 스레드의 우선순위를 반환합니다. 우선 순위 기부가 있는 경우 더 높은 (기부된) 우선순위를 반환합니다.

🔥스레드가 다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다. 우선순위 스케줄러는 이후 프로젝트에 사용되지 않습니다.