크래프톤 정글 TIL : 0824

lazyArtisan·2024년 8월 24일
TIL
0

정글 TIL

목록 보기
55/147

📚 Journal

면접 준비

동기 분께 면접에 관해 여쭤봤는데 짧게 모의 면접도 해주시고 피드백도 해주시고 꿀팁도 알려주셨다.

  • 확실하게 알고 있지 못하는 것에는 깔끔하게 잘 기억이 안 난다고 대답할 것. 잘 모르는 쪽으로 휩쓸려가면 최악.
  • A를 물어봤지만 A에 대해 대답한 후 관련된 내용 중에 내가 잘 아는 B에 대해 더 설명해서 내가 잘 아는 쪽으로 유도. 아니라고 생각하면 면접관이 알아서 끊을 것.
  • 잘 모르겠을 때 자신이 알고 있는 것을 기반으로 유추해서 말하거나 최대한 대답하는 것은 좋았음.
  • 음, 어 이런 식으로 자신이 없다는 식으로 말하면 안됨.
  • 결론을 먼저 두괄식으로 대답할 것. (딴 얘기 하면 면접관이 집중 못하고 중간에 있는 핵심 대답 못 들을 수도)
  • 단답형으로 한 번 설명한 후에 한 박자 쉬어갈 것.
  • 면접자와 눈을 마주치며 대답할 것.
  • 프로그램과 프로세스의 차이 : 변환되는 것이 아니라 프로세스는 프로그램의 추상화.
  • 프로세스와 쓰레드의 차이 : 프로세스는 메모리를 공유하지 않고, 쓰레드는 메모리를 공유한다.
  • 대부분 면접 볼 때 칠판 준다


📝 배운 것들

🏷️ busy waiting이 꼭 나쁜가?

Busy-waiting은 위에서 말했듯이 CPU를 많이 소모한다는 문제는 남아있다. 하지만 만약에 기다리고 있는 Task가 자주 호출되고 금방 끝나는 경우에는 잦은 Context Switching이 비쌀 수 있기 때문에 효율적으로 쓰이는 경우도 있으며 대표적으로 Spinlock이 여기에 해당한다.

https://soundness.tistory.com/4

🏷️ 쓰레드

프로세스 : 운영체제로부터 자원을 할당받은 작업의 단위

쓰레드 : 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위.

쓰레드를 사용하는 이유 : 동시성을 보장하기 위해 사용한다. 예를 들어 서버를 생성한다고 하자. 하나의 프로세스로 구성된 서버는 한번에 한명의 클라이언트의 요청밖에 처리할 수 없다. 여러 개의 프로세스로 구동되는 서버를 사용할 수도 있지만, 프로세스는 개별 공간이 크고, Context Switching에도 시간이 오래 걸린다.(프로세스의 Context 스위칭 시, CPU 레지스터, RAM과 CPU 사이의 캐시 메모리까지 초기화된다. 쓰레드의 경우 개별 컨텍스트만 Switching 해주면 된다.)

기본적으로 하나의 프로세스는 하나의 쓰레드를 가지고 생성되며, 생성된 프로세스 안에서 쓰레드를 추가하면 멀티쓰레딩이라고 한다. 멀티쓰레드는 한개 프로세스의 컨텍스트 안에서 돌아간다. 각각 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가지며, 쓰레드 ID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드, 범용 레지스터 값들이 포함된다. 나머지 자원은 다른 쓰레드와 공유한다.(만일 A 쓰레드가 B 쓰레드의 스택을 가리키는 포인터를 획득한다면, 해당 포인터를 활용하여 다른 쓰레드의 스택데이터를 조작하는게 가능하다.)

  1. Stack : 프로그램 실행 과정에서 생성되는 지역변수, 주소값 등을 저장하는 공간(순차적으로 주소가 낮아지는 방향으로 쌓임)

  2. Heap : 동적으로 할당되는 메모리 공간 (By malloc ...)

  3. Static : 1) Data : 초기화된 전역변수가 저장된다. 

        2) BSS : 초기화되지 않은 전역변수가 저장된다.

  4. Code : 프로그램 실행 코드

쓰레드의 장점 : 다수의 쓰레드가 같은 프로그램의 변수들을 공유하기 쉽다.

쓰레드의 단점 :

  1. 쓰레드 간의 동기화 문제가 발생한다. A 스레드가 어떤 자원을 사용하다가, B스레드로 제어권이 넘어간 후, B 스레드가 해당 자원을 수정했을 때, 다시 제어권을 받은 A스레드가 해당 자원에 접근하지 못하거나 바뀐 자원에 접근하게 되는 문제가 발생할 수 있다.

  2. 멀티프로세싱은 운영체제의 스케쥴러가 관장하는 반면, 멀티스레드는 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응할 수 있어야 한다. --> 일반적으로, 운영체제가 여러분의 쓰레드를 위해서 정확한 순서를 선택하게 될지 예측하는 방법은 없다.

  3. 디버깅이 까다롭다.

  4. 하나의 쓰레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.

https://one-step-a-day.tistory.com/122

🏷️ 모니터 락

모니터 락(Monitor Lock)은 동시성 프로그래밍에서 사용되는 중요한 개념으로, 모니터(monitor)라는 동기화 객체를 통해 여러 스레드가 공유 자원에 안전하게 접근할 수 있도록 제어하는 방법을 제공합니다. 모니터는 여러 스레드가 동시에 같은 자원에 접근하는 것을 방지하며, 자원의 일관성을 유지하는 데 중요한 역할을 합니다.

모니터(Monitor)란?

  1. 상호 배제(Mutual Exclusion): 모니터는 내부적으로 락을 관리하여, 한 번에 하나의 스레드만이 모니터에 포함된 코드에 접근할 수 있도록 보장합니다.
  2. 조건 동기화(Condition Synchronization): 모니터는 특정 조건이 만족될 때까지 스레드를 대기시키고, 조건이 만족되면 대기 중인 스레드를 깨우는 기능을 제공합니다.

모니터 락의 동작 방식

모니터 락은 객체 수준에서 구현되며, 일반적으로 다음과 같은 방식으로 동작합니다:

  1. 락 획득: 스레드가 모니터에 접근하려면 먼저 락을 획득해야 합니다. 락을 획득한 스레드는 모니터의 자원에 접근할 수 있으며, 다른 스레드의 접근을 방지합니다.

  2. 코드 실행: 락을 획득한 스레드는 모니터에 보호된 자원이나 코드 블록을 실행합니다. 이 동안 다른 스레드들은 해당 모니터에 접근할 수 없습니다.

  3. 조건 변수 대기: 만약 특정 조건이 충족되지 않으면, 스레드는 모니터 내에서 대기 상태로 전환됩니다. 이때 스레드는 조건 변수를 사용해 대기하며, 락을 다른 스레드에게 넘겨줍니다.

  4. 조건 만족 및 락 반환: 조건이 충족되면, 대기 중인 스레드는 다시 락을 획득하고 모니터의 보호된 자원에 접근할 수 있습니다. 작업이 끝나면 락을 반환하고, 모니터를 떠나면서 다른 대기 중인 스레드가 모니터에 접근할 수 있도록 합니다.



🖥️ PintOS

🔷 Alarm Clock

https://velog.io/@rivolt0421/Pintos-VSCode%EB%A1%9C-Pintos-%EB%94%94%EB%B2%84%EA%B7%B8%ED%95%98%EA%B8%B0

디버그 연결 성공

시도 1. 드르렁 리스트

/* Suspends execution for approximately TICKS timer ticks. */
void timer_sleep(int64_t ticks)
{
	// int64_t start = timer_ticks(); // OS 시작하고 시간이 얼마나 지났는지

	// ASSERT(intr_get_level() == INTR_ON);
	// while (timer_elapsed(start) < ticks) // 처음 시작부터 지금까지 지난 시간이 ticks 이하이면
	// 	thread_yield();					 // 현재 실행중인 프로세스를 waiting list 끝으로 보낸다

	// tid_t tid = thread_tid();
	extern struct list sleeping_list;
	struct thread *sleeping_thread = thread_current();

	// struct wait_block wb = {tid, timer_ticks() + ticks}; // 드르렁 하기 전에 정보 적어놓기
	sleeping_thread->sleep_ticks = timer_ticks() + ticks;

	list_push_back(&sleeping_list, &(sleeping_thread->elem)); // 명부에 정보 전달
	thread_block();											  // 드르렁. 명부에서 자기 이름 나오면 딱 1번 깨서 마저 실행.
}

더 가다듬어 보려고 했는데 synch.c에 있는 관련 함수들을 사용하면 될 거라는 얘기를 듣고 일단 그쪽으로 선회해보기로 함.

내가 쓰던 block()과 unblock()은 직접 접근하는 거라 좋지 않다고 함.

시도 2. synch.c와 친해지기

컨디션 변수는 특정 컨디션(조건)이 참이 될 때까지 모니터안의 코드가 기다릴 수 있게합니다. 각 컨디션 변수는 추상적인 조건과 관련있습니다. 예를 들면 “프로세스가 진행되는 동안 몇가지 데이터가 도착하는 조건”, “유저의 마지막 키보드 입력으로 부터 10초가 넘게 지나는 조건” 입니다. 모니터안의 코드가 특정 조건이 참이 되기를 기다릴 때, 그 코드는 원하는 조건과 관련된 컨디션 변수를 기다립니다(wait). 그 컨디션 변수는 락을 놓아주고 컨디션이 신호받는 것을 기다립니다. 반대로 이 코드가 특정 조건이 참이되도록 만드는 경우에는, 그 참이된 조건을 신호로 보내서(signal) 기다리는 코드 하나를 깨우거나, 전부한테 알려서(broadcast) 자는 코드를 전부 깨웁니다.

동기분도 모니터 락 쓰신 것 같음
특정 조건 만족하면 모니터 안에 들어있는 쓰레드들을 깨운다는 것 같음

근데 찾다보니까 좀 빡세서 일단 하던 드르렁 리스트 마저 만들어보고 하는게 나을듯

시도 3. 다시 드르렁 리스트

기왕 정답에 대한 방향성 힌트를 얻은 김에 다른 사람은 어떻게 했나 코드 말고 방향성 정도만 보려고 했는데, 내 드르렁 리스트랑 비슷하게 접근했었음. 어쨋든 가능하다는 것. 거의 다 했으니 마저 해보고 정 안되면 모니터 락으로 선회

// 드르렁 중인 친구들 수면 시간 체크하고 깨어날 시간이면 깨운다
struct list_elem *listE = list_begin(&sleeping_list);
while (listE != list_end(&sleeping_list))
{
    struct thread *sleeping_thread = list_entry(listE, struct thread, elem);

    if (sleeping_thread->sleep_ticks <= timer_ticks())  // 깨어날 시간이 되었을 때
    {
        listE = list_remove(listE); // 현재 요소를 제거하고 다음 요소로 이동
        thread_unblock(sleeping_thread); // 프로세스 깨운다
    }
    else
    {
        listE = list_next(listE); // 다음 요소로 이동
    }
}

chatgpt한테 뭐 틀렸을까 물어봤더니 (이전에 list.c 긁어서 물어봤었음) 깨울 때는 list_next()를 안 씀. 뭔가 이상해서 들어가봤더니

아뿔싸
알아서 넥스트로 가주는구나

	// 드르렁 중인 친구들 수면 시간 체크하고 깨어날 시간이면 깨운다
	struct list_elem *listE = list_begin(&sleeping_list);
	while (listE != list_end(&sleeping_list))
	{
		struct thread *sleeping_thread = list_entry(listE, struct thread, elem);

		if (sleeping_thread->sleep_ticks <= timer_ticks()) // 깨어날 시간이 되었을 때
		{
			listE = list_remove(listE);		 // 현재 요소를 제거하고 다음 요소로 이동
			thread_unblock(sleeping_thread); // 프로세스 깨운다
		}
		else
		{
			listE = list_next(listE); // 다음 요소로 이동
		}
	}

여기서 while 조건문 (!is_tail(listE)) 이걸로 바꿨더니 이상해졌음

그렇다고 함

	if (list_empty(&sleeping_list))
	{
		printf("sleeping_list is empty\n");
	}
	else
	{
		printf("sleeping_list is not empty\n");
	}

	struct list_elem *e = list_begin(&sleeping_list);
	if (e == NULL)
	{
		printf("Error: list_begin returned NULL\n");
	}
	else
	{
		printf("List element at %p\n", e);
	}

	for (e = list_begin(&sleeping_list); e != list_end(&sleeping_list); e = list_next(e))
	{
		printf("List element at %p\n", e);
	}

gpt랑 얘기하면서 이게 문제인거 같다는 지점을 계속 파고드는데, printf를 알아서 만들어 주는게 유용하기도 하지만 이런 식으로 문제 파악하면 되겠다는 걸 배우니까 좋은 것 같다.

늦은 시간임에도 TA 분이 도와주셔서 list 오류를 해결했다.

이후 구문에도 버그가 일어남.
문제는 파악함. 이 근처에서 (아마 실행할 쓰레드를 찾지 못하고) 무한 반복이 일어남.
그래서 디버깅 툴이 무한 반복돼서 터졌던 거였음.
내일 할 땐 이 부분을, 타임아웃 옵션 걸어서 디버깅해보자.



⚔️ 백준

📌 공유기 설치 복습

'공유기의 최소 인접 거리'의 최대를 구하는 문제

공유기의 최소 인접 거리가 될 수 있는 후보는 0부터 1,000,000,000인데
여기서 집의 위치를 생각하면 경우의 수를 좁힐 수는 있지만

가능한 경우의 수가 꽉꽉 들어차 있지 않아도 이분 탐색을 사용하는 것이 가능하고, 그것이 (코드 적는 것까지 감안하면) 더 빠르고 효율적이다.

log 2의 1,000,000,000은 29.x 임.
그냥 뭔가 숫자가 크면 이분탐색을 떠올려봐도 괜찮을 것 같음.

이분탐색은 그냥 == 조건으로 단순히 일치하는 값을 찾는 것이 아니라 조건이 성립하는 영역과 성립하지 않는 영역의 경계점을 구할 수 있다.

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0823

다음 포스트

크래프톤 정글 TIL : 0825

0개의 댓글