[정글] PintOS

크래프톤정글/PintOS

[정글] PintOS - Gitbook

아람2 2024. 11. 1. 22:20

원본 https://casys-kaist.github.io/pintos-kaist/

해석본 https://www.notion.so/PROJECT-1-THREADS-1305646decf681049375f6bff9e915fd

PROEJCT 1 : THREADS

Introduction

컴파일은 threads 디렉토리에서 진행되어야 한다

Background

과제의 쓰레드 시스템 코드를 읽고 이해해야 한다

🐣 쓰레드 Thread - 프로세스 내에서 동시에 실행될 수 있는 작은 단위, 프로세스의 공유 자원을 접근할 수 있다

쓰레드가 생성될 때, 스케줄링의 대상이 되는 새로운 문맥 Context 이 생성된다

thread_create() 의 인자로 실행하고자 하는 함수를 넣으면 문맥에서 실행된다

쓰레드는 해당 문맥에서 함수의 처음 부분부터 실행되고, 함수가 리턴될 때 종료된다

동기화 함수는 하나의 쓰레드가 다른 쓰레드를 기다려야 할 때 문맥 교환 Context Switch 를 강제 진행한다

문맥 교환이 일어나는 방식은 threads/thread.c 의 thread_launch() 에 정의되어 있다

문맥 교환은 현재 시행 중인 쓰레드의 상태를 저장하고, 다음으로 실행할 쓰레드의 상태를 복원한다

경고 - 스택에 할당하는 대신 Page Allocator 와 Block Allocator 를 사용해라

threads code

* loader.S, loader.h - kernel Loader, 커널의 한 부분

* init.c, init.h - 커널을 초기화하는 커널의 메인 프로그램

* thread.c, thread.h - thread.h 에서 thread 구조체를 정의한다

* palloc.c, palloc.h - 페이지 할당기

* malloc.c, malloc.h - 블록 할당기

* interrupt.c, interrupt.h - 기본적인 인터럽트 핸들링, 인터럽트 켜고 끄기 함수

* intr-stubs.S, intr-stubs.h - 저수준의 인터럽트 핸들링을 위한 어셈블리 코드

* synch.c, synch.h - 기본적인 동기화 함수들

* mmu.c, mmu.h - x86-64 의 페이지 테이블 연산을 위한 함수

* io.h - I/O 포트 접근을 위한 함수, devices 디렉토리 내 소스에서 주로 사용

* vaddr.h, pte.h - 가상 메모리와 페이지 테이블 엔트리와 함께 사용하는 함수와 매크로들

* flag.h - x86-64 내 flags 레지스터의 일부

Synchronization

적절한 동기화는 중요하다

동기화 문제들은 인터럽트를 비활성화시키면 쉽게 해결할 수 있지만 인터럽트가 비활성화 되어 있으면, 동시성이 없어진다 -> 하지 마라!

인터럽트 비활성화가 가장 효과적인 문제의 유형은 커널 쓰레드와 인터럽트 핸들러 사이에 공유된 데이터를 조정하는 것이다

인터럽트를 비활성화 시킬 때는 최대한 적은 코드에 적용되게 하고, synch.c 동기화 함수도 최소한으로 유지해라

인터럽트를 비활성화시키는 것은 디버깅에 유용하다

제출물에는 busy waiting (spin) 이 없어야 한다

Alarm Clock

현재의 timer_sleep 는 busy wait 방식 (반복문을 돌면서 시간이 경과할 때까지 thread_yield() 를 호출하는 방식) 이다

과제 1 - busy waiting 을 피하도록 timer_sleep() 을 다시 구현하라

timer 가 x번 tick 할 때까지 thread 호출의 실행을 일시 중단한다

시스템이 idle (다음 thread가 없는) 상태가 아니라면, thread 가 적절한 시간 동안 대기한 후 ready queue 에 놓이게 해라timer_sleep() 은 실시간으로 작동하는 thread 에게 유용하다 (인자는 타이머의 ticks)

Priority Scheduling

현재 실행 중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 Ready List 에 추가되면, 즉시 프로세서를 양보한다

우선순위는 실행 중인 상태에서도 변경될 수 있고,

자신의 우선순위를 내렸을 때 해당 쓰레드의 우선순위가 가장 높지 않다면 CPU를 즉시 양보한다

우선순위의 범위는 PRI_MIN(0) 부터 PRI_MAX(63) 까지이고 숫자가 작을 수록 우선순위가 낮다

우선순위 역전 Prioirty Inversion - 줬다 뺏음, 락이 끝나기를 기다림

+ 락은 CPU에 접근할 때 사용하는 게 아니라, 공유자원에 접근할 때 사용하는 거임

Advanced Scheduler

우선순위에 따라 실행할 쓰레드를 선택하지만, 우선순위 기부를 수행하지 않기 때문에

우선순위 기부 기능을 제외하고 우선순위 스케줄러가 정상 작동하도록 구현해야 한다

범용 스케줄러의 목표는 스레드의 다양한 스케줄링 요구를 균형 있게 맞추는 것이다

입출력을 많이 수행하는 스레드는 빠른 응답 시간이 필요하지만 CPU 사용 시간은 적게 필요하고

계산 중심의 스레드는 많은 CPU 시간을 받아야 하지만 빠른 응답 시간은 필요하지 않는다

잘 설계된 스케줄러는 이러한 요구사항을 모두 동시에 만족시킬 수 있다

가장 높은 우선순위의 비어 있지 않은 큐에서 스레드를 선택해 실행하며

여러 스레드가 있다면 라운드 로빈 방식을 순차적으로 실행한다

Niceness

각 스레드에는 nice 값이 있다, 해당 스레드가 다른 스레드에게 얼마나 "양보"해야 하는지를 나타낸다

양수의 nice 값은 스레드의 우선순위를 낮추어 다른 스레드에게 CPU 시간을 양보하게 하고

음수의 nice 값은 다른 스레드로부터 CPU 시간을 더 많이 차지한다, 0이면 영향을 주지 않는다

스레드의 우선순위는 공식에 따라 스케줄러가 동적으로 결정한다

초기 스레드는 nice 값이 0으로 시작하고, 다른 스레드들은 부모 스레드로부터 상속된 nice 값으로 시작한다

현재 스레드의 nice 값을 새로운 값으로 설정하고, 이를 바탕으로 스레드의 우선순위를 다시 계산한다

만약 실행 중인 스레드가 더 이상 가장 높은 우선순위를 가지지 않는다면 CPU를 양보 yield 한다

Calculating Priority

우리의 스케줄러는 64개의 우선순위와 64개의 준비 큐를 가지고 있으며, 큐는 PRI_MIN 부터 PRI_MAX 까지 번호가 매겨져 있다

스레드 우선순위는 스레드가 초기화될 때 처음 계산되고, 모든 스레드에게 대해 매 네번째 클록 틱마다 다시 계산된다

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

recent_cpu 는 해당 스레드가 최근에 사용한 CPU 시간을 추정한 값이고, nice 는 스레드의 nice 값이다

최근 n초 동안 각 초에 사용된 CPU 시간을 추적하는 n개의 요소로 이루어진 배열을 사용하는 방법은

스레드마다 O(n) 공간이 필요하고, 새로운 가중 평균을 계싼하는데 O(n) 시간이 소요된다

그래서 지수 가중 이동 평균 Exponentially Weighted Moving Average 를 사용한다

x(0) = f(0),

x(t) = ax(t − 1) + (1 − a)f(t),
 
a = k/(k + 1)

Summary

모든 스레드는 -20에서 20 사이의 nice 값을 가지며, 스레드가 직접 제어할 수 있다

각 스레드는 0 PRI_MIN 에서 63 PRI_MAX 사이의 우선순위를 가지며, 네번째 틱마다 계산된다

recent_cpu는 스레드가 "최근에" 사용한 CPU 시간의 양을 측정합니다. 매 타이머 틱마다 실행 중인 스레드의 recent_cpu 값이 1씩 증가한다

Appendix

Threads - Struct Thread

모든 struct thread 는 각 스레드 메모리 페이지의 시작 부분을 차지한다, struct thread 가 너무 커져서 안 된다 (1kB 미만)

커널 스택이 너무 커져서도 안 된다, 커널 함수에서는 큰 구조체나 배열을 동적으로 메모리 할당하라

스레드 식별자 tid 는 1부터 시작해 숫자 상으로 다음 높은 값이 부여된다, tid 는 커널이 돌아가는 내내 유일하게 유지된다

스레드를 doubly-linked-list에 담을때 쓰는 “리스트 요소”이다. ready_list (실행 준비를 마친 스레드들의 리스트)와 sema_down() 의 세마포어에 대기중인 스레드들의 리스트에서 모두 쓰인다. 해당 요소는 이중으로 임무를 수행할 수 있는데, 세마포어에서 대기중인 스레드는 준비되지 않은 스레드이기 때문이다 (역도 성립한다). <-- 우선순위에도 우선순위가 있다, 우선순위를 얻지 못하면 세마포어도 필요없다

Synchronization

동기화를 하는 가장 단순한 방법은 인터럽트를 불가능하게 하는 것이다,

인터럽트가 꺼지면 다른 스레드는 진행 중인 스레드를 선점할 수 없다

PintOS 는 선점가능한 Preemptible 커널이다, 커널 스레드는 언제든 선점당할 수 있다

인터럽트를 비활성화시키는 주된 이유는 외부의 인터럽트 핸들러와 커널 스레드를 동기화시키기 위해서입니다

외부 인터럽트 핸들러는 잠들게 할 수 없어서 비활성화시키지 않고 다른 방법으로는 동기화가 거의 불가능하다

몇가지 외부 인터럽트는 인터럽트 비활성화로도 막을 수 없으며 이런 인터럽트들은 마스크 불가능 인터럽트 NMIs 라고 하는데 (ex. 컴퓨터에 불이 났을 때처럼 긴급한 경우에만 사용) PintOS 에서는 다루지 않는다

JE) 함수를 구현할 때 어떤 것을 구현할지를 함수 안에 써놔야한다

하는 일이 똑같은 스레드를 여러개 만들 수도 있다

락 Locks

락은 초기값을 1로 하는 세마포어와 같다

오직 락을 갖고 있는 owner 쓰레드만이 락을 놓아줄 수 있다

PintOS 에서 락들은 "재귀적"이지 않다

모니터 Minotors

모니터락은 락 + 컨디션 변수

모니터는 세마포어나 락보다 더 높은 (추상화) 수준의 동기화 방법이다

동기화된 데이터, 모니터락, 한 개 이상의 컨디션 변수로 이루어진다

모니터 안에서 스레드는 모든 보호받는 데이터에 접근할 수 있고, 용건이 끝나면 모니터락을 놓아준다

컨디션 변수는 특정 컨디션이 참이 될 때까지 모니터 안의 코드가 기다릴 수 있게 한다

최적화 장벽 Optimization Barriers

컴파일러가 메모리 상태에 대해 어떤 가정을 못하게 막아주는 특별한 명령문

코드 짤 때 다시 봐야한대, 내용도 잘 안 들어와서 다시 읽어볼 예정

앞으로 To do

키워드 정리 + 깃북 + 구현해야 할 함수 정리 + make check, activate

구현해야 할 함수

timer_sleep() 재구현

1) timer_sleep() 을 busy_wait 방식에서 sleep()/ wakeup() 방식으로 다시 구현하자

- Files to Modify - threads/thread.*, devices/timer.c

Define Sleep Queue - static struct list sleep_list; and Initialize it,

생각해 봐야 할 것 - Where to declare the list and when to initialize it?

그 전에,

ticks 를 Local ticks 와 Global ticks 로 관리하여 커널에서 관리하기 편하게 선언해줌

Local Tick - 각 스레드의 wakeup time 관리, 스레드 구조체에서 수정

Global Tick - Sleep List 를 관리하기 위함

FIFO Scheduling 재구현

1) Scheduling 을 FIFO 에서 Priority Scheduling 으로 변경하자

2-1) Ready List 를 Thread Priority 로 정렬하라

2-2) 동기화 기법를 위한 Wait List 를 정렬하라

preemption 을 구현하라 - 쓰레드가 Ready List 안에 추가될 때 (타이머 인터럽트가 호출될 때)

- File to Modify - threads/thread.*, threads/synch.*

고려해야 할 점

Ready List 에서 가장 높은 우선순위를 가진 스레드를 선택해라

Ready List 에 스레드를 삽입을 때, 현재 실행 중인 스레드의 우선순위와 비교하라

현재 실행 중인 스레드보다 높은 우선순위를 가진 경우, 새로 삽입된 스레드를 스케줄해라

Lock 을 기다리고 있는 스레드 중에서 가장 높은 우선순위를 가진 스레드를 선택해라

PintOS 의 우선순위

Prioirty 는 PRI_MIN(=0) 부터 PRI_MAX(=63) 까지, 숫자가 클수록 우선순위가 높다 (DEFAULT 31)