pintOS project1: threads (KAIST.ver)

bdbest72·2021년 9월 27일
1

pintOS

목록 보기
1/9

kaist pintos

stanford pintos

https://poalim.tistory.com/

https://renelemon.tistory.com/


📖목표


최소한의 기능을 갖춘 thread system에서 device directory 와 thread directory 의 파일들을 적절히 수정해 Alarm Clock, Priority Scheduling, Advanced Scheduler 의 요구사항들을 충족하자!

reference solution 기준으로

devices/timer.c | 29 +++++++++++++++++++++++++++++
include/threads/fixed-point.h | 10 ++++++++++
include/threads/synch.h | 4 ++++
include/threads/thread.h | 21 +++++++++++++++++++++
threads/synch.c | 143 +++++++++++++++++++++++++++++++++++++++++++-
threads/thread.c | 135 ++++++++++++++++++++++++++++++++++++++++----
6 files changed, 330 insertions(+), 12 deletions(-)

가량의 변경사항이 만들어졌다.

  • note: fixed-point.h is a new file added by the reference solution.

📖코드로 thread system을 이해 해보자


💻init.c의 메인 함수


/* 이 위로는 수많은 헤더들이...*/

/* Page-map-level-4 with kernel mappings only. */
uint64_t *base_pml4;

#ifdef FILESYS
/* -f: Format the file system? */
static bool format_filesys;
#endif

/* -q: Power off after kernel tasks complete? */
bool power_off_when_done;

bool thread_tests;

static void bss_init (void);
static void paging_init (uint64_t mem_end);

static char **read_command_line (void);
static char **parse_options (char **argv);
static void run_actions (char **argv);
static void usage (void);

static void print_stats (void);

/* Pintos main program. */
int
main (void) {
	uint64_t mem_end;
	char **argv;

	/* Clear BSS and get machine's RAM size. */
	bss_init ();

	/* Break command line into arguments and parse options. */
	argv = read_command_line ();
	argv = parse_options (argv);

	/* Initialize ourselves as a thread so we can use locks,
	   then enable console locking. */
	thread_init ();
	console_init ();

	/* Initialize memory system. */
	mem_end = palloc_init ();
	malloc_init ();
	paging_init (mem_end);

#ifdef USERPROG
	tss_init ();
	gdt_init ();
#endif

	/* Initialize interrupt handlers. */
	intr_init ();
	timer_init ();
	kbd_init ();
	input_init ();

#ifdef USERPROG
	exception_init ();
	syscall_init ();
#endif

	/* Start thread scheduler and enable interrupts. */
	thread_start ();
	serial_init_queue ();
	timer_calibrate ();

#ifdef FILESYS
	/* Initialize file system. */
	disk_init ();
	filesys_init (format_filesys);
#endif

#ifdef VM
	vm_init ();
#endif

	printf ("Boot complete.\n");

	/* Run actions specified on kernel command line. */
	run_actions (argv);

	/* Finish up. */
	if (power_off_when_done)
		power_off ();
	thread_exit ();
}

/* main 함수까지만 */

❗핀토스의 메인 프로그램이다. 가장 처음 실행되는 함수라고 우선 이해했다.

우선 목표는 thread system에 대한 이해 및 non-busy wait method로 alarm clock을 구현하는 것이기에 이해 맞는 코드들을 주목하자면 다음과 같다.

초기화 함수:

  • thread_init()
  • timer_init()

시작 함수:

  • thread_start()
  • timer_calibrate()

종료 함수

  • thread_exit()

thread 함수들은 thread.c에, timer 함수들은 timer.c에 구현되어있고, 타이머 이전에 thread 함수들을 집중적으로 분석해보겠다.




💻thread.h


📑thread 구조체 정의


//thread에 대한 주석 설명은 아래에 (너무 김...)
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. */
};

    
/* States in a thread's life cycle. */
enum thread_status {
	THREAD_RUNNING,     /* Running thread. */
	THREAD_READY,       /* Not running but ready to run. */
	THREAD_BLOCKED,     /* Waiting for an event to trigger. */
	THREAD_DYING        /* About to be destroyed. */
};

/* Thread identifier type.
   You can redefine this to whatever type you like. */
typedef int tid_t;

//쓰레드에 대한 설명.
/* A kernel thread or user process.
 *
 * Each thread structure is stored in its own 4 kB page.  The
 * thread structure itself sits at the very bottom of the page
 * (at offset 0).  The rest of the page is reserved for the
 * thread's kernel stack, which grows downward from the top of
 * the page (at offset 4 kB).  Here's an illustration:
 *
 *      4 kB +---------------------------------+
 *           |          kernel stack           |
 *           |                |                |
 *           |                |                |
 *           |                V                |
 *           |         grows downward          |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           +---------------------------------+
 *           |              magic              |
 *           |            intr_frame           |
 *           |                :                |
 *           |                :                |
 *           |               name              |
 *           |              status             |
 *      0 kB +---------------------------------+
 *
 * The upshot of this is twofold:
 *
 *    1. First, `struct thread' must not be allowed to grow too
 *       big.  If it does, then there will not be enough room for
 *       the kernel stack.  Our base `struct thread' is only a
 *       few bytes in size.  It probably should stay well under 1
 *       kB.
 *
 *    2. Second, kernel stacks must not be allowed to grow too
 *       large.  If a stack overflows, it will corrupt the thread
 *       state.  Thus, kernel functions should not allocate large
 *       structures or arrays as non-static local variables.  Use
 *       dynamic allocation with malloc() or palloc_get_page()
 *       instead.
 *
 * The first symptom of either of these problems will probably be
 * an assertion failure in thread_current(), which checks that
 * the `magic' member of the running thread's `struct thread' is
 * set to THREAD_MAGIC.  Stack overflow will normally change this
 * value, triggering the assertion. */
/* The `elem' member has a dual purpose.  It can be an element in
 * the run queue (thread.c), or it can be an element in a
 * semaphore wait list (synch.c).  It can be used these two ways
 * only because they are mutually exclusive: only a thread in the
 * ready state is on the run queue, whereas only a thread in the
 * blocked state is on a semaphore wait list. */

😊thread status

  • Member of struct thread: enum thread_status status
    The thread's state, one of the following:

  • Thread State: THREAD_RUNNING
    The thread is running. Exactly one thread is running at a given time. thread_current() returns the running thread.

  • Thread State: THREAD_READY
    The thread is ready to run, but it's not running right now. The thread could be selected to run the next time the scheduler is invoked. Ready threads are kept in a doubly linked list called ready_list.

  • Thread State: THREAD_BLOCKED
    The thread is waiting for something, e.g. a lock to become available, an interrupt to be invoked. The thread won't be scheduled again until it transitions to the THREAD_READY state with a call to thread_unblock(). This is most conveniently done indirectly, using one of the Pintos synchronization primitives that block and unblock threads automatically (see section A.3 Synchronization).
    There is no a priori way to tell what a blocked thread is waiting for, but a backtrace can help (see section E.4 Backtraces).

  • Thread State: THREAD_DYING
    The thread will be destroyed by the scheduler after switching to the next thread.




💻thread.c


🔰kernal_thread()


/* thread/thread.c */
/* Function used as the basis for a kernel thread. */
static void
kernel_thread (thread_func *function, void *aux) 
{
  ASSERT (function != NULL);

  intr_enable ();       /* The scheduler runs with interrupts off. */
  function (aux);       /* Execute the thread function. */
  thread_exit ();       /* If function() returns, kill the thread. */
}


🔰thread_init()



/* Initializes the threading system by transforming the code
   that's currently running into a thread.  This can't work in
   general and it is possible in this case only because loader.S
   was careful to put the bottom of the stack at a page boundary.

   Also initializes the run queue and the tid lock.

   After calling this function, be sure to initialize the page
   allocator before trying to create any threads with
   thread_create().

   It is not safe to call thread_current() until this function
   finishes. */
   
void
thread_init (void) {
	// 설명1.1
	ASSERT (intr_get_level () == INTR_OFF);

	/* Reload the temporal gdt for the kernel
	 * This gdt does not include the user context.
	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
     
     	//설명1.2
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);
	
    //설명1.3
	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);

    //설명1.4
	/* 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 ();
}

📑설명1.1 interrupt 함수


결론
intr_get_level()로 현재 interrupt가 disabled(==INTR_OFF) 인지, enabled(INTR_ON) 인지 확인 후 disable 일 경우 계속 진행한다.

Assert (조건식) 함수는 assert.h 에 정의된 함수로, assert에 지정한 조건식이 거짓(false)일 때 프로그램을 중단하며 참(true)일 때는 프로그램이 계속 실행한다.
https://dojang.io/mod/page/view.php?id=764

이 경우 intr_get_level() 를 실행해 return 값이 INTR_OFF 와 같은지 확인한다.

intr_get_level() 은 threads/interrupt.h(.c) 에 정의되고/구현된 함수로:

/* Returns the current interrupt status. */
enum intr_level
intr_get_level (void) {
	uint64_t flags;

	/* Push the flags register on the processor stack, then pop the
	   value off the stack into `flags'.  See [IA32-v2b] "PUSHF"
	   and "POP" and [IA32-v3a] 5.8.1 "Masking Maskable Hardware
	   Interrupts". */
       
	asm volatile ("pushfq; popq %0" : "=g" (flags));

	return flags & FLAG_IF ? INTR_ON : INTR_OFF;
}
Type: **enum intr_level**
One of **INTR_OFF** or **INTR_ON**, denoting that interrupts are _disabled_ or _enabled_, respectively.

Function: enum intr_level **intr_get_level (void)**
Returns the current interrupt state.

코드 자체는 당장은 중요하지 않다. 참고로 동기화 문제를 해결하는 가장 안 좋은, 쉽고 무식한 방법은 interrupts를 무력화(disabling)하는 것이다.

이와 관련된 추가적인 함수는

Function: enum intr_level intr_set_level (enum intr_level level)
Turns interrupts on or off according to level. Returns the previous interrupt state.

Function: enum intr_level intr_enable (void)
Turns interrupts on. Returns the previous interrupt state.

Function: enum intr_level intr_disable (void)
Turns interrupts off. Returns the previous interrupt state.

https://web.stanford.edu/class/cs140/projects/pintos/pintos_6.html

이에 대한 자세한 설명은 링크를 참조하면 좋다.

📖external interrupts

External interrupts are those generated by devices outside the
CPU, such as the timer. External interrupts run with
interrupts turned off, so they never nest, nor are they ever
pre-empted.

/* External interrupts are those generated by devices outside the
   CPU, such as the timer.  External interrupts run with
   interrupts turned off, so they never nest, nor are they ever
   pre-empted.  Handlers for external interrupts also may not
   sleep, although they may invoke intr_yield_on_return() to
   request that a new process be scheduled just before the
   interrupt returns. */
   
static bool in_external_intr;   /* Are we processing an external interrupt? */
static bool yield_on_return;    /* Should we yield on interrupt return? */

/* Returns true during processing of an external interrupt
   and false at all other times. */
   
bool
intr_context (void) {
	return in_external_intr;
}

/* During processing of an external interrupt, directs the
   interrupt handler to yield to a new process just before
   returning from the interrupt.  May not be called at any other
   time. */
   
void
intr_yield_on_return (void) {
	ASSERT (intr_context ());
	yield_on_return = true;
}

static bool in_external_intr;
external interrupt가 처리되고 있는 중이라면 true를 아니면 false를 값으로 가진다.

bool intr_context (void) { return in_external_intr; }
external interrupt가 처리되고 있다면 true를 아니면 false를 return한다.


📑설명1.2 GDT(global decriptor table)


//thread.c
// Global descriptor table for the thread_start.
// Because the gdt will be setup after the thread_init, we should
// setup temporal gdt first.
static uint64_t gdt[3] = { 0, 0x00af9a000000ffff, 0x00cf92000000ffff };

The Global Descriptor Table (GDT) is specific to the IA32 architecture. It contains entries telling the CPU about memory segments. A similar Interrupts Descriptor Table (IDT) exists containing tasks and interrupts descriptors.

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

https://wiki.osdev.org/Global_Descriptor_Table

여기서는 이 정도만 짚고 넘어간다.


📑설명1.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);

결론
synchronization을 위한 lock 과 scheduling을 위한 list의 초기화를 담당한다.

https://web.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC90
A.3 synchronization에 아래 내용이 설명되어있다.

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

semaphore 든 lock이든 대기중인 threads의 list를 유지 혹은 지니는데, 이는 linked list implementation in lib/kernel/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);
}
Type: struct lock
Represents a lock.

Function: void lock_init (struct lock *lock)
Initializes lock as a new lock. The lock is not initially owned by any thread.

❗추가적인 함수:

Function: void lock_acquire (struct lock *lock)
Function: bool lock_try_acquire (struct lock *lock)
Function: void lock_release (struct lock *lock)
Function: bool lock_held_by_current_thread (const struct lock *lock)

https://web.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC90
자세한 내용은 A.3.3 Locks 를 참조


🔰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는 연결 구조체 리스트로 구현되어있다. 기초적인 연결 작업 및 값의 초기화를 진행한다.


📑설명1.4


/* 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()


thread_init()이 thread 실행을 위한 초기화였다면, init_thread()는 실행중인 혹은 이미 존재하는 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

memset()?
memset 함수는 메모리의 내용(값)을 원하는 크기만큼 특정 값으로 세팅할 수 있는 함수 입니다.
함수이름이 정말 명확하죠? memory + setting 메모리를 (특정 값으로) 세팅한다.
함수 원형
void memset(void ptr, int value, size_t num);
출처: https://blockdmask.tistory.com/441 [개발자 지망생]

❗Note: thread scheduling 을 위한 우선 순위로 수가 클 수록 높은 우선순위를 지닌다.

/* Thread priorities. */
#define PRI_MIN 0                       /* Lowest priority. */
#define PRI_DEFAULT 31                  /* Default priority. */
#define PRI_MAX 63                      /* Highest priority. */

🔰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);
}

🔰thread_create()


Function: tid_t thread_create (const char *name, int priority, thread_func *func, void *aux)
Creates and starts a new thread named name with the given priority, returning the new thread's tid. The thread executes func, passing aux as the function's single argument.

  • 새로운 thread를 만들고 실행한다. return 값으로 생성/실행된 thread의 포인터를 준다. 생성된 thread는 인자로 주어진 function을 수행한다.

    Type: void thread_func (void *aux)
    This is the type of the function passed to thread_create(), whose aux argument is passed along as the function's argument.

t->tf 는 struct intr_frame tf; / Information for switching / 로 switching을 위한 정보들을 담는다. struct intr_frame는 interrupt.h에 정의 되어있다.


/* 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에 포함된다. 순서는 스케쥴러 마음이다. 지금으로는 가장 뒷줄로 배치되게 되어있다.

Function: void thread_yield (void)
Yields the CPU to the scheduler, which picks a new thread to run. The new thread might be the current thread, so you can't depend on this function to keep this thread from running for any particular length of time. The current thread is not put to sleep .

🛑중요! - thread_yield()함수는 intr_handler 함수에 의해 yields_on_return변수의 값이 true일 경우 실행시킨다.
이는 timer_interrupt -> thread_tick 에서 thread_ticks 변수가 매 tick 마다 증가하다가 TIME_SLICE (4) 보다 크거나 같아지면 바로 실행된다는 뜻이다.
즉, 4 tick 마다 무조건 thread_yield()가 실행되는 것이다.

https://h2oche.github.io/2019/03/12/pintos-guide-1/

/*  Yields the CPU to the scheduler, which picks a new thread to run.  
    The current thread is not put to sleep and
    may be scheduled again immediately at the scheduler's whim. */
    
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);
}
  1. interrupt 함수 참조
  2. interrupt를 disable 한다.
  3. 현재 실행 중이던 쓰레드가 idle_thread가 아니라면, 현재 쓰레드를 실행 리스트의 제일 뒤에 넣는다.
  4. do_schedule 함수 실행 한다.
  5. interrupt 를 다시 원래 설정으로 복귀 시킨다.

🔰thread_unblock()


thread_block 함수에 의해 block 된 T(thread)를 다시 실행가능 상태로 되돌린다. T가 blocked 상태가 아니라면 error가 발생한다.

Function: void thread_unblock (struct thread *thread)
Transitions thread, which must be in the blocked state, to the ready state, allowing it to resume running (see Thread 구조체 단락). This is called when the event that the thread is waiting for occurs, e.g. when the lock that the thread is waiting on becomes available.

/* Transitions a blocked thread T to the ready-to-run state.
   This is an error if T is not blocked.  (Use thread_yield() to
   make the running thread ready.)

   This function does not preempt the running thread.  This can
   be important: if the caller had disabled interrupts itself,
   it may expect that it can atomically unblock a thread and
   update other data. */
   
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_push_back(&ready_list, &t->elem);
	t->status = THREAD_READY;
	intr_set_level(old_level);
}
  1. is_thread() 는 주어진 포인터가 thread 구조체를 가르키는 올바른 thread 포인터인지를 검증한다.

  2. ASSERT()를 통해 Blocked 된 T인지 검증한다.

  3. ready_list에 T를 다시 집어 넣는다. 가장 뒷 줄에!

/* Inserts ELEM at the end of LIST, so that it becomes the
   back in LIST. */
void
list_push_back (struct list *list, struct list_elem *elem) {
	list_insert (list_end (list), elem);
}

/* Inserts ELEM just before BEFORE, which may be either an
   interior element or a tail.  The latter case is equivalent to
   list_push_back(). */
   
void
list_insert (struct list_elem *before, struct list_elem *elem) {...}
  1. T의 thread status를 업데이트해주고 interrupt status 또한 원본으로 되돌린다.

🔰thread_block()


실행중인 thread를 running state에서 blocked state 로 바꾼다. 이 기능은 너무 Low-level(하드웨어와 가깝다)이라 가급적이면 비슷한 기능을 하는 synchronization 기능을 사용하는 것이 좋다.

Function: void thread_block (void)
Transitions(transite?) the running thread from the running state to the blocked state (see Thread States). The thread will not run again until thread_unblock() is called on it, so you'd better have some way arranged for that to happen. Because thread_block() is so low-level, you should prefer to use one of the synchronization primitives instead (see section A.3 Synchronization).

/* Puts the current thread to sleep.  It will not be scheduled
   again until awoken by thread_unblock().

   This function must be called with interrupts turned off.  It
   is usually a better idea to use one of the synchronization
   primitives in synch.h. */
   
void thread_block(void)
{
	ASSERT(!intr_context());
	ASSERT(intr_get_level() == INTR_OFF);
	thread_current()->status = THREAD_BLOCKED;
	schedule();
}




⏰Assignment01: Alarm-clock


💯test: alarm-single, alarm-mulitple


🔰thread_sleep(), thread_awake()

https://firecatlibrary.tistory.com/56?category=875424


/*-------------------------- project.1 -----------------------------*/
void 
thread_sleep(int64_t ticks){

	struct thread *curr = thread_current ();
	enum intr_level old_level;
	ASSERT (!intr_context ());
	old_level = intr_disable ();

	curr->wakeup_tick = ticks;

	if (curr != idle_thread)
		list_push_back (&sleep_list, &curr->elem); /* sleep_list에 추가 */
	
	update_next_tick_to_awake(ticks);

	/* thread_block()과 같은 역할을 한다. */
	do_schedule(THREAD_BLOCKED);
	intr_set_level (old_level);
}

/* sleep_list 중 가장 작은 tick보다 현재 tick이 클 경우 
    timer_interrupt 에서 호출된다. 이때 ticks 인자 값은 
	thread_awake가 호출 된 순간의 ticks이다. */
void 
thread_awake(int64_t ticks){
	/* next_tick 초기화 sleep_list의 변동으로 인한. */
	next_tick_to_awake = INT64_MAX; 
	struct list_elem *temp_list_elem = list_begin(&sleep_list);
	struct thread *t;

	for (temp_list_elem ; temp_list_elem != list_end(&sleep_list);){
		/* list_entry는 현재 elem(temp_list_elem)를 가지고 있는 thread 포인터를 리턴한다. 
			struct list_elem *t == (struct thread *t) &t->elem 
			(struct list_elem) example_name == (struct thread *t) t->elem 
			t->elem 의 값 == struct list_elem 의 이름? 변수명? 
		*/
		t = list_entry(temp_list_elem, struct thread, elem);

		if (t->wakeup_tick <= ticks){
			temp_list_elem = list_remove(&t->elem);
			thread_unblock(t);
		}
		else {
			update_next_tick_to_awake(t->wakeup_tick);
			temp_list_elem = list_next(temp_list_elem);
		}
	}
}

void 
update_next_tick_to_awake(int64_t ticks){

	next_tick_to_awake = MIN(next_tick_to_awake, ticks);

	//if (ticks > get_next_tick_to_awake()) next_tick_to_awake = ticks;
}

int64_t 
get_next_tick_to_awake(void){
	return next_tick_to_awake;
}

/*-------------------------- project.1 -----------------------------*/

💻alarm_wait.c


🔰기초 선언


static void test_sleep (int thread_cnt, int iterations);

void
test_alarm_single (void) 
{
  test_sleep (5, 1);
}

void
test_alarm_multiple (void) 
{
  test_sleep (5, 7);
}

/* Information about the test. */
struct sleep_test 
  {
    int64_t start;              /* Current time at start of test. */
    int iterations;             /* Number of iterations per thread. */

    /* Output. */
    struct lock output_lock;    /* Lock protecting output buffer. */
    int *output_pos;            /* Current position in output buffer. */
  };

/* Information about an individual thread in the test. */
struct sleep_thread 
  {
    struct sleep_test *test;     /* Info shared between all threads. */
    int id;                     /* Sleeper ID. */
    int duration;               /* Number of ticks to sleep. */
    int iterations;             /* Iterations counted so far. */
  };

static void sleeper (void *);

pintos -T 10 -- -q run alarm-multiple 명령어가 주어졌을 때 실행되는 코드들을 위한 기초 선언들.
기본적으로 test_sleep 함수에서 거의 대부분 처리한다는 것을 알 수 있다.


🔰test_sleep()



/* Runs THREAD_CNT threads thread sleep ITERATIONS times each. */
static void
test_sleep (int thread_cnt, int iterations) 
{
  struct sleep_test test;
  struct sleep_thread *threads;
  int *output, *op;
  int product;
  int i;

  /* This test does not work with the MLFQS. */
  /*
   If false (default), use round-robin scheduler.
   If true, use multi-level feedback queue scheduler.
   Controlled by kernel command-line option "-o mlfqs". 
bool thread_mlfqs;
  */
  ASSERT (!thread_mlfqs);

  msg ("Creating %d threads to sleep %d times each.", thread_cnt, iterations);
  msg ("Thread 0 sleeps 10 ticks each time,");
  msg ("thread 1 sleeps 20 ticks each time, and so on.");
  msg ("If successful, product of iteration count and");
  msg ("sleep duration will appear in nondescending order.");

  /* Allocate memory. */
  threads = malloc (sizeof *threads * thread_cnt);
  output = malloc (sizeof *output * iterations * thread_cnt * 2);
  if (threads == NULL || output == NULL)
    PANIC ("couldn't allocate memory for test");

  /* Initialize test. */
  //설명 2.1
  test.start = timer_ticks () + 100;
  test.iterations = iterations;
  lock_init (&test.output_lock);
  test.output_pos = output;

  /* Start threads. */
  //설명 2.2
  ASSERT (output != NULL);
  for (i = 0; i < thread_cnt; i++)
    {
      struct sleep_thread *t = threads + i;
      char name[16];
      
      t->test = &test;
      t->id = i;
      t->duration = (i + 1) * 10;
      t->iterations = 0;

      snprintf (name, sizeof name, "thread %d", i);
      thread_create (name, PRI_DEFAULT, sleeper, t);
    }
  
  /* Wait long enough for all the threads to finish. */
  timer_sleep (100 + thread_cnt * iterations * 10 + 100);

  /* Acquire the output lock in case some rogue thread is still
     running. */
  lock_acquire (&test.output_lock);

  /* Print completion order. */
  product = 0;
  for (op = output; op < test.output_pos; op++) 
    {
      struct sleep_thread *t;
      int new_prod;

      ASSERT (*op >= 0 && *op < thread_cnt);
      t = threads + *op;

      new_prod = ++t->iterations * t->duration;
        
      msg ("thread %d: duration=%d, iteration=%d, product=%d",
           t->id, t->duration, t->iterations, new_prod);
      
      if (new_prod >= product)
        product = new_prod;
      else
        fail ("thread %d woke up out of order (%d > %d)!",
              t->id, product, new_prod);
    }

  /* Verify that we had the proper number of wakeups. */
  for (i = 0; i < thread_cnt; i++)
    if (threads[i].iterations != iterations)
      fail ("thread %d woke up %d times instead of %d",
            i, threads[i].iterations, iterations);
  
  lock_release (&test.output_lock);
  free (output);
  free (threads);
}



💻timer.c


알고 가야 할 중요한 포인트!
timer.c
timer.h
System timer that ticks, by default, 100 times per second. You will modify this code in this project.


🔰timer_init()


🛑결론
timer_init이 실행될 경우 8254 PIT 라는 타이머가 PIT_FREQ(100) times per sec단위로 실행되어 지속적으로 timer interrupt을 수행해 ticks 값을 증가시킨다.
확실치는 않지만 그때마다 ticks을 증가시키는 것을 실행허눈 함수가 timer_interrupt로 추정한다.

/* Sets up the 8254 Programmable Interval Timer (PIT) to
   interrupt PIT_FREQ times per second, and registers the
   corresponding interrupt. */
void
timer_init (void) {
	/* 8254 input frequency divided by TIMER_FREQ, rounded to
	   nearest. */
	uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;

	outb (0x43, 0x34);    /* CW: counter 0, LSB then MSB, mode 2, binary. */
	outb (0x40, count & 0xff);
	outb (0x40, count >> 8);

	intr_register_ext (0x20, timer_interrupt, "8254 Timer");
}

🔰timer_interrupts


timer_init() 이 실행된 후 매 TIMER_FREQ (100) times per sec 마다 실행되어 ticks 값을 상승시키는 것으로 추정되는 함수.

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
}

📑 설명 2.1 Initialize test / timer_ticks()


  /* Initialize test. */
  //설명2.1
  test.start = timer_ticks () + 100;
  test.iterations = iterations;
  lock_init (&test.output_lock);
  test.output_pos = output;
  1. test.start 에 timer_ticks() (현재 ticks) 값에 100을 추가한 값을 저장한다. test가 100ticks = 1sec 뒤에 실행 될 예정임을 알 수 있다.
  2. test.iteration (iteration = 반복) 인자로 받은 반복 횟수를 저장한다.
  3. test를 위한 lock을 초기화한다. 초기화 된 값은 test.output_lock의 포인터가 가르키는 lock 구조체에 들어간다.
  4. Current position in output buffer = output을 저장한다.

🔰timer_ticks()


결론
OS가 실행되고나서의 지금까지의 ticks 를 리턴해준다. 이를 진행하는 동안에는 interrupt을 disable해둔다. 왜냐하면 이 함수가 실행되는 도중에 timer interrupt이 발생헤 (매 TIMER_FREQ times per sec 마다 interrupt이 발생하고 있다고 추정.) timer_ticks()가 실행됐을 때보다 늦은/더 큰 값의 ticks가 반환될 수 있다.

/* Number of timer ticks since OS booted. */
static int64_t ticks;

/* Returns the number of timer ticks since the OS booted. */
int64_t
timer_ticks (void) {
	enum intr_level old_level = intr_disable ();
	int64_t t = ticks;
	intr_set_level (old_level);
	barrier ();
	return t;
}
  1. interrupt 함수 단락에서 설명했듯이 intr_disable()은 interrupt를 disable 하고 이전 interrupt state를 return한다.
  2. 어디서 ticks 의 초기화가 이루어지는지는 모르겠다. 다만 init.c에서 timer_init()이 실행되고, timer_init()에서 timer_interrupt() 이 실행되고 ticks++을 실행하고 thread_tick()이 실행된다. thread_tick()에서는 idle_ticks++, kernel_ticks++를 실행한다.
  3. intr_set_level(old_level)을 통해 1.에서 disable 하기 전 원래 interrupt state로 되돌린다.
  4. barrier()

🔰barrier() - Optimisation barrier


An optimization barrier is a special statement that prevents the compiler from making assumptions about the state of memory across the barrier.
컴파일러가 메모리영역을 착각하지 않게끔 줄을 그어주는 역할이라고 이해했다.

https://web.stanford.edu/class/cs140/projects/pintos/pintos_6.html#SEC90
a.3.5 참고


📑설명 2.2 Start threads


    /* Start threads. */
  ASSERT (output != NULL);
  for (i = 0; i < thread_cnt; i++)
    {
      struct sleep_thread *t = threads + i;
      char name[16];
      
      t->test = &test;
      t->id = i;
      t->duration = (i + 1) * 10;
      t->iterations = 0;

      snprintf (name, sizeof name, "thread %d", i);
      thread_create (name, PRI_DEFAULT, sleeper, t);
    }
  

주어진 thread 개수만큼 thead를 실행시킨다.
Sleep_thread에 적절한 값 (i 번째 thread 임을) 저장하고 thread_create를 실행한다.
thread_create는 해당 단락에 설명되어있다.

🛑중요!

  • tid_t thread_create (const char name, int priority, thread_func func, void *aux)

인자를 보면 알 수 있지만 새롭게 생성된 각각의 thread들은 sleeper 라는 함수를 실행한다. sleeper 에는 t가 인자로 주어진다.

❓ snprintf?
#include <stdio.h>
int snprintf(char *buffer, size_t n, const char *format-string, argument-list);

snprintf() 함수는 배열 버퍼에 일련의 문자와 값의 형식을 지정하고 저장합니다. argument-list가 변환되며 format-string의 해당 형식 스펙에 따라 만들어집니다. snprintf() 함수는 n 인수가 추가된 sprintf() 함수와 동일하며, 버퍼에 작성될 최대 개수의 문자(끝 널 문자 포함)를 표시합니다.

format-string은 일반 문자로 구성되며 printf() 함수에 대한 형식 스트링과 같은 형식과 함수가 있습니다.


🔰Sleeper()


/* Sleeper thread. */
static void
sleeper (void *t_) 
{
  struct sleep_thread *t = t_;
  struct sleep_test *test = t->test;
  int i;

  for (i = 1; i <= test->iterations; i++) 
    {
      int64_t sleep_until = test->start + i * t->duration;
      timer_sleep (sleep_until - timer_ticks ());
      lock_acquire (&test->output_lock);
      *test->output_pos++ = t->id;
      lock_release (&test->output_lock);
    }
}

t_ 인자로 t 즉 sleeper_thread 포인터가 주어졌기에 이를 초기에 선언한다.

sleep_until 변수는 test->start (test가 시작된 ticks) , t->duration (thread가 실행되는데 필요한 혹은 sleep을 진행할 (기다릴) 시간으로 추정된다), i 로 구성되는데

i * t->duration 은 해당 thread를 주어진 iterations 반복 횟수 만큼 수행하기위해 자연스럽게 sleep_until 값이 각 i 번째 반복마다 t->duration을 i 번 더할 수 있게 해준다.

timer_sleep 안의 인자 (sleep_until - timer_ticks()) = ((i * duration) + (test->start - timer_ticks)) = ((동일) + (테스트가 시작된 ticks - 현재 ticks)음수 )

🛑추가 요망

왜 - 현재 ticks를 하는지 모르겠음.
*test->output_pos++ = t->id; 잘모르겠음


🔰timer_sleep


timer_sleep 은 인자로 주어진 ticks 만큼 이 함수를 콜한 thread의 수행작업을 중단시킨다. Suspends execution of the calling thread until time has advanced by at least x timer ticks

//수정전 busy wait 버젼
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

📅Priority scheduling

📖개요


  • Priority scheduling 이란?

    THREAD_READY state인 thread들을 ready_list로 관리해주며, scheduling (다음 실행할 thread를 고르는 과정)이 실행될 경우, thread가 실행 될 순서을 priority 라는 int 값으로 순서대로 실행되도록 관리하는 것.

priority scheduling 이 적용된 scheduling의 경우 다음의 행동들이 발생해야한다.

  1. threadready_list 에 추가 되었을때 (THREADREADY), 해당 _thread의 priority가 현재 THREADRUNNING 인 thread 보다 priority 가 높다면, **즉시 실행 중인 thread가 프로세서를 해당 _thread에게 양보**해야한다.

  2. thread 가 lock, semaphore, 아니면 conditional variable (condvar)을 기다리고 있을때 priority가 높은 순서대로 깨어나야한다.

  3. 실행중인 thread가 자신의 priority를 변화시키는 것은 언제나 생길 수 있지만 만약 현재 thread의 priority를 낮추는 행동이 더이상 highest priority가 아니게된다면 그 즉시 프로세서(CPU)를 양보해야한다.

🛑Priority 범위
숫자가 클 수록 priority 우선 순위가 높다.
thread.h 에 #define PRI_DEFAULT 31 와 같은 형태로 정의되어있다. 간단히 말해 0 ~ 63 이다.

PRI_MIN (0) ~ PRI_DEFAULT (31) ~ PRI_MAX (63)

  • thread_create() 함수가 실행 될 때 인자로 thread 의 initial priority 가 주어진다.

🚸Priority scheduling에서 발생가능한/해결해야 할 이슈들


https://velog.io/@bdbest72/pintOS-project1-threads-Priority-Inversion-donation
🛑해당 글에 더욱 자세하게 잘 설명되어 있습니다.


example of priority inversion.

https://web.eecs.umich.edu/~akamil/teaching/sp04/pri/#fig:inversion

1. Priority inversion

High, Medium, Low (각각 H, M, L, 혹은 그림상 C, B, A) priority를 가진 세 개의 thread가 있는데 lock을 L이 가진 상황에서 H가 실행되다가 Lock을 요청하면 Lock이 풀려날 때까지 대기 상태로 들어가는데 그러면 다음 priority 인 M thread가 실행된다. L이 lock을 가졌기에 생기는 inversion이다.


2. Priority donation

위의 P.I를 해결하기 위해 priority donation이 필요하다. 이는 C thread가 lock을 요청할 때 , lock이 다른 thread에 묶여 있다면, 잠시 자신의 priority를 A에게 양보하여, A가 Lock을 release 할 수 있게 해준다. A에 묶여있던 lock이 풀리면 다시 priority를 반환하여 정상적으로 C가 lock을 accquire하여 진행한다.

🛑Priority donation 에서 해결해야하는 문제점들

1. 하나의 쓰레드에 여러개의 priority가 donate 될 경우
2. donation 이 중첩 (nested) 될 경우.
예를 들어 H가 M이 가지고 있는 lock을 기다리고, M이 L이 가지고 있는 lock을 기다리고있는 상황. 이 경우 M과 L 모두 H의 priority를 잠시 얻어야한다. 필요하다면 8중첩 정도의 합리적인 수준의 nested prirority donation limit을 만들어도 좋다.

Finally, implement(구현) the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are provided in threads/thread.c.

void thread_set_priority (int new_priority);
Sets the current thread's priority to new priority. If the current thread no longer has the highest priority, yields.

int thread_get_priority (void);
Returns the current thread's priority. In the presence of priority donation, returns the higher (donated) priority.

🛑You need not provide any interface to allow a thread to directly modify other threads' priorities.

The priority scheduler is not used in any later project.


💻list.c


🔰list_entry() list_elem으로 thread를 역참조


/* Converts pointer to list element LIST_ELEM into a pointer to
   the structure that LIST_ELEM is embedded inside.  Supply the
   name of the outer structure STRUCT and the member name MEMBER
   of the list element.  See the big comment at the top of the
   file for an example. */
   
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
		- offsetof (STRUCT, MEMBER.next)))
        
ex:
struct list_elem *e = list_begin(&sleep_list);
t = list_entry(e, struct thread, elem);

코드는 아직 이해가 안되지만, 결과적으로

t = list_entry(e, struct thread, elem); 식으로 인자를 주면
e를 list_elem 맴버로 가지고 있는 구조체의 포인터를 리턴해준다!

profile
꿈에다가 우리들의 돛을 달고 앞으로 다가올 그 날을 위해 밤을 지나자

0개의 댓글