크래프톤 정글 TIL : 0908

lazyArtisan·2024년 9월 8일
TIL
0

정글 TIL

목록 보기
70/147

📚 Journal

갑자기 난이도 급하락함
기존에 만들어져 있는 함수에 예외처리 하는게 다라 좀 노잼

이라고 생각했는데 fdt 개어렵네
항상 겸손해라



📝 배운 것들

🏷️ inode

https://mysoftworld.tistory.com/18

inode는 파일의 메타데이터가 담겨있는 구조체다.
커널 영역에 있는 inode table에는 inode 정보들이 담겨있다.

파일 디스크립터는 프로세스마다 따로 갖고,
아이노드는 커널 영역에 하나로 공유한다.

ls -i 치면 아이노드 넘버와 디렉토리가 함께 뜬다

🏷️ c 배열 초기화

https://m.blog.naver.com/ilikebigmac/221589744264

🏷️ 페이지

여기서 말하는 "페이지(page)"는 가상 메모리 시스템에서 사용하는 메모리 관리 단위를 뜻합니다. 페이지는 운영체제가 메모리를 효율적으로 관리하기 위해 사용하는 고정 크기의 블록으로, 가상 메모리와 물리 메모리 사이에서 데이터를 관리할 때 중요한 역할을 합니다.

1. 페이지와 페이지 테이블

  • 페이지는 가상 주소 공간과 물리 주소 공간을 연결하는 중간 단계 역할을 합니다.
  • 운영체제는 페이지 테이블을 통해 가상 주소를 물리 주소로 변환합니다. 페이지 테이블에는 각 가상 페이지에 대한 물리 메모리 주소가 저장되어 있으며, CPU가 메모리에 접근할 때마다 이를 참조하여 주소 변환을 수행합니다.

2. 페이지의 역할

  • 가상 메모리 시스템에서 페이지는 가상 주소 공간을 작은 블록으로 나누어 관리하는 단위입니다.
  • 페이지 크기는 일반적으로 4KB이지만, 시스템에 따라 크기가 달라질 수 있습니다.
  • 가상 주소와 물리 주소 간의 매핑은 페이지 테이블에 의해 관리되며, 가상 주소가 어떤 물리적 메모리 블록을 참조할지 결정됩니다.

3. 페이지 테이블 엔트리(Page Table Entry, PTE)

  • 주석에서 언급된 "page table entry"는 페이지 테이블의 한 엔트리를 의미합니다. 이는 특정 가상 주소(VADDR)가 어느 물리 메모리 페이지와 연결되어 있는지를 나타냅니다.
  • 페이지 테이블 엔트리는 해당 페이지가 메모리에 존재하는지, 페이지 권한이 무엇인지 등의 정보를 담고 있습니다.

🏷️ expression must be a modifiable lvalue

10 = x;  // 잘못된 예: 상수는 수정 불가한 rvalue이므로 대입할 수 없음
int arr[5];
arr = new_arr;  // 오류: 배열 이름은 수정 불가능한 lvalue

"expression must be a modifiable lvalue" 오류는 C/C++에서 lvalue가 수정할 수 없는 경우에 발생합니다. lvalue는 "left-hand value"로, 메모리 위치를 가리키는 값이어야 합니다. 즉, lvalue는 변수와 같이 수정 가능한 메모리 주소를 가져야 합니다.

대입식 왼쪽에 이상한거 넣지 말라는 뜻



🖥️ PintOS

🔷 System Calls

wait (보류)

https://maxlevsnail.com/pintos-project-2/

https://velog.io/@biomatrix117/%ED%81%AC%EB%9E%98%ED%94%84%ED%86%A4-%EC%A0%95%EA%B8%80-TIL-0905#wait

내가 정리했던거랑 이거 보면 대충 어떻게 해야될지 다 알 수 있을듯

라고 생각했는데, 일단 fork를 먼저 구현한 후에 wait를 하는게 맞는듯.
기다릴 자식 프로세스를 어떻게 만들지도 아직 안 정해졌는데 wait 하기 좀 어려울듯.

create (수정)

어제 내가 해줬던 조건 검사 필요 없던 거였음.
동기가 그거 왜 해줌? 하길래 주석처리하고 wait 시간 늘려봤더니 멀쩡히 통과.

open

/* file(첫 번째 인자)이라는 이름을 가진 파일을 엽니다. */
int open(const char *file)
{
	if (file == NULL || pml4_get_page(thread_current()->pml4, file) == NULL || !is_user_vaddr(file) || strlen(file) == 0)
		exit(-1);

	return filesys_open(file);
}

create 유효 조건 검사하는거 띡 갈겼더니

perl -I../.. ../../tests/userprog/open-normal.ck tests/userprog/open-normal tests/userprog/open-normal.result
pass tests/userprog/open-normal
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-missing:open-missing -- -q   -f run open-missing < /dev/null 2> tests/userprog/open-missing.errors > tests/userprog/open-missing.output
perl -I../.. ../../tests/userprog/open-missing.ck tests/userprog/open-missing tests/userprog/open-missing.result
FAIL tests/userprog/open-missing
run: open() returned 0: FAILED
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-boundary:open-boundary -p ../../tests/userprog/sample.txt:sample.txt -- -q   -f run open-boundary < /dev/null 2> tests/userprog/open-boundary.errors > tests/userprog/open-boundary.output
perl -I../.. ../../tests/userprog/open-boundary.ck tests/userprog/open-boundary tests/userprog/open-boundary.result
pass tests/userprog/open-boundary
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-empty:open-empty -- -q   -f run open-empty < /dev/null 2> tests/userprog/open-empty.errors > tests/userprog/open-empty.output
perl -I../.. ../../tests/userprog/open-empty.ck tests/userprog/open-empty tests/userprog/open-empty.result
FAIL tests/userprog/open-empty
Test output failed to match any acceptable form.

Acceptable output:
  (open-empty) begin
  (open-empty) end
  open-empty: exit(0)
Differences in `diff -u' format:
  (open-empty) begin
- (open-empty) end
- open-empty: exit(0)
+ open-empty: exit(-1)
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-null:open-null -- -q   -f run open-null < /dev/null 2> tests/userprog/open-null.errors > tests/userprog/open-null.output
perl -I../.. ../../tests/userprog/open-null.ck tests/userprog/open-null tests/userprog/open-null.result
pass tests/userprog/open-null
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-bad-ptr:open-bad-ptr -- -q   -f run open-bad-ptr < /dev/null 2> tests/userprog/open-bad-ptr.errors > tests/userprog/open-bad-ptr.output
perl -I../.. ../../tests/userprog/open-bad-ptr.ck tests/userprog/open-bad-ptr tests/userprog/open-bad-ptr.result
pass tests/userprog/open-bad-ptr
pintos -v -k -T 60 -m 20   --fs-disk=10 -p tests/userprog/open-twice:open-twice -p ../../tests/userprog/sample.txt:sample.txt -- -q   -f run open-twice < /dev/null 2> tests/userprog/open-twice.errors > tests/userprog/open-twice.output
perl -I../.. ../../tests/userprog/open-twice.ck tests/userprog/open-twice tests/userprog/open-twice.result
pass tests/userprog/open-twice

open-missing, open-empty 말고는 다 통과함.

open-missing

/* file(첫 번째 인자)이라는 이름을 가진 파일을 엽니다. */
int open(const char *file)
{
	if (file == NULL || pml4_get_page(thread_current()->pml4, file) == NULL || !is_user_vaddr(file) || strlen(file) == 0)
		exit(-1);

	struct file *file_2;
	if (file_2 = filesys_open(file))
		return file_2;
	else
		exit(0);

	// return filesys_open(file);
}

억지를 부려보았지만

Acceptable output:
  (open-missing) begin
  (open-missing) end
  open-missing: exit(0)
Differences in `diff -u' format:
  (open-missing) begin
- (open-missing) end
  open-missing: exit(0)

실패

  int handle = open ("no-such-file");
  if (handle != -1)
    fail ("open() returned %d", handle);

테스트 파일을 보면,
open이 반환하는 값이 -1 이어야 함.

void test_main(void)
{
  // int handle = open ("no-such-file");
  // if (handle != -1)
  //   fail ("open() returned %d", handle);
  int handle = 111;
}

이렇게 바꿔보았으나

Executing 'open-missing':
(open-missing) begin
(open-missing) end
open-missing: exit(0)

상태 코드가 바뀌지는 않았음.
다시 생각해보니 당연. rdi였나? 거기에 넣어줘야 exit 상태 코드가 변함.

  • exit할 때 상태 코드는 0이어야 하고,
  • open은 아무 일도 발생 안 시켜야 하고,
  • open의 반환값은 -1이어야 함.

그냥 이거 하니까

통과함. 뭐임? 쉬운 거였네

open-empty

이것도 기존 조건문에서 따로 빼서 예외 처리 해주니까 통과.

close (보류)

https://maxlevsnail.com/pintos-project-2/

filesys.c에 있는 remove 쓰면 되는 건가? 하다가
힌트 좀 봤음. 보길 잘한듯.
파일 디스크립터 테이블을 순회해서 입력받은 fd를 찾으라고 함.

파일 디스크립터는 열린 파일에 붙은 값이니까
open을 뜯어보면 될듯

하고 열심히 뜯어봤는데 inode밖에 없음.
ctrl+f로 fd 찾아봤는데 그딴거 없음.
설마 fd table을 내가 만들어줘야 하는건가? 하고 보니까

file descriptor table

ㅇㅇ 진짜였음. 내가 구현해야됨.

번역:

리스트 너무 느려서 배열 말록해서 구현함

  • 각 쓰레드는 파일 디스크립터 요소들의 배열을 가리키는 struct fdtable_element •를 갖고 있음.
    • fdtable_element는 필드가 2개 있음: num, fd_element •target
      • num: large fd들
      • fd_element •target: 가리켜진 파일
  • 각 쓰레드는 file struct 포인터의 배열을 가리키고 있는 fd_element •를 갖고 있음.
    • fd_element는 필드가 2개 있음: stack, target
      • stack: 이 파일에서 열려있는 fd 개수
      • target: file struct
  • dup2 구현 끝남. large fd가 허용되게 할 수 있는지 생각해봐야함.
    • 테케들에 그렇게까지 큰 fd들이 없어서 구현 안 바꿈
  • stdin하고 stdout은 struct fd_element •1과 2로 표현됨. (이 주소는 불가능한 주소)
  • FD table free 제대로 안 하면 multi-oom 테스트 fail

아 근데 왤케 내장 list 라이브러리로 간단하게 하고 싶지?
느려봤자 얼마나 느리다는거임?

굳이 몸 비틀어가면서 리스트 띡- 하는거 포기해야되나?
근데 이 사람이 시행착오 겪고 "하지마세요"라고 취소선까지 그어놨는데
흠;

일단 실제 파일 디스크립터들이 어떻게 구현되는지 좀 확인해봐야할듯?

https://velog.io/@biomatrix117/%ED%81%AC%EB%9E%98%ED%94%84%ED%86%A4-%EC%A0%95%EA%B8%80-TIL-0905#-week04-pintos-project2-file-manipulation

가 아니라 저번에 정리해놨던 거에 (스탠포드 핀토스 기반이라고는 하지만) 해당 내용 있었음.
블로그 내용하고는 살짝 다르다. 그리고 next_fd를 어따 써먹는 건지 전혀 모르겠음.

아니 그리고 위에 있는 thread A랑 아래에 있는 thread A, B랑 fdt가 다른거임
이중 포인터는 또 왜 쓴거임

모르겠고 포인터 담는 배열만 있으면 되지 않을까? 바로 선언
했는데 아까 리스트가 왜 느리다고 했는지 바로 깨달아버림.
이거 원하는거 못 찾으면 인덱스 64까지 매번 순회 돈다.
그걸 극복하기 위해서 next_fd를 쓴게 아닐까 싶음.
근데 여전히 next_fd가 뭔지는 잘 모르겠음.

  1. last_fd를 선언해서 맨 끝이 어딘지 확인? → 그거 관리하는거 너무 귀찮
  2. fdt가 갖고 있는 원소 수만 체크하고 원소 다 돌면 탐색 끝? → 나름 괜찮은 타협안인듯

아 ㅇㅋㅇㅋ 다음에 할당할 파일 디스크립터 번호였구나

	memset(&t->fdt, 0, sizeof(t->fdt)); 
	// t->fdt = {0};, memset(&t->fdt, 0, 64); 쓰면 안됨

초기화하려다가 빨간 줄 떴었음.

  1. t->fdt = {0} 안되는 이유 : 전역 배열이 아니라 로컬 배열이라서 이렇게 하면 안된다고 함
  2. memset(&t->fdt, 0, 64) 안되는 이유 : 배열 전체의 크기는 64 * 8 = 512바이트인데 이렇게 하면 64비트만 초기화됨

fdt 0하고 1은 표준 입력, 출력으로 해놔야 되는거 아는데
뭐 어쩌라는 건지 모르겠고(콘솔 버퍼에 연결하라는거?) 어차피 쓰지도 않을테니까 일단 있는 척하기

thread가 종료되면

  • 모든 파일을 닫기
  • 파일 디스크립터 테이블 할당 해제

이제 이거 해야되는데
모든 파일 닫기는 ㅇㅋ 알겠음 2부터 63까지 순회하면서 파일 닫아버리면 되는거 아님
근데 할당 해제는 뭔 말일까? 그냥 배열 선언한건데 끄면 되는거 아님?

아 맞다 이거 malloc으로 힙 영역에 선언 안 해주면 스택 영역에 있는거라 사라지는구나
그래서 블로그에서 malloced array라고 했던 거였구나
피곤하다 피곤해

아오 뭔 소리여 배열인데 왜 이중 포인터로 선언해야됨

아오 할루시네이션
뭐가 맞는거임

ㅇㅋ 이중 포인터가 맞음
굳이 교차 검증 안 해봐도 다시 생각해보니까 이중 포인터가 맞음

아 그리고 아까 왜 위는 그냥 배열인데
아래는 이중 포인터임? 라고 가졌던 의문이 해소됨.

위에 건 구조체 선언해놓는거고
아래 건 구조체 쓸 때 얘기였던 것 같음

근데 그냥 struct file이 아니라 포인터 배열이어야 되는거 아닌가...?

애초에 포인터를 안 먹이면 빨간 줄 뜬다고...

https://stackoverflow.com/questions/15686890/how-to-allocate-array-of-pointers-for-strings-by-malloc-in-c

이것도 보고 분명 말록 제대로 한 거 맞는데
왜 안되지 하고 봤더니 stdlib를 include 안해서
커서 올려도 malloc 안 뜸
물론 stdlib include해줘도 안됨.

그냥 포인터 배열을 동적 할당 해준다는 간단한 건데
문제가 펑펑 터지고 있다.

"expression must be a modifiable lvalue" 오류가 발생하는 이유는, 배열 이름은 상수 포인터와 같은 역할을 하기 때문에, 배열에 대해 주소 자체를 변경할 수 없기 때문입니다. 배열은 고정된 메모리 주소를 가리키므로, t->fdt와 같이 배열 자체에 malloc()으로 동적 할당을 하려는 시도는 불가능합니다.

따라서, 동적 할당을 위해서는 배열을 포인터로 선언해야 합니다.

struct thread에는

	struct file **fdt; /* 파일 디스크립터 테이블 */
	int next_fd;	   /* 다음에 할당할 파일 디스크립터 번호 */

선언해주고

init_thread()할 때

	t->fdt = malloc(64 * sizeof(struct file *));   // 동적 할당 (없어지지 말라고)
	memset(t->fdt, 0, 64 * sizeof(struct file *)); // 모든 포인터를 0으로 초기화 // t->fdt = {0};, memset(&t->fdt, 0, 64); 쓰면 안됨
	t->fdt[0] = STDIN_FILENO;					   // 있는 척하기
	t->fdt[1] = STDOUT_FILENO;					   // 있는 척하기

이거 추가

Kernel panic in run: PANIC at ../../threads/thread.c:319 in thread_current(): assertion `t->status == THREAD_RUNNING' failed.
Call stack: 0x80042183f3 0x80042070b2 0x800420a95d 0x800420a3bb 0x800420b810 0x800420be32 0x8004207a97 0x8004206aee 0x8004206068
Translation of call stack:
0x00000080042183f3: debug_panic (lib/kernel/debug.c:32)
0x00000080042070b2: thread_current (threads/thread.c:321)
0x000000800420a95d: lock_held_by_current_thread (threads/synch.c:340)
0x000000800420a3bb: lock_acquire (threads/synch.c:198)
0x000000800420b810: palloc_get_multiple (threads/palloc.c:267 (discriminator 4))
0x000000800420be32: malloc (threads/malloc.c:103)
0x0000008004207a97: init_thread (threads/thread.c:559)
0x0000008004206aee: thread_init (threads/thread.c:163)
0x0000008004206068: main (threads/init.c:82)

그랬더니 바로 터짐

아니 말록이 stdlib가 아니라 다른 곳에 이미 있다고?
stdlib 빼도 컴파일 잘 되네?

pintos에서 따로 구현돼있는 말록이 있었음
여기로 데려간 다음

너 이거 쓸 준비안됐잖아
하면서 오류 일으켜버림

극단적인 방법으론 아예 이거 지워버리는 것도 있음 ㅋㅋㅋ
그냥 c 함수 malloc 써버리는거임

근데 그러면 안되겠지

아 그리고 위에 있던 슬라이드 다시 보니까 유저 영역이 아니라
커널 영역에 각 쓰레드가 갖고 있는 포인터 배열들 선언해야 된다는데
그건 또 어떻게 하는거여

아 이거였음?

지금 일요일 23시 26분인데
앞으로 남은 월, 화, 수 동안 전부 다 답지 안 보고 하는 건 불가능할 것 같음

알고리즘 할 때도 안되는 건 답지 봤었고
이후에는 실력 늘어서 웬만한 건 답지 안보고 하게 됐고

지금도 동기들한테는 잘만 물어보면서
인터넷에서 답지 보면 안된다는 자존심 세우면서

할 거 못하고 배울 거 못 배우면 안될듯

다음 건 수월하게 진행할 수 있을거라고 해도
파일 디스크립터 테이블 동적 할당하는 거 만큼은 답지 보자

해서 답지를 봤는데

https://velog.io/@smilelee9/pintos-kaist

init_thread()가 아니라 thread_create()할 때 해야되는거였구나

아 대충 선택지의 후보에는 들었는데
왜 여기까지 생각이 닿지 못했을까
그냥 THREAD_RUNNING부터 추론을 시작했으면 될 수도 있었을 것 같은데

근데 내 문제랑 완벽히 똑같은 문제가 설명돼있으니까 웬지 모를 쾌감이 느껴졌다
바로 아 할 수 있었는데 하고 아쉽긴 했지만

그리고 palloc으로 해도 되지만 그냥 malloc 쓰는게 좋을듯

https://velog.io/@c4fiber/pintOS-Palloc%EA%B3%BC-bitmap%EC%9D%98-%EC%97%B0%EA%B4%80%EC%84%B1
여기 보니까 4kb나 준다는데 굳이?

thread_create()에서 malloc 해주니까 오류 안 생기고 정상적으로 돈다.
이제 파일 디스크립터를 할당해주는 즐거운 과정만 남았다.

최적화 신경쓰는 멋있는 사람 같이 보이도록 ifdef USERPROG도 해줌

void thread_exit(void)
{
	ASSERT(!intr_context());

#ifdef USERPROG
	// 모든 파일 close 해줘야됨
	free(thread_current()->fdt);
	process_exit();
#endif

모든 파일 close도 해줘야되는데 여기서 든 생각이
어떤 프로세스가 연 파일을 다른 프로세스에서도 열 수가 있는데
파일 디스크립터에 있는거 다 닫아버리면
다른 프로세스가 열고 있던거 닫혀버리는거 아닌가?
그럼 안되지 않음?
여는거는 따로인가?

까지는 일단 생각하지 말자.
나중에 테케에서 문제되면 그때 생각해도 될듯.

(다음 날 생각해봤는데, 그래서 디스크에 락 검.
어차피 경쟁조건 해소하려고 락 필요함.)


아무튼 이제 create나 open할 때 파일 디스크립터를 추가시켜주면 됨

그건 내일의 내가 해줄거임



⚔️ 백준

📌 21606 아침 산책

저번에 못 풀긴 했는데
정답 풀이 논리를 기억하고 있었음
그래서 쉬울 줄 알았는데 실수 많이 해서 살짝 애먹음

IO=[-1]+list(input().strip()) # 안인지 밖인지

문자열을 받은 리스트인데 그대로 숫자('1'이 아니라 그냥 1)랑 비교해버린 실수

for i in range(1,N+1):
    if IO[i]=='0' and visited[i]==False: # 탐색의 시작점
        stack=[i]
        in_cnt = 0
        while stack:
            for edge in graph[i]:
                if visited[edge]==False:
                    visited[edge]=True
                    if IO[edge]=='1': 
                        in_cnt+=1
                    else: 
                        stack.append(edge)
        course += in_cnt*(in_cnt-1)

stack에서 pop한게 아니라 i를 그대로 쓰는 실수

for i in range(1,N+1):
    if IO[i]=='0' and visited[i]==False: # 탐색의 시작점
        visited[i] = True # 여기 == 해놓고 왜 안되지? 이러고 있었음
        stack=[i]
        in_cnt = 0
        while stack:
            e = stack.pop()
            for edge in graph[e]:
                if IO[edge]=='1': 
                    in_cnt+=1
                elif IO[edge]=='0' and visited[edge]==False: 
                    visited[edge]=True
                    stack.append(edge)
        course += in_cnt*(in_cnt-1)

visited[i] = True를 해줘야 된다는 사실을 몰랐음.
이거 추가 안 해주면 한 번 다시 되돌아왔을 때 스택에 또 추가된다.

알고 나서도 == 으로 해놓고 왜 안되지? 이러고 있었음.

import sys
input = sys.stdin.readline
N=int(input())
IO=[-1]+list(input().strip()) # 안인지 밖인지
visited = [False for i in range(N+1)] # 방문을 했었는지
course = 0
graph={i:[] for i in range(N+1)}
for _ in range(N-1): # 간선 받기
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# 순회하다가 밖이고 visited=false면 탐색 시작
# 안이 발견되면 안 개수 더하고 더 탐색 x
# 탐색 다 끝내면 안 개수가 n이라고 할 때 n(n-1)

for i in range(1,N+1):
    if IO[i]=='0' and visited[i]==False: # 탐색의 시작점
        visited[i] = True # 여기 == 해놓고 왜 안되지? 이러고 있었음
        stack=[i]
        in_cnt = 0
        while stack:
            e = stack.pop()
            for edge in graph[e]:
                if IO[edge]=='1': 
                    in_cnt+=1
                elif IO[edge]=='0' and visited[edge]==False: 
                    visited[edge]=True
                    stack.append(edge)
        course += in_cnt*(in_cnt-1)

    # 순회하다가 안이면 탐색 시작
    # 자기가 갖고 있는 간선들 확인하고 안이면 경로 개수 더하기
    elif IO[i]=='1':
        for edge in graph[i]:
            if IO[edge]=='1':
                course+=1

print(course)

아무튼 200점 완료

profile
lazyArtisan
이전 포스트

크래프톤 정글 TIL : 0907

다음 포스트

크래프톤 정글 TIL : 0909

0개의 댓글