🖥️ PintOS
🔷 Priority-donation
1. priority-donate-nest 통과시키기
우선순위 기부 효과가 풀리는 건 세마업 이후
old priority가 -1이면 아직 기부받지 않았다는 뜻
기부를 받으면 자신의 우선순위를 old priority에 저장한다
기부의 효과가 전부 풀릴 때 다시 원상복구해야한다
어콰이어
락에 자신의 우선순위를 제출한다.
락의 기부 우선순위가 갱신되었다면
해당 락의 홀더의 우선순위와 비교하여
높으면 갱신한다
갱신되었다면 해당 락 홀더가
기다리고 있는 락들의 홀더들에게
우선순위를 다시 제출한다.
릴리즈
자신의 락 리스트에서 해당락을 제거한 뒤에
자신의 락 리스트를 순회하면서
기부받을 우선순위의 최대를 갱신한다
갱신되었다면 해당 쓰레드가
기다리고 있는 락들의 홀더들에게
우선순위를 다시 제출한다.
동기분에게 물어봤다.
기다리고 있는 락은 하나밖에 없다.
lock_acquire 실패 기록
/* 안되는 버전 1 : 다다음 락에 닿지 못함. lock_to_update->holder != NULL을 하나라도 풀면 오류남. */
struct lock *lock_to_update = lock;
// 락이 기부할 우선순위가 현재 쓰레드의 우선순위보다 낮다면
while (lock_to_update->priority_to_donate < current_priority)
{
lock_to_update->priority_to_donate = current_priority; // 락 기부 우선순위 갱신
// 락 홀더의 우선순위가 현재 쓰레드의 우선순위보다 낮다면
if (lock_to_update->holder != NULL && lock_to_update->holder->priority < current_priority)
{
// 기부를 처음 받는다면 old_priority에 이전 우선순위를 저장한다
if (lock_to_update->holder->old_priority == -1)
lock_to_update->holder->old_priority = current_priority;
lock_to_update->holder->priority = current_priority;
}
if (lock_to_update->holder != NULL && lock_to_update->holder->waiting_lock != NULL)
lock_to_update = lock_to_update->holder->waiting_lock;
} /* 안되는 버전 2 : 다다음 락에 닿지 못함 */
struct lock *lock_to_update = lock;
while ((lock->holder != NULL) && (lock->holder->im_waiting == 1))
{
if (lock_to_update->priority_to_donate < current_priority)
{
lock_to_update->priority_to_donate = current_priority;
if (lock_to_update->holder->priority < lock_to_update->priority_to_donate)
{
if (lock_to_update->holder->old_priority == -1)
lock_to_update->holder->old_priority = lock_to_update->holder->priority;
lock_to_update->priority_to_donate = current_priority;
lock_to_update = lock_to_update->holder->waiting_lock;
continue;
}
}
break;
}lock_release용 재귀 코드 실패
void release_update(struct lock *lock)
{
if (lock->holder->old_priority != -1)
{
struct list *my_lock_list = &(lock->holder->lock_list); // 자신이 가진 lock들의 list
// 자신이 가진 락들을 다시 순회하여 최대 priority 얻기
int max_priority = lock->holder->old_priority;
struct list_elem *e;
for (e = list_begin(my_lock_list); e != list_end(my_lock_list); e = list_next(e))
{
int elem_priority = list_entry(e, struct lock, elem)->priority_to_donate;
max_priority = (elem_priority > max_priority) ? elem_priority : max_priority;
}
lock->holder->priority = max_priority; // 최대 priority로 갱신시킨 뒤에
if (lock->holder->waiting_lock != NULL) // 자신이 기다리고 있는 락이 있다면
release_update(lock->holder->waiting_lock); // 그 락 홀더의 우선순위도 업데이트
}
}통과한 코드 정리
priority-donate-chain도 동시에 통과되었다.
lock_acquire
void lock_acquire(struct lock *lock)
{
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(!lock_held_by_current_thread(lock)); // current_thread는 해당 락 아직 안 갖고 있음
thread_current()->waiting_lock = lock; // 해당 쓰레드가 기다리고 있는 락을 저장한다
int current_priority = thread_current()->priority;
struct lock *lock_n = lock;
// 만약 lock holder가 있었다면 (= lock을 기다려야 한다면)
while (lock_n->holder != NULL)
{
// 락 기부 우선순위를 갱신한다
if (lock_n->priority_to_donate < current_priority)
{
lock_n->priority_to_donate = current_priority;
// 락 홀더의 우선순위가 현재 쓰레드의 우선순위보다 낮다면
if (lock_n->holder->priority < current_priority)
{
// 기부를 처음 받는다면 old_priority에 이전 우선순위를 저장한다
if (lock_n->holder->old_priority == -1)
lock_n->holder->old_priority = lock->holder->priority;
// 락 홀더 우선순위를 갱신한다
lock_n->holder->priority = current_priority;
// 락 홀더가 기다리고 있는 락이 있었다면
if (lock_n->holder->waiting_lock != NULL)
{
lock_n = lock_n->holder->waiting_lock;
continue;
}
}
}
break;
}
sema_down(&lock->semaphore);
list_push_front(&(thread_current()->lock_list), &lock->elem); // 해당 쓰레드의 갖고있는 락 리스트에 락을 넣어준다.
lock->holder = thread_current();
lock->holder->waiting_lock = NULL; // 기다리고 있는 락을 없애준다
}lock_release
void lock_release(struct lock *lock)
{
ASSERT(lock != NULL);
ASSERT(lock_held_by_current_thread(lock));
// 자신이 가진 lock들의 list에서 해당 lock을 지워버린다
list_remove(&lock->elem);
// release_update(lock);
// if (list_empty(&lock->holder->lock_list))
// lock->holder->old_priority = -1;
/* 내려놓은 lock의 우선순위를 갱신해준다 */
if (lock->holder->old_priority != -1) // 우선순위를 기부받은 적이 있었다면
{
struct lock *lock_to_update = lock;
while (lock_to_update != NULL && lock_to_update->holder != NULL)
{
// 자신이 가진 락들을 다시 순회하여 최대 priority 얻기
int max_priority = lock_to_update->holder->old_priority;
struct list *holders_lock_list = &lock_to_update->holder->lock_list;
struct list_elem *e;
for (e = list_begin(holders_lock_list); e != list_end(holders_lock_list); e = list_next(e))
{
int elem_priority = list_entry(e, struct lock, elem)->priority_to_donate;
max_priority = (elem_priority > max_priority) ? elem_priority : max_priority;
}
lock_to_update->holder->priority = max_priority;
// 만약 남은 락이 없었다면 old_priority를 -1로 바꿔주기
if (list_empty(holders_lock_list))
lock_to_update->holder->old_priority = -1;
lock_to_update = lock_to_update->holder->waiting_lock;
}
}
if (list_empty(&lock->holder->lock_list))
lock->holder->old_priority = -1;
lock->holder = NULL;
sema_up(&lock->semaphore);
}2. priority-donate-lower
자신의 우선순위를 갱신하는 방법
: 현재 자신의 우선순위와 락 리스트를 쭉 훑고 얻은 최대 우선순위 중 최대값으로 갱신
자신의 우선순위가 갱신되었다면 waiting lock의 우선순위도 갱신 시도한다.
waiting lock의 우선순위를 갱신하는 방법
: 자신의 원래 우선순위와 락 리스트를 쭉 훑고 얻은 최대 우선순위 중 최대값으로 갱신
정리
thread_set_prirority
void thread_set_priority(int new_priority)
{
thread_current()->priority = new_priority;
if (thread_current()->old_priority != -1)
thread_current()->old_priority = new_priority;
update_priority(new_priority, thread_current());
check_priority_and_yield();
}우선순위가 변경된 것이 미치는 영향을 전파시킨다.
전파 시키는 거 구현하고도
thread_current()->old_priority = new_priority; 이 부분 놓쳐서 살짝 헤맴
update_priority
/* 어떤 쓰레드의 우선순위가 변경되었을 때 자신의 우선순위를 재점검하는 재귀함수 */
void update_priority(int my_priority, struct thread *t)
{
// 자신의 우선순위를 갱신하는 방법 : 현재 자신의 우선순위와 락 리스트를 쭉 훑고 얻은 최대 우선순위 중 최대값으로 갱신
// waiting lock의 우선순위를 갱신하는 방법 : 자신의 원래 우선순위와 락 리스트를 쭉 훑고 얻은 최대 우선순위 중 최대값으로 갱신
struct list *my_lock_list = &t->lock_list;
struct list_elem *e;
for (e = list_begin(my_lock_list); e != list_end(my_lock_list); e = list_next(e))
{
int elem_priority = list_entry(e, struct lock, elem)->priority_to_donate;
my_priority = (elem_priority > my_priority) ? elem_priority : my_priority;
}
if (my_priority == t->old_priority)
t->old_priority = -1;
t->priority = my_priority;
if (t->waiting_lock != NULL)
update_priority(t->waiting_lock->holder->old_priority, t->waiting_lock->holder);
}lock_release 살짝 응용.
이건 lock 기준이 아니라 쓰레드 기준으로 정보를 전파시킨다.
3. priority-donate-sema
Acceptable output:
(priority-donate-sema) begin
(priority-donate-sema) Thread L acquired lock.
(priority-donate-sema) Thread L downed semaphore.
(priority-donate-sema) Thread H acquired lock.
(priority-donate-sema) Thread H finished.
(priority-donate-sema) Thread M finished.
(priority-donate-sema) Thread L finished.
(priority-donate-sema) Main thread finished.
(priority-donate-sema) end
Differences in `diff -u' format:
(priority-donate-sema) begin
(priority-donate-sema) Thread L acquired lock.
- (priority-donate-sema) Thread L downed semaphore.
- (priority-donate-sema) Thread H acquired lock.
- (priority-donate-sema) Thread H finished.
(priority-donate-sema) Thread M finished.
- (priority-donate-sema) Thread L finished.
(priority-donate-sema) Main thread finished.
(priority-donate-sema) endlower까지 통과한 코드를 그대로 돌렸더니 나온 결과.
정리
void sema_up(struct semaphore *sema)
{
enum intr_level old_level;
ASSERT(sema != NULL);
old_level = intr_disable();
if (!list_empty(&sema->waiters))
{
list_sort(&sema->waiters, for_descending_priority, NULL);
thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem));
}
sema->value++;
intr_set_level(old_level);
check_priority_and_yield();
}엄청나게 비효율적이지만 어쨌든 통과...
4. priority-condvar
나머지 다 통과하는데 이것만 통과 안 함.
그래서 디버깅 문구 찍어봤는데 sema->waiters의 size가 1임.
starting은 되는데 왜??
알고보니까 그냥 priority-condvar 파일이 아니라
priority-donate-sema 파일 보면서
아니 다 잘 작동하는데 왜?? 이러고 있던 거였다.
이건 size 잘 찍힘.
왠지 테스트 코드에 없던 문구도 출력되더라...
좀 어이없는 실수.
cond_signal이랑 cond_wait를 수정해야 하는듯.
void cond_wait(struct condition *cond, struct lock *lock)
{
struct semaphore_elem waiter;
ASSERT(cond != NULL);
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(lock_held_by_current_thread(lock));
sema_init(&waiter.semaphore, 0);
// list_insert_ordered(&cond->waiters, &waiter.elem, &for_descending_priority, NULL);
// list_insert_ordered(&cond->waiters, &waiter.elem, &cond_descending_priority, NULL);
list_push_back(&cond->waiters, &waiter.elem);
list_sort(&cond->waiters, &cond_descending_priority, NULL);
lock_release(lock);
sema_down(&waiter.semaphore);
lock_acquire(lock);
}cond_wait에서 삽입할 때 우선순위대로 정렬해주기 위해
// 쓰레드를 우선순위 내림차순으로 정렬하기 위한 함수
bool cond_descending_priority(const struct list_elem *a, const struct list_elem *b, void *aux)
{
int ap = 0;
int bp = 0;
// 첫 번째 리스트 요소에서 우선순위를 가져옴
if (!list_empty(&list_entry(a, struct semaphore_elem, elem)->semaphore.waiters))
ap = list_entry(list_front(&list_entry(a, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority;
// else
// return ap < bp;
// 두 번째 리스트 요소에서 우선순위를 가져옴
if (!list_empty(&list_entry(b, struct semaphore_elem, elem)->semaphore.waiters))
bp = list_entry(list_front(&list_entry(b, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority;
// printf("ap : %d, bp : %d\n", ap, bp); // 두 값을 출력하여 확인
return ap > bp; // 우선순위 내림차순으로 정렬
}cond_descending_priority라는 걸 만들었는데
(priority-condvar) Thread priority 30 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 29 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 28 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 27 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 26 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 25 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 23 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 22 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 21 woke up.
(priority-condvar) Signaling...
(priority-condvar) Thread priority 24 woke up.
(priority-condvar) end마지막 24가 이상하게 정렬됨.
도저히 모르겠어서 옆 동기한테 물었더니
복잡하게 생각할 거 없이 cond_signal을 살짝만 건드려주면 된다고 함.
??????
그냥 정답 받아서 해결함.
정리
/* 옆자리에서 베껴온 함수 */
static bool sema_greater(const struct list_elem *a_,
const struct list_elem *b_, void *aux UNUSED)
{
const struct semaphore_elem *a = list_entry(a_, struct semaphore_elem, elem);
const struct semaphore_elem *b = list_entry(b_, struct semaphore_elem, elem);
return list_entry(list_front(&(a->semaphore.waiters)), struct thread, elem)->priority <
list_entry(list_front(&(b->semaphore.waiters)), struct thread, elem)->priority;
}
// 쓰레드를 우선순위 내림차순으로 정렬하기 위한 함수
bool cond_descending_priority(const struct list_elem *a, const struct list_elem *b, void *aux)
{
int ap = list_entry(list_front(&list_entry(a, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority;
int bp = list_entry(list_front(&list_entry(b, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority;
return ap > bp; // 우선순위 내림차순으로 정렬
}
void cond_signal(struct condition *cond, struct lock *lock UNUSED)
{
ASSERT(cond != NULL);
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(lock_held_by_current_thread(lock));
if (!list_empty(&cond->waiters))
{
// struct list_elem *max = list_max(&cond->waiters, cond_descending_priority, NULL);
// list_remove(max);
list_sort(&cond->waiters, cond_descending_priority, NULL);
// sema_up(&list_entry(max, struct semaphore_elem, elem)->semaphore);
// list_sort(&cond->waiters, for_descending_priority, NULL);
sema_up(&list_entry(list_pop_front(&cond->waiters), struct semaphore_elem, elem)->semaphore);
}
}기분이 살짝 더럽다.
일단 내가 만들었던 쓰레드용 비교 함수는 쓰는게 아닌게 맞았음.
그래서 나도 cond_descending_priority를 만들었는데?
list_inorder_insert를 할 때 오류가 나니까 억지로 보호 구문을 만들었고?
그 이후에 list_sort()를 시도해봤지만?
이미 보호 구문과 이상한 초기화 때문에 망가진 상태였고?
아무튼 고쳤더니 내 것도 제대로 작동한다.
살짝만 다시 갈아엎어보거나 침착하게 생각했으면 됐을텐데
아쉽다. mlfqs 앞두고 이것 때문에 계속 시간 낭비 하니까
마음도 급해지고 시야가 좁아진듯.
🔷 Advanced Scheduler
1. 개념 공부
4.4 BSD 스케줄러는 다단계 큐(multilevel queue)를 사용하여 우선순위에 따라 프로세스를 분류하고 관리함.
https://lorkhan-0307.github.io/posts/pintOS/
4.4BSD 스케쥴러가 활성화되면, 쓰레드들은 더이상 직접 자신의 우선순위를 컨트롤하지 않는다. thread_create()에 전달되던 우선순위 인자들은 무시될 것이며, thread_set_priority()나 thread_get_priority()로 향하는 요청들은 스케쥴러에서 결정된 쓰레드의 현재 우선순위만 반환하게 될 것이다.
일반적 사용을 위한 스케쥴러의 목표는 쓰레드들의 밸런스를 서로 다른 스케쥴링의 필요성에 맞추는 것이다. 많은 I/O를 필요로 하는 쓰레드는 지속적으로 input 및 output devices 들을 계속 바쁘게 하기 위해 빠른 response time을 필요로 하지만, CPU는 비교적 짧은 시간동안만을 필요로 한다. 반대의 경우로, 연산을 필요로 하는 쓰레드의 경우, 상대적으로 긴 시간의 CPU를 필요로 하지만, fast response time은 전혀 필요하지 않다. 이 둘 사이에 놓인 또 다른 쓰레드들은, I/O 에 의존적인 연산 시간을 가지고 있어, 그 사이의 시간들을 또 필요로 할 수도 있다. 훌륭하게 설계된 스케쥴러의 경우, 이러한 다수의 조건들을 동시에 쓰레드들에 제공할 수 있다.
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
recent_cpu는 쓰레드가 최근에 사용한 cpu의 시간을 의미하고(이는 하단의 calculating recent_cpu 를 참고) nice 는 쓰레드의 nice value를 의미한다. 결과는 내림을 통해 가장 가까운 정수로 바꿔야 한다. recent_cpu와 nice에 곱해지는 1/4 와 2 는 최적화된 값으로 알고 있지만, 그보다 더 깊은 의미는 가지지 않는다. 계산된 우선순위는 반드시 가능 범위인 PRI_MIN과 PRI_MAX 사이에 존재하여야 하므로 조정되어야 한다.
우리는 recent cput를 계산하여 각 프로세스가 가장 최근에 얼만큼의 CPU time을 할당받았는지를 계산하고자 한다. 더 정제된 계산을 위하여, 가장 최근의 CPU time은 덜 최근의 CPU time보다 더 무겁게 측정되어야 한다
https://www.youtube.com/watch?v=4-OjMqyygss
먼저 끝냈던 동기가 보면 좋다고 추천해줌
⚔️ 백준
📌 3055 탈출
깊은 복사 하는 방법
이차원 배열 복사해서 선언하지 말자
'그 오류' 난다
