Operating System (PintOS 프로젝트 1-1)

정글에 들어온지 8주차... 드디어 악명높은 PintOS 프로젝트 주간이 찾아왔다. mallocklab, webserver 프로젝트와 마찬가지로 처음 배우는 주제이다 보니 방대한 양의 새로운 지식을 빠르게 습득하는 과정은 역시 쉽지 않았다. 하지만, 팀원들과 lock, semaphore 등의 기능과 여러 함수들의 역할들에 대해 치열하게 논쟁하며 이해하는 과정을 통해 결국 주어진 시간 안에 목표를 달성할 수 있어 만족스럽게 한 주를 마무리 할 수 있었다. 아직 이해가 부족한 부분이 많지만 이해한 부분 까지는 가볍게 정리해 보고자 한다.

주요 개념

프로세스

프로세스(process)는 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말한다. 종종 스케줄링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미로 쓰인다.(위키백과)

프로세스는 각각 독립된 메모리 영역(code, data, stack, heap의 구조)을 할당받는다. 기본적으로 프로세스당 최소 1개의 스레드(메인 스레드)를 가지고 있다. 각 프로세스는 별도의 주소공간에서 실행되며, 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근할 수 없다.

프로그램

프로그램은 일반적으로 하드 디스크 등에 저장되어 있는 실행코드를 뜻하고, 프로세스는 프로그램을 구동하여 프로그램 자체와 프로그램의 상태가 메모리 상에서 실행되는 작업 단위를 지칭한다. 예를 들어, 하나의 프로그램을 여러 번 구동하면 여러 개의 프로세스가 메모리 상에서 실행된다.(위키백과)

스레드

스레드(thread)는 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위를 말한다. 일반적으로 한 프로그램은 하나의 스레드를 가지고 있지만, 프로그램 환경에 따라 둘 이상의 스레드를 동시에 실행할 수 있다. 이러한 실행 방식을 멀티스레드(multithread)라고 한다.(위키백과)

즉, 프로세스의 특정한 수행 경로라고 할 수 있으며, 프로세스가 할당받은 자원을 이용하는 실행의 단위이다. 스레드는 프로세스 내에서 각각 stack만 따로 할당받고 code, data, heap 영역은 공유한다.

프로세스 스케쥴링

여러개의 프로세스가 시스템 내 존재하므로 자원을 할당할 프로세스를 선택해야한다. 자원 관리는 시간과 공간(메모리)을 분할하여 관리할 수 있다. 프로세스 스케줄링은 프로세서 사용시간을 프로세스들에게 분배하는 작업이다.

목적

• 시스템의 성능향상
• 대표적 시스템 성능 지표
  • 응답시간(response time)
    작업 요청(submission)으로부터 응답을 받을때까지의 시간
• 작업처리량(throughput)
  • 단위 시간 동안 완료된 작업의 수
• 자원 활용도(resource utilization)
  • 주어진 시간(Tc) 동안 자원이 활용된 시간(Tr)
• 공평성
• 실행 대기 방지
• 예측 가능성 등...

스케줄링 기준

• 스케줄링 기법이 고려하는 항목들
• 프로세스의 특성
  • I/O-bounded or compute-bounded
• 시스템 특성
  • Batch system or interactive system
• 프로세스의 긴급성
• 프로세스 우선순위
• 프로세스 총 실행 시간 등...

스케줄링의 단계

발생하는 빈도 및 할당 자원에 따른 구분

• Long-term scheduling
  • Job scheduling
  • 시스템에 제출 할(kernel에 등록할) 작업 결정
  • 다중프로그래밍 정도(degree) 조절(시스템 내 프로세스 수 조절)
  • I/O-bounded와 computed_bounded 프로세스들을 잘 섞어서 선택해야함
  • 시분할 시스템에서는 모든 작업을 시스템에 등록(롱텀 불필요)
• Mid-term scheduling
  • Memory allocation
  • swapping(swap-in/swap-out)
• Short-term scheduling
  • Process scheduling
  • interrupt, block(I/O), time-out 등
  • 매우 빨라야함

스케줄링의 정책

• 선점(Preemptive scheduling) vs 비선점(Non-preemptive scheduling)

  • 선점: 타의에 의해 자원을 빼앗길 수 있음(할당 시간 종료, 우선순위 높은 프로세스 등장)
    장점 - context switch overhead가 적음
    단점 - 잦은 우선순위 역전, 평균 응답 시간 증가

  • 비선점: 할당 받은 자원을 스스로 반납할 때까지 사용
    단점 - context switch overhead가 큼
    time-sharing system, real-time system 등에 적합

• 우선순위(Priority)

  • 정적 우선순위
    • 프로세스 생성시 결정된 우선순위가 유지
    • 시스템 환경변화에 대한 대응이 어려움
  • 동적 우선순위
    • 프로세스 상태 변화에 따라 우선순위 변화
    • 구현이 복잡, 우선순위 재계산 overhead가 큼

Basic Scheduling algorithms

• FIFO
  • 비선점
  • 도착시간 기준
  • high resource utilization(자원을 효율적 사용가능)
  • batch system에 적합, interactive system에 부적합
  • 단점 : convoy effect(긴 대기시간), 긴 평균 응답시간
• RR(round-robin)
  • 선점
  • 도착시간 기준
  • 자원 사용 제한 시간(time quantum)이 있음
  • 할당된 시간이 지나면 자원 반납
  • 특정 프로세스의 자원 독점 방지
  • context switch overhead가 큼
  • 대화형, 시분할 시스템에 적합
• SPN(shortest-process-next)
  • 비선점
  • 실행시간(burst time) 기준
  • 평균 대기시간 최소화
  • 시스템 내 프로세스 수 최소화 -> 스케줄링 부하 감소, 메모리 절약, 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답시간 제공
  • starvation(무한대기) 현상 발생
  • 정확한 실행시간 알 수 없음
• SRTN(shortest remaining time next)
  • SPN의 변형
  • 선점
  • 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
  • 구현 및 사용이 비현실적
• HRRN(high-response-ratio-next)
  • SPN의 변형
  • aging concepts
  • 𝑹𝒆𝒔𝒑𝒐𝒏𝒔𝒆𝒓𝒂𝒕𝒊𝒐 = (𝑾𝑻+𝑩𝑻) / 𝑩𝑻 (응답률)
  • SPN의장점+ Starvation 방지
    
• MLQ(multi-level queue)
  • 작업(or 우선순위)별 별도의 ready queue를 가짐
  • Queue 사이에는 우선순위 기반의 스케줄링 사용
  • 최초 배정된 큐 벗어나지 못함
  • 각각의 큐는 각자의 스케줄링 방법 사용
  • 여러개의 Queue 관리 등 스케줄링 overhead
  • 우선순위 낮은 큐는 starvation 발생 가능
• MFQ(multi-level feedback queue)
  • 프로세스의 큐간 이동이 허용된 MLQ
  • 피드백을 통해 우선순위 조정
  • dynamic priority
  • 선점
  • Favor short burst-time processes
  • Favor I/O bounded processes
  • Improve adaptability
  • 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
  • 설계 구현이 복잡, starvation 문제, 스케줄링 overhead가 큼
  • 변형 - 큐마다 시간 할당량 다르게 배정, aging, 입출력 위주 프로세스들을 상위단계 큐로 이동 등...
  

PintOS 프로젝트 1-1 Alarm Clock

PintOS 프로젝트의 첫번째 미션은 Alarm Clock의 코드를 수정하는 것이다. PintOS 기본코드에는 Alarm Clock이 busy-waiting 기법으로 구현이 되어 있는데, busy-waiting은 while 문을 돌며 thread_yield()를 반복 호출한다. 즉, CPU를 계속해서 점유하면서 대기하고 있는 상태이므로 CPU 자원이 낭비 되고, 소모 전력이 불필요하게 낭비될 수 있다. 따라서 sleep / wake up을 이용해 다시 구현해야 한다.

busy waiting

# timer.c

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

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

sleep / wake up

# timer.c

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	thread_sleep(start+ticks);
}



static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
   	/*-------------------- Project1 -------------------------------------*/
	int64_t next_tick;
	next_tick = get_next_tick_to_awake();
	if (ticks >= next_tick)
	{
		thread_awake(ticks);
	}
	/*-------------------- Project1 -------------------------------------*/
}

# thread.c

void thread_sleep(int64_t ticks)
{
	// printf("\njoin : thread_sleep\n");
	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);
	}
	// list_push_back(&sleep_list, &curr->elem);

	update_next_tick_to_awake(ticks);
	do_schedule(THREAD_BLOCKED);
	intr_set_level(old_level);
}

/* ticks와 next_tick_to_awake를 비교하여 작은 값을 넣는다.*/
void update_next_tick_to_awake(int64_t ticks)
{
	next_tick_to_awake = MIN(next_tick_to_awake, ticks);
}

int64_t get_next_tick_to_awake(void)
{
	return next_tick_to_awake;
}



void thread_awake(int64_t ticks)
{
	next_tick_to_awake = INT64_MAX;
	struct list_elem *e= list_begin(&sleep_list);
	struct thread *t;

	for (e ; e != list_end(&sleep_list);)
	{
		t = list_entry(e, struct thread, elem);
		if (t->wakeup_tick <= ticks)
		{
			e = list_remove(&t->elem);
			thread_unblock(t);
		}
		else
		{
			update_next_tick_to_awake(t->wakeup_tick);
			e = list_next(e);
		}
	}
}