[크래프톤 정글 3기] 11/25(토) TIL

ClassBinu·2023년 11월 25일
0

크래프톤 정글 3기 TIL

목록 보기
43/120

08:13 입실
'점심 전까지 제발 바쁜 대기(Busy Waiting) 이해하고 싶다..'
라고 생각했는데 스타벅스 걸어오면서 같은 반 수강생에게 설명하다 보니까 자연스럽게 이해버렸다..?

Pintos

idle state(유휴 상태)

컴퓨터 시스템에서 CPU나 다른 자원이 현재 활동적으로 사용되지 않고, 어떤 작업도 수행하지 않는 상태

바쁜 대기라는 증거

이 시점에서 스레드1은 이미 처리 완료

즉, 현재 코드의 문제는 스레드가 준비큐에서 실행상태로 순차적으로 변경되고, 더 이상 스위칭이 필요 없을 때도 계속해서 스위칭을 반복해서 cpu의 비효율을 야기하는 것!

바쁜 대기 진짜 이해함!

자, 먼저 결과에 나오는 idle은 실행 상태가 CPU 유휴 상태라는 뜻이다.
이걸 '효율적으로 cpu를 점유한 상태'라고 잘못 생각해서 계속 이해 못한 거였음.
유휴 상태는 굳이 CPU를 쓸 필요가 없으면 CPU가 쉬고 있는 상태라고 이해.
(사실 다른 스레드가 있으면 그 스레드 처리하면 되는데 지금은 main 스레드가 하나만 있는 상황이라면 그냥 CPU가 유휴 상태인 게 나음.)

일드 전후로 현재 스레드를 출력해보면 순차적으로 스레드가 바뀌다가
어느 순간에 하나씩 빠진다.(터미네이트)
즉, 스레드가 실행 상태로 올라가면 일정 시간 동안 스레드가 조금씩 처리되다가
처리가 끝나면 터미네이트 되는 것.

그런데 스레드가 모두 출력이 되고 난 다음에 메인 스레드를 계속해서 번갈아가면서 스위칭이 일어나고, cpu를 점유한다. 그래서 테스트 결과에 커널 틱이 가득 차 있는 것!!
이게 바로 바쁜 대기!

이걸 대기 큐를 이용해서 메인이 계속해서 스위칭이 일어나는 게 아니라,
인터럽트로 대기 시킨 다음에 틱을 유휴 상태로 보내다가, 딱 필요할 때만 가져와서 처리하는 방식으로 수정해야 한다!!!

이제 대기 방식을 바꿔서 불필요한 kernel ticks를 줄이고, idle ticks를 늘리면 됨!

이건 왜 문제였을까?

처음에 생각한건, 그냥 스위칭을 한번만 하면 되지 않을까?
하는거였음.

/* 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)
	{
		printf("current: %s\n", thread_name());
	}
	thread_yield();
}

어림도 없지. 계속해서 main이 틱마다 점유하고 있는 상태임. 게다가 테스트 실패함. 아마 스레드를 처리하지 못해서?

구현해 보기!!

바쁜 대기 이해했으니까 이제 개선해보자.

필요한 것

  • ready_list가 아닌 sleep상태 스레드를 관리할 sleep_list
  • 스레드를 블록 상태로 바꿔주는 것
  • 인터럽트를 발생시켜서(sleep), 실행 중인 스레드를 sleep_list로 넣는 것
  • 인터럽트를 발생시켜서(awake), 스레드를 sleep_list에서 ready_list로 넣는 것

찾아보기

  • sleep_list는 기존 list 구조체를 사용하면 됨
/* 준비 상태 이전의 대기큐입니다. */
static struct list sleep_list;

구현 아이디어

sleep_list는 기존 list 구조체를 활용해서 간단히 생성!

  1. sleep_list 생성하고 초기화!
void
thread_init (void) {
	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 (). */
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&sleep_list); // 슬립 리스트 초기화
	list_init (&destruction_req);

	/* 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. 별도 변수는 만들지 않고 종료 시점을 스레드 구조체에 추가함!
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. */

	/* 깨어나야 할 틱 저장 */
	int64_t wake_up_ticks
  1. 기존 timer에서 현재 스레드 블록 처리하고, 스레드에 다시 일어나야 되는 시간 기록!
    최대한 함수 안 만들고 기존 구현된 함수 구현하기
void timer_sleep(int64_t ticks)
{
	int64_t start = timer_ticks();
	int64_t end = start + ticks;

	ASSERT(intr_get_level() == INTR_ON);
	// while (timer_elapsed(start) < ticks)
	// 	thread_yield();
	/* 현재 스레드에 깨어날 틱을 추가하고 sleep처리 */
	struct thread *current = thread_current();
	current->wake_up_ticks = start + ticks;
	thread_sleep();
}
  1. thread_yield 대체할 thread_sleep() 생성
/* 현지 실행 중인 스레드를 대기 상태로 변경하고 대기큐에 삽입합니다. */
void thread_sleep(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(&sleep_list, &curr->elem);
	do_schedule(THREAD_BLOCKED);
	intr_set_level(old_level);
}
  1. 매 틱마다 실행되는 tick 함수에 sleep_list 탐색 코드 추가!
void thread_tick(void)
{
	/* sleep_list에 awake_up_ticks가 만료된 스레드가 있는지 검색 */
	struct thread *t = thread_current();
	int64_t current_ticks = timer_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->wake_up_ticks <= current_ticks)
		{
			e = list_remove(e); // 스레드를 목록에서 제거
			thread_unblock(t);	// 스레드 깨우기
		}
		else
		{
			e = list_next(e);
		}
	}
    
 // (생략)

리스트에서 스레드 정보를 가져오는 함수 list_entry()에 대해서 더 자세히 알아보기

코드 컨벤션 때문에 브랜치 새로 파서 다시 했는데 sleep_list 초기화 안 해서 계속 오류 남.. 하나씩 코드 뜯어가면서 찾았다.. 2시간 걸림.. 읔..

idle thread

언제나 한 번에는 하나의 쓰레드만이 실행되고 나머지들은 (만약 있다면) 모두 비활성화 됩니다. 스케쥴러는 다음 실행할 쓰레드를 결정합니다. 만약 다음으로 실행할 쓰레드가 없다면 idle 쓰레드라는 특별한 쓰레드를 실행합니다. (idle 쓰레드는 idle()로 실행됩니다.) 동기화 함수는 하나의 쓰레드가 다른 쓰레드가 뭔가를 하는 것을 기다려야 할 때 문맥교환(context switch) 을 강제 진행합니다.

idle 쓰레드는 일종의 더미 쓰레드라고 할 수 있다!

스케줄링 다시 복습

FCFS(First Come, First Serve)

선입 선처리
비선점형 스케줄링(새치기 불가 스케줄링)
레디큐를 FIFO로 구현하면 됨

선입선처리를 처리 시간이 오래 걸리는 프로세스가 자원을 점유할 때,
나머지 프로세스의 대기 시간이 계속 길어져서 전체적을 평균 대기 시간이 올라가는 문제

호위 효과(convoy effrect)
긴 CPU bust를 가진 프로세스 때문에 다른 프로세스들이 오래 기다림.
즉, 나머지 프로세스가 큰 프로세스를 줄줄줄 따라 다니는 호위 행렬처럼 보임.

SJF(Shortest Job First, SJF)

최소 작업 우선 스케줄링
비선점형 스케줄링

대기 중인 프로세스들 중에 가장 짧은 CPU burst를 갖는 프로세스를 우선 선택
동일 수행시간이라면 FCFS로 처리
평균 대기 시간이 가장 작음(최적)
근데 CPU burst 파악이 어려움.(미래를 예측해야..? 불가능)
그래서 CPU Burst를 추정하는 방식으로 작동함.

SRTF(Shortest Remaining Time First)

최소 잔여 시간 우선 스케줄링
선점형 스케줄링
(남는 시간이 짧은 프로세스가 새치기해서 먼저 처리됨.)

Priority

우선순위 스케줄링
프로세스에 기록된 가장 높은 우선순위를 가진 프로세스에게 CPU 할당

Round Robin(RR)

순환 할당 스케줄링
시분할 시스템
규정 시간량(시간 할당량)에 따라 선점
시간이 만료되어 타이머에서 완료 인터럽트 발생 시 디스패치
선점형 FCFS라고 볼 수 있음.
일반적으로 평균 대기 시간은 길다.

Multilevel Queue(MLQ)

다단계 큐 스케줄링

프로세스들 간에 우선순위에 따라 상이한 큐로 나뉘어서 대기
각각의 프로세스는 큐에 고정됨(큐를 바꿀 수 없음.)
각 큐별로 개별의 알고리즘으로 작동 가능

Multilevel Feedback Queue(MLFQ)

다단계 피드백 큐
가장 일반적인 CPU 알고리즘
큐 간의 프로세스 이동 가능

Highest Response Rate Next(HRN)

가변적 우선 순위 =
(대기 시간 + 서비스를 받을 시간) / 서비스를 받을 시간

운영체제(아주 쉬운 세 가지 이야기)

교재 가볍게 훑어가면서 읽기!

운영체제의 근간

  1. 가상화(가상 메모리)
  2. 병행성(프로세스, 스레드)
  3. 영속성(파일 시스템)

개요

프로그램의 역할

반입(fetch) -> 해석(decode) -> 실행(execute)
이게 폰 노이만 구조임!

시스템 콜 vs 프로시저 호출

시스템 콜은 제어를 운영체제에게 넘길 때,
하드웨어 특권 수준으로 상향 조정

trap이라는 하드웨어 명령어에 의해 모출되고,
트랩 핸들러 함수에게 제어권을 넘긴다.

커널모드

커널모드에서는 충돌이 발생하면 커널 패닉, 시스템 크래시가 발생하며 시스템에 심각한 영향을 미침.
유저 모드에서는 충돌이 일어나도 시스템과 무관함.

컨널 모드, 유저 모드가 필요한 이유는 하드웨어를 비롯한 시스템의 보호를 위해서임!
그래서 진짜 필요할 때만 잠깐 커널 모드로 특권 명령어를 실행하고,
나머지는 유저 모드로 위험한 명령어는 작동 안 시키는 것!

가상화

복숭아가 있다고 치자..

오.. 가상화는 뭔가 은행에 예치된 돈이 찍힌 통장과 같은 것.
사실 은행은 그 많은 돈을 다 보유하고 있지 않지만 가상화를 통해 마치 돈이 있는 것처럼 가상화 함.
즉, 실물의 현금을 여러 사람이 공유하고 있는 것과 같음. 지급준비율의 개념을 차용..?
컴퓨터가 결국 현실의 원리와 철학이 반영된 분야임.

프로세스

프로세스는 실행 중인 프로그램이다.
프로그램의 인스턴스라고 표현!

프로세스 API(시스템 콜)

  • fork()
    프로세스 생성
    이때 생성된 프로세스는 이 함수를 호출한 프로세스의 복사본(자식)이다!
    이거 중요!!
    이때 부모는 자식의 PID를 반환받고,
    자식은 0을 반환받는다.
    (약간 트리 같은 느낌..?)
    그 후 준비 상태가 됨.

  • wait()
    실행을 잠시 중지
    자식이 종료될 때 부모는 자식의 종료 상태를 수집하기 위해 원래 자신의 실행 흐름을 블록시키고, 자식이 종료될 때까지 기다림. 자식이 종료되면 자식의 자원 등을 반납하고 다시 자신이 원래 실행 흐름으로 돌아감.

  • exec()
    자기 자신이 아닌 다른 프로그램을 실행할 때 사용
    fork()가 자신의 복사본을 만들어서 실행한다면,
    exec()는 다른 프로그램의 실행한다.
    이때 새로운 프로세스를 만드는 게 아니라 생성된 프로세스의 코드 세그멘트와 정적 데이터 부분을 엎어 쓰는 것. 힙과 스택은 초기화된다.

exec() 는 특정 함수가 아니다. 비슷한 기능의 여러 함수의 시리즈이다.

  • execl(): 프로그램의 경로와 명령줄 인자를 명시적으로 나열하여 실행합니다.
  • execp(): 시스템의 PATH 환경 변수를 사용하여 실행 파일을 찾고, 명령줄 인자를 명시적으로 나열하여 실행합니다.
  • execlp(): execl()과 execp()의 기능을 결합한 형태입니다.
  • execv(): 프로그램의 경로와 명령줄 인자 배열을 사용하여 실행합니다.
  • execvp(): execv()와 execp()의 기능을 결합한 형태입니다.
  • execve(): 프로그램의 경로, 명령줄 인자 배열, 그리고 환경 변수 배열을 사용하여 실행합니다.

fork() 이후에 흔히 수행되는 작업은 자식 프로세스가 exec() 시리즈 함수 중 하나를 호출하여 새로운 프로그램을 실행하는 것. 이를 통해 자식 프로세스는 독립적인 작업 또는 서비스를 수행할 수 있음.

fork()와 exec() 구분하는 이유는 이 조합이 프로세스를 생성하고, 뭔가 세팅을 하고 그 후에 실행을 할 수 있는 방법이기 때문!

자료 구조

운영체제에는 다양한 자료 구조가 있다.

  • 프로세스 리스트
  • 레지스터 문맥(context)
  • 프로세스 제어 블럭(PCB)

context는 프로세스만 있는 게 아니었다. 레지스터도 context가 있다. 레지스터 context도 스위칭이 일어남!

제한적 직접 실행(Limited Direct Execution)

CPU 가상화가 제한적 직접 실행임!
문맥 교환 등을 통해 cpu가 여러 개인 것처럼 쓸 수 있는데 이때, 커널와 유저를 나누어서 제한적으로 직접 실행한다.

프로세스를 CPU에서 제한 없이 직접 실행하면 하드웨어 접근 등 모든 명령어를 제한 없이 실행할 수 있음.

그래서 trap table을 만들고 이를 통해 시스템을 통제한다. 즉, 프로세스는 CPU에서 직접적으로 실행되기는 하지만 일부 제한을 받는다.

시스템 콜이 발생하면 trap table을 통해 어떤 핸들러(메모리 위치)를 실행해야 할지 알려준다.

너무 궁금했던 게 책에 있었다!!
시스템 콜은 왜 일반적인 프로시저 콜처럼 생겼을까?

사실 시스템 콜도 평범한 C함수임.
대신 시스템 콜 부분은 어셈블리어로 작성되어 있음.
하지만 이 시스템 콜은 내부에서 trap을 호출한다.
시스템 콜이 호출되면 시스템 콜은 인자와, open()에 해당하는 시스템 콜을 커널과 약속된 메모리 공간이나 레지스터에 저장. (모든 시스템 콜은 고유 번호가 있음)

그리고 trap 명령어를 실행.
(trap은 하드웨어에서 발생하는 이벤트)

이때 제어권이 커널로 넘어감.

trap이 실행되고 특권 명령어가 실행되고 난 후 c라이브러리가 시스템 콜의 리턴값을 읽고, 제어권을 시스템 콜을 호출한 프로그램에게 다시 넘긴다.

트랩 테이블은 커널이 부팅 시에 만든다.

그럼 사용자가 직접 시스템 콜을 실행시키면 되는거 아닌가?
시스템 콜의 코드 위치는 운영체제만 알고 있고 응용 프로그램은 모른다.

하드웨어에게 트랩 테이블의 위치를 알려주는 건 매우 강력한 기능! 이것 또한 특권 명령어임.

시스템 콜을 공부하면서 느낀 점. 웹의 프론트와 백엔드와 비슷하다.
유저 영역을 프론트엔드, 크널 영역을 백엔드(데이터베이스)로 본다면 비슷하다.
즉, API요청(시스템 콜)을 통해 제한적으로 백엔드와 데이터베이스에 접근시키고 나머지는 유저 모드에서 동작해야 한다!
그래서 사용자의 입력값을 주의해야 한다. 시스템 콜도 인자로 넘어온 값으로 커널 영역에 메모리에 접근한다 거나 문제를 막아야 하는 것처럼, 웹도 sql 인젝션과 같은 기법 등으로 데이터베이스 등에 접근하게 되는 문제나, 백엔드의 관리자 권한을 탈취당하는 일 등을 방지해야 한다!

협조 방식 인터럽트 vs 비협조 방식 인터럽트

Cooperative vs Non-Cooperative

협조 방식

인터럽트를 보내면 그걸 받는 프로세스가 중단 여부를 결정
소프트웨어 인터럽트, 웹 브라우저 확장

비협조 방식

하드웨어, 또는 커널이 인터럽트를 자동으로 처리
시스템 안정성 높이고 프로세스 간 협력 없이도 인터럽트 처리 보장
대표적으로 하드웨어 인터럽트, 타이머 인터럽트, 시스템 콜

스케줄링

스케줄링 평가 항목

반환 시간(turnaround time) = 작업 완료 시각 - 작업 도착 시간

응답 시간(response time) = 스케줄 되는 시간 - 작업 도착 시점
(선점형 방식에서 중요)

profile
ClassBinu
이전 포스트

[크래프톤 정글 3기] 11/24(금) TIL

다음 포스트

[크래프톤 정글 3기] 11/26(일) TIL

2개의 댓글

comment-user-thumbnail
Peter J
2023년 11월 25일

놀라워요

1개의 답글