中庸 中庸

어떤 문제를 해결하는 데 걸리는 소요시간의 lower bound 를 찾는 방법 중의 하나인 방해꾼 논법에 대해 알아보겠습니다. 방해꾼 논법 (Adversary Argument) 1. 해결하는 사람 (Solver) 와 상대방 (Adversary) 간의 일종의 스무고개 같은 게임입니다. 2. Adversary 는 input 을 가지고 있고, solver 는 input 이 무엇인지 확인할 수 없습니다. 3. solver는 adversary 에게 질문을 할 수 있습니다. 이 때, 질문은 형식에 맞춰 질문해야 합니다. ( 알고리즘의 계산 모델 제약 조건이 질문의 형식 제약이라고 생각할 수 있습니다. ) 4. adversary는 solver 의 질문에 대해 답변을 해주어야 합니다. 이 때, solver 가 최대한 ..

해결 가능한 어떤 문제가 주어져 있다고 했을 때, 이 문제를 해결하는 algorithm 의 upper bound 와 lower bound 를 어떻게 정의할 수 있을까요? 먼저 Upper Bound 에 대해 알아봅시다. 해결 가능한 어떤 문제를 T 시간 안에 해결하는 algorithm 이 존재한다. 해당 문제를 해결하는 algorithm 의 upper bound 가 T 이다. 이 두 명제는 서로 동치입니다. 그렇다면, 의미없지만 당연한 예시로 size 가 n 인 array 를 sort 하는 문제는 O(n^100) 으로 해결할 수 있을 것이고, O(n^90) 으로도 해결할 수 있을 것입니다. 그렇기 때문에 Upper Bound 간 우열이 존재합니다. 더 짧은 시간 안에 문제를 해결하는 것이 우수하다고 생각하..

Trace07은 built-in 명령어 jobs를 구현하는 문제입니다. jobs 명령어는 현재 실행 중인 작업들의 리스트를 출력해주는 함수입니다. 실행 중인 작업들의 리스트를 출력해주는 함수는 tsh.c 내부에 listjobs()로 구현이 되어있습니다. 먼저 listjobs 함수를 살펴보겠습니다. void listjobs(struct job_t *jobs, int output_fd); 함수 헤더를 살펴보니 paremeter로 jobs배열과 file_descriptor 를 받는 것을 알 수 있습니다. 이미 글로벌 변수로 jobs를 선언해 준 것이 있으니 첫번째 인자로는 jobs를 넣어주면 될 것 같고 file descriptor는 원래 프로세스가 파일을 다룰 때 사용하는 추상적인 값이지만 어떤 파일을 다뤄..

Trace05 는 실행파일을 Background job 으로 실행시키는 문제입니다. trace05는 특정 형태로 출력할 것을 요구합니다. 이 형식을 확인하기 위해서 trace05.txt 파일을 열어봅시다. # # trace05.txt - Run a background job. # /bin/echo -e tsh\076 ./myspin1 \046 NEXT ./myspin1 & NEXT WAIT SIGNAL /bin/echo -e tsh\076 quit NEXT quit Trace05는 myspin1 실행파일을 & 를 이용해 백그라운드 job으로 실행시키는 것을 알 수 있습니다. tshref가 ./myspin1 &을 입력하면 어떤 것을 출력하는지 확인해봅시다. [숫자] (숫자) command 형태로 출력하는 ..

Trace02 는 Foreground job의 형태로 실행파일을 실행시키는 문제입니다. 쉘에서 새로운 프로그램을 실행시키기 위한 방법은 1. fork()를 통해서 자식 프로세스를 생성하고 2. 자식 프로세스에서 execve 을 통해 새로운 프로그램을 실행시키는 것입니다. execve는 제어흐름을 변경하여 새로운 프로그램을 실행시키고 다시 원래 프로그램으로 돌아오지 않았다는 것을 복기하며 trace02를 진행해봅시다! Trace03, Trace04 는 각각 프로그램을 foreground job으로 argument 없이 실행, foreground job으로 argument를 갖고 실행하는 문제입니다. Trace02를 해결하면 execve 호출을 통해 같이 해결됩니다. 최종코드 void eval(char *c..

Trace01 은 Shell 의 명령어 중 Built-in 명령어인 quit을 구현하는 문제입니다. tsh 를 실행한 후 quit을 입력하면, 쉘이 종료되도록 구현하면 됩니다. main 함수에서 eval(cmdline) 가 호출되므로 eval 함수의 definition 을 살펴봅시다. void eval(char *cmdline) { } 입니다. eval 함수 내에서 cmdline을 parsing하고 builtin_cmd(혹은 builtin_command) 함수로 전달해 빌트인 명령어인지 확인할 수 있도록 합니다. 그리고 builtin_cmd 함수 내에서는 명령어가 quit 이면 쉘을 종료할 수 있는 코드를 작성해주도록 합니다. 최종코드 void eval(char *cmdline) { char *argv[..

Trace00 은 EOF(End of File)이 입력되면 쉘을 종료되도록 tsh을 구성하는 것입니다. tsh.c 의 main 함수 내에 이미 구현되어 있거나 구현되어 있지 않다면 다음과 같이 입력해주면 됩니다. if (feof(stdin)) { fflush(stdout); exit(0); } 표준 입력을 받아 feof이면 exit 시키는 간단한 문제입니다.

Shell Lab을 하기 위한 기본기가 되는 UNIX의 C로 구현된 프로세스 제어 함수들에 대해 알아봅시다. UNIX는 C프로그램을 이용해서 다음과 같은 프로세스 제어 기능을 제공합니다. 1. 프로세스 ID 가져오기 2. 프로세스 생성하기, 프로세스 종료하기 3. Reaping Child Process (자식 프로세스 정리하기) 4. 프로그램 로딩하기 및 실행하기 1. 프로세스 ID 가져오기 types.h 다음과 같은 함수가 정의되어 있습니다. 1. pid_t getpid(void) : 호출한 함수의 프로세스 id를 리턴. 2. pid_t getppid(void) : 호출한 함수의 부모의 프로세스 id를 리턴. 2-1. 프로세스 생성하기 int fork() : 호출하는 프로세스와 동일한 새 프로세스를 생..