개발 환경 설정

💡AWS EC2 Ubuntu 18.04 (x86_64) 에서 진행!

• 내 개발 환경
  • ubuntu
    
• EC2 세팅

$ sudo apt update
$ sudo apt install -y gcc make qemu-system-x86 python3

• 원본 건드리는 거 아님!! 팀의 리포지터리로 복제해서 작업하는 것!
  • pyotato로 리포 복제
  • 내 리포 내에서 브랜치 만들어서
  • 원본 master에 올리는게 아니라 복제한 내 리포에서 작업하기
• 복제

$ git clone --bare https://github.com/casys-kaist/pintos-kaist.git
$ cd pintos-kaist.git
$ git push --mirror https://github.com/pyotato/pintos-kaist.git
$ cd ..
$ rm -rf pintos-kaist.git
$ git clone https://github.com/pyotato/pintos-kaist.git

• pintos 작동 성공 확인 ✅ 20 of 27 tests failed 뜨면 성공적!

$ cd pintos-kaist
$ source ./activate
$ cd threads
$ make check
# .............. tons of operation results ............
20 of 27 tests failed.

• 일단은 클론은 성공
  

Kaist gitbook

• kaist gitbook

Pintos Project 1 - Thread (Youtube)

• 출처
• lecture slides

  📌 과제

  • Alarm clock
  • Priority scheduling
  • Advanced scheduler (선택)

1. ⏰Alarm clock

Main goal

• Modify the system timer_alarm(int ticks)
  • timer_alarm(int ticks) : A system call that wakes up a process in ticks amount of time.
• Currently Pintos is using busy waiting
  • busy waiting :

Files to modify

• threads/thread
• devices/timer
• current timer_sleep()
  
  

device/thread.c

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void thread_yield (void) 
{
	struct thread *curr = thread_current (); /* 1️⃣gets the pointer to the current thread struct "curr"*/
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable (); /*2️⃣disables disrupt*/
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem); /*3️⃣ puts the current struc to the end of the ready_list*/
	do_schedule (THREAD_READY);/* 4️⃣changes the state of the currently running thread to "THREAD_READY" & context switch*/
	intr_set_level (old_level);
}

(YOUTUBE) pintos/src/device/timer.c

void thread_yield (void)
{
	struct thread *cur = thread_current ();/* 1️⃣gets the pointer to the current thread struct "curr"*/
    enum intr_level old_level;
    
    old_level = intr_disable (); /*2️⃣disables disrupt*/
    if (cur != idle_thread)
    	list_push_back (&ready_list, &cur->elem);/*3️⃣ puts the current struc to the end of the ready_list*/
    cur->status = THREAD_READY;/* 4️⃣changes the state of the currently running thread to "THREAD_READY"*/
    schedule(); /* 5️⃣switch context */
    intr_set_level (old_level); /* 6️⃣set intr level back to original state */


}

functions in thread_yield()

• thread_current() : return the current thread
• intr_disable() : disable the interrupt & return previous interrupt state
• intr_set_level(old_level) : set a state of interrupt to the state passed to parameter & return previous interrupt state
• list_push_back(&ready_list, &cur->elem) : insert the given entry to the last of list
• put the current structure (&cur->elem) at the end of the ready_list
• schedule() : do context switch

Improving timer_sleep()

1. OS(Operating System) puts itself to the blocked state
2. OS is responsible to wake the blocked process, frequently checking the timer interrupt
🤗 This approach saves the CPU cycle & power consumption

• 2 types of list in current pintos
  • all_list
  • ready_list : data structure that represents a set of processes that are waiting for a CPU to be executed
• Need to implement new list
  • sleep_list : list of blocked threads, represent a set of threads that are in the blocked state
    
• When a process calls timer_sleep()
  1. OS puts the thread to a sleep_list()
  2. OS keeps check of the timer
  3. When the timer if up, it wakes up and moves the thread from the sleep_list to the read_list

Implementation Details

1. Define Sleep Queue.

static struct list sleep_list;

2. Initial Sleep Queue.
3. CheckPoints 🤔

• Where to declare the list
• When to initialise it
  
• Implementing blocked base to timer_sleep
  • The basic design idea : Every time when a timer interrupt handler is executed, a Kernel needs to check if there are any threads to wake up
  1. Scan the blocked thread list
  2. Find if local tick for the block thread > global tick
  3. If the current time >= tick : need to wake up some threads in the blocked list (otherwise it doesn't have to scan all the blocked thread)
     

Implementation of Alarm Clock

• Thread : Move thread (itself) to the sleep queue
  • When timer_sleep() is called, check the tick
  • If there is time left till the wakeup, remove the caller thread from ready_list and insert it to the sleep queue.

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	// while (timer_elapsed (start) < ticks)
	// 	thread_yield ();
	if(timer_elapsed(start) < ticks)
		thread_sleep(start+ticks); /*start+ticks : pass alarm time it needs to wake up */	/* 🤗implement yourself*/
}

• Challenges : start time might not be valid since context switchinh occurs before line (2)
  
  

  timer interrupt()

  • Timer interrupt is heart of everything!

  • Determine which threads to wake up everytime

  • For the threads to wake up, remove them from the sleep queue and insert it to the ready_list (Don't forget to change the state of the thread from sleep to ready!!)

  • Depending on the Organisation the sleep_list, the time to identify the threads to wake up might differ!
    

    

SUMMARY OF FUNCTIONS TO MODIFY

• thread_init() : add the code to initialise the sleep queue data structure
• timer_sleep() : call the function that insert thread to the sleep queue
• timer_interrupt() : at every tick, check whether some thread mush wake up from sleep queue and call wake up function

Design tips for modularization

• Functions to add

1. A function that sets thread state to blocked & wait , then insert it to sleep queue.
2. A function that find the thread to wake up from sleep queue and wake it up.
   • Wake up threads : take it from sleep queue and put it in ready_list
3. A function that save the minimum value of tick that threads have.
4. A function that return the minimum value of tick.

Testing results

$ pintos -- -q run alarm-multiple

---

2. 🥇Priority Scheduling

Main goal

• Pintos uses FIFO scheduling
• Modify PintOS scheduler for priority scheduling (Expected results)
  • Sort the ready list by the thread priority
  • Sort the wait list for synchronisation primitives (semaphore, condition variable, and locks)
  • Implement the preemption
  • Preemption point : when the thread is put into the ready_list (not everytime when the timer interrupt is called)

Files to modify

• threads/thread.*
• threads/synch.*

3 Things to consider

1. When selecting a thread to run in the ready_list select the one with the highest priority
2. Preemption

• When inserting the new thread to the ready list, compare the priority with the running thread
• Schedule the newly inserted thread if it has the higher priority with the currently running thread

3. Lock : semaphore, condition variable

• When selecting a thread from the set of threads waiting for a lock (or condition variable), select the one with the highest priority

Priority in PintOS

• Priority rangeds from PRI_MIN(=0) to PRI_MAX(=63)
  • The larger the number, the higher the priority
  • Default is PRI_DEFAULT(=31)
• PintOS sets the initial priority when the thread is created by thread_create()
• Existing functions

/* Change priority of the current thread to new_priority */
void thread_set_priority(int new_priority) 

/* Return priority of the current thread*/
int thread_get_priority(void)

Implementation of Priority Scheduling

tid_t thread_create(const char *name, int priority, thread_func * function, void * aux)

Codes we have to modify

• Insert thread in ready_list in the order of priority (not that it is not scalable)
• When the thread is added to the ready_list , compare priority of new thread & priority of the current thread
• If the priority of the new thread is higher, call schedule() (the current thread yields CPU)
  
• void thread_unblock(struct thread *t) : When the thread is unblocked, it is inserted to ready_list in the priority order
• void thread_yield(void) : The current thread yields CPU and it is inserted to ready_list in priority order
• void thread_set_priority(int new_priority) : Set priority of the current thread, reorder the ready_list

  • current thread_set_priority() only sets value to new_priority.

  • we need to modify thread_set_priority() value, position of the thread within ready_list

    

🤔 현재 코드에서는 cmp_priority가 undefined 인데 뭐로 바꿔줘야하지?

/* Transitions a blocked thread T to the ready-to-run state.
   This is an error if T is not blocked.  (Use thread_yield() to
   make the running thread ready.)

   This function does not preempt the running thread.  This can
   be important: if the caller had disabled interrupts itself,
   it may expect that it can atomically unblock a thread and
   update other data. */
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->elem); /*delete this code*/
	list_insert_ordered(& ready_list, & t->elem,cmp_priority,NULL); /*put the newly unblocked thread in the ready_list, according to the priority */
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

Change the synchronization primitives

• Lock
• Semaphore
• Condition variables

Wake the waiting thread with respect to the thread's priority

• Priority inversion
  • Cause : PintOS lock/unlock threads in FIFO

Semaphore in PintOS

/* initialise semaphore to the given value */
void sema_init(struct semaphore *sema, unsigned value)

/* request the semaphore. 
Acquired the semaphore? decrease the value by 1 : process has to block */
void sema_down(struct semaphore *sema) 

/* release the semaphore and increase the value by 1 */
void sema_up(struct semaphore *sema)

Need to modify

✅ void sema_down(struct semaphore *sema)
✅ void sema_up(struct semaphore *sema)

Lock in PintOS

/* initialise the lock data structure*/
void lock_init(struct lock *loc)

/* request the lock */
void lock_acquire(struct lock *loc) 

/* release the lock*/
void lock_release(struct lock *loc)

• lock_init() is already implemented by semaphore, in order to update lock data structure according to priority, it is efficient to modify semaphore!

Condition Variable in PintOS

/* initialise the condition variable data structure*/
void cond_init(struct lock *loc)

/* 
once process calls cond_wait(), the process is set to block state 
and waits for signal by the condition variable
*/
void cond_wait(struct lock *loc) 

/* send a signal to thread of the highes priority wiating in the condition variable*/
void cond_signal(struct lock *loc)

/*  send a signal to all threads waiting in the condition variable*/
void cond_broadcast(struct lock *loc)

Need to modify

• Modify to insert threadt at waiters list in order of priority
• If the process is set to wait list, we need to sort the process according to priority
  ✅ void sema_down(struct semaphore * sema)
  ✅ void cond_wait(struct condition * cond,struct lock * lock)
• Sort the waiters list in order of priority
  • It is to consider the case of changing priority of threads in waiters list
    ✅ void sema_up(struct semaphore *sema)
    ✅ void cond_signal(struct condition *cond, struct lock *lock UNUSED)

Priority Inversion

• Real life implications (ft. NASA)
  

Solutions for Priority Inversion

1.Priority Donation

• Inheriting the priority of the lock holder

• The thread that acquired the LOCK inherits the highest priority of the incoming threads
  

Issues to consider when implementing

🪺 Nested Donation

• we need to make our priority donations to implement this nested donation

👥 Multiple Donation

• the priority of the current thread should always have the updated HIGHEST PRIORITY (not it's original priority)

Data structure for Multiple Donation

• KEYPOINTS
  • Thread has to maintain a list of doners!
    

Data structure for Nested Donation

• KEYPOINTS
  • wait_on_lock : lock that it waits for
  • Need to maintain the lock that it waits for
  • Once we inherit a priority
  • Check if we need to inherit the prioity to the child

Implementing Priority Donation

Functions to modify

/* initialises data structure for priority donation */
static void init_thread(struct thread *t, const char *name, int priority)

/*
1️⃣ if the lock is not available, store address of the lock
2️⃣ store the current priority & maintain donated threads on list (multiple donation)
3️⃣ donate priority
*/
void lock_acquire(struct lock * lock)

/* when the lock is released , REMOVE the thread that holds the lock on donation list & set priority properly
*/
void lock_release(struct lock * lock)

/* set priority considering the donation */
void thread_set_priority(int new_priority)

Checking results

---

코드 뜯어보기 (진행중)

/devices/timer.c

1. void timer_sleep(int64_t ticks)

• 대략 TICKS 단위 동안 (타이머가 째깍거릴 동안) 실행 미루기

/* 
Suspends execution for approximately TICKS timer ticks. 

*/
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

• 현재 코드는 작동하지만 busy wait 중임!
  • busy wait : loop를 돌면서 현재 시간을 체크하면서 시간이 충분히 흐를 때까지 thread_yield() 함수 호출

  /threads/thread.c

  1. void thread_yield(void)

• CPU 양보해줌. 현재 thread를 sleep 상태에 (큐)에 넣지 않고 스케줄러가 한가하면 곧바로 이 thread가 스케줄링될 수 있도록 해주는 함수
  1. 이전 레벨의 interrupt를 비활성화해주기
  2. 현재 thread가 idle하지 않다면 (external interrupt 중이 아니라면)
  3. ready_list의 맨 끝으로 현재 thread를 줄세우기
  4. 스케줄러

void thread_yield (void) {
	struct thread *curr = thread_current (); /* 현재 run(실행)중인 thread 리턴.*/
	enum intr_level old_level; /*interrupt 활성화 여부*/

	ASSERT (!intr_context ()); /*#####test######*/

	old_level = intr_disable (); /* interrupt 비활성화하고 이전 interrupt 상태 리턴해줌 */
	if (curr != idle_thread)/* Returns true during processing of an external interrupt and false at all other times. */
		list_push_back (&ready_list, &curr->elem); /* ready_list 끝에 현재 elem 삽입. */
		do_schedule (THREAD_READY);    /* 새로운 process 스케줄링 해주는 함수. 현재 thread의 상태를 THREAD_READY로 바꿔주고 run(실행)해야할 다른 thread찾고 그 thread로 switch함 ⚠️진입 지점에 interrupt 비활성화된 상태여야함. ⚠️ */
		intr_set_level (old_level);    /* old_level에서 상세한 대로 interrupt을 활성/비활성화해주고 이전 interrupt 상태를 리턴해줌 */
}

---

Project1 변경해야할 함수들 총정리

1. Alarm

---

2. Priority Scheduling

---

3. 4BSD like sceduling

---

Semaphore & Mutex

1. Deadlock (교착상태)

1-1. 교착 상태 발생 필요조건(4가지 만족해야 발생)

3. Mutex

3-1. Mutex == Mut(ual) Ex(clusion)

3-2. lock이 걸렸다면 대기실로~

3-3. busy-waiting == (while thread==손님)자원요청

4. Semaphore

4-1. Semaphore는 여러개의 공유 자원에 대한 접근

4-2. thread가 임계영역에 진입할 때마다 'P'외치기 (thread가 차지한 테이블 ++)

4-3. thread의 작업 완료 (공유자원 사용 해제) 'V'외치기 (thread가 차지한 테이블 --)

5. 간단 요약

Mutex

• 여러 스레드를 사용하는 환경에서 자원에 대한 접근을 강제하기 위한 동기화 매커니즘
• Boolean 타입 Lock변수 사용
• 공유자원을 사용중인 thread 있을 경우, 다른 thread가 공유자원 요청 시 Block하고 wait 큐에 넣기
• Lock은 lock을 건 thread만 해제 가능

SpinLock

• Mutex와 유사, Busy-waiting 하므로 wait큐가 없음 (전체 thread와 실행 중인 thread 큐, 2개)
• Mutex-nonblocking 모델로 볼 수 있음 (공유자원 접근을 막지 않음)

Semaphore

• semaphore 변수(counter)를 통해 wait, signal 관리
• counter가 양수일 때는 공유자원 요청을 수락할 수 있는 개수 (0이면 모두 lock이 걸려 대기(wait)해야하는 상태, 음수면 절대값이 lock이 걸린 개수)
• 계수 세마포어로 사용가능, 접근 가능한 공유 자원의 수가 1개 일때 (이진 세마포어)는 뮤텍스처럼 사용가능
• Lock을 걸지 않은 thread도 signal을 보내 lock 해제 가능

6. C언어로 보기 (업로드 예정)