Project 1. Alaram and Priority Scheduleling
Thread Local storage
스택은 위에서부터 쌓이지만 magic number를 만나면 stack over flow가 발생함
따라서 우리가 Thread 구조체에 Member 변수를 추가할때
magic number 밑에 넣으면 안됨
만일 magic number 밑에 넣으면
스택이 자라면서 Member 변수를 덮어쓰게 됨
4 kB +---------------------------------+ | kernel stack | | | | | | | | V | | grows downward | | | | | | | | | | | | | | | | | +---------------------------------+ | magic | | intr_frame | | : | | : | | name | | status | 0 kB +---------------------------------+
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
};1. Alaram
related files
1. timer.c
2. thread.h
목적
현재 code는 thread가 block 되지 않고 ready list에서 계속 check를 당하는 busy waiting 상태에 빠져있음
busy waiting으로 동작하게 되면 CPU를 너무 많이 잡아먹게됨 (CPU가 쉬는 시간이 없음 실제 thread가 running할 시간이 아닌데 ready에 있는애가 언제 일어날까 계속 확인함)
이를 방지하기 위해서 우리는 running 하던 애를 ready로 돌려보내는게 아닌 block으로 돌려보 것임
block으로 가게되면 thread가 일어나야될 시각에만 신호가 가게됨
Busy waiting
Thread : 나 2시까지 잘게 (현재 1시)
나 : 일어났니? 아니네 잘자 (1시 1분)
나 : 일어났니? 아니네 잘자 (1시 2분)
나 : 일어났니? 아니네 잘자 (1시 3분)
나 : 일어났니? 아니네 잘자 (1시 4분)
나 : 일어났니? 아니네 잘자 (1시 5분)
...
나 : 일어났니? 이제 일하자 (2시)
이 상태인걸 우리는
Thread : 나 2시까지 잘게 (현재 1시)
나 : 2시야 일어나 일하자 (2시)
로 만들어 주는 것이다
해당 블로그는 중간중간 작성한 것이 아니라서 코드는 prj 1의 내용을 다 담고있음
- 각 내용은 주석에 있음
timer.c
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks (); //현재 ticks을 받아와 start에 저장
ASSERT (intr_get_level () == INTR_ON);
thread_current()->tick_s = start + ticks; // 현재 thread의 tick_s에 OS시작부터 자야할 시간까지를 포함한 ticks를 저장
while (timer_elapsed (start) < ticks){
sema_sleep(&sema); // 현재 thread를 semaphore에 넣고 재운다
}
}void
sema_sleep(struct semaphore *sema){
enum intr_level old_level; // interrupt를 막기위한 변수
old_level = intr_disable (); // interrupt 막기 시작
while (sema->value == 0) { // value가 0이라면 이미 다른 누군가가 접근해있는 상태이니
list_push_back (&sema->waiters, &thread_current()->elem); // 대기 리스트에 넣고
thread_block (); // 현재 thread의 상태를 block으로 전환
}
sema->value--; // while문에 걸렸거나 혹은 탈출했다면 해당 프로세스에 진입한거니 진입 checke
intr_set_level (old_level); // interrupt를 이전 상태로 돌림
}void
sema_awake(struct semaphore *sema, int64_t ticks){ // sema가 깨는 타이밍을 잡는 함수
struct thread *temp; // 임시 thread를 선언
enum intr_level old_level;
size_t waiter_size = list_size(&sema->waiters);
for (int i=0 ; i<waiter_size ; i++) { // sema->watier 가 비어있지 않다면 즉, 대기하는 애들이 있다면
temp = list_entry (list_pop_front (&sema->waiters), struct thread, elem); // 제일 앞에 있는 애를 pop하고 임시 thread로 확장
if (temp->tick_s <= ticks){ // 임시 thread의 tick_s이 time_interrupt의 ticks(OS ticks)보다 작다면 이제 깨어나야하니깐
thread_unblock(temp); // 깨워주고
sema->value++; // 프로세스에서 탈출하니깐 value++ 해줌
}
else
list_push_back(&sema->waiters, &temp->elem); // ticks의 시간이 안되었다면 다시 list 제일 뒤에 넣어줌
}
}/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
sema_awake(&sema, ticks); // timer_interrupt는 tick이 절대적으로 흐르니깐 해당 tick을 이용하여 sema를 깨운다
}우리는 Thread 안에 tick을 저장하여 Thread의 tick을 확인해서 깨울것임 - int64_t tick_s; -- int64_t로 type을 선언한 이유는 기존에 사용하고 던 tick type과 자료형을 맞추기 위해서
thread.h
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
int64_t tick_s; /* tick info for time check*/
int init_pri;
struct lock *waitLock;
struct list dona;
struct list_elem dona_elem;
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
};2. Priority
related files
1. thread.c
2. thread.h
3. sync.c
4. sync.h
목적
우리의 Thread는 우선순위가 있다
모든 일을 들어온 시간에 맞춰서 처리할 순 없지 않은가
급한 일을 먼저 처리해줘야한다
그러기 위해서 우리는 우선순위를 부여할 것이고, 우선순위 역전현상, 등 도 같이 해결을 해야할 것이다.
우선순위 역전현상 : 상대적으로 우선순위가 가장 높은 프로세스인 'A'가 마치 우선순위가 가장 낮은 프로세스처럼 실행이 되는 현상
출처: 도리의 디지털라이프
나보다 우선순위가 낮은 Thread가 lock을 갖고 있다면 나의 우선순위를 낮은 애에게 기부해서 우선순위를 올려준후 작업이 끝나면 lock을 release하게 한다.
그 이후 내가 lock을 취득한다
thread.c
/*
test_max_priority
redy list가 비어있지 않을때 current_thred의 priority와
ready의 첫번째 thread의 priority를 비교해서
ready_list의 thread priority가 크다면
--> thread_yield를 실행한다
(현재 thread는 ready로 ready의 첫번째를 running으로 옮김)
ready_list는 항상 우선순위가 높은 순서로 정렬됨
*/
void
test_max_priority (void) {
if (!list_empty (&ready_list))
if (list_entry (list_front (&ready_list), struct thread, elem)->priority >
thread_current ()->priority)
thread_yield ();
}/*
현재 list에 들어올 input 의 priority와 list에
기존에 들어있던 element의 priority를 비교하였을 때
input 이 크면 True를 반환하고
input 이 작으면 False를 반환한다
--> 우선순위 정렬을 위해서 사용함
해당 True 를 들고 나가면 prev elem의 앞에 list_insert가 동작함
*/
bool
compare_priority (const struct list_elem *input, const struct list_elem *prev,
void *aux UNUSED) {
return list_entry (input, struct thread, elem)->priority >
list_entry (prev, struct thread, elem)->priority;
}
/*
thread_yield는 현재 돌고 있는 thread를 ready_list로 보내고
ready_list에 있는 첫번째를 꺼내서 launch를 합니다
*/
void
thread_yield (void) {
struct thread *curr = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable ();
if (curr != idle_thread) {
list_insert_ordered (&ready_list, &curr->elem, compare_priority, NULL);
// ready list에 thread를 넣을때 우선 순위가 높은 순서로 맞춰서 넣는다
}
do_schedule (THREAD_READY);
intr_set_level (old_level);
}/*
Thread가 block에서 깨어나 ready list로 들어갑니다.
block에서 ready_list로 들어갈 때 우선 순위에 맞춰서 들어간다
*/
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_insert_ordered (&ready_list, &t->elem, compare_priority, NULL);
t->status = THREAD_READY;
intr_set_level (old_level);
}/*
현재 Thread의 init_pri를 새로운 pri를 받음
그후 refresh_pri를 실행시켜
thread가 받은 donation의 우선순위와 비교하여
높은 둘중 높은 우선순위를 사용함
이후 dona_priority() 함수를 사용하여
해당 Thread와 연결된 thread들에게 현재 thread의 priority를 전달해줌
그리고 test_max_priority를 사용하여
스케쥴링을 함
*/
void
thread_set_priority (int new_priority) {
thread_current()->init_pri=new_priority;
refresh_pri ();
dona_priority(); // 여기는 없어도 동작 함
/*
이유 : refresh_pri();를 통해서 thread_current()는 이미 최대의 priority를 갖게됨
하지만 이미 lock으로 연결된 애들은 thread_curren()보다 낮음 따라서 얘가 더 높은 값은 갖는것은 큰 문제가 되지 않음
*/
test_max_priority ();
}/*
현재 Thread의 waitLock 이 NULL이면 돌면 안됨
연결된게 없으니깐
NULL이 아니면
순회하면서 priority를 추가
*/
void
dona_priority (void) {
struct thread *cur = thread_current ();
for (int i = 0; i < 8; i++) {
if (cur->waitLock ==NULL)
break;
struct thread *hold = cur->waitLock->holder;
hold->priority = cur->priority;
cur = hold;
}
}/*
현재 Thread에서
Donation안에 있는 list를 순회함
이때 Donation list 안에 있는 temp thread가 가진 waitLock이
remove 로 요청된 lock과 동일하면
donation list에서 해당 dona_elem을 지움
*/
void
remove_lock (struct lock *lock) {
struct thread *cur = thread_current ();
struct thread *temp;
struct list_elem *temp_e;
for (temp_e = list_begin (&cur->dona); list_end (&cur->dona) != temp_e;
temp_e = list_next (temp_e)) {
temp = list_entry (temp_e, struct thread, dona_elem);
if (temp->waitLock == lock)
list_remove (&temp->dona_elem);
}
}/*
현재 Thread priority에 해당 Thread의 초기 priority를 넣어줌
현재 Thread의 우선순위와 현재 Thread가 받은 dona 의 우선순위를 비교하여
더 큰 우선 순위를 적용한다
*/
void
refresh_pri (void) {
struct thread *cur = thread_current ();
int temp;
cur->priority = cur->init_pri;
if (!list_empty (&cur->dona))
list_sort (&cur->dona, compare_priority, NULL);
if (!list_empty (&cur->dona)) {
temp = list_entry (list_begin (&cur->dona), struct thread, dona_elem)->priority;
if (cur->priority < temp)
cur->priority = temp;
}
}
thread.h
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
int64_t tick_s; /* Thread는 자신이 일어날 tick을 가짐*/
int init_pri; /* Thread의 초기 pri을 가짐 */
struct lock *waitLock; /* Thread가 획득해야 하는 lock을 저장 */
struct list dona; /* Thread가 donation 받은 우선순위 저장 */
struct list_elem dona_elem;/* Thread donation에 저장하기 위한 donation element 저장 */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
};
void test_max_priority (void);
bool compare_priority (const struct list_elem *input,
const struct list_elem *prev, void *aux UNUSED);
/* Implement for Priority Donation */
void dona_priority (void);
void remove_lock (struct lock *lock);
void refresh_pri (void);synch.h
/* One semaphore in a list. */
/* 기존에 synch.c 중간에 위치해있던 구조를 header로 옮김
- 중간에 위치함으로써 synch.c 파일에 함수를 넣어서 사용할 때
- 문제가 될 수있음 따라서 구조체를 이동
*/
struct semaphore_elem {
struct list_elem elem; /* List element. */
struct semaphore semaphore; /* This semaphore. */
};
bool compare_sema_priority (const struct list_elem *,const struct list_elem *, void *);synch.c
/*
lock을 요청한다
lock을 요청한다는 것은 내가 일을 할 것이라는 말인데
내가 일을 할 수 있는 공간이 있는지도 확인하게 된다
내가 일을 할 수 있는 공간이 있다면 바로 일을 하면되고
그게 아니면 sema_down을 통해서 thread block으로 빠져 대기를 하게 된다
unblock 신호를 받고 나오게 되면 cur->waitLock = NULL로
해당 thread와 이어진 lock->holder를 현재 Thread로 변경해줌
--> Nested donation 본다면 좀 더 이해하기 쉬움
최초의 접근을 통해 lock은 lock->holder에 자기 자신이 들어가게됨
*/
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
struct thread *cur = thread_current ();
if (lock->holder) {
cur->waitLock = lock;
list_insert_ordered (&lock->holder->dona, &cur->dona_elem, compare_priority,
NULL);
dona_priority ();
}
sema_down (&lock->semaphore);
cur->waitLock = NULL;
lock->holder = cur;
}/*
Thread L의 할일이 끝났다면 lock을 이제 release 합니다
lock을 릴리즈할때 remove_lock을 통해서 donation list에서 release 되는 lock과
동일한 lock을 찾아 지워줌 --> donation list에서 release된 lock의 정보를 지운다
그 후 refresh_pri()를 통해서 현재 thread의 초기값 혹은 현재 thread가 받은 priority 중
가장 큰 값을 적용해주고
현재 thread의 lock->holder를 NULL로 놔준다
이후 sema_up을 진행한다
*/
void
lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
remove_lock (lock);
refresh_pri ();
lock->holder = NULL;
sema_up (&lock->semaphore);
}/*
sema up의 신호를 받고 thread를 block에서 꺼냅니다.
우리는 waiters에 우선순위 순서로 너놓았기 때문에
waiters의 제일 앞에서 pop해서 thread_unblock을 실행합니다.
그리고 sema의 값을 1을 올려주고
ready list 첫번째의 thread -> priority와
current thread의 priority 비교와
thread_yield를 해주는
test_max_priority를 실행해줌
*/
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, compare_priority, NULL);
thread_unblock (
list_entry (list_pop_front (&sema->waiters), struct thread, elem));
}
sema->value++;
test_max_priority ();
intr_set_level (old_level);
}/*
Thread에 접근할때
최초의 접근이라면 바로 lock을 갖고 작업을 진행 (이땐 sema 가 1)
그 이후 또다른 접근이 존재한다면 sema 가 0이기 때문에 while문으로 들어간다
while문에서 sema->waiters(block된 애들이 대기하는 곳)에 우선순위에 맞춰서 넣는다
*/
void
sema_down (struct semaphore *sema) {
enum intr_level old_level;
ASSERT (sema != NULL);
ASSERT (!intr_context ());
old_level = intr_disable ();
while (sema->value == 0) {
list_insert_ordered (&sema->waiters, &thread_current ()->elem,
compare_priority, NULL);
thread_block ();
}
sema->value--;
intr_set_level (old_level);
}아래 부분은 coditional variable을 위한 code
/*
sema_ele 에 대한 크기 priority를 비교하기 위함
우선순위가 크면 True 작으면 false
기존에 있던 compare는 list에 대한 elem을 위한 것이었기 때문에
보다 정확한 동작을 하기 위해서 sema용으로 만듦
*/
bool
compare_sema_priority (const struct list_elem *a, const struct list_elem *b,
void *aux UNUSED) {
struct semaphore_elem *sa = list_entry (a, struct semaphore_elem, elem);
struct semaphore_elem *sb = list_entry (b, struct semaphore_elem, elem);
struct list *input_sema_list = &(sa->semaphore.waiters);
struct list *prev_sema_list = &(sb->semaphore.waiters);
int input_sema_pri =
list_entry (list_begin (input_sema_list), struct thread, elem)->priority;
int prev_sema_pri =
list_entry (list_begin (prev_sema_list), struct thread, elem)->priority;
return input_sema_pri > prev_sema_pri;
}
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, compare_sema_priority, 0);
lock_release (lock);
sema_down (&waiter.semaphore);
lock_acquire (lock);
}
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)) {
list_sort (&cond->waiters, compare_sema_priority, 0);
sema_up (&list_entry (list_pop_front (&cond->waiters),
struct semaphore_elem, elem)
->semaphore);
}
}
result
하루에 집중을