Pintos Project1 - 스레드 전반적인 흐름 잡기

크래프톤 정글

Pintos Project1 - 스레드 전반적인 흐름 잡기

Jerry_K 2024. 11. 11. 11:50

✨ 스레드

프로그램에서 실행 흐름을 만들어 주는 실행 단위
각 스레드는 자신의 스택과 CPU 레지스터 상태를 관리
실행할 작업을 기억하고 스스로 수행할 수 있는 독립적인 흐름
스레드는 단순히 데이터를 담는 자료구조가 아니라 프로세서에서 실행되는 상태를 담고 있음

✨ 프로그램 스레드 실행

thread_init → thread_start → thread_create 의 순서대로 진행

1. thread_init ()

void thread_init (void)

맨 처음 프로그램 실행 시 실행
스레드 시스템 초기화하는 역할
전역 변수 및 리스트 초기화
매인 스레드 초기화

2. thread_start ()

void thread_start (void)

스레드 시스템 실제로 시작
스케줄링이 가능한 상태로 전환
유휴 스레드(idle thread) 생성 및 초기화 작업

3. thread_create ()

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

스레드의 메모리 할당
스레드 초기화 (init_thread)
스택 설정 및 인자 전달
스레드 준비 상태로 설정 및 추가 (thread_unblock)
CPU 선점 검사 (thread_test_preemption)
스레드의 본질적 역할은 thread_func에 의해 결정
특정 함수 포인터(function)와 함수에 전달할 인수(aux)를 받아 실행
- auxiliart (보조의, 추가적인)의 약자

➕ 추가 내용 (특정 변수에 포인터 형을 쓰는 이유)

struct thread {
	...
 
    int init_priority;
    struct lock *wait_on_lock;
    struct list donations;
    struct list_elem donation_elem;

	...
};

여기서 포인터를 사용하여 각 스레드들과 자원 공유

✨인터럽트

1. intr_enable ()

enum intr_level intr_enable (void)

인터럽트 활성화
어셈블리 명령어 sti를 사용하여 인터럽트 플래그 (IF) 설정

2. intr_disable()

enum intr_level intr_disable (void)

인터럽트 비활성화
어셈블리 명령어 cli를 사용하여 인터럽트 플래그(IF) 비활성화

✨ 스레드 상태 변화

1. thread_block ()

void thread_block (void)

현재 스레드의 상태를 block으로 변경
- 현재 스레드를 블록하는 함수이므로 매개변수 필요없음
schedule 함수 호출
- 현재 스레드를 삭제하지는 않고, 다음 스레드와 context switch
block 상태가 되면 현재 스레드 CPU 사용 중단하고 다른 대기중 스레드 CPU 사용
- block 상태의 스레드는 CPU 점유를 하지 않음

2. thread_unblock ()

void thread_unblock (struct thread *t)

스레드의 상태를 READY로 변경 및 ready 리스트 넣음
현재 실행 중인 스레드가 아닌, 다른 스레드를 깨우기 때문에 매개변수 필요
"enum intr_level old_level " (인터럽트 비활성화)
- 다른 스레드에 의해 스케줄링 상태 변동될 수 있기 때문에 인터럽트 비활성화 필요

✨ 그 외 기타 스레드 함수

- idle ()

static void idle (void *idle_started_ UNUSED)

시스템에 실행 가능한 다른 스레드가 없을 때 주로 사용
- ready_list에 준비된 스레드가 없는 경우
- 시스템이 놀고 있는 동안 CPU 점유
모든 스레드가 BLOCKED 상태
전력 관리 및 대기 상태 유지
- idle 함수에 hit 명령어를 통해 CPU가 놀고 있을 때 전력 소비 줄임
항상 실행할 스레드를 가지게하여 스케줄링이 끊기지 않도록 보장

- kernel_thread ()

static void kernel_thread (thread_func *function, void *aux)

커널 스레드가 생성될 때 해당 스레드의 실행을 관리
- 새로 생성된 커널 스레드의 메인 함수 역할
작업이 끝나면 스레드 종료
파일 시스템 관리, 메모리 관리, 드라이버와 상호작용 같은 작업 담당
하드웨어에 직접 접근하고, 메모리와 CPU자원을 직접 관리

- next_thread_to_run ()

static struct thread *next_thread_to_run (void)

스케줄러가 다음에 실행 할 스레드를 결정하는 데 사용
다음에 실행할 스레드를 ready list에 제거하고 반환
리스트가 비어 있으면 idle thread 실행되도록 함

- do_iret ()

void do_iret (struct intr_frame *tf)

CPU 레지스터와 세그먼트 레지스터의 값 복원
인터럽트 반환(iretq)를 통해 사용자 모드 또는 커널 모드로 복귀
context switch 같이 중단된 프로그램의 상태를 복구하여 정상적인 실행 흐름으로 돌아감

- do_schedule ()

static void do_schedule(int status)

현재 스레드의 상태 변경 및 메모리 해제 요청이 필요한 경우
- schedule에서 상태 변경 및 메모리 해제가 추가됨
내부에 schedule 함수 포함

- schedule ()

static void schedule (void)

다음 스레드의 상태를 RUNNING으로 변경
thread_ticks는 0으로 초기화
스레드의 상태가 DYING인 경우 destruction 리스트에 삽입
현재 스레드와 다음 스레드와 contest switch

- allocate_tid ()

static tid_t allocate_tid (void) {
	static tid_t next_tid = 1;
	tid_t tid;

	lock_acquire (&tid_lock);  // tid 할당 시 동시 접근 방지
	tid = next_tid++;
	lock_release (&tid_lock);

	return tid;
}

next_tid는 정적 변수로 여러번 호출되더라도 값 유지
lock_acquire를 사용하여 tid 할당 중 다른 스레드 동시 접근 제어
lock_release를 사용하여 tid 할당이 완료되면 락 해제

✨ 타이머

1. timer_init ()

void timer_init (void)

PintOS의 타이머 시스템 초기화
일정한 주기로 인터럽트 발생
각 스레드의 시간 관리, 스케줄링, 시간 지연 기능을 가능하게 함

2. timer_interrupt ()

void timer_interrupt(struct intr_frame *args UNUSED)

시스템의 ticks 값을 증가하여 시간 추적
thread_tick을 통해 선점형 스케줄링 지원
- 현재 스레드의 실행 시간 관리
깨어날 시간이 된 스레드를 READY 상태로 전환 후 스케줄링에 참여

✨ 세마포어

세마포어 예시

struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

struct semaphore file_sema; // 파일 시스템에 대한 접근을 관리하는 세마포어
struct semaphore io_sema;   // 입출력에 대한 접근을 관리하는 세마포어
struct semaphore sync_sema; // 동기화 작업을 위한 세마포어

위의 예시와 같이 필요한 조건의 세마포어 생성

- 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, thread_compare_priority, 0);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

맨 처음 왜 current thread를 wait list에 보내는지 의문
- current thread가 sema_down이 실행됐다는게, 해당 세마포어 자원이 현재 사용 중으로 아직 자원을 얻지 못함
- 당장 실행 할 수 없으니 자원이 비워질 때까지 대기 상태로 전환
- 때문에 현재 실행 중인 스레드를 wait list에 보내야 함
value > 0 인 경우
- 스레드 실행 후 value - 1
value = 0 인 경우
- sema_down에서는 실행 중이던 스레드가 자원을 기다리기 위해 실행을 일시 중지 (thread_block)
- 스레드가 block 상태에 들어가면, sema_down 함수는 while 루프 안에 멈춰 있음
  - sema_up을 통해 다시 깨어날 때까지 실행되지 않음

- sema_up()

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, thread_compare_priority, 0);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),struct thread, elem));
	}
	
	sema->value++;
	thread_test_preemption();
	intr_set_level (old_level);
}

wait 리스트에 있는 경우, unblock을 통해서 ready 리스트로 삽입
ready list에 스레드를 추가 했기 때문에, CPU 선점 체크
sema의 value ++

- 세마포어 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");
}

/* Thread function used by sema_self_test(). */
static void
sema_test_helper (void *sema_) {
	struct semaphore *sema = sema_;
	int i;

	for (i = 0; i < 10; i++)
	{
		sema_down (&sema[0]);
		sema_up (&sema[1]);
	}
}

세마포어를 이해하기 좋은 테스트이다.
실행 순서
- thread_create를 통해 sema_test_helper 스레드 생성 후 ready 리스트 삽입
- main 스레드에서 sema_up(&sema[0]) 실행
  - sema[0]의 value ++
  - 현재 스케줄링 중인 메인 스레드 일 마치고 서브 스레드 스케줄링 실행
- 서브 스레드에서 sema_down(&sema[0]) 실행
  - value > 0 이기 때문에 block 되지는 않고 sena[0] value --
- 서브 스레드에서 sama_up(&sema[1]) 실행
  - sema[1]에서의 value ++
  - 이후 서브 스레드 반복문 1회 종료
- main 스레드에서 나머지 sema_down(&sema[1]) 실행
  - - value > 0 이기 때문에 block 되지는 않고 sena[0] value --
    - 이후 메인 스레드 반복문 1회 종료
- 위의 과정은 10번 반복한다.

✨ LOCK

- lock_acquire

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->wait_on_lock = lock;
		list_insert_ordered (&lock->holder->donations, &cur->donation_elem, 
					thread_compare_donate_priority, 0);
		donate_priority ();
	}
	
	sema_down (&lock->semaphore);
	cur->wait_on_lock = NULL;
  	lock->holder = cur;
}

Lock을 다른 스레드가 보유하고 있으면, 현재 스레드는 대기
sema_down에서는 락이 해제될 때까지 현재 스레드 대기 상태로 전환
락이 해제된 상태라면 바로 통과 후 세마포어 값 감소

void donate_priority (void)
{
   struct thread *cur = thread_current();
    int depth;

    for (depth = 0; depth < 8; depth++) {
        if (!cur->wait_on_lock)
            break;

        struct thread *holder = cur->wait_on_lock->holder;
        if (holder->priority >= cur->priority)  // 이미 높은 우선순위를 가진 경우 중단
            break;

        holder->priority = cur->priority;
        cur = holder;
    }
}

donate_priority 함수로 우선순위 역전 해결
깊이는 임의의 값 8 사용

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

해당 lock을 가지고 있는 holder의 lock 해제
lock을 사용 할 수 있도록 sema_up

void remove_with_lock (struct lock *lock)
{
  struct list_elem *e;
  struct thread *cur = thread_current ();

  for (e = list_begin (&cur->donations); e != list_end (&cur->donations); e = list_next (e)){
    struct thread *t = list_entry (e, struct thread, donation_elem);
    if (t->wait_on_lock == lock)
      list_remove (&t->donation_elem);
  }
}

현재 스레드가 가지고 있던 lock을 해제 할 때 사용
lock을 기다리며 우선순위를 기부한 스레드들을 현재 스레드의 donations 리스트에서 제거
donation_elem
- ex) thread A가 Lock을 소유하고 있고, thread B가 그 lock을 기다리며 우선순위를 기부한 경우
- thread B의 donation_elem은 thread A의 donations 리스트에 연결

void refresh_priority(void) {
    struct thread *cur = thread_current();
    cur->priority = cur->init_priority;

    if (!list_empty(&cur->donations)) {
        list_sort(&cur->donations, thread_compare_donate_priority, NULL);
        struct thread *highest = list_entry(list_front(&cur->donations), struct thread, donation_elem);
        if (highest->priority > cur->priority)
            cur->priority = highest->priority;
    }
}

현재 스레드의 (기부 받을수 있는) priority를 (원래의) init_priority로 변경
donations 중 우선 순위 정렬
donations 중 우선순위가 가장 높은 스레드의 우선 순위가 현재 스레드의 우선순위보다 높은 경우
- 가장 높은 스레드의 우선 순위 값을 현재 우선 순위에게 기부
현재 우선순위 다시 계산하여 최신 상태로 유지
스레드의 우선순위 변경되거나, 대기 중인 스레드의 우선순위 변경 될 때 호출
기본 우선순위와 기부받은 우선순위 고려하여 현재 스래드 최종 우선 순위 결정

✨ condition variable

특정 조건이 충족될 때까지 스레드가 기다리도록 함
- 조건이 충족될 때까지 스레드가 안전하게 대기
스레드가 조건을 기다리면서 lock을 잠시 놓아 다른 스레드가 자원에 접근할 수 있도록
- 조건 충족되면 다시 lock을 획득하여 작업을 이어감

- 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);
	list_insert_ordered (&cond->waiters, &waiter.elem, sema_compare_priority, 0);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

waiter 구조체 안에 있는 semaphore를 0으로 초기화
waites 리스트에 waiter를 우선순위에 따라 삽입
현재 스레드가 가지고 있던 lock 해제
- 다른 스레드가 이 lock을 사용 할 수 있도록
- lock을 가지고 있으면 다른 스레드가 자원을 사용하지 못함
sema_down에서 현재 스레드를 대기 상태로 전환
- waiter.semaphore = 0 이므로 sema_down을 호출하면 스레드는 대기 상태
- (대기 상태는 cond_signal, cond_broadcast를 통해 깨울 수 있음)
lock_acquire를 호출하여 lock을 다시 획득

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

조건 변수를 기다리는 스레드 중 하나를 깨우는 역할
waiters를 우선순위대로 정렬
sema_up은 semaphore_elem에 연결된 세마 포어을 값을 증가 시킴
- sema_up을 통해서 세마포어의 값을 증가시켜 대기중인 스레드 깨움

'크래프톤 정글' 카테고리의 다른 글

Pintos Project2 - User Programs 키워드 (0)	2024.11.21
Pintos Project2 - ELF 파일 (0)	2024.11.21
Pintos Project1 - Priority Scheduling (2) (0)	2024.11.07
Pintos Project1 - Priority Scheduling (1) (2)	2024.11.07
Pintos Project1 - Alarm Clock (1) (0)	2024.11.05

현재글Pintos Project1 - 스레드 전반적인 흐름 잡기

Jerry의 컴퓨터 일기 💻

connecting the dots

Today :
Yesterday :

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Jerry의 컴퓨터 일기 💻

Pintos Project1 - 스레드 전반적인 흐름 잡기

✨ 스레드

✨ 프로그램 스레드 실행

1. thread_init ()

2. thread_start ()

3. thread_create ()

✨인터럽트

1. intr_enable ()

2. intr_disable()

✨ 스레드 상태 변화

1. thread_block ()

2. thread_unblock ()

✨ 그 외 기타 스레드 함수

- idle ()

- kernel_thread ()

- next_thread_to_run ()

- do_iret ()

- do_schedule ()

- schedule ()

- allocate_tid ()

✨ 타이머

1. timer_init ()

2. timer_interrupt ()

✨ 세마포어

- sema_down()

- sema_up()

- 세마포어 self-test

✨ LOCK

- lock_acquire

- lock_release

✨ condition variable

- cond_wait

- cond_signal

'크래프톤 정글' 카테고리의 다른 글

'크래프톤 정글'의 다른글

티스토리툴바

Pintos Project1 - 스레드 전반적인 흐름 잡기

✨ 스레드

✨ 프로그램 스레드 실행

1. thread_init ()

2. thread_start ()

3. thread_create ()

✨인터럽트

1. intr_enable ()

2. intr_disable()

✨ 스레드 상태 변화

1. thread_block ()

2. thread_unblock ()

✨ 그 외 기타 스레드 함수

- idle ()

- kernel_thread ()

- next_thread_to_run ()

- do_iret ()

- do_schedule ()

- schedule ()

- allocate_tid ()

✨ 타이머

1. timer_init ()

2. timer_interrupt ()

✨ 세마포어

- sema_down()

- sema_up()

- 세마포어 self-test

✨ LOCK

- lock_acquire

- lock_release

✨ condition variable

- cond_wait

- cond_signal

'크래프톤 정글' 카테고리의 다른 글

'크래프톤 정글'의 다른글

관련글

티스토리툴바