[크래프톤 정글 3기] 11/27(월) TIL

08:19 입실
운영체제 해당 부분 책 빠르게 읽어 나가기
1~2시간 정도 자료구조 복습하기
핀토스 몰입!

---

핀토스

---

EC2 에러

VSC 원격 접속 불가

웹 접속 아래 메시지 출력
Failed to connect to your instance
Error establishing SSH connection to your instance. Try again later.

SSH 접속 후 아래 명령어로 해결

sudo apt-get install ec2-instance-connect

---

Priority-change

지금은 준비큐에 있는 스레드들이 RR 방식으로 순차적으로 들어간다.

이걸 우선순위에 맞춰서, 만약 새로 들어온 스레드가 현재 실행 중인 스레드보다 높으면 선점해야 한다.

처음에는 매 틱마다 레디 큐를 순회하면서 우선순위가 높은 걸 꺼내오려고 했는데, 그것보다 레디큐에 삽입 시 정렬하면 될 것 같음.

---

필요한 기능

1. 순위 비교 함수

/* 우선 순위 비교 함수 */
static list_less_func *priority_less(const struct list_elem *a, const struct list_elem *b,
																		 void *aux UNUSED)
{
	const struct thread *thread_a = list_entry(a, struct thread, elem);
	const struct thread *thread_b = list_entry(b, struct thread, elem);

	return thread_a->priority > thread_b->priority;
}

2. 기존 push_back을 insert_ordered로 대체

void thread_unblock(struct thread *t)
{
	enum intr_level old_level;

	ASSERT(is_thread(t));

	old_level = intr_disable();
	ASSERT(t->status == THREAD_BLOCKED);
	// list_push_back(&ready_list, &t->elem);
	list_insert_ordered(&ready_list, &t->elem, priority_less, NULL);
	t->status = THREAD_READY;
	intr_set_level(old_level);
}

3. 실행 중인 스레드의 우선순위가 변경된 경우,
   레디큐의 첫 번째 스레드의 우선순위와 비교해서
   레디큐의 우선순위가 더 높으면 교체(yield)

/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	struct thread *front = list_entry(list_front(&ready_list), struct thread, elem);
	if (front->priority > new_priority)
		thread_yield();
}

---

priority-fifo 디버깅

동일 우선순위라면 도착 순서대로 실행되어야 하는데,
그렇지 않음.

실제 정렬 코드는 문제 없음.
실행 중인 스레드 우선 순위 변경 시 문제 발생

/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	
	/* 대기 큐가 비었을 경우 예외 처리*/
	if (list_empty(&ready_list))
		return;
	
	struct thread *front = list_entry(list_front(&ready_list), struct thread, elem);
	if (front->priority > new_priority)
		thread_yield();
}

---

함수 포인터

/* 반환 타입 그대로 쓰기 */
static bool priority_less (const struct list_elem *a, const struct list_elem *b,
            	void *aux UNUSED) { 
  const struct thread *thread_a = list_entry (a, struct thread, elem);
  const struct thread *thread_b = list_entry (b, struct thread, elem);

  return thread_a->priority > thread_b->priority;
}

/* typedef로 쓰기 */
/* 우선 순위 비교 함수 */
static list_less_func
*priority_less (const struct list_elem *a, const struct list_elem *b,
            	void *aux UNUSED) { 
  const struct thread *thread_a = list_entry (a, struct thread, elem);
  const struct thread *thread_b = list_entry (b, struct thread, elem);

  return thread_a->priority > thread_b->priority;
}

여기까지 알람 구현 완료!
이제 우선순위 시작!

---

우선순위 역전

우선순위 역전(priority inversion)

임계영역 접근 문제로 높은 우선순위 스레드가 락을 취득하지 못해서, 우선순위가 낮은 스레드가 지나치게 오랫동안 자원을 점유할 때 생기는 문제

즉, 우선순위가 역전되는 현상이 발생

---

우선순위 상속

priority inheritance

우선순위 역전이 발생했을 때,
우선순위가 낮은 쓰레드를 우선순위를 올려서
(마치 최우선 순위에게 상속 받는 것처럼)
최대한 빨리 실행을 마치게 해서 락을 반납하게 하는 것

---

운영체제

---

멀티 쓰레드 주소 공간

---

생산자 - 소비자 문제

한정 버퍼 문제(bounded-buffer problem)
여러 개의 프로세스를 어떻게 동기화할 것인가

---

경쟁 조건

명령어의 실행 순서에 따라 결과가 달라지는 상황
또는 데이터 경쟁

---

락과 임계영역, 그리고 원자성

락은 임계영역을 원자 단위 명령어인 것처럼 실행되도록 함.
원자성이라는 건 0아니면 1이라는 거.
트랜잭션 개념과 비슷.
실행될거면 다 실행되고, 안 될거면 다 안되는 거
애매하게 일부만 실행되는 건 원자성이 아님.

---

락

용어

• mutex : 일종의 변수
• lock(&mutex) : 소유할 수 없으면 반환 값 없음
• unlock(&mutex)
• unlocked, free, acquired
• owner : 락 소유자

---

근사 카운터

전역 변수, 지역 변수를 두고 각 스레드는 지역 변수에만 접근하고 주기적으로 전역 변수에 반영하는 방식으로 경쟁 조건을 방지

실시간으로 값이 반영되지 않기 때문에 근사 카운터, 혹은 엉성한 카운터라고 함.

---

모니터

컨디션 변수(conditional variable)

일종의 큐 자료 구조
어떤 실행의 상태(조건)가 원하는 것과 다를 때
조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐

---

세마포어

세마포어는 락과 컨디션 변수로 모두 활용할 수 있다!
다익스트라가 고안함

락으로 사용되는 세마포어 수도 코드

#include <semaphore.h>
sem_t s;
tem_init(&s, 0, 1); /* 1로 초기화 */

int sem_wait(sem_t *s) {
	decrement the value of semaphore s by one;
    wait if value of semaphore s is negative;
}

int sem_post(sem_t *s) {
	increment the value of semaphore s by one;
    if there are one or more threads waiting, wake one;
}

세마포어를 락 처럼 가능, 불가능의 2가지 상태로 쓰면 이진 세마포어

컨디션 변수로서 세마포어

어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈춤
하나의 쓰레드가 어떤 사건 발생을 기다리고,
다른 쓰레드는 해당 사건을 발생시킨 후 시그널을 보내
기다리는 쓰레드 깨우기
: 세마포어 초기값을 0으로 설정하면 이런 효과가 있음.

/*
parent: begin
child
parent: end
*/

sem_t s;

void *
child(void *arg) {
	printf("child\n");
    sem_post(&s); // 시그널 전달: 자식의 동작 끝
    return NULL;
    
int
main(int argc, char *argv[]) {
	sem(init(&s, 0, 0);
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&S); // 자식 대기
    printf("parent: end\n");
    return 0;
}