1. Alarm Clock

Main goal : System call that wakes up a process in ticks amount of time

• Modify current 'busy-waiting' alarm into 'sleep/wakeup' alarm.
• ticks 시간 만큼 후에 wake-up process를 진행
• wake up 후엔 해당 프로그램이 돌아간 후 다시 sleep 상태로 돌아가게 된다

Files to modify:

• threads/thread.*
• devices/timer.*

Design of sleep/wakeup alarm

• yield()를 통해 running state에서 ready state로 가는 것이 아닌 sleep()을 통해 blocked state로 가도록 해야함
• 현재 존재하는 all_list, ready_list에 더해서 sleep_list도 구현
• wakeup(), list_push_back()을 통해서 thread가 sleep_list에서 ready_list로 이동할 수 있도록 함

구현 목록

• sleep_list and thread_init
• local tick and global tick
• timer_sleep and thread_sleep
• insert_sleep_listp : insert thread into sleep list in order of wakeup_tick
• timer_interrupt
• thread_wakeup => thread_awake
• set_global_tick and get_global_tick => update_next_tick_to_wake and get_next_tick_to_awake
• (Challenge) start = timer_ticks() 값이 invalid해지는 것을 방지할 방법 고안

functions to add
1. sets thread state to blocked and insert into sleep queue (thread_sleep)
2. finds the thread to wake up from sleep queue and wake it up (thread_wakeup)
3. saves the minimum value of tick that threads have (set_global_tick)
4. returns the minimum value of tick (retrieve the global variable tick) (get_global_tick)

static struct list sleep_list

• when to decare the list and when to initialize it?
• thread_init 에서 sleep_list를 initialize하는 부분 추가

local tick and global tick

• local tick : 각각의 thread가 깨어나야 하는 시각에 대한 field 추가 (e.g. int64 wakeup_tick)
• global tick : the minimum value of the local ticks in the threads (where to decalre and when to initialize?)

void timer_sleep(int64_t ticks)

• move thread(itself) to sleep queue
• looking at ticks, if there is time left till the wakeup, remove the caller thread from ready_list and insert into sleep_list
• (Challenge) start = timer_ticks() 값이 중간에 invalid 해지는 것을 방지할 방법 고안
  • mutex로 처리?
  • disable_interrupt로 처리?

thread_sleep(int64_t ticks) <-- (start + ticks)

• caller thread의 state를 blocked로 변경, sleep queue에 넣어주기
• if the current thread is not idle thread, change the state of the caller thread to BLOCKED
• store the local tick to wake up(start + ticks) into the thread's struct
• update the global tick if necessary
• call schedule
• when manipulating thread list, disable interrupt

timer_interrupt(int64_t ticks)

• at every tick, check whether some threads must wake up(remove from sleep queue, call wakeup(), push into ready queue)
• 깨울 thread를 결정하고, 깨우는 thread에 대해서는 sleep_list에서 제거하고, ready_list에 넣어주고, thread의 state를 바꿔주는 등 일련의 과정을 수행하는 루틴 (interrupt handler)
• alarm time(깨어나야하는 시각) 기준 오름차순으로 정렬 하는 등 sleep_list를 어떻게 정리하느냐에 따라 깨울 thread를 결정하는데 걸리는 시간이 크게 달라질 수 있음
• check slee_list and the global tick
• find any threads to wake up
• move them to the ready_list if necessary
• update the global tick

Things I might use from thread.c

• next_thread_to_run
• idle
• thread_block
• do_schedule
• scheduel : stop current thread and run the next thread to run

other TODOs in thread.c

• thread_set_priority
• thread_get_priority
• thread_set_nice
• thread_get_nice
• thread_get_load_avg
• thread_get_recent_cpu

Things I might use from timer.c

• ticks : number of timer ticks since OS booted
• timer_ticks : returns the number of timer ticks since OS booted
• timer_elapsed(then) : number of timer ticks elapsed since THEN

Things I might use from list.c

• list_sort: sorts list according to LESS given auxilary data AUX, runs on O(nlogn)
• list_insert_ordered : insert ELEM in the position in LIST, sorted according ro LESS given auxilary data AUX, runs in O(n)

2. Priority Scheduling

Main Goal : FIFO 새 priority scheculing

• sort ready list by priority
• sort wait list for synchronization primitives
• implement preemption (preemption point : when thread is put into ready list, not every timer interrupt)

files to modify

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

구현 목록

• thread struct -> add priority field (already there)
• ready_list with priority -> implemented when inserting into list
• thread_create -> schedule if priority is higher than the current
• thread_unblock -> insert to ready list in priority order
• thread_yield -> insert to ready list in priority order
• thread_set_priority -> change priority and reorder in the ready list according to the changed priority
• bool cmp_priority(a, b, aux) -> 내림차순

Synchronization

Main Goal : 현재 semaphore 또는 condition을 기다리고 있는 waiters list는 FIFO로 구현되어있다. 이걸 priority에 따라 CPU를 점유하도록 수정

Files to modify

• thread.*
• synch.*

구현 목록

• sema_down : insert thread into semaphore waiters list in priority order
• sema_up : sort before popping a thread from the front of the semaphore waiters list
• cond_wait : insert threads into condtion variable waiters list in priority order
• cond_signal : sort before popping a thread from the front of the conditional variable waiters list
• cmp_sem_priority : for ordering descending semaphores that will go in conditional variable waiters list containing a thread => list_begin을 통해 가장 앞에 하나만 확인하긴 하지만 결국엔 하나밖에 안들어있는 리스트일 것으로 보임

Functions

• sema_init(sema, value) : initiate SEMA with VALUE and initiate SEMA's waiters list
• sema_down : "P" function. while sema value is 0, thread is queued at the end of waiters list and thread is blocked, scheduled to give running state to the next thread
  • interruption is disabled when sema_down starts but it says the next thread will probably turn interrupt back on... which i don't understand.. and it is explained in the Project1 FAQ ~
  • if sema value is not 0 when this function is called, the thread won't block in waiters list and go straight to decrementing the value and ending the function.
• sema_try_down : try decrementing and return true/false
• sema_up : "V" function. increment sema value. if there is something in the waiters list, pop front, unblock to make it get to sema.
• lock_init : lock = mutex(binary semaphore) -> also initializes another semaphore
• lock_acquire : do sema down and the holder of the lock becomes the current thread
• lock_try_acquire : try sema down, if success, current thread holds the lock
• lock_release : lock holder to NULL(freeing the holder), sema up(releasing the lock)
• lock_held_by_current_thread : checks if the current thread is the holder of the lock
• struct semaphore_elem : One semaphore in a list?? -> elem, semaphore ==> HAVE NO IDEA WHAT THIS IS
• cond_init : initalizes condition variable - allows one piece of code to condition and cooperating code to receive the signal
• cond_wait : atomically realease lock and wait for condition to be signaled by other codes(event의 발생/ 원하는 컨디션이 충족되어서 signal이 올 때 까지) current thread must be already holding the lock before calling this function
• initiate semaphore in the list, push it to the end of the waiters list of the condition variable, release lock, sema down(block this semaphore and make it sleep), lock acquire..? why do i get the lock after being blocked....?
• condition variable은 오로지 한개의 lock에만 연결이 되어있을 수 있지만, lock은 여러개의 condition variable과 연관되어있을 수 있음
• so..... semaphores can sleep in condition variable. i think this means a particular semaphore will wait(sleep) until a condition is fullfilled and the conditions signals it
• but then wouldn't all other threads wait for the semaphore? wouldn't other threads that use the semaphore might not need this particular condition? I guess these are conditions that is mendatory for the semaphores?
  => 집단지성을 통해 내린 결론 : each new semaphore that is initiated into condition variable's waiters list act as a lock for holding the thread back into sleeping state
• cond_signal : if the waiters queue for cond is not empty, pop front to get the semaphore waiting and sema up the semaphore
• cond_broadcast : signal all semaphores in list

오류 잡기

list_sort() 함수를 추가한 후 계속 그 다움 줄에 있는 list_pop_front()에서 에러가 났으며, 타고타고 들어간 결과 !empty_list() assertion에서 문제가 발생하고 있엇다.
그런데 문제는 전혀 문제가 없는 문장을 추가한거라 몇시간을 해결을 못하고 끙끙대고 있었다.
그러다가 혹시 몰라 중괄호를 추가하였는데... 됐다... 앞으로는 중괄호를 꼭 잘 챙겨서 써넣어야겠다..

Priority Donation

Priority Inversion

• Thread L acquires the lock
• Thread H requests for the lock but since it can't get it yet because L is holding it, H blocks
• Thread M comes in the ready list and since it has nothing to do with the lock, it doesn't block and rather preempts L
• When M is done, L continues and after releasing the lock H starts running again
• this results in priority inversion between H and M, where thread M with lower priority runs beforehand H

Priority Donation

• lock을 기다리고 있는 thread의 priority가 높다면 lock을 가지고 있는 thread에게 동일한 priority를 상속해줘서 (donate 해줘서) 이 semaphore에 대해서 기다리고 있는 thread 보다 우선순위가 낮은 thread에게 순서를 뺏기지 않도록 하는 것
• Thread L 이 H 의 priority를 상속함으로써 H가 priority에 맞게 M보다 빠르게 할일을 처리할 수 있다.
• (아래 이미지의 경우 위 이미지와 다르게 thread M 역시 lock을 request 했기 때문에 block 했다가 acquire lock을 한 것 처럼 나오는데, priority donation을 설명하기에는 예시가 잘못되었다고 생각한다. thread M이 lock을 요구할 것이었다면 priority donation이 일어나지 않은 위 이미지의 상황에서도 똑같이 block을 했다가 가장 마지막에 acquire lock을 했을 것이기 때문이다. priority donation을 통해서 priority inversion이 일어나지 않았음을 보여주기 위해서는 thread M은 lock에 대해 요구를 해서 block 되어있는 것이 아니라 priority에 의해서 기다리고 있어야 한다.)
• priority donation 은 lock/semaphore의 wait list에 thread가 들어갈 때마다 가능한지 확인되어야 할 것 같다.

Nested Donation issue

• donation을 받은 thread가 waitlist에 들어가있는 lock을 들고있는 thread도 연쇄적으로 priority를 donate 해줘야 한다.
• (lock을 들고 있는 thread가 lock을 요구하는 thread와 그 thread가 들고있는 lock까지 연쇄적으로 'nesting' 하고 있는 형태)
• if nested donation is not considered
• 해결 방안 : lock that the thread it waiting for

Multiple Donation issue

• 여러개의 lock을 가지고 있는 경우, 각각의 lock의 waitlist의 thread의 최대 priority를 donate 받을텐데, 이때 만약 최대의 priority를 donate해주고 있던 lock을 release하게 된다면 남은 다른 lock의 donor 중에서 최대값으로 다시 update를 해줘야 함
• 해결 방안 : linked list of donors

thread struct for priority donation

• priority
• original_pri : store the original priority (store when initiated? when donation occurs?)
• wait_on_lock : define which lock the thread is waiting on
• donations : list of donor_elem
• d_elem(donor_elem) : element for linking into a donations list

구현 idea

1. Nested donation

   • when a new thread waits on a lock, check the holder of the lock, check if i have to donate
   • if i have to donate, link into donations list of the holder
   • also check if the holder of the lock is waiting for any lock and continue on through the link

2. Multiple donation

   • if a thread received a donation insert d_elem of the donor into the thread's donations list
   • this linked list should be ordered descending for the priority (when inserting)
   • when the thread holds another lock, (이미 해당 lock의 waitlist에 있을 때 priorit가 가장 높은 thread 였을 테니까, 현재 상태는 볼 필요가 없음)
   • when a new thread comes into a lock that the thread is holding -> new thread가 lock의 waitlist에 들어가는 insertion이 이루어질 때 checks for donation and links into the donations list if necessary
   • when a lock is released, before giving the lock to another thread, check donations list for a thread on a wait for the particular lock, and if there is, remove the d_elem of that thread out of the donations list

구현 목록

• struct thread : add fields for prioirty donation
• init_thread : modify initiation according to the changed thread struct
• lock_acquire : (when a new thread is trying to acquire the lock!)
  • donate_priority() : check if the holder of the lock needs donation, if it does link into donations list
  • store current priority in original_pri and maintain donated threads on list
    • when i have a lock?? -> i guess this means managing donations list of the holder of the lock (this should be done within the donate_priority function
• lock_release : from the donation list remove the thread that is waiting for the lock (or now holds the lock?)(check if the new holder of the lock is in the donations list?)
  • remove_with_lock() (한양대 설명 자료에서 설정한 함수명) : 함수명에서 힌트를 얻은 것은 내가 lock을 release 함으로써 lock을 얻게되는 thread가 있음 -> 그러면 내가 알고있는 그 lock의 새로운 holder thread의 d_elem 값을 가져와서 내 donations list에서 list_remove
    • thread entry를 제거하라고 함 (자료형을 잘 확인해보기)
    • what if it's not in the donations list?
    • list_remove는 list의 안쪽에 있어야 함
    • list의 front라면 front pop, back이라면 back pop을 해줘야 함
    • only if it was the front of the list, refresh_priority()
    • list에 없다면 아무 동작도 하지 않음
  • remove_donor() : (위에 한양대 자료에서 제안한 remove_with_lock 함수명이 적합하지 않다고 생각해 변경) lock을 release 하기 전에 lock의 semaphore의 waiting list에서 기다리고 있는 첫번째 thread를 확인 -> 해당 thread의 d_elem을 donations list에서 제거 -> donations list를 탐색할 때 조건은 위와 동일
  • refresh_priority() : check max value in donations list and the stored priority value of mine and refresh the superficial(표명상의) priority -> back to the original priority value if there is none in the donations list
• thread_set_priority : set priority considering donation
  • change priority of the current holder (probably called when a donor wants me to change -> nope this is not possible since donations occur when a current thread waits on a lock and wants it's holder to get a higher priority)
  • since now i am changed, try donating my new value to holders of lock that i am waiting for => this is the case for donate_priority
  • this should be called when i release a lock
  • since i have released a lock and the donors regarding the lock, my priority should have changed and preemption might occur due to that
    -> then why not add test_max_priority to lock_release and leave thread_set_priority alone..?
  • 아냐아냐 이 함수는 외부에서 해당 thread의 priority를 강제로 변경해주고자 할 때 사용하는 함수이다
  • 따라서 내 priority가 변경이 되고, original_priority도 변경된 값을 저장해주고, donation 받는 것을 고려해서 refresh_priority를 해주고,
  • 나의 새로운 priority값이 엄청 클 수도 있는데, 내가 지금 기다리고 있는 lock이 있다면 새로운 priority로 nest들을 갱신시켜주어야 함 (donations list에 연결은 이미 되어있을 것임)
  • 근데 또 lock의 waitlist에 있어서 donate를 해야하는 상황이라면 test_max_priority를 해서 thread_yield를 하는 상황은 안오지 않나 싶기도 한데,
  • donate_priority는 lock을 기다리는 상황에서만 발동한다고 생각하면 되지 않을까 싶기도 함... 으으으 너무 헷갈린다

구현 시작

struct thread

• should a thread have multiple locks that it is waiting for? asked gpt -> says it depends on how the system that I am making is made.. (thanks alot..) -> so I looked into lock_acquire again => thread blocks when trying to acquire the lock but can't -> this means that a thread can only be waiting for just one lock at a time
• still very confused on which should be a pointer variable and which shouldn't be
  • donations는 initiate 하려고 보니까 list_init에서 애초에 리스트의 주소를 줘야 한다는 것을 확인 -> thread struct 내에서 donations가 포인터이지는 않고, list init을 할 때 donations라는 list 요소의 주소를 사용함 -> thread struct 안에 donations list 가 있어야지, donations list가 다른 곳에 존재하고 그걸 가리키는 포인터가 thread에 있으면.. list의 위치는 어떻게 할당해줄건데.. ㅇㅇ 그래서 안됨

lock_acquire()

• when lock is not available, store address of the lock into wait_on_lock => was very confused on when this field should be stored
  • lock_acquire는 sema_down을 통해서 아직 lock을 얻지 못했을 때 blocked 상태를 유지하게 되는데, sema_down에 의해서 blocked 된 상태를 유지할 때 값을 store 하는건 불가능 -> initiate when thread initiates!

lock_release()

• Hypothesis 1
• Hypothesis 2

init_thread()
original_pri는 thread를 init 할 때 값을 할당해줘야 할까 donation을 받을 때 값을 store 해줘야 할까?
donation을 받을 때마다 store 하는 것은 불가능함 -> 매번 갱신된 값이 저장될 것이기 때문 -> 안전하게 initiating을 할 때 저장해주는게 좋지 않을까 생각
대신 저장공간을 낭비할 수는 있지 않을까 싶음 (아닌가?)

오류 잡기

donation 관련 코드들을 추가하니 assertion에서 시작된 debug panic이 계속해서 발생했다.
-> gdb를 VS Code에서 실행해보려고 했으나 지난 주와 마찬가지로 실행이 정상적으로 되지 않는 상황이다. 아무리 설정을 만져보고 검색을 해보고 GPT에서 물어봐도 해결이 되지 않아서 결국 command line에서 gdb를 사용하기로 마음을 먹었다. (조만간 VS Code를 삭제했다가 다시 설치해볼까 싶다...)
-> command line에서 gdb를 실행하는 방법을 익혀서 실행을 해 보았다. (생각보다 재미있었다) 하지만 아무리 해봐도 중간부터 실행이 되지 않고 멈추는 현상에서 벗어나지 못했다.
-> 결국 디버깅을 하는데 시간이 더 걸려서 시간이 너무 낭비되는 것 같아 포기를 했다.
-> 그와중에 매우 당황스럽게도 디버깅을 포기하고 아무것도 바꾼게 없는 것 같은데, 다시 돌려봤을 때 이전과 같은 debug panic이 발생하지 않는 것으로 확인이 되었다.

다시 코드를 찬찬히 살펴보며 priority donation이 정상적으로 이루어지지 않는 이유를 살펴보았다.

처음 구현을 했을 때 thread_set_priority 함수에서 새로 설정하는 우선순위를 thread의 priority 필드와 original_pri 필드 둘 모두에서 넣어주었다. 하지만 다른 팀원의 코드와 비교를 해보니, 굳이 priority 필드에 새로운 값을 할당해줄 필요가 없다는걸 깨달았다.
refresh_priority 함수에서 어차피 priority 필드를 최종 업데이트 해주게 된다. 따라서 필요없이 두번이나 해당 필드를 조작할 필요가 없다.

remove_with_lock 함수를 처음 구현할 땐 제거할 elem을 만나면 바로 삭제하고 for문의 list_next()로 넘어갈 수 있을거라고 생각했다. 그러나 생각해보니 list_remove를 하면 list_next의 인자로 넣어줄 수 있는 elem이 사라지는 것이기 때문에 for문 내에서 list_remove의 return 값인 다음 elem을 받아서 넘겨줘야 한다.

refresh_priority 관련해서는 두가지 방법으로 구현할 수 있다.
첫번째 방법은 donations list을 쭉 돌면서 현재 우선순위보다 높은 값이 있는 경우에만 priority를 덮어씌워주는 방법이다. 이 방법은 linear 하게 list를 서치한다.
두번째 방법은 donations list를 list_sort를 사용해서 우선순위가 가장 높은 elem이 list의 맨 앞에 오도록 해서 해당 thread 하나만 비교하는 방법이다. 이 방법이 한양대 설명자료 등에서 제안이 되는 방향인 것 같다. list_sort와 같이 이미 만들어진 함수를 손쉽게 사용할 수 있다는 점은 장점이라고 볼 수 있으나, 요소들을 두개씩 비교해서 순서를 정렬하는 방식이다 보니 시간복잡도는 더 높지 않을까 생각한다.