크래프톤 정글 week11, day81 - 시간 복잡도, 연결리스트, argument passing

< 시간 복잡도 >

https://moonmisae-cdpt.tistory.com/171

시간 복잡도(Big-oh Notaion)

 

< 연결 리스트 >

https://moonmisae-cdpt.tistory.com/172

연결 리스트(Linked List)

---

pintos project 2 - userprog의 첫 테스트는 argument passing 이다.

args-none, args-single 등등 여러 테스트 케이스가 있지만 argument passing으로 하나로 묶어서 해결하는게 좋을 것 같다.

하나씩 할려고 해도 결국 다른 부분이 완성이 되야 테스트가 넘어가는 것 같다.

일단 argument passing의 시작은 init.c의 main 함수에서 시작한다.

int
main (void) {
	uint64_t mem_end;
	char **argv;
	/* Clear BSS and get machine's RAM size. */
	bss_init ();
	

	/* Break command line into arguments and parse options. */
	argv = read_command_line ();
	argv = parse_options (argv);

	/* Initialize ourselves as a thread so we can use locks,
	   then enable console locking. */
	thread_init ();
	console_init ();

	/* Initialize memory system. */
	mem_end = palloc_init ();
	malloc_init ();
	paging_init (mem_end);

#ifdef USERPROG
	tss_init ();
	gdt_init ();
#endif
	/* Initialize interrupt handlers. */
	intr_init ();
	timer_init ();
	kbd_init ();
	input_init ();
#ifdef USERPROG
	exception_init ();
	syscall_init ();
#endif
	/* Start thread scheduler and enable interrupts. */
	thread_start ();
	serial_init_queue ();
	timer_calibrate ();

#ifdef FILESYS
	/* Initialize file system. */
	disk_init ();
	filesys_init (format_filesys);
#endif

#ifdef VM
	vm_init ();
#endif

	printf ("Boot complete.\n");
	/* Run actions specified on kernel command line. */
	run_actions (argv);

	/* Finish up. */
	if (power_off_when_done)
		power_off ();
	thread_exit ();
}

main 함수는 pintos가 시작하는 구간이며 터미널에서 입력한 명령줄을 가져오고 여러 구조체들을 초기화시키는 역할을 하는 등 프로젝트의 메인 구간이다.

read_command_line() 함수에서 명령줄을 가져온다.

static char **
read_command_line (void) {
	static char *argv[LOADER_ARGS_LEN / 2 + 1];
	char *p, *end;
	int argc;
	int i;

	argc = *(uint32_t *) ptov (LOADER_ARG_CNT);
	p = ptov (LOADER_ARGS);
	end = p + LOADER_ARGS_LEN;
	for (i = 0; i < argc; i++) {
		if (p >= end)
			PANIC ("command line arguments overflow");

		argv[i] = p;
		p += strnlen (p, end - p) + 1;
	}
	argv[argc] = NULL;

	/* Print kernel command line. */
	printf ("Kernel command line:");
	for (i = 0; i < argc; i++){
		if (strchr (argv[i], ' ') == NULL)
			printf (" %s", argv[i]);
		else
			printf (" '%s'", argv[i]);
	}
	printf ("\n");

	return argv;
}

이 함수에서 명령줄에 입력한 인자를 argv에 담아 반환한다.

static char **
parse_options (char **argv) {
	for (; *argv != NULL && **argv == '-'; argv++) {
		char *save_ptr;
		char *name = strtok_r (*argv, "=", &save_ptr);
		char *value = strtok_r (NULL, "", &save_ptr);

		if (!strcmp (name, "-h"))
			usage ();
		else if (!strcmp (name, "-q"))
			power_off_when_done = true;
#ifdef FILESYS
		else if (!strcmp (name, "-f"))
			format_filesys = true;
#endif
		else if (!strcmp (name, "-rs"))
			random_init (atoi (value));
		else if (!strcmp (name, "-mlfqs"))
			thread_mlfqs = true;
#ifdef USERPROG
		else if (!strcmp (name, "-ul"))
			user_page_limit = atoi (value);
		else if (!strcmp (name, "-threads-tests"))
			thread_tests = true;
#endif
		else
			PANIC ("unknown option `%s' (use -h for help)", name);
	}

	return argv;
}

다음 parse_options으로 가서 입력한 명령어를 각 부분으로 분류하고 argv를 반환한다.

그 후 스레드와 malloc 등등 초기화할 부분을 초기화시켜주고 argv 인자를 매개로 run_actions 함수를 실행한다.

 

static void
run_actions (char **argv) {
	/* An action. */
	struct action {
		char *name;                       /* Action name. */
		int argc;                         /* # of args, including action name. */
		void (*function) (char **argv);   /* Function to execute action. */
	};
	/* Table of supported actions. */
	static const struct action actions[] = {
		{"run", 2, run_task},
#ifdef FILESYS
		{"ls", 1, fsutil_ls},
		{"cat", 2, fsutil_cat},
		{"rm", 2, fsutil_rm},
		{"put", 2, fsutil_put},
		{"get", 2, fsutil_get},
#endif
		{NULL, 0, NULL},
	};

	while (*argv != NULL) {
		const struct action *a;
		int i;

		/* Find action name. */
		for (a = actions; ; a++)
			if (a->name == NULL)
				PANIC ("unknown action `%s' (use -h for help)", *argv);
			else if (!strcmp (*argv, a->name))
				break;

		/* Check for required arguments. */
		for (i = 1; i < a->argc; i++)
			if (argv[i] == NULL)
				PANIC ("action `%s' requires %d argument(s)", *argv, a->argc - 1);

		/* Invoke action and advance. */
		a->function (argv);
		argv += a->argc;
	}
}

이 함수는 인자로 받아온 argv[]에 지정된 모든 동작을 실행한다.

action의 맨 처음 값인 {"run", 2, run_task}의 run_task 로 들어가면

static void
 run_task (char **argv) {
	const char *task = argv[1];

	printf("Executing '%s':\n", task);
#ifdef USERPROG
	if (thread_tests){
		run_test (task);
	} else {
		process_wait (process_create_initd (task));
	}
#else
	run_test (task);
#endif
	printf ("Execution of '%s' complete.\n", task);
}

argv의 두 번째 인자를 받아와 그 값으로 프로세스를 생성시킨다.

process_wait (process_create_initd (task));의 process_create_initd로 들어가면

 

tid_t
process_create_initd (const char *file_name) {
	char *fn_copy;
	tid_t tid;

	/* Make a copy of FILE_NAME.
	 * Otherwise there's a race between the caller and load(). 
	 * FILE_NAME의 복사본을 만듭니다.
	 * 그렇지 않으면 발신자와 load() 사이에 경합이 발생합니다.
	 */
	fn_copy = palloc_get_page (PAL_USER);
	if (fn_copy == NULL)
		return TID_ERROR;
	strlcpy (fn_copy, file_name, PGSIZE);

	// // 스페이스 전 첫 부분을 실행하고자 하는 파일의 이름으로 지정
	// // argument passing
	char *save_ptr;
	strtok_r (file_name, " ", &save_ptr);

	/* Create a new thread to execute FILE_NAME. */
	tid = thread_create (file_name, PRI_DEFAULT, initd, fn_copy);

	// if (tid == TID_ERROR)
	// 	palloc_free_page (fn_copy);
	// return 	tid;
	if (tid == TID_ERROR) {
		palloc_free_page (fn_copy);
		palloc_free_page (file_name);
	}
	return tid == TID_ERROR ? TID_ERROR : tid;
}

인자로 보낸 task를 file_name으로 지정해 쓰레드를 생성하고 생성이 안됐으면 Error를 반환 생성됐으면 스레드 id를 반환한다.

 

int
process_wait (tid_t child_tid) {
	/* XXX: Hint) The pintos exit if process_wait (initd), we recommend you
	 * XXX:       to add infinite loop here before
	 * XXX:       implementing the process_wait. */
	struct thread *t = get_thread_from_tid(child_tid);
	if (t == NULL) {
		return -1;
	}

	sema_down(&t->wait_sema);
	list_remove(&t->child_list_elem);

	sema_up(&t->exit_sema);

	return t->exit_status; 
}

반환된 tid 값을 인자로 받아 process_wait으로 들어오면 해당 tid의 스레드를 가져와 sema_down 호출을 통해 대기시키고 세마포어가 다시 오를때까지 블락하며, 이 후 종료 상태를 반환한다.

이렇게 argument passing 은 진행되고 이 후 시스템 콜로 이동한다.

다시 한번 복습으로 쭉 훑어봤는데 흐름은 파악했지만 각 함수들을 깊게 들어가면 헷갈리긴 한다. 좀 더 공부해야될듯

 

학습 시간 : 10 ~ 24시