[TIL] - 2023.05.27

📌  공부한 내용

 

💻 - Thread.c 코드 분석

1. ASSERT

// ASSERT(조건식) 함수는 assert에 지정한 조건식이 거짓이면 프로그램을 중단하며 참이면 프로그램을 계속 실행한다.
ASSERT(intr_get_level () === INTR_OFF); // => intr_get_level() 함수는 현재 interrupt가 disabled인지, enabled(INTR_OFF)인지 확인후 disabled(INTR_ON)일 경우 계속 진행

이 함수로 해당 결과가 제대로 진행됐는지 테스트 할 수 있다.

동기화 문제를 해결하는 가장 안 좋고 무식한 방법은 interrupts를 무력화(disabled) 시키는 것이다.

2. GDT

static uint64_t gdt[3] = { 0, 0x00af9a000000ffff, 0x00cf92000000ffff };

Global descriptor table로 CPU 전체의 메모리 세그먼트를 말한다.

세그 먼트 영역에 대한 데이터를 일정한 디스크립터 형식으로 기술하고 이를 하나의 테이블에 모아두고자 하는 것

3. lock_init(), list_init()

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

/* Lock used by allocate_tid(). */
static struct lock tid_lock;

/* Thread destruction requests */
static struct list destruction_req;

/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);

// 동기화를 위한 lock과 scheduling을 위한 listdml 초기화

 

쓰레드들은 기본적으로 프로세스에 할당된 메모리 공간을 공유하기에 동기화 이슈가 발생하는데 이를 조절하기 위한 함수들이 (lock_init()) /threads/synch.c에 구현되어 있음

세마포어나 lock이나 대기중인 threads의 list를 유지, 보유하는데 이것은 list.c에 구현되어 있음.

 

💡 - lock은 binary semaphore라고도 하는데 0 혹은 1의 값만을 가지기 때문이다. 이곳에서는 lock이라고 표현되었지만 일반적으로 Mutex라고 한다. 다만 Mutex는 Semaphore의 제한된 버젼이 아닌 독립적인 기법으로 봐야한다. 왜냐하면 Mutex든 Semaphore 든 각각의 장단점을 가지고 있는 완벽하지 못한 상호배제 기법이기 때문이다. 둘의 가장 큰 차이점은 화장실(공유자원)으로 가는 키의 개수가 1개냐 복수개냐이다.

 

https://worthpreading.tistory.com/90 → 세마포어와 뮤텍스의 차이

👉 lock_init()

/* Initializes LOCK.  A lock can be held by at most a single
   thread at any given time.  Our locks are not "recursive", that
   is, it is an error for the thread currently holding a lock to
   try to acquire that lock.

   A lock is a specialization of a semaphore with an initial
   value of 1.  The difference between a lock and such a
   semaphore is twofold.  First, a semaphore can have a value
   greater than 1, but a lock can only be owned by a single
   thread at a time.  Second, a semaphore does not have an owner,
   meaning that one thread can "down" the semaphore and then
   another one "up" it, but with a lock the same thread must both
   acquire and release it.  When these restrictions prove
   onerous, it's a good sign that a semaphore should be used,
   instead of a lock. */

void
lock_init (struct lock *lock) {
	ASSERT (lock != NULL);

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

 

lock은 뮤텍스의 개념과 가깝고 뮤텍스는 키가 하나이기 때문에 키를 반환하지 않으면 사용할 수가 없다.

세마포어는 키를 소유하는 사람이 없고 갯수?로 적용하기 때문에 하나의 키를 사용하는 것이 번거울때 lock 대신에 세마포어를 사용하는 것이 좋을 수 있다.

 

👉 list_init()

/* List element. */
struct list_elem {
	struct list_elem *prev;     /* Previous list element. */
	struct list_elem *next;     /* Next list element. */
};

/* List. */
struct list {
	struct list_elem head;      /* List head. */
	struct list_elem tail;      /* List tail. */
};

/* Initializes LIST as an empty list. */
void
list_init (struct list *list) {
	ASSERT (list != NULL);
	list->head.prev = NULL;
	list->head.next = &list->tail;
	list->tail.prev = &list->head;
	list->tail.next = NULL;
}

list → 연결 구조체 리스트로 구현.

4.Thread 초기화

/* Initial thread, the thread running init.c:main(). */
static struct thread *initial_thread;
    
    /* Set up a thread structure for the running thread. */
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();

running_thread()

/* Returns the running thread.
 * Read the CPU's stack pointer `rsp', and then round that
 * down to the start of a page.  Since `struct thread' is
 * always at the beginning of a page and the stack pointer is
 * somewhere in the middle, this locates the curent thread. */
#define running_thread() ((struct thread *) (pg_round_down (rrsp ())))

현재 실행중인 thread의 포인터를 반환한다.

init_thread()

//인자로 받는 값
initial_thread = running_thread ();
init_thread (initial_thread, "main", PRI_DEFAULT);

/* Does basic initialization of T as a blocked thread named
   NAME. */
   
static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = priority;
	t->magic = THREAD_MAGIC;
}

/* Random value for struct thread's `magic' member.
   Used to detect stack overflow.  See the big comment (thread 구조체 설명)
   at the top of thread.h for details. */
#define THREAD_MAGIC 0xcd6abf4b

thread_start()

/* Starts preemptive thread scheduling by enabling interrupts.
   Also creates the idle thread. */

void thread_start(void)
{
	/* Create the idle thread. */
	struct semaphore idle_started;
	sema_init(&idle_started, 0);
	thread_create("idle", PRI_MIN, idle, &idle_started);

	/* Start preemptive thread scheduling. */
	intr_enable();

	/* Wait for the idle thread to initialize idle_thread. */
	sema_down(&idle_started);
}

 

idle_started → 하나의 c프로그램에서 하나의 main함수 안에서 여러 함수호출들이 이루어지는 것처럼, pintos kernel 위에서 여러 thread들이 동시에 실행될 수 있도록 하는 단 하나의 main thread이다.

thread_create를 하는 순간 idle thread가 생성되고 동시에 idle 함수가 실행된다. idle thread는 여기서 한번 schedule을 받고 바로 sema_up을 하여 마지막의 sema_down을 풀어주어 thread_start가 작업을 끝내고 run_action()이 실행 될 수 있도록 해주고 idle 자신은 block된다.

idle thread는 pintos에서 실행가능한 thread가 하나도 없을 때 wake 되어 작동하는데, 이것은 CPU가 무조건 하나의 thread는 실행하고 있는 상태를 만들기 위함이다

 

Thread의 진행 흐름

thread_init → thread 실행 (THREAD_RUNNING) → thread 종료(THREAD_DYING)

                                                                                   → thread 준비상태(THREAD_READY)

• thread가 준비상태 일때 Thread_Ready에 들어가고 READY_QUEUE에서 관리한다.
• ready_queue에서 넣고 빼는 순서를 정하는 것이 scheduling의 기본 작업이다.
• pintos는 round-robin으로 구현되어 있음

thread_create()

• 새로운 thread를 만들고 실행한다. return 값으로 생성/실행된 thread 포인터를 넘겨준다.

/* Creates a new kernel thread named NAME with the given initial
   PRIORITY, which executes FUNCTION passing AUX as the argument,
   and adds it to the ready queue.  Returns the thread identifier
   for the new thread, or TID_ERROR if creation fails.

   If thread_start() has been called, then the new thread may be
   scheduled before thread_create() returns.  It could even exit
   before thread_create() returns.  Contrariwise, the original
   thread may run for any amount of time before the new thread is
   scheduled.  Use a semaphore or some other form of
   synchronization if you need to ensure ordering.

   The code provided sets the new thread's `priority' member to
   PRIORITY, but no actual priority scheduling is implemented.
   Priority scheduling is the goal of Problem 1-3. */

tid_t thread_create(const char *name, int priority, thread_func *function, void *aux)
{
	struct thread *t;
	tid_t tid;

	ASSERT(function != NULL);

	/* Allocate thread. */
	t = palloc_get_page(PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	/* Initialize thread. */
	init_thread(t, name, priority);
	tid = t->tid = allocate_tid();

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t)kernel_thread;
	t->tf.R.rdi = (uint64_t)function;
	t->tf.R.rsi = (uint64_t)aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock(t);

	return tid;
}

thread_yield()

• CPU를 잠시 스케쥴러에게 양보한다. 여기서 스케쥴러가 어떤 쓰레드를 먼저 실행시킬지 고른다.
• 실행중인 쓰레드는 sleep되지 않고 다시 ready list에 포함된다.

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_push_back(&ready_list, &curr->elem);
	do_schedule(THREAD_READY);
	intr_set_level(old_level);
}

 

 

---

 

💭  느낀 점 & 배운 점

 

여러번 읽다보니까 대충 구조가 어느 정도 잡힌다. 구조는 어느정도 파악했는데 실질적으로 코드를 구현하는 것은 별개인 것 같고, 아직 할 일이 태산인듯 하다. 이번 주말까지 alarm은 구현 완료를 목표로 잡고 정진해야겠다.

 

갑작스러운 비에 아침 운동을 안가려다가 비 맞으면서 걸어갔다 왔는데 생각보다 운동이 잘됨

당분간은 비 소식에 운동을 못가니 못가는 만큼 더 공부를 많이 해야할듯 하다. 

 

---

 

🔥  내일 공부할 내용

- thread_init() 수정 : 

    - sleep queue 구조 선언 및 초기화

- timer_sleep() 수정 :

    - seelp queue에 thread 삽입

- timer_interrup() 수정 :

    - 모든 tick들을 sleep queue에서 wake up 했는지 검사하고 wake up 함수로 wake up 시키기

 

 

---

 

🗒️  포스팅

 

https://spongecake.tistory.com/94

[BFS] - G5_13549_숨바꼭질 3

 

 

 

 

「 나는 다른 무엇보다 인간이 자기 자신을 사랑한다는 것에 놀라고는 한다. 그럼에도 인간은 자신에 대해서만큼은 자신의 판단보다 다른 사람의 판단을 더 신뢰한다. (...) 어떻게 나의 생각이 아니라 다른 사람의 판단을 더 신뢰할 수 있다는 말인가! 」

-마르쿠스 아우렐리우스, 명상록, 12.4

 

다른 사람의 반응이 실제 나의 의견만큼 중요하지 않다는 것을 안다면 우리는 더 많이 행복해질 수 있다.

어떤 일에 대한 다른 사람의 생각을 알기 위해 너무 많은 시간을 소비하지 말라. 내가 생각하는 것이 무엇인지 알기 위해 노력하라.

결과에 대해 생각하는 대신 가져올 효과에 대해, 그리고 그것이 옳은 일인지 아닌지에 대해 더 생각하라.

「 사람을 지배하는 원칙을 눈여보라. 특히 지혜로운 사람들의 원칙을 보라. 그들이 무엇으로부터 멀리 달아나려 하고 무엇을 추구하는지에 대해서.  」

-마르쿠스 아우렐리우스, 명상록, 4.38

 

그 누가 되었든, 누군가를 선택하여 그들이 하는 일을 지켜보자 혹은 그들이 하지 않은 일을 지켜봐도 좋다. 그들이 한 것처럼 우리도 최선을 다하는 것이다.

 

 

 

---