Pintos Project1 - Alarm Clock

Jocy·2022년 5월 25일

Process와 Thread

Process

Process는 프로그램이 메모리에 적재되어 컴퓨터에서 실행되고 있는 프로그램을 말하며
CPU의 스케쥴링의 대상이 되는 작업(task)
Multi-Process(멀티프로세스)는 여러개의 프로세스를 통해서 동시에 두 가지 이상의 일을 병렬 수행
프로세스 중 문제가 발생되더라도 다른 프로세스를 이용해서 처리할 수 있는 장점이 있습니다.

Thread

Thread(스레드)는 Process 내에서 실행되는 흐름의 단위
하나의 프로세스 내에서 두 개 이상의 스레드가 실행하는 경우는 Multi-Thread(멀티스레드) 라고 합니다.
여러 작업이 동시에 되는 Multi-Process(멀티프로세스)와 공통점이 있지만,
멀티프로세스는 프로세스 별로 개별적으로 메모리 공간을 차지하지만
멀티스레드는 프로세스 내의 메모리를 공유하여 사용할 수 있다는 차이점이 존재합니다.
그렇기 때문에 일부 스레드에 문제가 생기면 다른 스레드에도 영향을 줄 수 있는 단점이 존재합니다. 추가적으로 멀티스레드는 스택 영역은 개별적으로 사용 합니다.

멀티쓰레드는 자원을 공유하는 특성 때문에 Pintos 의 쓰레드 설계는
쓰레드간의 동기화(Synchronization) 고려해야 합니다.
이런 특성을 고려하여 Pintos Project1에서 구현하고자 하는 것은 크게 3가지이다.

Alarm clock : 실행중인 스레드를 잠시 재웠다가 일정 시간이 지나면 다시 깨우도록 하는 기능

Priority Scheduling : Ready 상태의 리스트에 가장 높은 priority를 가진 쓰레드가 Running 상태가 될 수 있도록 만들어주는 것

Advanced Scheduler : 실행이 안되는 우선순위가 낮은 쓰레드들의 priority를 조절해서 실행하는 방법(MLFQ)

Project 1-1 : Alarm Clock

busy-waiting 문제점

현재 Alarm Clock 기능은 비효율적으로 많은 CPU 시간을 낭비하는 busy-waiting 방식으로 구현
아래의 그림과 같이 Ready <-> Running 의 상태를 반복적으로 수행하게 됨

Sleep/Awake 구현

이러한 문제점을 개선하기 위해 sleep_list에서 block state로 관리하고 wake 시간이 되기 전까지는 Ready 상태에 포함되지 않다가 시간이 되었을 때 Ready로 바꿔서 진행합니다.

1. wakeup 변수, sleep, awake 함수의 프로토타입 추가

일어나야할 시간을 기록하는 변수와 추후에 사용할 sleep, awake 함수를 위한 프로토 타입 추가

/* thread/thread.h */
struct thread{
    ...
    int64_t wakeup; // 깨어나야 하는 ticks 값
    ...
    void thread_sleep(int64_t ticks);
	void thread_awake(int64_t ticks);
    ...
}

2. sleep_list 를 추가하고 초기화

/* thread/thread.c */
static struct list sleep_list;

void thread_init (void) 
{
  ...
  list_init (&ready_list);
  list_init (&sleep_list);
  ...
}

3. 쓰레드들의 일어날 시간을 저장하고 sleep_list에 추가, 스레드 상태를 block state

idle_thread는 sleep 되지 않도록해서 CPU가 항상 실행 상태를 유지
sleeplist함수에 list_insert_order를 사용하여 wakeup시간 순서대로 정렬하면
추후에 ready상태의 elem들을 불러오는 리소스를 줄이는데 용이합니다.

/* thread/thread.c */
void
thread_sleep (int64_t ticks)
{
  struct thread *cur;
  enum intr_level old_level;

  old_level = intr_disable ();	// 인터럽트 off
  cur = thread_current ();
  
  ASSERT (cur != idle_thread);

  cur->wakeup = ticks;			// 일어날 시간을 저장
  list_push_back (&sleep_list, &cur->elem);	// sleep_list 에 추가
  thread_block ();				// block 상태로 변경

  intr_set_level (old_level);	// 인터럽트 on
}

4. timer_sleep() 함수의 while문 수정

timer_sleep함수로 스레드들의 wakeup 시간을 정하고 block 상태로 변경합니다.

/* devices/timer.c */
void 
timer_sleep (int64_t ticks) 
{
  int64_t start = timer_ticks ();
  thread_sleep (start + ticks);
}

5. thread_awake 함수 추가

sleep_list를 돌면서 일어날 시간이 지난 스레드들을 찾아서 Ready 리스트로 옮기고, 스레드 상태를 ready state 로 변경합니다.

/* thread/thread.c */
void
thread_awake (int64_t ticks)
{
  struct list_elem *e = list_begin (&sleep_list);

  while (e != list_end (&sleep_list)){
    struct thread *t = list_entry (e, struct thread, elem);
    if (t->wakeup <= ticks){	// 스레드가 일어날 시간이 되었는지 확인
      e = list_remove (e);	// sleep list 에서 제거
      thread_unblock (t);	// 스레드 unblock
    }
    else 
      e = list_next (e);
  }
}

6. timer_interrupt 함수 수정

timer interrupt 함수로 인해 ticks가 증가하면서 깨워야할 스레드를 찾고 깨워줍니다.

/* devices/timer.c */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
  ticks++;
  thread_tick ();
  thread_awake (ticks);	// ticks 가 증가할때마다 awake 작업 수행
}