poArlim poArlim

자 이제 스레드의 마지막 미션인 Advanced Scheduler 를 구현해보도록 하자. Advanced Scheduler 는 Pintos 도큐먼트 Appendix B 에 기록되어 있는 4.4BSD Scheduler 와 같은 맥락의 스케줄러를 구현하도록 요구한다. 4.4BSD Scheduler 는 Multi-Level Feedback Queue Scheduler 의 구성이며, 이를 줄여서 pintos 의 코드에서는 mlfqs 로 나타나 있다. 4.4BSD 스케줄러의 상세한 내용은 전에 다룬 포스트가 있으니 자세한 이해를 원한다면 아래 링크에서 읽어보길 바란다. (recent_cpu, load_avg 값의 계산식을 분석하는 부분이 매우 흥미롭다.) [Pintos] 4.4BSD 스케줄러(4.4BSD Sche..

드디어 Priority Scheduling 의 마지막 파트인 Priority Inversion 까지 왔다. 이전에 다루었던 문제들보다 꽤 많이 복잡해서 생각보다 시간이 오래 걸렸다ㅜㅜ 시작해보자! Priority Inversion 핀토스 Documents 에 나와있는 설명을 해석해보자. 우선 priority inversion 이란 다음과 같은 상황에서 발생한다. H (high), M (medium), L (low) 라는 세 개의 스레드가 있고 각각의 우선순위는 H > M > L 일 때, H 가 L 을 기다려야 하는 상황(예를 들어, H 가 lock 을 요청했는데 이 lock 을 L 이 점유하고 있는 경우)이 생긴다면 H 가 L 에게 CPU 점유를 넘겨주면 M 이 L 보다 우선순위가 높으므로 점유권을 선점..

이번에는 동기화 도구들의 스케쥴링 방식을 살펴보자. 스케쥴링 도구들의 코드는 thread 폴더의 synch.h, synch.c 에 구현되어 있다. 우리가 다루어야 할 동기화 도구는 lock, semaphore, condition variable 3가지이다. 하나씩 살펴보자. /* thread/synch.h */ struct semaphore { unsigned value; /* Current value. */ struct list waiters; /* List of waiting threads. */ }; struct lock { struct thread *holder; /* Thread holding lock (for debugging). */ struct semaphore semaphore; /* B..

스케쥴링은 ready 상태에 있는 스레드들의 순서를 관리하여 가장 높은 priority 를 가진 스레드가 running 상태가 될 수 있도록 만들어주는 것이다. 현재상태 우선 현재 pintos 가 스케쥴링을 어떻게 관리하고 있는지 살펴보자. ready_list 에 새로운 스레드가 push 되는 순간을 찾아보면 될 것 같다. /* thread/thread.c */ void thread_unblock (struct thread *t) { enum intr_level old_level; ASSERT (is_thread (t)); old_level = intr_disable (); ASSERT (t->status == THREAD_BLOCKED); list_push_back (&ready_list, &t->el..

이번 포스트에서는 핀토스의 첫 번째 과제인 Alarm Clock 을 구현해보도록 한다. Alarm Clock 운영체제에는 실행중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 기능이 있는데, 이 기능을 Alarm Clock 이라고 한다. 현재 핀토스에 구현되어 있는 Alarm Clock 기능은 busy-waiting 방식으로 구현되어 있는데 이는 매우 비효율적으로 많은 CPU 시간을 낭비하게 한다. busy-waiting 방식에서 sleep 명령을 받은 스레드의 진행 흐름은 아래와 같이 진행된다. 잠이듬 -> 깨어남 -> 시간확인 -> 다시잠 -> 깨어남 -> 시간확인 -> ... -> 깨어남 -> 시간확인(일어날시간) -> 깨어남 이러한 문제가 발생하는 내면을 살펴보면 스레드의 상태가..

이 포스트에서는 본격적인 프로젝트에 들어가기 위해 꼭 필요한 개념들을 잡아두기 위해 여러 가지 배경 지식들을 설명한다. 이는 pintos kernel 에서 threads 의 기본적인 흐름도, 범용 레지스터 개념, struct thread 의 구조, 주어진 코드 분석(thread.h, thread.c, switch.h, switch.S) 등이 포함된다. 진행흐름 전 포스트에서 살펴봤다시피 pintos 의 loader 는 우리를 init.c 의 main 함수로 가져다놓는다. 이 main 함수를 살펴보면 여러 초기화 작업 후에 가장 먼저 나오는 작업은 thread 의 시작이다. 코드에서 한 번 살펴보자. /* thread/init.c */ /* Pintos main program. */ int main(voi..

멀티스레드 프로그램에서는 구조가 상이한 여러 스레드들이 함께 존재한다. 어떤 스레드는 다수의 I/O 요청을 처리하지만 복잡한 연산 작업은 없을 수 있으며, 어떤 스레드는 I/O 요청 없이 다수의 복잡한 연산 작업 만으로 이루어져 있을 수 있다. 위의 첫 번째 스레드는 I/O 장비와의 빠른 반응속도를 필요로 하지만 CPU time 은 거의 필요하지 않지만, 뒤의 스레드는 반대이다. 이렇게 다양한 스레드들이 존재하기 때문에, 효율적인 프로그램을 위해서 Scheduler(스케줄러) 는 이러한 요구들이 최대한 효율적으로 사용되도록 배치해야 한다. 이를 위해 스케줄러는 priority 라는 속성을 관리하는데, 이 속성에 기반하여 스레드들의 처리 순서를 결정한다. 이 포스트에서는 4.4BSD Scheduler 스케..

스레드(Thread) 쓰레드는 프로세스 내에서 실행되는 흐름의 단위를 말한다. 환경에 따라 하나의 프로세스 내에서 두 개 이상의 쓰레드가 실행될 수 있는데 이를 멀티스레드(multithread) 라고 한다. 멀티 쓰레드는 멀티 프로세스와 여러 작업이 동시에 이루어 진다는 공통점이 있지만, 멀티 프로세스에서 각 프로세스는 독립적으로 실행되며 각 프로세스는 별개의 메모리 공간을 차지하는 반면 멀티 스레드는 프로세스 내의 메모리를 공유하여 사용할 수 있다는 차이점이 존재하며 이러한 자원을 공유하는 특성 때문에 pintos 의 스레드 설계는 스레드간의 동기화(Synchronization) 에 신경을 써야한다. 이 포스트는 pintos 의 동기화에 사용될 수 있는 여러 방법들을 소개한다. Disabling Int..