PINTOS Project1 - Threads

오늘부터 PINTOS(KAIST ver.) 프로젝트를 시작했다. 핀토스를 처음 접했을 때 느끼는 점은 도대체 뭐하라는거지? 이다.

Project 1 - Threads 에서는

 

1. Thread들의 생성 및 관리

2. Timer Interrupt

3. Synchronization

4. Scheduling

 

에 대해 알아본다. 개념 - 프로젝트 진행 순서로 정리한다.

PINTOS = Pint OS

Pint OS, 즉 작은 OS라는 뜻이다. 작은 OS를 가지고 여러가지 프로젝트를 수행한다.

1. 사용법

1. /pintos 경로에서 source ./activate (로그인할때마다 해야하므로 .bashrc에 명령어를 추가하는 것이 좋다.)

 

2. threads 폴더 들어가서 make clean - make check를 수행하면 Test Case들에 대해서 채점을 수행한다.

 

3. Test Case 한가지만 돌리고 싶다면, pintos/(프로젝트명)/build에 들어가서 아래 명령어를 수행하면 된다.

pintos -T (Timout이 걸리는 시간) -- -q -run (Test case 이름)

ex) pintos -T 10 -- -q run alarm-multiple

→ alarm-multiple 이라는 test case를 수행하며, 10초 후에는 무조건 종료하라.(무한루프에 빠지는 경우를 방지할 수 있다.)

 

 

4. 수행한 결과는 threads/build/tests/threads 폴더에 들어가면 확인해볼 수 있으며, Test Case에 관한 정보/코드는 pintos/tests/threads에 있다.

threads/build/tests/threads/ 에 .output파일이 내가 짠 코드의 Test Case 결과이며, 틀렸을 경우 Expected Output과 Actual Output이 비교되어 출력된다.

 

2. 개념

1) Synchronization

 

  동기화란, 임의의 메모리 공간을 공유하는 쓰레드들이 의도한 순서대로 작업을 수행하도록 보장하는 작업이다. 한 Process 안에 있는 Thread들 간에는 Scheduler에 의해 임의적으로 Preemption(CPU를 차지하는 행위)이 발생하게 되는데, 이 과정에서 프로그램 작성자의 의도와 다르게 실행되는 경우를 방지한다. 이번 프로젝트에서는 동기화에 사용되는 5가지 방법들을 구현한다. (동기화가 필요한 이유는 아래 글을 참고)

 

one-step-a-day.tistory.com/122

쓰레드와 Mutex

 

2) Interrupts

 

  Interrupt란 원하는 Event가 발생했을 때 알림을 받기 위한 장치이다. Interrupt를 끄면 Preempt가 일어나지 않기 때문에 동기화가 보장된다. (non-maskable interrupt도 있다.) 하지만 Interrupt를 끄게 되면 필요한 신호들을 받지 못할 수 있기 때문에, 활용 시 주의해야 한다.

 

Ex ) 핸드폰의 벨소리나 진동 같은 기능이라고 생각하면 된다. 벨소리나 진동이 없다면, 우리는 전화나 메시지가 오는지 항상 핸드폰을 보고있어야 할 것이다. 벨소리나 진동이 있기 때문에 다른일을 하다가도 전화가 온 것을 인지하고 받을 수 있다.

 

3) Semaphore

 

여러 Process/Thread 사이의 Critical Region을 정상적으로 관리하기 위한 Nonnegative Integer이다. 

Semaphore의 값을 1이라고 가정하자. Critical Region에 접근할 때 Semaphore의 값을 1 감소시키고,  나올 때 1을 증가시킴으로써 Critical Region에 접근하는 쓰레드는 항상 1개 이하로 유지할 수 있다.(Semaphore의 값을 증가/감소시킬 때는 Atomic Operation을 보장하기 위하여, Interrupt를 Disable한다.)

 

  1. P(Down) : 양수이면, 1 줄여라.

  2. V(Up) : 1 늘려라.

 

* 정확히 한번 일어날 Event에 대해서는 0으로 초기화된 semaphore를 사용할 수 있다. 예를 들어 A라는 쓰레드가 있고 A 쓰레드가 B 쓰레드를 시작시키고 특정 작업이 완료되면 B가 A에게 signal을 보내길 기다린다고 하자. A는 0으로 초기화된 semaphore를 만들고 P(Down)을 수행한다. 이 때 이미 0이므로 수행하지 못하고 기다리게 되고, B에게 수행권을 넘긴다. B가 실행되었을 때, 업무를 완료한 뒤 V(up)를 실행한다. 그럼 semaphore는 1이 되고, A가 Down을 실행하여 다시 semaphore는 0이 된다. (Cond-val 수행 시 이 용도로 사용된다.)

 

* Semaphore를 Up하면, 마지막에 Priority에 따라 Preempt(thread_yield)를 수행할 것이다. 이 때 Interrupt handler가 sema_up 함수를 호출하는 경우를 고려해야 한다. (감이 오지 않는다면 Project3까지 꼭 기억해두기로 하자.)

 

관련 파일 : synch.c, synch.h

 

4. Locks(Mutex)

 

Binary Mutex를 Lock이라고 부른다. Thread 프로젝트에서는 Semaphore의 소유권을 정하기 위해 사용된다. (synch.h의 struct lock에서 정의되어 있다.)

 

관련 파일 : synch.c, synch.h.

 

5. Monitors

세마포어나 Lock보다 한층 고차원의 동기화 수단이다. 특정 조건을 충족했을 때 Thread에 signal을 보내 작업을 수행하게 할 수 있다. 이번 프로젝트에서는 Cond라는 test에서 사용된다.

 

* Monitor의 구성요소

1) data being syncronized

2) lock(monitor lock)

3) one or more condition variables

 

* Monitor 작동 순서(protected Data에 접근할 때)

1) monitor lock을 획득한다.(=모니터 안으로 들어간다.)

2) 모니터 안에 들어가게 되면, 쓰레드가 protected data에 대한 control을 갖게 된다.

3) 작업이 끝나면 monitor lock을 release한다.

 

Monitor의 condition variable은 access를 허용하는 조건을 control할 수 있다. '특정 데이터가 도착할 때까지' 혹은 '사용자가 최종적으로 키를 친 뒤 10초 후 ' 라던지의 조건이다. 이런 조건들이 true가 되는 조건들을 걸어놓으면, lock을 release(+1)하고 특정 조건을 만족할 때까지 기다린다. condition이 true가 되면, 특정 기다리는 쓰레드를 깨우거나 모든 쓰레드를 깨우는 등의 작업을 할 수 있다.

 

include/threads/synch.h.

5. Optimization Barriers

(동기화의 수단으로 어떻게 사용되는지 잘 모르겠다.)

: 사용자의 의도와 다르게 Compiler Optimization 되는 것을 막아준다. barrier()를 쓴 곳에서는 Compiler Optimization이 수행되지 않는다. 코드 곳곳에서 사용되는 것을 볼 수 있다.(pintos/devices/timer.c)

 

* Compiler Optimization이란?

 : 컴파일러가 코드의 내용을 파악하여 필요없는 부분을 수행하지 않거나 작업 순서를 변경하는 등의 방법으로 최적화하는 행위

 

6. Priority

  Thread들은 Priority(우선순위)라는 정보를 가지고 있고, 반드시 Priority가 높은 Thread가 먼저 실행되어야 한다. (만일 Priority가 높은 것이 실행되지 않는다면, 중요하지 않은 프로그램이 실행되느라 중요한 프로그램이 계속 실행되지 못하는 상황이 벌어질 수 있다.) 하지만 Semaphore나 Lock을 사용하다 보면, Priority가 낮은 프로세스가 실행되는 상황이 발생한다.

 

* Priority Donation

  Priority가 10인 Thread A가 Lock A를 가지고 실행되는 도중 Priority가 30인 Thread B가 생성되는 상황을 가정하자. Thread B는 생성이 완료된 후 Ready Queue에 추가되고, Priority가 Thread A보다 높으므로 실행된다. Thread B가 실행 도중 Lock A를 요청한다면 어떻게 될까?

  Thread A가 Lock을 가지고 있기 때문에, Thread A가 실행이 되고 Thread B는 Lock을 획득할 때까지 기다리게 된다. 이렇게 되면 Priority가 10인 Thread A가 Priority 30인 Thread B보다 먼저 실행이 되는 상황이 발생한다. 이런 상황을 Priority Inversion이라고 부르고, 이런 상황을 방지하기 위해 Thread B의 Priority 30을 Thread A에게 부여하게 된다. 그럼 Thread A는 Priority 30이 되므로, Priority Inversion이 일어나지 않는다. 이를 Priority Donation이라고 부른다.

 

프로젝트 진행

1. Alarm Clock : 

목표 : Thread를 생성한 뒤 특정 시간이 지나면 특정 작업을 수행하게 하고싶다. 기본적으로 구현되어있긴 하지만, Busy Waiting 방식을 사용하고 있어 매우 비효율적이다. timer_sleep() 등 함수를 수정하여 Busy Waiting 방식을 효율적으로 변경한다.

 

* Busy Waiting : Thread A가 5tick 뒤에 특정 작업을 실행하길 원한다고 하자. 매 Tick마다 Thread A가 실행되어 5tick이 되었는지를 확인하는 방법을 Busy Waiting이라고 한다.

 

[ 상세 설명 ] 

 

1) 현재 :

   1. thread_create() 함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   2. thread가 실행되며 목표한 시간이 지났는지 확인한다.

   3. 목표한 시간에 도달하지 않았으면 ready_list에 넣는다.

   4. ready_list의 맨 앞에 있는 thread를 실행한다.

 

thread를 여러개 생성한 뒤, 2-3-4를 반복하면서 계속 목표한 시간에 도달되었는지 확인하고, 도달하면 thread를 종료시킨다. Test Case 수행 결과를 보면 kernel ticks, idle ticks, user ticks가 있는데 의미하는 바는 아래와 같다.

 

kernel ticks : kernel thread들이 수행되는데 걸리는 시간

idle ticks : idle thread가 수행되는데 걸리는 시간

user ticks : 사용자 프로그램이 수행되는데 걸리는 시간

 

Busy Waiting으로 구현되어있기 때문에, 모든 thread들이 종료될 때까지 idle thread는 수행되지 않는다. (user ticks는 현재 보지 않아도 된다.) 따라서, Busy Waiting으로 수행하면 아래와 같은 결과를 얻을 수 있다.

 

idle ticks : 0, kernel ticks : 800, user ticks : 0 

 

2) 목표 : 

   1. Sleep List를 만든다.

   2. thread_create()함수를 사용하여 thread를 생성하며, 실행해야할 함수로 timer_sleep() 혹은 timer_sleep()의 wrapper를 전달한다.

   3. thread가 time_sleep 함수를 실행하며 목표한 시간이 지났는지 확인한다.

   4. 목표한 시간이 지나지 않았으면 sleep_list에 추가한다.

   5. Sleep List에 있는 Thread들의 최소 Wakeup Tick을 전역변수에 저장한다.

   5. timer interrupt(매 tick마다 발생)마다 최소 Wakeup Tick보다 작은지 확인한다.

   6. 목표한 시간에 도달하면, sleep list에서 해당 thread를 제거하고, ready_list에 추가한다.

   7. ready_list에 추가된 thread는, 자신의 차례가 되면 실행되고 종료된다.

 

위와 같이 실행하면, 목표한 시간에 도달하지 못한 thread들은 모두 sleep_list에서 실행되지 않고 자고 있다. 따라서 idle_thread가 실행되며 아래와 같은 결과를 얻을 수 있다.(결과는 조금씩 다를 수 있다.)

 

idle ticks : 500, kernel ticks : 300, user ticks : 0 

 

2. Priority Scheduling

목표 :

   1. 현재는 thread들이 생성되면 ready_list의 맨 뒤에 넣고 순차적으로 실행된다. 하지만 thread에는 priority라는 우선순위를 나타내는 변수가 있다. 우선순위가 높은 것들이 먼저 실행되도록 관련 함수들을 변경한다.

   2. Semaphore와 Lock을 사용하여, Critical Region에서 Atomic Operation이 일어남을 보장한다.

   + Critical Region에 여러개의 쓰레드가 동시에 접근할 때, 하나의 작업이 종료되기 전에 다른작업이 시작되면 데이터가 이상해질 수 있다. 따라서 Critical Region에서 작업하는 Thread에게는 Lock의 소유권을 부여하고, Lock을 소유하지 못한 Thread들은 Lock의 소유권이 풀릴 때까지 Waiters에서 기다린다.  

   3. 2번의 상황에서 Priority가 높은 Thread가 Priority보다 낮은 Thread가 먼저 수행되는 것을 막기 위해, Priority Donation 이라는 개념을 적용한다.

3. Cond Var(Monitors)

   1. Monitor 구조를 활용한다.

4. Multi Level Feedback Queue Scheduler

   1. Priority Donation만으로는 Starvation 등의 문제를 해결하지 못한다. recent_cpu, load_average 등의 변수를 활용하여 Priority를 유동적으로 변경해주는 Multi Level Feedback Queue Scheduler를 적용한다.

후기

OS의 맛을 볼 수 있는 재미있는 프로젝트였다. 앞으로 훨씬 더 어려워질 것 같아 걱정이지만 열심히 공부하고 정리해야겠다.

Debugging은 gdb보단 printf와 뇌버깅이 훨씬 더 편한것같다..