[Pintos-KAIST] Project 2 : Hierarchical Process Structure

μœ μ„ Β·2024λ…„ 5μ›” 9일
pintosμ •κΈ€ 8μ£Όμ°¨μ •κΈ€ 9μ£Όμ°¨
0

Pintos - KAIST

λͺ©λ‘ 보기
9/16
post-thumbnail

πŸ‘©πŸ»β€πŸ’» GITHUB λ ˆν¬μ§€ν† λ¦¬
πŸ‘©πŸ»β€πŸ’» GITHUB Hierarchical Process Structure 이슈

과제 μ„€λͺ…

  • ν•€ν† μŠ€λŠ” ν”„λ‘œμ„ΈμŠ€κ°„μ— λΆ€λͺ¨μ™€ μžμ‹κ΄€κ³„λ₯Ό λͺ…μ‹œν•˜λŠ” 정보가 μ—†μŒ
    • λΆ€λͺ¨μ™€ μžμ‹μ˜ ꡬ뢄이 μ—†κ³  μžμ‹ ν”„λ‘œμ„ΈμŠ€μ˜ 정보λ₯Ό μ•Œμ§€ λͺ»ν•˜κΈ° λ•Œλ¬Έμ— μžμ‹μ˜ μ‹œμž‘/μ’…λ£Œ 전에 λΆ€λͺ¨ ν”„λ‘œμ„ΈμŠ€κ°€ μ’…λ£Œλ˜λŠ” ν˜„μƒμ΄ λ°œμƒκ°€λŠ₯ β†’ ν”„λ‘œκ·Έλž¨μ΄ μ‹€ν–‰λ˜μ§€ μ•ŠμŒ
    • ex) init ν”„λ‘œμ„ΈμŠ€λŠ” μœ μ € ν”„λ‘œμ„ΈμŠ€μ˜ 정보λ₯Ό μ•Œμ§€ λͺ»ν•˜κΈ° λ•Œλ¬Έμ— μ‚¬μš©μž ν”„λ‘œκ·Έλž¨μ΄ μ‹€ν–‰ 되기 전에 ν•€ν† μŠ€λ₯Ό μ’…λ£Œ
  • ν”„λ‘œμ„ΈμŠ€μ˜ 정보에 λΆ€λͺ¨μ™€ μžμ‹ν•„λ“œλ₯Ό μΆ”κ°€, 이λ₯Ό κ΄€λ¦¬ν•˜λŠ” ν•¨μˆ˜λ₯Ό μ œμž‘
    • μžμ‹ ν”„λ‘œμ„ΈμŠ€ : 리슀트둜 κ΅¬ν˜„
    • μžμ‹ λ¦¬μŠ€νŠΈμ—μ„œ μ›ν•˜λŠ” ν”„λ‘œμ„ΈμŠ€λ₯Ό 검색, μ‚­μ œν•˜λŠ” ν•¨μˆ˜ κ΅¬ν˜„
  • ν”„λ‘œμ„ΈμŠ€ λ””μŠ€ν¬λ¦½ν„°(struct thread)에 λΆ€λͺ¨ ν”„λ‘œμ„ΈμŠ€μ™€ μžμ‹ ν”„λ‘œμ„ΈμŠ€λ“€μ„ κ°€λ¦¬ν‚€λŠ” 자료ꡬ쑰 μΆ”κ°€
  • exec(), wait(), fork() κ΅¬ν˜„ (μ„Έλ§ˆν¬μ–΄λ₯Ό 이용)

κ΅¬ν˜„

1. ν”„λ‘œμ„ΈμŠ€ 계측 ꡬ쑰 κ΅¬ν˜„

1.1. 헀더 파일 μ„ μ–Έ

  • include/threads/thread.h
#include "threads/synch.h" /** project2-System Call */

1.2. thread 자료ꡬ쑰 μˆ˜μ •

  • include/threads/thread.h
#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4;                     /* Page map level 4 */
	/** project2-System Call */
	int exit_status;

	int fd_idx;              // 파일 λ””μŠ€ν¬λ¦½ν„° 인덱슀
    struct file **fdt;       // 파일 λ””μŠ€ν¬λ¦½ν„° ν…Œμ΄λΈ”
    struct file *runn_file;  // 싀행쀑인 파일

    struct intr_frame parent_if;  // λΆ€λͺ¨ ν”„λ‘œμ„ΈμŠ€ if
    struct list child_list;
    struct list_elem child_elem;

	struct semaphore fork_sema;  // forkκ°€ μ™„λ£Œλ  λ•Œ signal
    struct semaphore exit_sema;  // μžμ‹ ν”„λ‘œμ„ΈμŠ€ μ’…λ£Œ signal
    struct semaphore wait_sema;  // exit_semaλ₯Ό 기닀릴 λ•Œ μ‚¬μš©
#endif

1.3. init_thread() ν•¨μˆ˜ μˆ˜μ •

  • threads/thread.c
static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);

	/** project1-Advanced Scheduler */
    if (thread_mlfqs) {
        mlfqs_priority(t);
        list_push_back(&all_list, &t->all_elem);
    } else {
        t->priority = priority;
    }

    t->wait_lock = NULL;
    list_init(&t->donations);

    t->magic = THREAD_MAGIC;

    /** #Advanced Scheduler */
    t->original_priority = t->priority;
    t->niceness = NICE_DEFAULT;
    t->recent_cpu = RECENT_CPU_DEFAULT;

	/** project2-System Call */
    t->runn_file = NULL;

    list_init(&t->child_list);
    sema_init(&t->fork_sema, 0);
    sema_init(&t->exit_sema, 0);
    sema_init(&t->wait_sema, 0);
}

1.4. thread_create() ν•¨μˆ˜ μˆ˜μ •

  • threads/thread.c
tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;

	ASSERT (function != NULL);

	/* Allocate thread. */
	t = palloc_get_page (PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	/* Initialize thread. */
	init_thread (t, name, priority);
	tid = t->tid = allocate_tid ();

	#ifdef USERPROG
	/** project2-System Call */
    t->fdt = palloc_get_multiple(PAL_ZERO, FDT_PAGES);
    if (t->fdt == NULL)
        return TID_ERROR;

    t->exit_status = 0;  // exit_status μ΄ˆκΈ°ν™”

    t->fd_idx = 3;
    t->fdt[0] = 0;  // stdin μ˜ˆμ•½λœ 자리 (dummy)
    t->fdt[1] = 1;  // stdout μ˜ˆμ•½λœ 자리 (dummy)
    t->fdt[2] = 2;  // stderr μ˜ˆμ•½λœ 자리 (dummy)

    list_push_back(&thread_current()->child_list, &t->child_elem);
#endif

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t) kernel_thread;
	t->tf.R.rdi = (uint64_t) function;
	t->tf.R.rsi = (uint64_t) aux;
	t->tf.ds = SEL_KDSEG;
	t->tf.es = SEL_KDSEG;
	t->tf.ss = SEL_KDSEG;
	t->tf.cs = SEL_KCSEG;
	t->tf.eflags = FLAG_IF;

	/* Add to run queue. */
	thread_unblock (t);

	/** project1-Priority Scheduling */
	if(t->priority > thread_current()->priority)
		thread_yield();

	return tid;
}

2. get_child_process() ν•¨μˆ˜ κ΅¬ν˜„

  • userprog/process.c
  • ν˜„μž¬ ν”„λ‘œμ„ΈμŠ€μ˜ μžμ‹ 리슀트λ₯Ό κ²€μƒ‰ν•˜μ—¬ ν•΄λ‹Ή pid에 λ§žλŠ” ν”„λ‘œμ„ΈμŠ€ λ””μŠ€ν¬λ¦½ν„°λ₯Ό λ°˜ν™˜
    • struct thread *thread_current(void) : ν˜„μž¬ ν”„λ‘œμ„ΈμŠ€μ˜ λ””μŠ€ν¬λ¦½ν„° λ°˜ν™˜
  • pidλ₯Ό κ°–λŠ” ν”„λ‘œμ„ΈμŠ€ λ””μŠ€ν¬λ¦½ν„°κ°€ μ‘΄μž¬ν•˜μ§€ μ•Šμ„ 경우 NULL λ°˜ν™˜
/** project2-System Call */
struct thread *get_child_process(int pid);
int process_add_file(struct file *f);
struct file *process_get_file(int fd);
int process_close_file(int fd);

β†’ process.h에 ν•¨μˆ˜ μ„ μ–ΈλΆ€ν„°!

/** project2-System Call */
struct thread 
*get_child_process(int pid) 
{
    struct thread *curr = thread_current();
    struct thread *t;

    for (struct list_elem *e = list_begin(&curr->child_list); e != list_end(&curr->child_list); e = list_next(e)) {
        t = list_entry(e, struct thread, child_elem);

        if (pid == t->tid)
            return t;
    }

    return NULL;
}

3. fork κ΅¬ν˜„ 및 κ΄€λ ¨ ν•¨μˆ˜ κ΅¬ν˜„

3.1. fork() κ΅¬ν˜„

  • userprog/syscall.c

pid_t fork(const char *thread_name) {
    check_address(thread_name);

    return process_fork(thread_name, NULL);
}

3.2. process_fork() ν•¨μˆ˜ κ΅¬ν˜„

  • userprog/process.c
tid_t
process_fork (const char *name, struct intr_frame *if_ UNUSED) {
	struct thread *curr = thread_current();

    struct intr_frame *f = (pg_round_up(rrsp()) - sizeof(struct intr_frame));  // ν˜„μž¬ μ“°λ ˆλ“œμ˜ if_λŠ” νŽ˜μ΄μ§€ λ§ˆμ§€λ§‰μ— λΆ™μ–΄μžˆλ‹€.
    memcpy(&curr->parent_if, f, sizeof(struct intr_frame));                    // 1. λΆ€λͺ¨λ₯Ό μ°ΎκΈ° μœ„ν•΄μ„œ 2. do_fork에 전달해주기 μœ„ν•΄μ„œ

    /* ν˜„μž¬ μŠ€λ ˆλ“œλ₯Ό μƒˆ μŠ€λ ˆλ“œλ‘œ λ³΅μ œν•©λ‹ˆλ‹€.*/
    tid_t tid = thread_create(name, PRI_DEFAULT, __do_fork, curr);

    if (tid == TID_ERROR)
        return TID_ERROR;

    struct thread *child = get_child_process(tid);

    sema_down(&child->fork_sema);  // μƒμ„±λ§Œ 해놓고 μžμ‹ ν”„λ‘œμ„ΈμŠ€κ°€ __do_forkμ—μ„œ fork_semaλ₯Ό sema_up 해쀄 λ•ŒκΉŒμ§€ λŒ€κΈ°

    if (child->exit_status == TID_ERROR)
        return TID_ERROR;

    return tid;  // λΆ€λͺ¨ ν”„λ‘œμ„ΈμŠ€μ˜ 리턴값 : μƒμ„±ν•œ μžμ‹ ν”„λ‘œμ„ΈμŠ€μ˜ tid
}

3.3. duplicate_pte() ν•¨μˆ˜ κ΅¬ν˜„

  • userprog/process.c
static bool
duplicate_pte (uint64_t *pte, void *va, void *aux) {
	struct thread *current = thread_current ();
	struct thread *parent = (struct thread *) aux;
	void *parent_page;
	void *newpage;
	bool writable;

	/* 1. TODO: If the parent_page is kernel page, then return immediately. */
	if (is_kernel_vaddr(va))
        return true;

	/* 2. Resolve VA from the parent's page map level 4. */
    parent_page = pml4_get_page(parent->pml4, va);
    if (parent_page == NULL)
        return false;

	/* 3. TODO: Allocate new PAL_USER page for the child and set result to
	 *    TODO: NEWPAGE. */
	 newpage = palloc_get_page(PAL_ZERO);
    if (newpage == NULL)
        return false;

	/* 4. TODO: Duplicate parent's page to the new page and
	 *    TODO: check whether parent's page is writable or not (set WRITABLE
	 *    TODO: according to the result). */
	memcpy(newpage, parent_page, PGSIZE);
    writable = is_writable(pte);

	/* 5. Add new page to child's page table at address VA with WRITABLE
	 *    permission. */
	if (!pml4_set_page (current->pml4, va, newpage, writable)) {
		/* 6. TODO: if fail to insert page, do error handling. */
		return false;
	}
	return true;
}

3.4. __do_fork() ν•¨μˆ˜ κ΅¬ν˜„

  • userprog/process.c
static void
__do_fork (void *aux) {
	struct intr_frame if_;
	struct thread *parent = (struct thread *) aux;
	struct thread *current = thread_current ();
	/* TODO: somehow pass the parent_if. (i.e. process_fork()'s if_) */
	struct intr_frame *parent_if = &parent->parent_if;
	bool succ = true;

	/* 1. Read the cpu context to local stack. */
	memcpy (&if_, parent_if, sizeof (struct intr_frame));
    if_.R.rax = 0;  // μžμ‹ ν”„λ‘œμ„ΈμŠ€μ˜ returnκ°’ (0)

	/* 2. Duplicate PT */
	current->pml4 = pml4_create();
	if (current->pml4 == NULL)
		goto error;

	process_activate (current);
#ifdef VM
	supplemental_page_table_init (&current->spt);
	if (!supplemental_page_table_copy (&current->spt, &parent->spt))
		goto error;
#else
	if (!pml4_for_each (parent->pml4, duplicate_pte, parent))
		goto error;
#endif

	/* TODO: Your code goes here.
	 * TODO: Hint) To duplicate the file object, use `file_duplicate`
	 * TODO:       in include/filesys/file.h. Note that parent should not return
	 * TODO:       from the fork() until this function successfully duplicates
	 * TODO:       the resources of parent.*/

    if (parent->fd_idx >= FDCOUNT_LIMIT)
        goto error;

    current->fd_idx = parent->fd_idx;  // fdt 및 idx 볡제
    for (int fd = 3; fd < parent->fd_idx; fd++) {
        if (parent->fdt[fd] == NULL)
            continue;
        current->fdt[fd] = file_duplicate(parent->fdt[fd]);
    }

    sema_up(&current->fork_sema);  // fork ν”„λ‘œμ„ΈμŠ€κ°€ μ •μƒμ μœΌλ‘œ μ™„λ£ŒλμœΌλ―€λ‘œ ν˜„μž¬ fork용 sema unblock

    process_init();

    /* Finally, switch to the newly created process. */
    if (succ)
        do_iret(&if_);  // 정상 μ’…λ£Œ μ‹œ μžμ‹ Processλ₯Ό μˆ˜ν–‰ν•˜λŸ¬ 감

error:
    sema_up(&current->fork_sema);  // λ³΅μ œμ— μ‹€νŒ¨ν–ˆμœΌλ―€λ‘œ ν˜„μž¬ fork용 sema unblock
    exit(TID_ERROR);
}

4. exec κ΅¬ν˜„ 및 κ΄€λ ¨ ν•¨μˆ˜ κ΅¬ν˜„

  • μžμ‹ ν”„λ‘œμ„ΈμŠ€λ₯Ό μƒμ„±ν•˜κ³  ν”„λ‘œκ·Έλž¨μ„ μ‹€ν–‰μ‹œν‚€λŠ” μ‹œμŠ€ν…œ 콜
  • ν”„λ‘œμ„ΈμŠ€λ₯Ό μƒμ„±ν•˜λŠ” ν•¨μˆ˜ 이용 (Command Line Parsing μ°Έμ‘°)
  • ν”„λ‘œμ„ΈμŠ€ 생성에 성곡 μ‹œ μƒμ„±λœ ν”„λ‘œμ„ΈμŠ€μ— pid 값을 λ°˜ν™˜, μ‹€νŒ¨ μ‹œ-1 λ°˜ν™˜
  • λΆ€λͺ¨ ν”„λ‘œμ„ΈμŠ€λŠ” μžμ‹ ν”„λ‘œμ„ΈμŠ€μ˜ μ‘μš© ν”„λ‘œκ·Έλž¨μ΄ λ©”λͺ¨λ¦¬μ— νƒ‘μž¬ 될 λ•ŒκΉŒμ§€ λŒ€κΈ°
  • μ„Έλ§ˆν¬μ–΄ 이용
  • cmd_line : μƒˆλ‘œμš΄ ν”„λ‘œμ„ΈμŠ€μ— μ‹€ν–‰ν•  ν”„λ‘œκ·Έλž¨ λͺ…λ Ήμ–΄
  • pid_tλŠ” tid_t와 λ™μΌν•œ int μžλ£Œν˜•

4.1. exec() κ΅¬ν˜„

  • userprog/syscall.c
int 
exec(const char *cmd_line) 
{
    check_address(cmd_line);

    off_t size = strlen(cmd_line) + 1;
    char *cmd_copy = palloc_get_page(PAL_ZERO);

    if (cmd_copy == NULL)
        return -1;

    memcpy(cmd_copy, cmd_line, size);

    if (process_exec(cmd_copy) == -1)
        return -1;

    return 0;  // process_exec μ„±κ³΅μ‹œ 리턴 κ°’ μ—†μŒ (do_iret)
}

4.2. process_exec() ν•¨μˆ˜ μˆ˜μ •

  • userprog/process.c
int
process_exec (void *f_name) {
    char *file_name = f_name;
    bool success;

    /* μŠ€λ ˆλ“œ κ΅¬μ‘°μ—μ„œλŠ” intr_frame을 μ‚¬μš©ν•  수 μ—†μŠ΅λ‹ˆλ‹€.
     * ν˜„μž¬ μ“°λ ˆλ“œκ°€ μž¬μŠ€μΌ€μ€„ 되면 μ‹€ν–‰ 정보λ₯Ό λ©€λ²„μ—κ²Œ μ €μž₯ν•˜κΈ° λ•Œλ¬Έμž…λ‹ˆλ‹€. */
    struct intr_frame if_;
    if_.ds = if_.es = if_.ss = SEL_UDSEG;
    if_.cs = SEL_UCSEG;
    if_.eflags = FLAG_IF | FLAG_MBS;

    /* We first kill the current context */
    process_cleanup();

    /** #Project 2: Command Line Parsing - λ¬Έμžμ—΄ 뢄리 */
    char *ptr, *arg;
    int argc = 0;
    char *argv[64];

    for (arg = strtok_r(file_name, " ", &ptr); arg != NULL; arg = strtok_r(NULL, " ", &ptr))
        argv[argc++] = arg;

    /* And then load the binary */
    success = load(file_name, &if_);

    /* If load failed, quit. */
    if (!success)
        return -1;

    argument_stack(argv, argc, &if_);

    palloc_free_page(file_name);

    /** #Project 2: Command Line Parsing - λ””λ²„κΉ…μš© 툴 */
    // hex_dump(if_.rsp, if_.rsp, USER_STACK - if_.rsp, true);

    /* Start switched process. */
    do_iret(&if_);
    NOT_REACHED();
}

5. wait κ΅¬ν˜„ 및 κ΄€λ ¨ ν•¨μˆ˜ κ΅¬ν˜„

  • ν˜„μž¬ process_wait()λŠ”-1을 리턴
    • init ProcessλŠ” μœ μ € ν”„λ‘œμ„ΈμŠ€κ°€ μ’…λ£Œλ  λ•ŒκΉŒμ§€ λŒ€κΈ°ν•˜μ§€ μ•Šκ³  ν•€ν† μŠ€ μ’…λ£Œ
  • process_wait() κΈ°λŠ₯을 κ΅¬ν˜„
    • μžμ‹ν”„λ‘œμ„ΈμŠ€κ°€ λͺ¨λ‘ μ’…λ£Œλ  λ•ŒκΉŒμ§€ λŒ€κΈ°(sleep state)
    • μžμ‹ ν”„λ‘œμ„ΈμŠ€κ°€ μ˜¬λ°”λ₯΄κ²Œ μ’…λ£Œκ°€ λλŠ”μ§€ 확인
  • wait() μ‹œμŠ€ν…œ 콜 κ΅¬ν˜„
    • process_wait() ν•¨μˆ˜μ™€ λ™μΌν•œ κΈ°λŠ₯을 μˆ˜ν–‰

5.1. wait() κ΅¬ν˜„

  • userprog/syscall.c
int wait(pid_t tid) {
    return process_wait(tid);
}

5.2. process_wait() ν•¨μˆ˜ μˆ˜μ •

  • userprog/process.c
int
process_wait (tid_t child_tid UNUSED) {
	/* 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 *child = get_child_process(child_tid);
    if (child == NULL)
        return -1;

    sema_down(&child->wait_sema);  // μžμ‹ ν”„λ‘œμ„ΈμŠ€κ°€ μ’…λ£Œλ  λ•Œ κΉŒμ§€ λŒ€κΈ°.

    int exit_status = child->exit_status;
    list_remove(&child->child_elem);

    sema_up(&child->exit_sema);  // μžμ‹ ν”„λ‘œμ„ΈμŠ€κ°€ 죽을 수 μžˆλ„λ‘ signal

    return exit_status;
}

ν…ŒμŠ€νŠΈ κ²°κ³Ό


profile
μœ μ„ 
Sunny Day!
이전 포슀트

[Pintos-KAIST] Project 2 : File Descriptor

λ‹€μŒ 포슀트

[Pintos-KAIST] Project 2 : Extend File Descriptor

0개의 λŒ“κΈ€