synch.c File Reference

#include "threads/synch.h"
#include <stdio.h>
#include <string.h>
#include "threads/interrupt.h"
#include "threads/thread.h"

Include dependency graph for synch.c:

Classes
struct	semaphore_elem

Functions
void	donate_priority (void)
void	remove_with_lock (struct lock *)
void	refresh_priority (void)
static bool	cmp_d_priority (const struct list_elem *, const struct list_elem *, void *aux)
static bool	cmp_sem_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
void	sema_init (struct semaphore *sema, unsigned value)
void	sema_down (struct semaphore *sema)
bool	sema_try_down (struct semaphore *sema)
void	sema_up (struct semaphore *sema)
static void	sema_test_helper (void *sema_)
void	sema_self_test (void)
void	lock_init (struct lock *lock)
void	lock_acquire (struct lock *lock)
bool	lock_try_acquire (struct lock *lock)
void	lock_release (struct lock *lock)
bool	lock_held_by_current_thread (const struct lock *lock)
static bool	cmp_d_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
void	cond_init (struct condition *cond)
void	cond_wait (struct condition *cond, struct lock *lock)
void	cond_signal (struct condition *cond, struct lock *lock UNUSED)
void	cond_broadcast (struct condition *cond, struct lock *lock)

Function Documentation

cmp_d_priority() [1/2]

static bool cmp_d_priority ( const struct list_elem *  , const struct list_elem *  , void *  aux  )

static

Here is the caller graph for this function:

cmp_d_priority() [2/2]

static bool cmp_d_priority ( const struct list_elem *  a, const struct list_elem *  b, void *aux  UNUSED  )

static

                                                                                        {
    return list_entry(a, struct thread, d_elem) -> priority \
        > list_entry(b, struct thread, d_elem) -> priority ? \
        1 : 0; 
}

cmp_sem_priority()

static bool cmp_sem_priority ( const struct list_elem *  a, const struct list_elem *  b, void *aux  UNUSED  )

static

                                                                                          {
    return list_entry (list_begin (&list_entry (a, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority \
        > list_entry (list_begin (&list_entry (b, struct semaphore_elem, elem)->semaphore.waiters), struct thread, elem)->priority;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cond_broadcast()

void cond_broadcast	(	struct condition *	cond,
		struct lock *	lock
	)

                                                           {
    ASSERT (cond != NULL);
    ASSERT (lock != NULL);
 
    while (!list_empty (&cond->waiters))
        cond_signal (cond, lock);
}

Here is the call graph for this function:

cond_init()

void cond_init

(

struct condition *

cond

)

                                   {
    ASSERT (cond != NULL);
 
    list_init (&cond->waiters);
}

Here is the call graph for this function:

cond_signal()

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, cmp_sem_priority, NULL);
        sema_up (&list_entry (list_pop_front (&cond->waiters),
                    struct semaphore_elem, elem)->semaphore);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

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);
    /*------------------------- [P1] Priority Scheduling - Condition variables --------------------------*/
    // list_push_back (&cond->waiters, &waiter.elem);
    list_insert_ordered (&cond->waiters, &waiter.elem, cmp_sem_priority, NULL);
    lock_release (lock);
    sema_down (&waiter.semaphore);
    lock_acquire (lock);
}

Here is the call graph for this function:

donate_priority()

void donate_priority

(

void

)

                      {
    ASSERT(thread_current()->wait_on_lock != NULL);
    struct thread *curr_lock_holder = thread_current()->wait_on_lock->holder; // 현재 내가 기다리는 락을 소유하고 있는 스레드
    int nested_depth = 8;
    
    // 만약 내 우선 순위가 lock이 걸린 스레드보다 높다면 우선순위 기부
    while (thread_get_priority() > curr_lock_holder->priority){
        if (nested_depth-- <= 0) break; // nested_depth 확인
        curr_lock_holder->priority = thread_get_priority(); // 내 우선 순위 기부
        
        // 홀더가 또 다른 락을 기다리고 있을 때 반복문 다시 순회
        if (curr_lock_holder->wait_on_lock != NULL)
            curr_lock_holder = curr_lock_holder->wait_on_lock->holder;
        else
            break;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

lock_acquire()

void lock_acquire

(

struct lock *

lock

)

                                 {
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));
 
    if (lock->holder != NULL) { // 해당 lock의 holder가 존재한다면
        thread_current()->wait_on_lock = lock;// 해당 락을 wait_on_lock에 추가한다.
        list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem, cmp_d_priority, NULL);
        donate_priority();
    }
    sema_down (&lock->semaphore);
    thread_current()->wait_on_lock = NULL; // 해당 스레드의 wait_on_lock을 NULL로 만든다.
    lock->holder = thread_current();
}

Here is the call graph for this function:

Here is the caller graph for this function:

lock_held_by_current_thread()

bool lock_held_by_current_thread

(

const struct lock *

lock

)

                                                      {
    ASSERT (lock != NULL);
 
    return lock->holder == thread_current ();
}

Here is the call graph for this function:

Here is the caller graph for this function:

lock_init()

void lock_init

(

struct lock *

lock

)

                              {
    ASSERT (lock != NULL);
 
    lock->holder = NULL;
    sema_init (&lock->semaphore, 1);
}

Here is the call graph for this function:

Here is the caller graph for this function:

lock_release()

void lock_release

(

struct lock *

lock

)

                                 {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));
 
    remove_with_lock(lock);
    refresh_priority();
 
    lock->holder = NULL;
    sema_up (&lock->semaphore);
}

Here is the call graph for this function:

Here is the caller graph for this function:

lock_try_acquire()

bool lock_try_acquire

(

struct lock *

lock

)

                                     {
    bool success;
 
    ASSERT (lock != NULL);
    ASSERT (!lock_held_by_current_thread (lock));
 
    success = sema_try_down (&lock->semaphore);
    if (success)
        lock->holder = thread_current ();
    return success;
}

Here is the call graph for this function:

refresh_priority()

void refresh_priority

(

void

)

                      {
    struct list_elem *donation_elem;
    struct list *curr_donations = &thread_current()->donations;
    int donations_priority;
 
    thread_current()->priority = thread_current()->priority_base; // 스레드의 우선순위를 기부 받기 전의 우선순위로 변경한다.
    if (!list_empty(curr_donations)){ // donation에 스레드가 존재하는지를 먼저 확인한다.
        list_sort(curr_donations, cmp_d_priority, NULL);
        donation_elem = list_begin(curr_donations);
        donations_priority = list_entry(donation_elem, struct thread, d_elem)->priority;
        if (thread_get_priority() < donations_priority)
            thread_current()->priority = donations_priority;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

remove_with_lock()

void remove_with_lock

(

struct lock *

lock

)

                                    {
    struct list_elem *curr = list_begin(&thread_current()->donations);
    struct thread *curr_thread;
 
    while (curr != list_end(&thread_current()->donations)){ // 전체 순회
        curr_thread = list_entry(curr, struct thread, d_elem);
        if (curr_thread -> wait_on_lock == lock)
            curr = list_remove(curr); // donations에서 해당 락을 기다리고 있던 스레드 제거
        else
            curr = curr -> next;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

sema_down()

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, cmp_priority, NULL);
        // list_push_back (&sema->waiters, &thread_current ()->elem);
        thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}

Here is the call graph for this function:

Here is the caller graph for this function:

sema_init()

void sema_init	(	struct semaphore *	sema,
		unsigned	value
	)

                                                   {
    ASSERT (sema != NULL);
 
    sema->value = value;
    list_init (&sema->waiters);
}

Here is the call graph for this function:

Here is the caller graph for this function:

sema_self_test()

void sema_self_test

(

void

)

                      {
    struct semaphore sema[2];
    int i;
 
    printf ("Testing semaphores...");
    sema_init (&sema[0], 0);
    sema_init (&sema[1], 0);
    thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
    for (i = 0; i < 10; i++)
    {
        sema_up (&sema[0]);
        sema_down (&sema[1]);
    }
    printf ("done.\n");
}

Here is the call graph for this function:

sema_test_helper()

static void sema_test_helper ( void *  sema_ )

static

                               {
    struct semaphore *sema = sema_;
    int i;
 
    for (i = 0; i < 10; i++)
    {
        sema_down (&sema[0]);
        sema_up (&sema[1]);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

sema_try_down()

bool sema_try_down

(

struct semaphore *

sema

)

                                       {
    enum intr_level old_level;
    bool success;
 
    ASSERT (sema != NULL);
 
    old_level = intr_disable ();
    if (sema->value > 0)
    {
        sema->value--;
        success = true;
    }
    else
        success = false;
    intr_set_level (old_level);
 
    return success;
}

Here is the call graph for this function:

Here is the caller graph for this function:

sema_up()

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, cmp_priority, NULL); // waiter_list 정렬
        struct thread *new_lockholder = list_entry(list_pop_front (&sema->waiters), struct thread, elem);
        thread_unblock (new_lockholder); // 세마포어를 해제하고 레디 상태로 만들어준다.
        if (thread_get_priority() < new_lockholder->priority ){
            if (intr_context())
                intr_yield_on_return();
            else
                thread_yield();
        }
    }
    intr_set_level (old_level);
}

Here is the call graph for this function:

Here is the caller graph for this function: