이번 주 회고

겪은 문제

• cond_signal()은 조건 변수의 대기 큐 중 제일 priority가 높은 쓰레드를 깨워야 함.
• 즉 cond_wait()에서 struct condition의 대기 큐 waiters에 쓰레드를 priority의 내림차순으로 삽입해야 함.
• 하지만 ready_list의 삽입에 사용했던 우선순위 비교 함수를 그대로 사용 시, 테스트 케이스를 통과하지 못함.

// 잘못된 방식
void cond_wait(struct condition *cond, struct lock *lock){
    // 생략...
    // cond의 대기 큐에 현재 쓰레드를 priority 역순으로 삽입
    list_insert_ordered (&cond->waiters, &waiter.elem, dsc_priority, NULL);
}

/* priority의 내림차순 정렬에 사용되는 함수. */
bool dsc_priority (const struct list_elem *x, const struct list_elem *y, const void *aux){
	struct thread *tx = list_entry(x, struct thread, elem);
	struct thread *ty = list_entry(y, struct thread, elem);
	return (tx -> priority) > (ty -> priority);
}

문제 원인

struct semaphore_elem {
	struct list_elem elem;
	struct semaphore semaphore;
};

• waiters에는 struct thread의 elem이 아니라, struct semaphore_elem의 elem이 들어감
• 기존 비교 함수는 elem이 struct thread의 일부라고 가정하고, priority 멤버를 참고하려고 함
• list_entry는 elem이 struct thread의 일부라고 가정하고, 이를 바탕으로 priority의 주소를 계산
• 하지만 struct semaphore_elem에는 priority가 없으므로, 잘못된 주소 참조로 정렬 실패

해결방법

struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
	struct thread *thread;				// 해당 쓰레드를 가리킴
};

void cond_wait(struct condition *cond, struct lock *lock){
    // 생략...
    struct semaphore_elem waiter;
    waiter.thread = thread_current();
}

• semaphore_elem에 원래 thread의 주소를 가리키는 thread 멤버를 추가

/* waiters 리스트 -> priority의 내림차순으로 정렬할 시 사용되는 함수. */
bool dsc_sema_priority (const struct list_elem *x, const struct list_elem *y, const void *aux){
	struct semaphore_elem *tx = list_entry(x, struct semaphore_elem, elem);
	struct semaphore_elem *ty = list_entry(y, struct semaphore_elem, elem);
	return (tx -> thread -> priority) > (ty -> thread -> priority);
}

list_insert_ordered (&cond->waiters, &waiter.elem, dsc_sema_priority, NULL);

• dsc_sema_priority 함수를 만들어, semaphore_elem 기준으로 주소를 찾음
• 이후 thread 멤버로 원래 struct thread에 접근하고 priority를 비교
• 이 함수를 사용해 구현하므로 정상 통과

프로젝트 회고

• 말록 랩, 프록시 랩에선 하나의 소스코드만 수정해도 됐지만, 이번엔 여러 소스코드를 오가며 작업을 해야 했음. 전역 변수나 함수의 공유에 익숙치 않았고, 화면을 번갈아 봐야 하는 번거로움 때문에 체감상 난이도가 높게 느껴짐.
• 하지만 책을 읽어도 명확히 머리속에 흐름이 안 그려졌던 스케줄링과 쓰레드 개념을 직접 구현하려고 시도하니, 과정을 보다 잘 이해할 수 있었음. 제일 확실한 공부는 직접 만들어 보는 것임을 깨달음.

핀토스 문맥 전환 과정

struct thread: 쓰레드 관리 구조체

• 핀토스에서 실행 중인 각 쓰레드는 struct thread 구조체로 관리됨
• 구조체의 enum thread_status status 멤버는 쓰레드의 현재 상태를 나타냄
  • THREAD_RUNNING: cpu에서 실행 중.
  • THREAD_READY: ready queue에서 실행할 준비가 된 상태. 현재 실행 중이진 않지만 BLOCKED 상태도 아닌 쓰레드.
  • THREAD_BLOCKED: 특정 이벤트를 기다리는 쓰레드. sleep timer 종료라든가, 세마포어/뮤텍스 해제라든가.
  • THREAD_DYING: 삭제 예정인 쓰레드. 실행 중인 쓰레드를 바로 삭제할 순 없으므로, 일단 이 상태로 표시해 두었다가 이후 스케줄러가 해당 쓰레드를 정리.

thread_create(): 쓰레드 생성

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

• (1) 쓰레드명 name의 쓰레드를 생성하고, 우선순위 priority 설정
• (2) 새로운 쓰레드는 function 실행 (매개변수 aux 전달)
• (3) 새로운 쓰레드는 ready queue에 삽입됨
• (4) 쓰레드 ID 반환 (실패 시 TID_ERROR 반환)

ready_list, all_list: 쓰레드 리스트

// 흔히 ready queue라 불림
// THREAD_READY 상태의 쓰레드를 관리
static struct list ready_list;

// 모든 쓰레드 (running + ready + blocked)를 관리
// 처음으로 스케줄링될 때 삽입되고, 쓰레드가 종료될 때 삭제됨
static struct list all_list;

• 새롭게 쓰레드를 생성하면 all_list 맨 끝에 삽입됨
• 쓰레드가 ready 상태가 되면, ready_list에 삽입됨
  • ready_list는 우선순위의 역순으로 정렬됨 -> 올바른 위치를 찾아 삽입됨

schedule, do_schedule: 쓰레드 스케줄링

static void schedule (void){
    // 현재 실행 중인 쓰레드
    struct thread *curr = running_thread ();
    // ready_list 맨 앞 쓰레드. 비어 있으면 idle 쓰레드
	struct thread *next = next_thread_to_run ();

    // 다음 쓰레드를 실행 처리
    next->status = THREAD_RUNNING;

    if (curr != next){
        // 문맥 전환을 실제로 수행하는, 어셈블리어로 가득한 함수
        thread_launch (next);
    }
}

• 현재 쓰레드에서, ready_list의 맨 앞 쓰레드로 문맥 전환 수행
• 이 과정에서, 문맥 전환될 쓰레드의 status를 THREAD_RUNNING으로 전환
• 현재 쓰레드와 ready_list 맨 앞 쓰레드가 동일하지 않은 경우, thread_launch로 문맥 전환 (어셈블리어로 가득해 일단 생략)

// status로 쓰레드 상태 변경
void do_schedule(int status){
    // 현재 쓰레드의 status를 매개변수로 바꾼다.
	thread_current ()->status = status;

	// 새롭게 스케줄링
	schedule ();
}

• 핀토스에서는 do_schedule()에서 쓰레드 상태 변경을 해 주고, do_schedule() 내부에서 schedule()을 호출
• do_schedule이 호출되기 전엔 인터럽트가 해제되어야 함
• 아래 상황에서 호출될 수 있음
  • (1) 현재 쓰레드가 종료될 때 (thread_exit())
    • THREAD_DYING으로 변경
  • (2) 현재 쓰레드가 세마포어, 슬립 타이머 등에 의해 블록될 때 (thread_block())
    • THREAD_BLOCKED로 변경
  • (3) 현재 쓰레드가 yield 시스템 콜을 보낼 때 (thread_yield())
    • THREAD_READY로 변경
  • (4) 현재 쓰레드가 우선순위가 더 높은 쓰레드에 의해 선점될 때
    • THREAD_READY로 변경
    • 보통 ready_list 맨앞 노드가 현재 쓰레드의 priority보다 높은 경우, thread_yield()를 실행하는 식으로 구현
• status 변경해 준다고 ready_list에서 자동으로 쓰레드가 삽입 / 삭제되지는 않음에 유의
  • 그건 다른 함수에서 수동으로 처리해야 함

키워드 정리

프로세스

• 프로세스: 실행 중인 프로그램

• 프로세스 생성 시 커널 영역에 PCB(프로세스 컨트롤 블록)이 생성됨

  • 프로세스 식별에 필요한 정보가 저장됨 (프로세스 ID, 레지스터 값, 프로세스 상태[실행/대기/블록 등], 스케줄링 우선순위 등)
  • 이러한 정보를 문맥이라고도 함

• 문맥 교환: 프로세스 간 실행을 전환하는 것

  • 기존 프로세스의 문맥을 PCB에 백업하고, 새로운 프로세스를 실행하기 위해 해당 프로세스의 문맥을 PCB로부터 복원

쓰레드

• 쓰레드: 프로세스 내 실행 흐름 단위
• 여러 쓰레드로 프로세스를 동시에 실행하는 것: 멀티쓰레딩
• 프로세스끼리는 자원을 공유하지 않지만, 프로세스 내 쓰레드끼리는 같은 프로세스 내 자원을 공유함
  • 프로세스 내 스레드는 코드, 데이터, 힙 영역을 공유
  • 하지만 각기 다른 레지스터(프로그램 카운터 값 등) 및 스택을 가짐
• 장점: 쓰레드 간 협력과 통신에 유리
• 단점: 한 쓰레드에 문제가 발생하면 프로세스 전체에 문제가 생김

CPU 스케줄링

• 프로세스 / 쓰레드 등 작업 단위에 CPU 자원을 배분하는 방법
  • 준비 큐: CPU 할당을 기다리는 작업 단위를 위한 큐
    • 준비 큐에서 실행할 작업 단위를 선택하는 과정이 스케줄링
  • 선점형 스케줄링: 다른 작업 단위가 이용 중인 CPU를 도중에 빼앗을 수 있음
  • 비선점형 스케줄링: 한 작업 단위가 CPU에 스케줄링되면, 종료 시까지 빼앗을 수 없음

비선점형 스케줄링

• FCFS(First come first served, 선입 선처리)
  • 준비 큐에 삽입된 순서대로 CPU를 할당
• SJF(Shortest Job First, 최단 작업 우선)
  • 준비 큐에 삽입된 작업 단위 중, CPU 사용 시간의 길이가 짧은 작업 단위부터 CPU를 할당

선점형 스케줄링

• RR(Round Robin, 라운드 로빈)
  • 정해진 시간(타임 슬라이스)만큼 돌아가며 CPU를 할당
  • 정해진 시간을 모두 사용했음에도 작업 단위가 완료되지 않으면, 다음 작업 단위에게 넘겨주고 레디 큐 맨 뒤로 이동 (선점형)

• SRTF (Shortest Remaining Time First, 최소 잔여 시간 우선)
  • 정해진 시간(타임 슬라이스)만큼 CPU를 사용
  • CPU를 사용할 다음 프로세스로는, 준비 큐 중 남아 있는 작업 시간이 가장 적은 프로세스를 선택
• 우선순위 스케줄링
  • 준비 큐 중 가장 높은 우선순위를 가진 작업 단위에 CPU를 할당
  • 일반적으로 입출력 집중 작업 단위는 우선순위를 높게, CPU 집중 작업 단위는 우선순위를 낮게 설정
  • 우선순위가 같은 경우 Round Robin으로 처리
  • 문제점: 기아 현상 -> 우선순위가 낮은 작업 단위가, 높은 작업 단위에 의해 실행이 계속 연기됨
  • 해결법: 에이징 -> 오랫동안 대기한 프로세스의 우선순위를 점차 증가
• MLFQS(Multilevel Feedback Queue, 다단계 큐)
  • 우선순위별로 준비 큐를 여러 개 사용
  • 우선순위가 가장 높은 큐의 작업 단위들 먼저 처리
    • 비어 있으면 그 다음 우선순위 큐의 프로세스들을 처리
  • 작업단위는 각 준비 큐 사이를 이동할 수 있음
    • 일단 우선순위가 가장 높은 큐에 삽입됨
    • CPU 사용 시간이 길어지면, 낮은 우선순위로 이동
    • 낮은 우선순위에서 너무 오래 기다리면, 높은 우선순위로 이동

동기화

• 동기화
  • (1) 상호 배제: 공유 자원에 접근할 때 한 개의 작업 단위만 접근하게 하는 것
    • 하단 상호 배제 에 설명해 줌
  • (2) 실행 순서 제어: 작업 단위를 올바른 순서대로 실행하게 하는 것
    • e.g., Writer 프로세스가 파일에 값을 저장해야, Reader 프로세스가 파일에 저장된 값을 읽을 수 있음

상호 배제

• 공유 자원: 여러 작업 단위가 공동으로 사용하는 자원
  • 전역 변수, 파일, 입출력장치, 보조기억장치 등
• 임계 구역: 공유 자원에 접근하는 코드 중, 동시에 실행하면 문제가 발생하는 코드 영역
  • 여러 작업 단위가 동시에 임계 구역의 코드를 실행하여 발생하는 문제 -> 레이스 컨디션
  • 임계 구역에 진입한 작업 단위가 있다면, 다른 프로세스는 임계 구역 밖에서 기다리도록 설정해야 함
• 상호 배제: 한 작업 단위가 임계 구역에서 작업 중이면, 다른 작업 단위는 임계 구역에 들어갈 수 없게 제어하는 것
  • 단, 임계 구역에 아무 작업 단위도 진입하지 않았으면, 진입하고 자 하는 프로세스는 들어갈 수 있어야 함 (진행)
  • 한 프로세스가 임계 구역에 진입하고 싶다면, 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 함 (유한 대기)

동기화 기법

뮤텍스 락

• 상호 배제를 위한 도구
• 임계 구역에 진입하는 작업 단위는, 현재 자신이 임계 구역에 있음을 알리기 위해 뮤텍스 락을 잠글 수 있음
• 다른 작업 단위는, 임계 구역이 잠겨 있으면 기다리고, 잠겨 있지 않으면 임계 구역에 진입할 수 있음

뮤텍스 락의 구현

• 자물쇠 역할: 쓰레드 간 공유되는 전역 변수 lock
  • false면 열려 있고, true면 잠겨 있음
• 임계 구역을 잠그는 acquire 함수
  • 작업 단위가 임계 구역에 진입하기 직전에 호출
  • lock이 false: lock을 true로 바꾸고, 임계 구역에서의 작업을 진행
  • lock이 true: lock이 false가 될 때까지 임계 구역 밖에서 대기 (대기 큐에 삽입)
• 임계 구역의 잠금을 해제하는 release 함수
  • 임계 구역에서의 작업이 끝나고 호출
  • lock을 false로 바꾸고, 대기 큐의 프로세스 중 1개(보통 우선순위가 제일 높은 친구)를 준비 큐로 옮김
  • release는 현재 뮤텍스 락을 acquire한 작업 단위만 수행할 수 있음
• 임계 구역 코드 전후로 acquire(), release() 함수를 두어 보호할 수 있음

acquire();
// 임계 구역
release();

세마포어

• 뮤텍스 락 -> 한 작업 단위만 임계 구역에 진입 가능
• 세마포어로는 여러 작업 단위의 진입을 허용 가능

세마포어의 구현

• 자물쇠 역할: 임계 구역에 진입할 수 있는 작업 단위의 개수를 나타내는 전역 변수 semaphore
  • 현재 임계 구역 내 작업 단위의 수에 따라 값이 변동됨
  • semaphore == 0일 때 잠김 (더 작업단위가 못 들어온단 소리)
• 임계 구역을 잠그는 wait 함수
  • semaphore >= 1이라면, semaphore를 1 감소시키고 임계 구역에 진입
  • semaphore == 0이라면, semaphore가 1 이상의 값이 될 때까지 임계 구역 밖에서 대기 (대기 큐에 삽입)
• 임계 구역의 잠금을 해제하는 signal 함수
  • 임계 구역에서의 작업이 끝나고 호출
  • semaphore를 1 증가시키고, 대기 큐의 프로세스 중 1개(보통 우선순위가 제일 높은 친구)를 준비 큐로 옮김

wait();
// 임계 구역
signal();

모니터

• 모니터 내 공유 자원 존재
  • 공유 자원에 접근하려는 작업 단위를, 모니터 큐에 삽입
  • 모니터 안엔 항상 1개의 프로세스만 진입 가능
• 모니터 내부에서 작업 단위의 실행할 순서를 제어하기 위해, 조건 변수를 사용
  • 조건 변수별로 대기 큐가 존재. 모니터의 대기 큐와 다름에 유의할 것
  • wait 연산: 호출한 작업 단위를 대기 상태로 전환 후, 조건 변수의 대기 큐에 삽입
    • 작업 단위가 아직 실행될 조건이 되지 않았을 때 중단
  • signal 연산: wait를 이용해 조건 변수의 대기 큐에 삽입된 프로세스의 실행을 재개
    • 작업 단위가 실행될 조건이 충족되었을 때 사용
• 동작과정은 아래 그림 참고

교착 상태

• 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상으로, 데드락(deadlock)으로도 불림
• e.g., 프로세스 A가 임계구역 진입 전 lock1을 잠그고, 프로세스 B가 임계구역 진입 전 lock2를 잠금
  • 만일 이후 A가 lock2가 false가 되길 기다리고, B가 lock1이 false가 되기를 기다리면 교착 상태가 발생
  • 해결법: 프로세스 A, B가 모두 lock1 -> lock2 순서로만 자원을 요청하도록 순서를 통일