! 주의. project3에 swap 관련에서 에러가 걸린게 여기에 원인 있을 수 있으니 플로우를 참고만 할것.
마감 10분전에 총정리
말도 안된다
Alarm Clock
busy wating을 해결해라
-> 리스트 수정할때마다 인터럽 끄고 키는거 하지말라는거임?(x)
-> 얘가 while문으로 도는거 하지 말라는 거임?(대충 비슷)
-> 아 그럼 일정 시간 이상 자도록 그동안 다른 곳에서 정확한 시간 재서 그 tick동안 공회전 시키면 되나? (x)
-> tick이 갱신되는, timer interrupt 부분에서 스레드를 깨운다.
아니 근데 어떻게 재워
재운다는게 뭔 소리야
어디 앉아있으라고 해?
-> sleep list라고 별도의 list에 blocked 된 상태로 넣어두고, 설정한 tick이 지났을 때 ready list에 넣어준다.
쇼킹....
sleep list라는 개념도 안 알려주고
일단 busy wating을 해결하라고하는 git book도 쇼킹
이게 바로....카이스트?
일단 처음 하자니 뭘 추가하는것도 다
내가 넣자고 우기는거같고 다 망가질거같고 했지만
평범하게 얘네 그냥 다 하더라고요
전 타이머 인터럽트때 하면 되는구나깨닫고
세마포어 걸어주고있었는데......
....
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
thread_wake_up(ticks);
}
우기는 대로 해주고 있는 모습
또 어느 시간때마다 깨우냐 그것도 좀 난감했었음
왜냐하면 tick 경과를 알려면
thread가 재워진 시점 기준으로 tick 시간이 지나야하는데
내가 가진 건 부팅후 전체 시간 경과만 알려주는 ticks만 있었단 말야
thread안에 thread 시작 기점 tick을 넣어줘봤자
잠드는 타이밍은 또 케바케인데 너무한게 아닌가
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
thread_sleep(timer_ticks() + ticks);
}그냥 잠드는 시점을 같이 인자로 넘겨주면 되는구나..^^
왜이리 당연한것도 떠오르지 않는 걸까?
다들 이런 날것의 코딩을 하는걸까?
아무튼 리스트에 넣어서 블락 처리도 해줘.
thread_block이란 함수가 있었지만 자립해야하는지 알고
직접 상태 block으로 바꿔주는 정성을 해줬지만 지금은 냉정하게 자동화한 모습
void
thread_sleep(int64_t tick) {
enum intr_level old_level = intr_disable();
struct thread *curr = thread_current ();
if (curr != idle_thread) {
curr->ticks = tick;
list_push_back (&sleep_list, &curr->elem);
thread_block();
}
intr_set_level(old_level);
}그리고 아무튼 깨운대
그럼 깨우는 거...
sleep list에 있는 애 앞에 있는애 하나 꺼내서
tick 경과했는지 확인하고
경과 안 했으면 도로 넣고
했으면 ready list에 넣어주면 되는데
그럼 사실 뒤엣놈은 죄없이 기다려야한단 말이에요
그래서 리스트 순회해서 모든애를 확인해야하거든요
근데 저한텐 그 과정이 너무나 번거롭고..있을수없고..
list 함수와 서먹하고...
그래서 팀원분이 구현한걸 입에 넣어왔습니다
void
thread_wake_up(int64_t ticks){
if(list_empty(&sleep_list))
return;
struct list_elem *e;
for (e = list_begin(&sleep_list); e != list_end(&sleep_list);)
{
struct thread *t = list_entry(e, struct thread, elem);
if (ticks >= t->ticks)
{
e = list_remove(e);
thread_unblock(t);
}
else{
e = list_next(e);
}
}
}이러면 alarm의 priority 케이스까지 통과하지만
제겐 아직 list 함수가 정없게 느껴졌던 시절...
Priority Scheduling
조금 하니 케이스가 몇개가 통과가 되어서 기쁨
근데 쭉 보는데
이거 분량이...
진짠가?
지금 이걸 끝내고 advanced 구현까지 필수라고?
donation 하다 죽을거같은데...
donation이 사실 advanced scheduler가 아닌지 진짜 생각했는데
priority였어요 일단 해야하니 합니다
priority 에 대한 미니 케이스를 봅시다
priority_change
void
test_priority_change (void)
{
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
msg ("Creating a high-priority thread 2.");
thread_create ("thread 2", PRI_DEFAULT + 1, changing_thread, NULL);
msg ("Thread 2 should have just lowered its priority.");
thread_set_priority (PRI_DEFAULT - 2);
msg ("Thread 2 should have just exited.");
}
static void
changing_thread (void *aux UNUSED)
{
msg ("Thread 2 now lowering priority.");
thread_set_priority (PRI_DEFAULT - 1);
msg ("Thread 2 exiting.");
}
오케이!
모르겠음
테스트 c코드 저는 일단 긁어서
지피티한테 해석해달라고 합니다
저혼자서도 할수는있겠죠 하지만 힘들겠죠
그래서 대강 골자 파악하면 그때부터 디테일을 봅니다
근데 사실 이정도는 그냥 보면 알죠 처음 보는 함수
음
thread_create
thread_set_priority
시작 시점부터 짱 쎈놈을 소환하는 것,
그리고 set으로 짱 센놈을 약화시키는 것을 반복하면서
그때그때 가장 쎈놈을 앞에 세워야하는 케이스군요
어!
그거 priority만 비교해서 넘겨주면 되는거아님?
근데... ready list 다 순회해? 아님 그때그때?
만약 새로만든 놈이 더 쎄면 status ready로 만들어주고
스케줄 시켜? 그럼 중간에 인터럽트도 꺼야해?
thread_yield()가 다해줘......
저는 busy wating때 thread_yield()를 쓰지 말래서
(timer interrupt 부분에 while로 tick마다
thread_yield하는 극악무도한 함수였음)
걔가 나쁜놈인줄 알고 신뢰하지 않았는데 알고보니
나쁜 놈은 아니었더라고요...
id_t
thread_create (const char *name, int priority,
thread_func *function, void *aux) {
struct thread *t;
tid_t tid;
...
// 생성시 선점형 구현
struct thread *curr = thread_current();
if (curr->priority < t->priority){
thread_yield();
}
return tid;
}
알아주지 못해서 미안해...
set priority는 처음에는
현재 thread의 priority만 갱신해주는 순진한 놈인데
이제 눈치껏 yield해주는 부분을 넣으면 됩니다....
(그리고 이 자식과 이후에 지옥을 경험했음)
(근데 내가 만든 지옥임)
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
struct thread *curr = thread_current();
enum intr_level old_level = intr_disable();
// ready list를 세팅에 따라 priority 순으로 정렬
curr->priority = new_priority;
list_insert_ordered(&ready_list, &curr->elem, thread_priority_less, NULL);
do_schedule(THREAD_READY);
intr_set_level (old_level);
}상태를 ready로 바꿔주고 schedule하나
do_schedule하나 큰 상관은 없는데
제가 울면서 이거라도 상관있나 하고 고친 흔적입니다
벌써 change가 되니 스스로가 좀 천재같음
아 근데 여기서
list_insert_ordered(&ready_list, &curr->elem, thread_priority_less, NULL);에
thread_priority_less 라는 함수가 있거든요
이걸 만들면서 나...좀 .. 특별?을 느꼈음
list_insert_ordered함수 뭔가
애초에 순서순으로 넣어주다니 너무 완벽해보여서 의심되는데
나보고 비교하는 함수 자체를 두번째 인자로 넣어줘야해서
역시 완벽한 놈은 까다롭다는 걸 알았음
근데 대체 두번째 인자로 함수를 넣는데
어떤 형식으로 넣어야하는 것이냐
less 라는 걸 봤거든요
void
list_insert_ordered (struct list *list, struct list_elem *elem,
list_less_func *less, void *aux) {
struct list_elem *e;
ASSERT (list != NULL);
ASSERT (elem != NULL);
ASSERT (less != NULL);
for (e = list_begin (list); e != list_end (list); e = list_next (e))
if (less (elem, e, aux))
break;
return list_insert (e, elem);
}... 뭔소리야
less (elem, e, aux)
이거 뭐냐고
마지막에 aux라는 인자를 쓰기때문에
less 형은 마지막에 전부 이 인자(딱히 쓰지도않는)를 써야하는
불운한 운명에 걸립니다
대충 리스트 순회하면서 전부 정리해주나보지?
이해를 포기한 모습...
저는 이때 지피티에게 의탁했습니다
그리고 팀원에게 설명해줄때 이해했죠
동료학습...짱!
bool
thread_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, elem);
struct thread *thread_b = list_entry(b, struct thread, elem);
return thread_a->priority > thread_b->priority ;
}대충 만들어준거 보고 이해했습니다
아~ 꺼내와서 thread priority 비교해주나봄~!
맞는말임
그리고 이 함수와 지옥을 경험함...
(근데 내탓임)
그치만 애초에 지피티가 만들어준 함수를 쓰면서 특별함을 느낀건
alarm clock도 하고 여기까지 순탄하게 와서겠죠
그치만 이제부터..
semaphore가 기다린다...
priority sema
static thread_func priority_sema_thread;
static struct semaphore sema;
void
test_priority_sema (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
sema_init (&sema, 0);
thread_set_priority (PRI_MIN);
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 3) % 10 - 1;
char name[16];
snprintf (name, sizeof name, "priority %d", priority);
thread_create (name, priority, priority_sema_thread, NULL);
}
for (i = 0; i < 10; i++)
{
sema_up (&sema);
msg ("Back in main thread.");
}
}
static void
priority_sema_thread (void *aux UNUSED)
{
sema_down (&sema);
msg ("Thread %s woke up.", thread_name ());
}너무 간단하죠?
그래요 그냥 create해서
sema_down 시키고
sema_up으로 순차적으로 깨우는 테스트입니다
근데 내껀
아무도 안 깨.....
모두 back in main thread에 있어...
얘들아 우리 일어나기로 했잖아....
순간 전 main thread가 짱쎼서
못일어나는줄 알았어요
그래서 짱쎈데도 sema up 한순간
짱쎈 애를 제치고 일어나야하는건가? 했는데
main 쓰레드 priority 보세요
thread_set_priority (PRI_MIN);
PRI_MIN 뜻 : 0임, 즉 젤 약함
후.....
바보였다...
근데 이제보니 깨우는 애는 깨우는 애고
쟤는 걍 잠그는 얘에요
wakeup때 깨운 거지 잠글때 yield해준건 아니잖아
priority 비교 안해줬잖아
semaphore안에도 waiter라는 리스트 있잖아
....
근데 대충 ㅎㅎ; yield해준다고 알앗어;
했지만 이해는 못한 상태로 했습니다
어떻게 했냐면 팀원이 했길래 저도 함
와... 얼레벌레 레전드
sema_down (struct semaphore *sema) {
enum intr_level old_level = intr_disable();
ASSERT (sema != NULL);
ASSERT (!intr_context ());
while (sema->value == 0) {
list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_priority_less, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}ordered로 순서대로 넣고
꺼낼때도 sort해서 꺼내줘야지..^^
(불안감 상승으로 과도하게 처리하는 모습)
void
sema_up (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
old_level = intr_disable ();
sema->value++;
if (!list_empty (&sema->waiters)){
list_sort(&sema->waiters, thread_priority_less, NULL);
struct thread *next_thread = list_entry (list_pop_front (&sema->waiters),
struct thread, elem);
thread_unblock (next_thread);
if(next_thread->priority > thread_current()->priority){
thread_yield();
}
}
intr_set_level (old_level);
}
하나만 하면 안 되냐고요?
아마 될건데 해보시고 제보 부탁드립니다
그럼 이제
cond가 날 기다림
이제 슬슬 cond를 하고 나면 합법 아닌가 거기까지만해도
인류의 도리를 한게 아닌가 생각이 듦
priority-condvar
static thread_func priority_condvar_thread;
static struct lock lock;
static struct condition condition;
void
test_priority_condvar (void)
{
int i;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
lock_init (&lock);
cond_init (&condition);
thread_set_priority (PRI_MIN);
for (i = 0; i < 10; i++)
{
int priority = PRI_DEFAULT - (i + 7) % 10 - 1;
char name[16];
snprintf (name, sizeof name, "priority %d", priority);
thread_create (name, priority, priority_condvar_thread, NULL);
}
for (i = 0; i < 10; i++)
{
lock_acquire (&lock);
msg ("Signaling...");
cond_signal (&condition, &lock);
lock_release (&lock);
}
}
static void
priority_condvar_thread (void *aux UNUSED)
{
msg ("Thread %s starting.", thread_name ());
lock_acquire (&lock);
cond_wait (&condition, &lock);
msg ("Thread %s woke up.", thread_name ());
lock_release (&lock);
}
길지만 복잡하지않음
아직은 괜찮음
signaling하는데 한놈도 안깸
왜이렇게 잠꾸러기들이 많은거임
cond wait 함수좀 보세요
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_push_back (&cond->waiters, &waiter.elem);
list_insert_ordered(&cond->waiters, &waiter.elem, semaphore_priority_less,NULL);
lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);
}list_push_back이 원래 있던 놈이거든요
근데 이론적으로 말도안됨
sema 쓰고 있잖아요
난 sema 처리햇음
근데 왜 못일어남?
쓰고보니 어 그러네? 라고 지금 생각이 들정도로
헷갈리는 사안임
근데 보세요
list_insert_ordered(&cond->waiters, &waiter.elem, semaphore_priority_less,NULL);
여기 얘는 sema-Waiters 라는 리스트가 아니라
struct condition *cond 라는 걸 받아와서
struct semaphore_elem waiter; 라고
semaphore_elem이라는 걸 지 스스로 만들어서
sema_init (&waiter.semaphore, 0);로
waiter.semaphore라고 그 elem의 semaphore를
스스로 init하고 있음
뭐야?
결론은 같은 sema down을 쓰지
같은 sema를 쓰는게 아니라는 말입니다
그래서 cond라는 리스트 자체를 priority순으로
정렬해서 깨워줘야하는 거구요
해결법도 뭔가 단순해서 납득이 안됨
- wait를 ordered로 넣는다(이게 실효성없음이 밝혀지긴함 팀원분이)
- signal할때 sort해서 sema_up으로 꺼낸다^^
하...
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_push_back (&cond->waiters, &waiter.elem);
list_insert_ordered(&cond->waiters, &waiter.elem, semaphore_priority_less,NULL);
lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);
}
다른팀이 이거쉽대서
오진짜?? 했는데
저 악독한
semaphore_priority_less를 보세요
thread간 priority만 비교해서는 안됩니다
쟤는 semaphore elem을 인자로 받기때문에
그 안에 있는 어딘가의 thread의 priority를 비교해야한다고요
가녀린 초짜에겐 너무 어려워서
지피티에게 도와달라고했음
AI가 곧 세계를 지배할 거임
bool semaphore_priority_less(const struct list_elem *a,
const struct list_elem *b,
void *aux UNUSED) {
struct semaphore_elem *sem_a = list_entry(a, struct semaphore_elem, elem);
struct semaphore_elem *sem_b = list_entry(b, struct semaphore_elem, elem);
if (list_empty(&sem_a->semaphore.waiters)) {
return false; // a가 빈 리스트라면 b가 무조건 크다고 가정
}
if (list_empty(&sem_b->semaphore.waiters)) {
return true; // b가 빈 리스트라면 a가 무조건 작다고 가정
}
struct thread *thread_a = list_entry(list_front(&sem_a->semaphore.waiters),
struct thread, elem);
struct thread *thread_b = list_entry(list_front(&sem_b->semaphore.waiters),
struct thread, elem);
return thread_a->priority > thread_b->priority;
}
list_elem으로 받아서 semaphoer_elem으로 바꾸고
거기서 semaphore 안의 waters 리스트 안에있는
맨 앞의 thread를 비교하는...악독한 모습
심지어 빈 리스트 예외처리도 해줘야함
여기까지 했는데
이제 donation하래
강의를 봐서 대충 알거같은데
동시에 thread에 추가하는 구조체가 왕많아서
대체 어쩌라는건지... 싶었음
priority-donate-one
길어
언제 donate도 하고 sema도 고치고
mlfqs도 할 거야 난 자고싶어
static thread_func acquire1_thread_func;
static thread_func acquire2_thread_func;
void
test_priority_donate_one (void)
{
struct lock lock;
/* This test does not work with the MLFQS. */
ASSERT (!thread_mlfqs);
/* Make sure our priority is the default. */
ASSERT (thread_get_priority () == PRI_DEFAULT);
lock_init (&lock);
lock_acquire (&lock);
thread_create ("acquire1", PRI_DEFAULT + 1, acquire1_thread_func, &lock);
msg ("This thread should have priority %d. Actual priority: %d.",
PRI_DEFAULT + 1, thread_get_priority ());
thread_create ("acquire2", PRI_DEFAULT + 2, acquire2_thread_func, &lock);
msg ("This thread should have priority %d. Actual priority: %d.",
PRI_DEFAULT + 2, thread_get_priority ());
lock_release (&lock);
msg ("acquire2, acquire1 must already have finished, in that order.");
msg ("This should be the last line before finishing this test.");
}
static void
acquire1_thread_func (void *lock_)
{
struct lock *lock = lock_;
lock_acquire (lock);
msg ("acquire1: got the lock");
lock_release (lock);
msg ("acquire1: done");
}
static void
acquire2_thread_func (void *lock_)
{
struct lock *lock = lock_;
lock_acquire (lock);
msg ("acquire2: got the lock");
lock_release (lock);
msg ("acquire2: done");
}
정말 길죠
요약하자면
얘네들이 순서대로 lock을 얻어야함... priority가 존중되어야겠죠??
근데 저는 처음에
아무도 얻지못함
싸움은 무엇도 해결하지 못하는 결말이 나옴
(단순히 말하자면 acquire: 부분 msg자체가 안뜸)
이젠 lock까지 건드리는구나
게임이었으면 전 중수쯤 되었겠죠
그래서...
전 사실 이해자체를 처음부터 잘못하고 있었음
그때그때마다 list에
현재 스레드의 donations라는 리스트를
구조체로 추가해주거든요
//Donation용
struct lock *wait_on_lock; // 현재 기다리는 lock 포인터
struct list donation; // 현재 이 스레드가 받는 기부리스트가 있을 경우.
struct list_elem d_elem;
아니 근데
wait_on_lock... 이해했어
donation... 이해했어
근데 리스트를
elem으로 잇는다는 건 이해했단 말임
그래서 donation이라는 리스트 자체를
한 스레드에 넣는다는 것자체가
엥?
싶었음
너무 뚱뚱해지지않음?
그래서 d_elem만 넣음
donaiton_list라는 list를 thread_init시
그 모든 list 갱신 시점에 init하고
나 그때그떄 넣어서
뭐...
lock이라는 놈은...
뒤엣놈이 바로 걸리니깐...
스레드를 그때그때 넣어주면 되겠다...
그것들을 이으면..(되겠냐?)
그리고 여기서
초기 priority를 기억해두라는 말을 함
뭐야 어케 기억하라고
간단히 하면 그냥 구조체에 저장하면 되지만
구조체 넣을수록 뚱뚱해지잖아? 살 많으면 건강에 안 좋음
그래서 그때그때 내 유지를 이을 애와
priority를 바꿔줬어....
그리고 lock 제거할때 원위치하면 되겠지 했어...
이런 바보 흔치않습니다
근데 아무리봐도
그러면 막 뭐 a b c 로 이어지면
a의 priority는 너무 먼 여행을 한단말임
손상당할거같음
다른 애들 priority도 꼬임
답지 훔쳐봄
음~ 그냥 구조체에 저장함
음~ 교체 때려침
d_elem만 하면
lock관계가 망한다는 것을 이때 깨달아서
donations는 만들어주고 거기에 넣어주는 방식
(이때도 donaitions 어디에 init함?
엥? wait_on_lock은 어디에 inint함?
하는 쌩쇼좀 했음.
전자의 답은 thread마다 있으니 thread 안 이고
후자는 lock의 포인터지 lock이 아니라서 init할 필요없음)
(이런 바보도 pintOS 과제를 하니까 당신도 파이팅)
그래서 전반적인 구조를 파악했음!!!
donations를 순환하며 donate를 갱신하면 되는구나!!
하고 lock할때마다 donations에 넣어주고
순서대로 넣고 순서대로 꺼내면 되겟당^^ 했는데 안됨.
왜지?
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
struct thread *curr = thread_current ();
if(!thread_mlfqs){
// priority 순으로 donation 리스트 넣는법....
if(lock->holder){
curr->wait_on_lock = lock; // lock을 필요로 하는 thread의 address 저장
list_insert_ordered(&curr->wait_on_lock->holder->donation, &curr->d_elem, donation_priority_less,NULL); // donation 리스트에 넣기.
donate_priority();
}
}
sema_down (&lock->semaphore);
lock->holder = thread_current ();
curr->wait_on_lock = NULL;
}
donate_priority();가 보이시나요?
그렇다면 당신은 행운의... 아무튼
그래...
순서대로 넣기만했지
donate하는 과정이 없었고
왜 그런 과정이 있어야하는지 상상도 못했음....
하지만 생각해보면 donation이라는 개념 자체가 이게 핵심인거같음...
답지보고 아 ㅋㅋ donate해야하는구나;
그럼 함수 제목만 보고 만들어봐야지;
donate 메커니즘자체를
생각치 못해서 실패!
애초에 뭐하는거임? 이랬음
결국 답지봄
void
donate_priority(void)
{
struct thread *curr = thread_current();
for(int depth = 0; depth < 8;depth++){
if(curr->wait_on_lock){
struct thread *t = curr->wait_on_lock->holder;
t->priority = curr->priority;
curr = t;
}
}
}.......
depth라는걸 쓴대
근데 그걸 어케쓰라는거임
타고 들어가는것도 아니고
근데 걍 이거 보세요
depth만큼 반복..그러니까 반복하는 변수일뿐이지
얘는 그냥 자기 lock holder를 타고 들어가기만 합니다
이거 max가 8이잖아요
왜 8인지 검색했는데 안나옴
당연함
git book이 max를 지정해줌....
전 다 봤는데 왜 못봤을까요?
심지어 다른 분에게 들어서 알았습니다
주워듣기 실력 쩐다
이걸 하고 나서
뭔가 안되는걸 발견하고 노려봤는데
priority가 lock 제거되고나서
원위치 되어야하는데
그 과정이 없다는걸 깨닫고
(일일이 순서를 test 케이스 보고 그려봐서
깨달은 거라 개감동받고
뭣보다 여기서 날것으로 짜고 그대로 되어서
스스로가 천재같았지만
PintOS의 가장 천재부분은 여기밖에없음)
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
struct list_elem *e;
struct thread *holde = lock->holder;
// donation list를 순회하며 해당하는 lock을 가진 thread list에서 제거
if (!list_empty(&holde->donation)){
for(e = list_begin(&holde->donation); e != list_end(&holde->donation);)
{
if(list_entry(e, struct thread, d_elem)->wait_on_lock == lock){
list_entry(e, struct thread, d_elem)->wait_on_lock = NULL; // wait_on_lock 초기화
// 해당하는 스레드의 priority 초기화
donate_set_priority(list_entry(e, struct thread, d_elem));
list_remove(e); // d_elem 제거
}
else{
e = list_next(e);
}
}
}
// Donation 용 추가 (여기까지)
}
lock->holder = NULL;
// 현재 스레드의 priority를 init 값으로 초기화
donate_set_priority(thread_current());
sema_up (&lock->semaphore);
}그래요 저 donate_set_priority
제법 반짝이지 않나요
아님 말고
근데 이게 백준에 나왔으면
새싹 문제에 있었을 거임
void
donate_set_priority(struct thread *new){
enum intr_level old_level = intr_disable();
new->priority = new->init_pri;
struct list_elem *e;
int big_pri = -1;
//donation에 따라 priority set.
if(!list_empty(&new->donation)){
for(e = list_front(&new->donation); e != list_end(&new->donation);)
{
if(list_entry(e, struct thread, d_elem)->priority > big_pri){
big_pri = list_entry(e, struct thread, d_elem)->priority;
}
else{
e = list_next(e);
}
}
}
if(big_pri != -1){
new->priority = big_pri;
}
intr_set_level (old_level);
}나중에 팀원분이 이거 왜 순회하냐고 물어봤거든요
그때 왜 바꿔줘야했냐고 물어봤는데
어쩐지 대답 못했거든요
그게 뭔가 이미 어디선가 priority를
그냥 저렇게 순회하지 말고
init_priority라고 초기 값을
넣어주면 되는 거 아니냐고
흠...
듣고보니 그런거같아...
근데 아닙니다
왜냐하면 테스트 케이스가 통과 안시켜줌
예외 케이스 찾으면 제보부탁드립니다
(근데 아마 donations에서 누가 영향주면 영향이 있는 뭐 그런거겠죠)
이쯤 하면
당신의 priority-sema와 priority-condvar가 죽습니다...
대체 왜?
why?
sema는 안 건드렸는데?
이때부터 나와 less 함수의 지옥이 시작됨
정답은 thread_set_priority 함수에서
priority를 초기화시켜줬잖아요
근데 생각해보면 지금 priority donation 여부에따라
왕 유동적임 초기화된거 날아감
사실 set_priority는
thread 자체의 priority를 바꿔주는 함수임
그래서 init_priority를 바꿔줘야함
bool
thread_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, elem);
struct thread *thread_b = list_entry(b, struct thread, elem);
if(thread_mlfqs){
return thread_a->priority > thread_b->priority;
}
return thread_a->init_pri > thread_b->init_pri;
}이때부터 시작되는 지옥...
여러분은 함수명을 알차게 지으세요
나중에 이거 priority 바꿔주는 함수인줄 알고 씀...
대충 donate에 따라 변하는건지
init이 바뀌는 건지 부분을 잘 찾아서
그때그때 해결하면
이젠 하산해도 될거같고....
Advanced Scheduler
나 12시까지 근무한적이없었는데
지옥
..
그냥 퇴근하고 아침에 쓰겠습니다
bye
...
점심입니다
시간이 없었습니다 아침에 발표조율하느라고
그럼 가봅시다
...
Advanced schedluer에
그 뭐냐 다중 멀티 레벨 피드백 큐라면서
얘가 알려주는 건 큐 여러개가 아니고
그냥 공식 알려줌. 4.4BSD 대체 뭔지 찾아봤는데
그저 이러한 스케줄 방법을 쓰는 OS 버전 이름임.
난 뭐 nice recent_cpu 등을 모아서
뭐 F4같은 닉네임인줄 알았는데 아니었음.
이제보니 공식화해서 실제로
멀티 레벨 피드백 큐를 쓰는 것같은 효과를 낸다고...
그래도 큐 안쓰고 공식만 쓰죠? 짱이죠?
malloc의 망령에서 벗어났죠?
그래서 쫄았던 것도
git book 내용이 길다 = 내가 다알려줄거임
이라는 뜻이었음
실제로 일정 tick마다 공식에 따라
priority를 갱신해주는 것뿐임.
이건 강의도 많이 참고하지 않았음.
어차피 git book에 다 나와있음.
근데 오히려 불안했음.
다 나와있다 = 오 금방 끝날 거같은데? == 지옥의 디버깅
심지어 여기는 공식을 좀더 정밀하게 계산하기 위해
정수를 실수형으로 바꾸었다가 실수식 계산을 해서 씀.
이 개념 자체가 대체 뭔소리인지 좀 째려봤는데
뭔 소리인지 알게되었을때 스스로가 좀 뿌듯했음.
(물론 지피티에게 물어봤음 자아가없음)
근데 공식 계산이라서
오히려 실수형이 뭐 정수형으로 숫자 몇으로 나왔다...
잘못 계산한거다... 라는 걸
알아볼 자신이 없었음
다행히 에러가 내가 알아보게 나옴
((((((음수 나옴))))))
그래..
아무튼 음수가 아니라는 건 알겠어......
옆 팀원분이 알려주셨는데 오버플로우..
오히려 왕 큰값이 나와서 음수로 나오는 거같다고..
(오버헤드라고 하는건가? 아무튼.)
아니 정수를 실수로 바꿔서 실수식 계산을 하면 음수뜨고
정수를 실수로 안 바꾸고 실수식 계산 해야 양수가 뜨는거임
비합리적임
뭔가 다른 부분이 잘못되어서 이게 뻑난거임
근데 아무리 봐도 뭐가 잘못된건지 모르겠음
그래서 블로그 코드 21415124개 봤음
나랑....
똑같음
똑같음
똑같음
뭐 매크로명까지 똑같진 않았지만
그런것까지 바꾸고 싶지 않았음 프로그래머의 자존심은
정말 비효율적이긴 한데 아무튼
그래서 그나마 좀 납득가능한..
예를 들어
59/60 x(뭐) + (1/60) x (뭐) 라고 할때
이거 사실 (59x(뭐)+1x(뭐))%60 이라고 해도 되고
사실 나누는 횟수 자체가 적을 수록 오버헤드가 적긴할거아님
이걸로 바꾸니까 실제로 됐고
void
calculating_load_avg(void){
int size= list_size(&ready_list);;
if(thread_current() != idle_thread){
size +=1;
}
load_avg = DIVI_X_N(ADD_X_N(MULTI_X_N(load_avg,59),size),60);
}
(여기서 list_size가 반환하는게 타입이 안 맞나 노려봄
근데 애초에 절케 작은 정수가 큰일이 나겠습니까
그냥 절실한거지 내가)
아 이런걸해야한다고?? 까다롭네 했는데
59/60 x(뭐) + (1/60) x (뭐) 처럼 진행한
팀원분 코드는 됨......
나는 알아내길 포기했음
나와 그분은 피가 다른거임
내 피에는... 컴퓨터의 피가...흐르지않는거임...
그래서 이 부분이 그게 어려웠음...
그........
디버깅 개어려워
왜 안돼
계산이 틀렸대
공식대로 했는데?
응 네 공식은 안됨
......
아무튼 그렇게 load-1 케이스를 통과하자
load-60 케이스가 안됨
- 매 초마다 priority 계산하는 함수에서 외부 인터럽트가 들어온다고 콜스택 뜸
- 60초간 잠들었다가 그간 2초마다 출력해야하는걸 한번에 출력해서 0초부터 60초까지 load_avg값이 똑같이 나옴
아니 내가
어디에서 들어오는 인터럽트를 어떻게 아냐고
무슨 인터럽트인지 어떻게 아냐고..........!
그래서 울고싶었음
추적을 어케하라는거임
인터럽트 핸들러가 인터럽트가 들어와서 잡긴했겠죠
그게 누군데요...
콜스택 옆에 discriminator 3 인가
뭐 식별자 몇번인지 알려주는데
그거 설명 어디에 있는데.......
....
그래서 모든 부분을 수정했는데
load-60에서 60초간 잠드는건 도저히 낫지를 않는거임
아니 분명 되어야옳음
왜냐하면 모든 블로그 코드를 참고했으니까
(너무 뭐라하지마세요 저도 골자는 제가 다 짰었어요)
(근데 디버깅이 안되잖아요)
(이게 만약 독자적인 저희팀 코드에서 앞부분 문제였다 하면 인생이 너무 아득해졌다고요 저는)
....
하지만 그때는 그 주의 마지막부분
인간도 만나고 싶지 않아서
동료에게 물어보지 않고 디버깅했음
혼자 디버깅하는데
챗 지피티도 모르고
스택 오버플로우도 모를때 해결법
printf를 찍는다
...
왜 여태 안찍었나요?
아니 찍으면 안되는줄알고
진짜 안 되는 부분이 있긴함
인터럽 끄고 키는 부분 사이나 아무튼
그럴때는 출력이 불가하긴한데
테스트 케이스 사이나
적당히 되는 함수들이 존재함
그래서 찍었음
1초마다 갱신됨
게다가 1초마다 load_avg도 잘 갱신되고있음
갑자기 정신승리하고싶어졌음
얘가 출력을 안해주는 거지 저는 계산 잘하고있는데용 ㅠㅠ
아무것도 해결되진 않았지만 마음은 좀 나아짐
그래서 thread별 priority도 찍어봄
헉!!
priority 음수나옴^^
나는 음수와 인연이 깊나봄
아련해짐
0~63 사이로 잘라줘봤자 뭐가 나아질까요
그냥 이제 음수는 0나오고 개 큰 수는 63뜨겠죠
아무튼 처리는 해줬습니다
이때 실제 쓰레드가 어디에 빠져서 갇혀있는지 알게되니
해결되진 않아도 마음을 조금 따뜻해졌음
(이거 이대로 해결 안되면 그대로 홧병됨)
(그날 저녁 먹으면서 홧병느꼈음)
근데 이상했단말야
앞에선 set_nice 부분에서 23으로 갱신되었는데
왜 자기 혼자 63이라는 독보적인 수를 갖냐 이말입니다
결말 : priority 갱신시 현재 쓰레드 recent_cpu를 갖고 오고있었다^^ 받은 쓰레드별로 갱신하려고 쓰레드 인자도 받아왔으면서^^
휴 정말 바보같앗당..
이제 되겠지!?!?!?!!?
안 됨
static int64_t start_time;
static void load_thread (void *aux);
#define THREAD_CNT 60
void
test_mlfqs_load_60 (void)
{
int i;
ASSERT (thread_mlfqs);
// printf("main priority : %d\n", thread_current()->priority);
start_time = timer_ticks ();
msg ("Starting %d niced load threads...", THREAD_CNT);
for (i = 0; i < THREAD_CNT; i++)
{
char name[16];
snprintf(name, sizeof name, "load %d", i);
thread_create (name, PRI_DEFAULT, load_thread, NULL);
}
msg ("Starting threads took %d seconds.",
timer_elapsed (start_time) / TIMER_FREQ);
// printf("main priority_2 : %d\n", thread_current()->priority);
for (i = 0; i < 90; i++)
{
int64_t sleep_until = start_time + TIMER_FREQ * (2 * i + 10);
int load_avg;
// printf("go!\n");
// printf("main priority_3 : %d\n", thread_current()->priority);
timer_sleep (sleep_until - timer_ticks ());
// printf("good!\n");
load_avg = thread_get_load_avg ();
msg ("After %d seconds, load average=%d.%02d.",
i * 2, load_avg / 100, load_avg % 100);
}
}
static void
load_thread (void *aux UNUSED)
{
int64_t sleep_time = 10 * TIMER_FREQ;
int64_t spin_time = sleep_time + 60 * TIMER_FREQ;
int64_t exit_time = spin_time + 60 * TIMER_FREQ;
thread_set_nice (20);
// printf("%s 이는 priority가 %d구요\n", thread_current()->name,thread_current()->priority);
// printf("%d라는 recent_cpu를 가지고 있답니다... \n", thread_current()->recent_cpu);
timer_sleep (sleep_time - timer_elapsed (start_time));
while (timer_elapsed (start_time) < spin_time){
// printf("당신은 함정에 걸렸습니다...\n");
// printf("%s 인 제가 범인이고 저의 priority는 %d 랍니다...\n", thread_current()->name, thread_current()->priority);
continue;}
timer_sleep (exit_time - timer_elapsed (start_time));
}
눈물의 printf 흔적
while 문에 빠지면 함정에 걸렸습니다가
무한히 나오거든요
마치 저의 심정같았습니다
인생을 증오했습니다
그리고 체념했죠
그래......
비록 이 케이스가 통과가 안되니
다른 케이스 디버깅도 못하고 있지만
인간은 패배할
수없어
그렇지만 어느덧 토요일 저녁
오늘 슬슬 마무리해야 내일 발표 준비도 하고 총정리도 하는 시간입니다 다른 말로 망했다고 하죠
그래서 다른 분에게..
다른 팀에게 물어보고...!!!
안되면..!!!
때려치자..!!!!!
알게되었습니다
모두 다들 엥 다넣었는데?? 하다가
보니까
bool
thread_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, elem);
struct thread *thread_b = list_entry(b, struct thread, elem);
if(thread_mlfqs){
return thread_a->priority > thread_b->priority;
}
return thread_a->init_pri > thread_b->init_pri;
}
bool
thread_donation_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, elem);
struct thread *thread_b = list_entry(b, struct thread, elem);
return thread_a->priority > thread_b->priority;
}
bool
donation_priority_less(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
struct thread *thread_a = list_entry(a, struct thread, d_elem);
struct thread *thread_b = list_entry(b, struct thread, d_elem);
return thread_a->priority > thread_b->priority;
}
자 차이점이 보이십니까?
첫번째는 init을 비교.
두번쨰는 priority를 비교.
세번째는 priority를 비교하는대신 d_elem을 써서 쓰레드 가져옴.
첫번째 이름을 보세요
thread_priority_less
...
thread_priority를 비교하는거같지않습니까?
thread_donation_priority_less...
thread_priority를 비교할때
donation용 같지 않습니까?
mlfqs 특징 : donation 버전 배제해야함
전 다 pass 하길래
휴^^ 처리 잘했다 안심~ 했는데
여기서...
이런.........
........
엄청나게 긴 코드는 이런일들이 있는거겠죠?
이래서 가독성이라는게....
필요한....
거겠죠.........?
아무튼 계산해서 갱신하는건 priority지
init_priority가 아니기때문에 안 되던 문제였습니다
그래서 모든 눈물도 결국 환희가 되어 끝낼수있었지만
정말 아찔한 디버깅이었음은 부정할수없습니다
이후 recent 케이스가 통과가 안되었었는데
매크로에서 실수 계산시
int64_t로 캐스팅해줘야하는데
매크로 손보다 깜박 지웠었지 뭐에요^^
#define f (1<<14)
#define f_2 (1<<13)
#define CONVERT_N_X(n) (int)n*f
#define ADD_X_Y(x,y) ((x) + (y))
#define SUB_X_Y(x,y) ((x)-(y))
#define ADD_X_N(x,n) ((x)+(n)*f)
#define SUB_X_N(x,n) ((x)-(n)*f)
#define SUB_N_X(n,x) ((n)*f-(x))
#define MULTI_X_Y(x,y) (int)(((int64_t)(x))*(y)/f)
#define MULTI_X_N(x,n) ((x)*n)
#define DIVI_X_Y(x,y) (int)(((int64_t)(x))*f/y)
#define DIVI_X_N(x,n) ((x)/n) ....
그거 고치니 전부 통과됐어..
대체 얼마나 고쳤으면 이걸로 전부 통과가 되는걸까요?
저는 구현을 한거겠죠? 그쵸?
끝났으면 됐어...
별개로 고려할만한 이슈는 all_list로
thread 전부 관리하기 위해 list init,
list insert, list remove 시점을 잘 써야한다는것...
...
헛짓거리 : set_nice에서 yield를 안하고있는거아님????
헛짓거리2 : unblock만 하는거지 ready list에만 넣고 schedule은 안하는데 yield는 안하고 있는거아님...???
아니 나름 타당한 헛짓거리임
당연히 priority는 바뀌는데 넘어가지않으면
yield 문제겠죠 그치만
리스트에서 밀려서 뒤에 있느라 못나와 그런것일거다<라는 추정에
리스트에..
밀려...?
왜...?
(정답:리스트 정돈안되고있어서^^)
후...
여러분은 페어프로그래밍하세요
팀원은 저의바보같은 짓을 발견해줄지도 모르잖아요
이제 Project 2군요
집가고싶다
끝
화이트 보드에 쓴 이유는 별 다른게 아니고
필기한 아이패드를 참고해서 총정리해야하는데
아이패드 화면이 좁음
(분할해서 여태 내용 총정리를 아이패드 반절화면에 집어넣기 쉽지않음)
