weasel의 우당탕탕 개발기

운영체제 과제 2(implementing simple schedulers on xv6)

테스트 환경

• OS : Ubuntu 16.04
• gcc : gcc 5.4.0

개요

운영체제 두번째 과제인 Implementing simple schedulers (FCFS,MLFQ) 에 대한 내용입니다.

크게 FCFS 정책과 MLFQ 정책을 사용하게끔 분기됩니다.

FCFS

과제 명세 :

먼저 FCFS 스케쥴링의 명세는 다음과 같습니다.

1. 먼저 생성(fork())된 프로세스가 먼저 스케줄링 되어야 한다.
2. 스케줄링된 프로세스는 종료되기 전까지는 swithc-out 되지 않는다.
3. 프로세스가 스케쥴링 된 이후 100ticks이 지날때까지 종료되거나 sleeping 하지 않으면 종료해야한다.
4. 실행중인 프로세스가 sleeping으로 전환되면 다음 프로세스가 스케줄링된다.
5. sleeping 상태이면서 먼저 생성된 P가 깨어나면 그 프로세스로 스케줄링 된다.

작동과정 설명 :

첫번째로 FCFS 스케쥴링 정책 내에서의 작동 과정,설정값들과 예시입니다.

먼저, ptable에는 pid 순서대로(만들어진 순서대로) 삽입되어 있습니다.

그렇기 때문에 ptable에서 ptable.proc[0,1,2,3....]이렇게 접근을 한다면 생성된 프로세스에 접근을 할 수 있습니다.

또, pid 순서대로 들어있기 때문에 별도의 큰 조작 없이도 First Come First Served의 스케쥴링이 수행가능합니다. (1번 명세)

하지만 기존의 정의되어 있는 struct proc에는 이 Process가 얼마만큼의 시간동안 수행되었는지에 대한 정보를 담고있지 않기 때문에

위와 같이 uint ctime과 uint stime을 추가해줍니다.
ctime의 역할은 프로세스가 생성된 시간을 의미하고,

(사실 pid가 이 역할을 대체할 수 있고 더 정확합니다.)

stime은 스케쥴러에 의해 이 Process가 선택된 시간(ticks)을 의미합니다.

위의 사진처럼 FCFS 알고리즘에 의해서 선택되었을때 , stime을 현재의 ticks로 설정해줍니다.

FCFS 알고리즘의 역할은 가장 이전에 생성된,다시 말해서 pid가 가장 작고 현재 수행가능한 상태(RUNNABLE) 인

Process를 고르는 것입니다..

그렇기 때문에 아래와 같은 code block으로 조건을 만족하는 적합한 Process를 선택합니다.

for(p=ptable.proc;p<&ptable.proc[NPROC];p++){  // ptable.proc을 앞에서부터 순차적으로 탐색함, NPROC까지 탐색함
if(p->state!=RUNNABLE)
     continue;
else{
     p->stime=ticks;
     ...
     p->state=RUNNING
    ...
     swtch(&(c->scheduelr),p->context);
    ...
}

SLPEEING이 끝나고 wake 하게 될때도 ptable 을 순차적으로 앞에서부터 탐색하기 때문에
pid가 낮은,먼저 생성된 Process를 처리할 수 있습니다.

또, 실행된지 100ticks가 넘어갔을때 종료하는 조건은 trap.c 내에

로 구성되어 있습니다. 현재 tick에서 stime 을 뺀 결과가 100보다 크거나 같다는 뜻은,

이 Process가 100tick이상 run되었다는 뜻입니다.(항상 스케쥴될때 stime=0으로 현재 ticks으로 초기화)

그렇기 때문에 이 Process의 killed을 1로 바꿔주고, 이렇게 되면 다음 timer때 이 프로세스는 죽습니다.

FCFS Test 결과와 간단한 설명

조건 : NUM_CHILD를 5에서 7로 수정,

첫번째 테스트 (sleep이나 yield를 하지 않고)

예상대로, sleep,yield 아무것도 하지 않았으니 먼저 생성되는 P5부터 P11까지 출력을 순차적으로 진행합니다.

두번째 테스트 (yield를 할때)

예상대로, yeild를 하더라도 먼저 생성된 프로세스에게 우선권이 있으므로 다시 CPU 사용권한이 돌아와 진행합니다.

세번째 테스트 (sleep) 을 할때

sleep을 하면 순차적으로 진행되는것처럼 보이지만 ,
...P25->P19->P20->P21->P22->P23->P24->P19 이부분에서

P24의 다음으로 P25가 스케쥴링되는것이 아니라 wakeup한 P19가 선택되어 진행됩니다.

이러한 현상은 꾸준히 관찰할수 있습니다만, 테스팅되는 하드웨어에 따라 상황이 달라짐을 확인했습니다.

네번째 테스트 100tick을 초과했을때

예상대로 , pid가 가장 작은 프로세스가 실행되다가 100tick이 지나면 강제종료되고,

다음 프로세스가 스케줄링됨을 확인할수 있습니다. 또 모든 자식 프로세스가 강제 종료되면 OK메세지를 확인가능합니다.

트러블슈팅

FCFS는 비교적 간단한 구현이어서 FCFS 그 자체는 크게 어렵지는 않았습니다.
다만 xv6의 내부적인 기능을 처음 구현하다보니 sched 함수나 scheduler 함수와 같은 중추적인 함수들을 분석하는데 시간을 쏟았습니다.

또 trap.c 함수 내에서의 trap 함수가 어떻게 사용되는지 분석하는데 시간을 투자했습니다..

MLFQ (Multi Level Feedback Queue)

과제 명세 :

먼저 MLFQ 스케쥴링의 명세는 다음과 같습니다.

작동 과정 설명:

MLFQ 구현의 가장 중요한 점은 L0 큐와 L1 큐 각각의 스케쥴링 알고리즘이 같은 부분이 존재하지만 몇가지 점이 다르다는 것입니다.

L0 큐는 기본적으로 Round robin(Q=4ticks) 이고, L1 큐 는 Round robin(Q=8tciks) 에 priority 가 고려대상이라는 것입니다.

먼저 ptable의 구조는 이전과 동일합니다. 차이점은 proc.h에 정의되어 있는 proc 구조체입니다.

속해있는 Q level 을 드러내는 int lev, 우선순위를 나타내는 int priority, 작동한 시간을 의미하는 int rtime (0부터 시작),

이 Process가 CPU를 독점하는지 체크하는 int monopolize ( 1은 독점중,0은 독점중이 아님)등이 추가되었습니다.

먼저 proc.c 안에 정의된 allocproc 함수에서

와 같은 코드로, 초기에 priority를 0으로, 초기 lev을 0으로, monopolize 값을 0으로 초기화해줍니다.

이를 통해 처음 실행되는 프로세스의 우선순위를 0으로 , 그리고 가장 높은 레벨의 큐(L0)로 삽입됩니다.

그 다음으로 스케쥴링을 담당하는 scheduler 함수입니다.

첫번째 사진은 RUNNABLE 한 프로세스 중 L0큐 에 속해있는 프로세스의 존재를 측정하고,

있다면 L0큐를 탐색하여 적절한 Process를 찾는 부분입니다.

먼저 L0 큐 내에 존재하는한 적절한 프로세스의 개수를 다음과 같이 찾을수 있습니다.

1. 프로세스가 구동가능한 상태인가? (RUNNABLE)
2. 프로세스의 큐 레벨이 0인가?

위 두가지 조건을 모두 만족해야 적절한 프로세스라고 할수 있습니다.
적절한 프로세스를 찾았다면, rtime을 0으로 초기화해주고 context swithcing이 일어납니다.

두번째 사진은 L0 큐에 적절한 Process가 없을때 L1 큐를 탐색하고 가장 높은 Priority 를 가지는 Process를 선택하는 부분입니다.

프로세스를 순차적으로 돌면서 L1 큐에 있는 것중에서 Priority가 가장 높은 프로세스를 선택합니다.
그 후 그 프로세스로 context swithcing이 일어납니다.
priority 우선순위가 같다면 , ptable을 시작에서부터 순차적으로 탐색하기때문에 FCFS로 행동합니다.

MLFQ 구조는 trap.c가 중요합니다.

trap.c에서 MLFQ와 관련해서 동작하는 것은 크게

1. 지금 현재 프로세스의 rtime 을 증가시키는것.
2. 지금 현재 구동중인 프로세스가 L0큐인데,rtime이 4 tick 이상이고, 독점적이지 않을때 L1 큐로 강등하고 yield() 를 수행함.
3. 지금 현재 구동중인 프로세스가 L1큐인데,rtime이 8 tick 이상이고, 독점적이지 않을때 priority가 0보다 크다면 1만큼 감소시키고,

yield() 을 수행.
4. Starvation을 방지하기 위해 100 tick 마다 Priority boosting을 수행.

하는 4가지로 구분 될 수 있습니다.

단계별로 설명하겠습니다.

1. 지금 현재 프로세스의 rtime을 증가시키는것. 입니다.
   
   위와 같은 코드로 수행됩니다.

주요 원리는 TIMER interrupt는 매 tick 마다 발생되므로, 그에 맞춰서 현재 구동중인 프로세스 정보를 얻어오고 그 프로세스의 rtime을 1만큼 증가시킵니다.

2. 지금 현재 구동중인 프로세스가 L0큐인데,rtime이 4 tick 이상이고, 독점적이지 않을때 L1 큐로 강등하고 yield() 수행함.
   
   위와 같은 코드로 수행됩니다.

현재 레벨이 0이고, 실행된 rtime이 4tick상이고, 독점적이지 않는다면 yield() 를 호출하고 L1 큐로 강등시킵니다. yield 함수는 sched 함수를 호출하고 sched에서 scheduler가 호출되니 다음 프로세스를 스케쥴링합니다.

3. 지금 현재 구동중인 프로세스가 L1큐인데,rtime이 8 tick 이상이고, 독점적이지 않을때 priority가 0보다 크다면 1만큼 감소시키고, yield() 을 수행.
   
   위와 같은 코드로 수행됩니다.

전체적으로 두번째 L0 와 비슷하지만, priority가 0보다 크다면 1만큼 감소시키는것이 다릅니다.
감소를 하거나 하지 않은 두가지 경우 모두에서 yield를 호출 하기 때문에 yield 함수는 sched 함수를 호출하고 sched에서 scheduler가 호출되니 다음 프로세스를 스케쥴링합니다.

4. Starvation을 방지하기 위해 100 tick 마다 Priority boosting을 수행.

trap.c

proc.c

위와 같이 trap.c에서 proc.c에 정의된 priboosting 함수를 호출합니다.
priboosting 함수는 아래에서 설명하겠지만, L1에 있는 모든 프로세스들을 L0큐로 올리고, priority를 0으로 초기화합니다.

MLFQ Test 결과와 간단한 설명

조건 :

1. NUM_LOOP2를 300000(30만) 으로 수정
2. NUM_LOOP3를 200000(20만) 으로 수정
3. NUM_LOOP4를 500000(50만) 으로 수정

테스트 조건을 수정한 이유는 뚜렷한 경향성을 파악하기 위해서 충분한 Iteration을 확보하기 위함입니다.

첫번째 테스트 (priority를 변경하면서)

예상대로 pid 값이 더 큰 프로세스의 priority가 더 높게 설정되기 때문에, pid 값이 더 큰 프로세스가 먼저 끝나게 되고,

pid값이 작은 프로세스 ( 사진에서 5번 프로세스 혹은 4번)가 L0에서 실행되는 시간이 긴 경향을 보입니다.

두번째 테스트(priority 변경 없이)

예상대로 pid 값이 작은 프로세스가 L1의 비율이 높습니다.

이는 , L1 큐에서는 같은 priority 를 가지는 프로세스라면 FCFS로 동작하기 때문입니다..

세번째 테스트 (yield)

왠만하면 L0의 4 tick quantum을 다 사용하지 않기 때문에 시간 사용량이 초기화되니,

계속 L0에 남아있게 됩니다. L0는 Round robin이기 때문에 거의 동시에 작업이 완료됩니다.

네번째 테스트 (monopolize)

monopolize라는 시스템콜을 사용한 테스트입니다.

가장 큰 PID를 가진 프로세스가 CPU 독점을 요청하기 때문에 가장 큰 pid인

Process 45가 CPU를 독점합니다. MLFQ 스케쥴링은 일어나지 않기 때문에
L0의 에서 모든 작업을 완료합니다.

다른 프로세스는 test2의 결과와 유사한것을 볼 수 있습니다.

트러블슈팅

FCFS 와는 다르게 고려해야할 부분이 많았습니다.
대표적으로 두가지 문제가 있었습니다.

1. 스케쥴링 함수를 구현할때 여러가지 조건문이 중첩됨.
2. monopolizing의 구현

다음과 같이 해결했습니다.

1. 중첩되는 모든 케이스를 명시하는것이 아니라 큰 틀에서 if문을 분기하여 처리함.
2. 현재 프로세스가 rtime을 넘겼을때 yield하는 부분에서 monopolize 체크를 위하여, proc 구조체에 플래그를 삽입함. 이를 통해 trap 함수에서 호출될때 혖현재 프로세스의 monopolize flag를 체크해서 독점적이지 않을때만 CPU 자원을 포기하도록 구현함.

시스템 콜

과제 수행을 위해 필요한 System call은 총 4개입니다.

1. void yield(void)
2. int getlev(void)
3. void setprioirty(int pid,int priority)
4. void monopolize(int password)

각각의 시스템 콜 구현체를 먼저 보이고 , 공통적인 부분은 마지막에 첨부합니다

첫번재로 void yield(void) 함수입니다.

sys_yield 시스템콜은 proc.c에 정의되어 있는 yield 함수를 호출하는 것입니다. 현재 프로세스가 CPU 자원을 반납하는 행동입니다.

두번째로 int getlev(void) 함수입니다. 현재 프로세스의 큐 레벨을 반환하는 것입니다.


getlev 시스템콜은 proc.c 에 정의 한 getlev 함수를 호출합니다.

proc.c 에서 정의된 getlev 함수는
현재 프로세스가 독점중인 상태라면 1을 반환하고,

그렇지 않다면 현재 프로세스의 큐레벨인 lev 을 반환합니다. (return myproc()->lev);

세번째로 void setpriority(int pid,int priority) 함수입니다. 인자로 받은 pid와 일치하는 프로세스의 priority를 인자 priority로 변경합니다.


setpriority 시스템콜은 proc.c에 정의한 setprocpriority 함수를 호출합니다.

proc.c에서 정의된 setprocpriority 함수는
현재 ptable에서 인자 pid와 매칭되는 프로세스를 찾고, 인자 priority로 프로세스의 priorirty를 변경합니다.(targetP->priority=priority)

시스템콜이기 때문에 argint를 이용하여 인자를 받습니다.

마지막으로 void monopolize(int password) 함수입니다. 인자로 받은 password와 미리 설정한 본인의 학번과 비교한뒤 일치하면

현재 프로세스를 CPU에 독점적인 권한을 가지게 변경합니다.


monopolize 시스템콜은 proc.c에 정의한 monopolize 함수를 호출합니다.

proc.c에 정의된 monopolize 함수는
먼저 ptable의 lock을 acquire해주고

현재 프로세스의 monopolize가 1이라면,독점적이라면, 인자 password를 학번 2016026599와 체크한후, 일치하면

monopolize를 0으로 바꾸어 독점해제하고, 현재 프로세스를 L0으로 이동시키고 priority를 0으로 변경합니다.

일치하지 않으면 독점을 해제하고, 현재 프로세스를 kill 합니다.(kill 함수의 행동과 유사하게 행동합니다)

그 후 "wrong password at calling monopolize"라고 유저에게 안내합니다.

현재 프로세스의 monopolize가 0이라면,독점적이 아니라면, 인자 password를 학번 2016026599와 체크한후, 일치하면

monopolize를 1으로 바꾸어 독점을 시작하고, 현재 프로세스를 L0으로 이동시키고 priority를 0으로 변경합니다.

일치하지 않으면 현재 프로세스를 kill 합니다.(kill 함수의 행동과 유사하게 행동합니다).

그 후 "wrong password at calling monopolize"라고 유저에게 안내합니다.

그 후 ptable의 lock을 release 해줍니다.

시스템 콜 공통 사항

usys.S

user.h

syscall.h

syscall.c

Makefile 시스템 콜 부분

Makefile 코드 분기를 위해서 삽입한 부분

시스템콜 트러블슈팅

몇가지 마이너한 이슈가 있었습니다.

시스템콜의 인자를 처리할때는 argint을 사용한다는 것을 몰라 사용하지 못했고, 좀 더 자료를 찾아본 후 적용가능했습니다.

monopolize 함수의 처리가 trap.c 내부 에서 일어나야 할지 , proc.c 내부에서 일어나야할지 선택해야 했습니다.

proc 구조체를 수정해 monopolize flag 자체는 proc.c 내부에서 수정하되 trap 내부에서 체크하여 적용하는 것으로 구현했습니다.

코드

Operating-System-xv6

운영체제 과제 1 ( Simple User-level Unix Shell)

테스트 환경 :

• OS : Ubuntu 16.04
• gcc : gcc 5.4.0

개요 :

운영체제 첫번째 과제인 Simple User-level Unix shell에 대한 내용입니다.

크게 interactvie mode와 batch mode로 나뉘어지고
사용자가 입력한 명령 혹은 batch file을 읽어와서

명령을 수행하고 그 결과를 출력하는 프로그램입니다.

작동과정 설명 :

Interactvie Mode

첫번째로 interactvie mode내에서의 작동 과정과 예시입니다.
크게 사용자로부터 입력을 받아오고,

입력을 특정한 기준을 가지고 분할하여
execvp 함수를 사용하여 처리합니다.

1. fgets() 함수를 통해 사용자에게 입력을 받습니다.
2. strtok 함수를 사용하여 semi-colon과 space를 기준으로 raw한 입력을 유의미하게 분할합니다.
3. 분할된 명령어들은 char* 이차원 배열에 저장됩니다.
4. 명령의 개수만큼 fork 함수를 통해 자식프로세스를 생성합니다.
5. 자식프로세스안에서 execvp 함수를 통해 저장된 명령어를 처리합니다.
6. 부모 프로세스에서는 모든 자식프로세스가 끝나기를 기다린후, 모두 종료되면 다시 1번으로 돌아가도록 유도합니다.
   만약 이 과정에서 에러가 검출된다면 유저에게 알려줍니다.

작동예시 :

실행된 후 먼저 사용자가 명령을 입력할때까지 프로그램은 대기합니다.

그 후 사용자가 명령을 입력하면 (ex.ls -al)

> ls -al

위와 같이 명령을 처리합니다.

복수의 명령어( semi-colon으로 구분된)도 병렬적으로 처리가 가능합니다. (출력 순서는 섞일수 있습니다.)

> ls -al;pwd;ifconfig

quit command 입력시 쉘을 종료합니다.

> quit

에러 처리:

존재하지 않는 명령어를 입력시 유저에게 알려줍니다.

> thisisnotvalid

아무 입력을 하지 않고 엔터를 입력할 경우 다시 입력하도록 유도합니다.

아무 입력을 하지 않은 상태에서 ctrl-D를 입력할 경우 shell은 종료됩니다.

실행 전제 :

1. 입력의 길이는 최대 1000자입니다.
2. 입력받는 명령어는 최대 50개입니다.
3. 명령어당 옵션의 개수(space로 구분하는 ex) -a -l -v -> 3개)는 최대 10개입니다.

작동과정 설명 :

Batch mode

두번째로 batch mode에 대한 설명과 예시입니다.
유저가 main 함수의 인자로 넘긴 batch_file을 읽어오고

명령어를 분할하고 처리하는 과정은 interactvie mode와 동일합니다.

1. fgets() 함수를 통해 사용자가 실행될때 첨부한 batch_file을 한줄단위로 읽어옵니다.
2. 마지막줄을 읽었다면 중지합니다.
3. 만약 명령어가 없고 개행문자만 있는 빈 줄(\n)을 읽었다면 다음 라인을 읽기 위해 1번으로 돌아갑니다.
4. strtok 함수를 사용하여 semi-colon과 space를 기준으로 raw한 입력을 유의미하게 분할합니다.
5. 분할된 명령어들은 char* 이차원 배열에 저장됩니다.
6. 명령의 개수만큼 fork 함수를 통해 자식프로세스를 생성합니다.
7. 자식프로세스안에서 execvp 함수를 통해 저장된 명령어를 처리합니다.
8. 부모 프로세스에서는 모든 자식프로세스가 끝나기를 기다린후, 모두 종료되면 다음 라인을 읽기 위해 1번으로 돌아갑니다.
   만약 이 과정에서 에러가 검출된다면 유저에게 알려줍니다.

작동예시:

./shell [batch_file] 형식으로 batch mode를 사용합니다.

vim test.txt

에러 처리:

존재하지 않는 명령어를 입력시 유저에게 알려줍니다.

> vim test.txt

사용자가 두개의 batch file을 인자로 넣을시 유저에게 경고를 보여주고 shell을 종료합니다.

실행 전제 :

1. 입력의 길이는 최대 1000자입니다.
2. 입력받는 명령어는 최대 50개입니다.
3. 명령어당 옵션의 개수(space로 구분하는 ex) -a -l -v -> 3개)는 최대 10개입니다.

기타 에러 처리 사항:

1. fork가 실패했을시 메모리에 심각한 문제가 있다고 판단하여 shell 을 종료합니다.
2. batch file을 fopen을 사용했을대 NULL이 반환될시 비정상적 작동을 막기 위해 shell을 종료합니다.
3. batch file을 두개 이상 사용시 (ex. ./shell batch_file batch_file 유저에게 경고를 보여준후 shell을 종료합니다.
4. 명령어를 분할하는 단계에서 \n 개행문자를 삭제합니다. 개행문자가 삭제되지 않고 execvp의 인자로 입력될시 illegal option 에러를 표출하기 때문입니다.

코드

Operating-System-xv6

도전기? 후기? 어느단어를 써야할지 한참 고민하다가 도전기로 선택했습니다.
도전기로 선택한 이유는 결과와 상관없이 공채의 모든 과정에서 배운점이 굉장히 많았거든요.

그런면에선 개발자 취준생인 저의 성장기도 맞는 것 같습니다.

글이 굉장히,매우 호흡이 깁니다. 적당히 스크롤 내려가면서 스킵하면서 읽어주세요.. 공채 얘기만 궁금하시면 뜬금없는 블라인드 공채 목차쯤부터 보시면 됩니다.

조금 늦은 시작

저는 서울 소재 H대학교에서 컴퓨터계열을 전공하다 3학년을 수료하고 20년도 초에 사회복무요원으로 입대하게 되었습니다.
여러가지 사정들로 군 복무가 굉장히 늦어졌고, 3학년을 마칠때까지 아직 진로에 대해서 확실히 정하지 못했습니다. 분명 개발을 좋아하고 적당히 실력도 있었지만, 그만큼 컴퓨터공학에 대한 열정도 있어서 진학 후 연구도 하고 싶었습니다. 개발자와 진학 중 하나를 선택하기 위해서는 일단 군 문제 먼저 해결해야한다고 생각해 일단 복무를 시작했습니다.

그러던 중, 5월쯤 취업한 친한 과 동기를 만나서 여러가지 얘기를 하던 중, 본인의 입사동기 중 한명은 매일 백준에서 알고리즘 1문제를 꾸준히 풀었다 라는 말을 듣게 되었습니다. 일반적인 사람이라면 흘려듣거나 or 조언을 받아들일텐데 저는 태생적으로 반골기질이 있어서인지 그게 그렇게 어렵고 대단한 일인가? 라는 생각이 먼저 들게 되었습니다. 그 노력을 폄하하려는게 절대 아니라 정말 순수하게 궁금했습니다.

사실 이전까지 알고리즘 문제를 단 한번도 풀어보지 않았지만 갑자기 저런 당돌한 생각이 들더라구요.

습관 들이기와 실패

학부때 배운 알고리즘 지식을 제외하고 PS계통에 대한 지식은 전무했습니다. 자료구조와 알고리즘에 대한 조금의 배경지식은 있었지만, 그것을 제외하고는 완전한 뉴비수준이었습니다.
일반적으로 근무지에서 정해진 일을 하고 난 후에 어느정도의 개인시간이 보장되기에 노트북을 들고와 대략 6월부터 백준사이트에서 아주 난이도가 낮은 문제부터 한 문제씩 풀기 시작했습니다.

구현, 자료구조, 탐색, DP 와 같은 알고리즘 분류도 조금씩 신경쓰면서 풀었습니다. 매일 문제가 잘 풀리거나 쉬운 문제 같은 경우는 2~3문제, 어려운 문제라면 1시간씩 고민해가면서 풀고 정 풀리지 않으면 해답을 참고하되 저만의 논리구조를 머릿속에 구상해서 다시 풀어보았습니다. 평균적으로 1일 1문제 정도는 꼬박꼬박 풀었습니다.

https://github.com/BecomeWeasel/daily_algo_challenge 에 업로드하면서 성취감을 느꼈습니다. 여러분도 참고해보세용!

3개월간은 정말 재밌게, 그리고 제가 느끼기에도 성장한다는 것을 느낄정도로 열심히 했습니다. 하지만 문제가 생겼습니다. 10월쯤 되어서 조금씩 귀찮아지기 시작했고, 다시 로스트아크라는 게임에 열중하게 되면서 알고리즘을 완전 뒤편으로 미루게 되었고 시간을 좀 허비하게 되었습니다.

로스트아크는 정말 재밌게 했습니다. 진짜 재밌었어요..

다시 시작하기

21년도 4~5월쯤 되어서야 흘러가는 시간이 너무 아깝다고 느껴서 다른 개발 공부와 알고리즘 풀이를 다시 시작했습니다. 이전의 감각을 찾기 위해서 무리하지 않고 평일에만 1문제씩 풀고, 주말은 무리하지 않고 알고리즘 공부가 아닌 다른 개발 공부를 했습니다. 또 백준뿐만 아니라 리트코드와 프로그래머스 문제들도 풀었습니다.
개인적으로 문제들의 다양성은 백준이 좋지만, 질은 리트코드가 압도적이라고 생각합니다.
또 동아리 후배 둘과 스터디를 구성해 알고리즘 스터디를 시작했습니다.
개인적으로 이게 정말 정말 많은 도움이 되었습니다. 여러분들도 단기적인 스터디 말고 긴 호흡의 스터디를 구성하는걸 추천드립니다.

같이 스터디를 하면서 함께 성장한 IS 오렌지와 CS 강민이 정말 고마웡,,🙇‍♂️

뜬금없는 블라인드 공채

알고리즘 문제를 조금씩 풀면서 스터디를 해가던 중 카카오에서 2022 신입 개발자 블라인드 채용 공고를 올린 것을 보게 되었습니다. 일반적으로 코딩테스트의 난이도를 생각했을때 문제의 질이나 난이도적인 측면에서 높은 기업이기에 이전에도 종종 카카오 코테를 참고하곤 했습니다.

입시를 준비할때도 실전모의고사가 가장 효과가 좋듯 정말 가볍게 코딩테스트만 보기로 마음먹고 지원을 해보았습니다. 모두들 아시다시피 카카오는 지원을 할때 필수적인 정보만 적고 자기소개서나 학력같은걸 일체 명시하지 않습니다.

지원자격도 학력 및 전공에 제한이 없고 남성의 경우 군필의 제한만 있었습니다.
저는 지원할때는 아직 소집해제 전이였지만, 입사전에는 소집해제를 하기 때문에 지원을 해보았습니다.

또 저는 3학년까지 밖에 마치지 않았고 졸업하기까지는 1년이 남았지만 , 일반적인 기업에서 요구하는 것처럼 졸업이나 졸업예정자 조건을 카카오는 요구하지 않았습니다.

저는 아래처럼 4개의 전형절차중에서 1단계인 1차 온라인 코딩테스트만 찍먹만 해보려고 지원을 했습니다.

지원과정에서 입사를 희망하는 계열사를 1지망 2지망으로 선택하는데 저는 카카오페이와 카카오 본사를 각각 선택했습니다.

1차 코딩테스트

1차 코딩테스트는 9월 11일로 지원하고 일주일 정도의 시간이 있었습니다. 엄청 대단한것을 준비하지는 않았고, 기출문제들을 풀어보면서 카카오 코테들의 경향성을 파악하는데 시간을 들였습니다. 이 경향성 분석이 조금 도움이 되었던 것 같습니다. 기본적인 자료구조와 알고리즘을 다시 복습하고, 제가 스스로 정리한 문제 분류별 해결방법을 다시 읽어보면서 기다렸습니다.

9월 11일이 되어서 5시간동안의 1차 코딩 테스트를 응시했습니다. 1차 코딩테스트의 후기는 다른 글에도 많이 정리되어있으니 크게 다루지는 않겠습니다.
총 7개의 문제가 있었고, 확실히 이전보다는 난이도가 많이 낮았습니다. 난이도는 체감상 실버 2문제, 골드 3문제, 플래티넘 이상 2문제 정도였습니다.

그렇지만 첫 코딩테스트이기도 하고 시간이 정해져있다는 압박감에 5번문제(양과 늑대) 같은 쉬운 탐색 문제나 6번문제 (구간합)문제를 보고 머리가 하얗게 변했습니다. 풀이도 잘 떠오르지 않았습니다.

결과적으로 4.5개의 문제만 해결할 수 있어서 탈락을 직감했습니다.

그렇게 지내던 중, [카카오] 2022 신입 개발자 블라인드 채용 1차코딩테스트 결과 안내드립니다. 라는 제목의 메일을 받게 되었고, 뒹굴거리면서 확인을 했는데 결과는 충격적이게도 합격이었습니다.

기쁘다는 감정보다 이때까지 공부하던것이 그렇게 헛되지 않았구나라는 감정을 먼저 느끼게 되었습니다.

2차 코딩테스트

그리고 정말 급급하게 2차 코딩테스트를 준비해야 했습니다. 2차 코딩테스트를 준비하면서 알게된 점이 2차 코딩테스트는 엄청난 알고리즘 실력보다 디자인(그 디자인이 아닌 설계)과 최적화에 집중해야 한다는 것을 알게 되었습니다.

기출 문제와 채점하는 환경이 대부분 공개되어 있기때문에 2021,2020 블라인드 공채 2차 코테문제를 스터디원 중 한명과 같이 풀어보았습니다. 그런데 아무리 해봐도 풀리지가 않았습니다. 전날까지 보고갔는데도 도저히 모르겠더라구요..
자포자기의 심정이었습니다.

그렇게 9.25일이 되어서 2차 코딩테스트를 치루게 되었습니다. 2차 코딩테스트는 10문항 정도의 CS 객관식+주관식 문제와 하나의 문제인 시스템 설계와 최적화 파트로 구성되어 있습니다. 중간 중간 휴식시간을 포함해서 총 7시간 정도 응시하고, 캠과 화면 모니터링을 켜고 봐야합니다.

CS 문제

대부분의 문제는 CS 코어 과목에서 출제되었고 기본에 충실한 문제들이었습니다. 학부 수업을 충실하게 들은 전공자라면 큰 부담이 되지 않는 문제 8문제 정도와 살짝 헷갈릴 수 있는 2문제 정도로 구성되어 있습니다. 저는 10문제 중에서 7개 정도 맞았던 걸로 기억합니다.

CS 테스트는 점수보다 적부라는 썰이 있습니다.

설계와 최적화 문제

어차피 해설이 올라올 것이고 아직은 민감할 수 있기 때문에 자세히는 언급하지 않고 간단하게 말씀드리겠습니다.

2차 코딩테스트는 ICPC같은 대회처럼 응시자들의 점수와 나의 등수를 실시간으로 확인할 수 있기에 부담이 되었습니다. 저는 부담을 최대한 덜 받기 위해서 잘 확인하지 않았습니다.
문제가 시나리오1,2로 구성되기에 합산점수로 최종점수가 매겨집니다.

복수의 사용자들의 실력에 맞게끔 정렬하는 것이 최종 목적인데, 사용자들의 실제 실력을 알 수 없기 때문에 온라인 게임에서 많이 볼 수 있는 랭크 기반 매칭시스템을 구현하는 것이 방법입니다.

제한적인 검색이 가능하기 때문에 사례를 많이 찾아보았고 Elo 시스템을 채택하였습니다. 그 후 적당히 최적화 방법을 계속 구현해 최종점수를 조금씩 끌어올렸습니다. 응시 종료 30분전 점수판이 프리징되는데 그 때 기준으로 300등대 초반으로 마무리했습니다.

2차 코테를 끝내고 카카오가 3자리수대의 채용을 한다고 했으니 약간 희망을 품었지만,신경쓰지 않고 얼마 안남은 소집해제만 대비하며 내년 복학준비만 생각하고 있었습니다.

그러던 와중 소집해제일인 10.14일이 되었고 뭔가 기분이 묘한 감정을 느끼던 와중에
[카카오] 2022 신입 개발자 블라인드 채용 2차코딩테스트 안내드립니다. 라는 제목의 메일을 받게 되엇습니다.

1지망으로 작성한 카카오페이에 합격이었습니다. 뭔가 일이 이상하게 굴러가고 있다는 것을 느끼게 되었고 기분이 이상했습니다.

HR 인터뷰

자기소개서와 HR 인터뷰 준비하기

특이하게도 카카오페이는 1차가 기술인터뷰가 아닌 HR인터뷰였습니다.
일반적으로 최종면접이 인성면접인데 순서가 반대였습니다.

후에 알게되었지만, 다 이유가 있었습니다.

HR인터뷰 단어가 생소했지만, 컬쳐핏 면접이나 인성면접으로 생각했습니다. 소집해제 날부터 급하게 자기소개서를 준비했습니다.

공대생치고는 드림클래스나 서포터즈,교내 홍보대사같은 대외활동을 많이 해본편이어서 여러 대외활동을 위한 자기소개서는 꽤 써보았지만, 취업준비를 당연히 해본적이 없기에 자기소개서부터 걱정이였습니다. 하지만 다행히도 문항들은 평이한 수준이었고, 프로젝트 경험과 같은 일반적인 질문들로 구성되었습니다.

입대하기전 SKT에서 수상했던 AI 공모전 우승경험을 중점적으로 작성했고 그 과정에서 접근방식과 해결방식 위주로 작성했습니다. (후술하겠지만 이 부분에서 굉장히 좋은 평가를 받았습니다.) 또 아주 조그만 프로젝트도 작성했습니다.

자기소개서와 포트폴리오를 작성하면서 느낀 점이 프로젝트 경험이 많이 부족하다는 점을 절실히 깨닫게 되었습니다.

알고리즘+CS+프로젝트 이 삼박자가 완벽해야 취준에 성공할 수 있어보입니다.

자기소개서를 제출하고는 급하게 HR인터뷰를 준비했습니다. 경험이 전무하다보니 어디서부터 접근해야할지 몰라 많이 헤맸지만, 교내 홍보대사 활동을 통해서 다양한 전공의 사람들과 많이 만날수 있게 되었고, 대부분이 취업준비를 하거나 이미 취업을 한 상태여서 주변에서 정말 정말 많은 도움을 받게 되었습니다.

학교생활을 하면서 다양한 전공의 사람들과 교류하며 인맥을 넓히는 것은 확실하게 도움이 됩니다.

또 카카오페이라는 테크핀 기업에 대한 분석과 결제&송금 도메인에 대한 지식을 공부하게 되었습니다. 여러 유튜브를 참고하면서 인성면접 빈출문제에 대한 답변과 개발회사에 국한되는 가치관 질문을 거의 다 준비했습니다.

인터뷰를 마치고

HR인터뷰는 10월 말경에 화상으로 진행되었습니다.

덜덜 떨면서 참여했는데, 면접관분이 긴장을 풀어주시려고 많이 노력해주셨고 면접관의 태도나 질문에서 따뜻함을 느낄 수 있어서

결과에 상관없이 카카오페이에 대한 이미지가 매우 좋게 각인되었습니다.

인터뷰는 다행히도 일반적인 수준과 익숙한 질문들로 구성되었지만 면접관분이

가끔 정말 날카로운 질문으로 답변 내용을 확인하고는 하셨습니다.

1,2차 코딩테스트를 마치고는 둘다 탈락했다고 생각했지만, HR인터뷰를 마치고는 합격에 대한 아주 조금의 확신을 가지게 되었습니다.
자세히는 말씀드리기 어렵지만, 복수의 파트에서 좋은 평가를 받게 되어 조금의 희망이 생겼습니다.

1,2차 코딩테스트를 응시할때는 정말 모의고사 느낌으로 보자, 경험만 쌓자 였지만,
HR인터뷰를 마치고부터는 정말 진심모드로 최선을 다해서 준비해야겠다는 생각을 하게 되었습니다.

면접을 마치고 일주일쯤 뒤에 메일 제목부터 강한 스포일러를 당했습니다.
[카카오페이] HR 인터뷰 전형 합격을 축하드립니다! 라는 메일을 받게 되었습니다.
이제 그렇게 열망하던 카카오 입사까지 1단계만 남았다는 것이 실감나게 되었습니다.

기술 인터뷰

기술인터뷰 준비하기

기술 인터뷰, 2차 인터뷰, 최종 면접 다 맞는 말이지만 기술 인터뷰라고 하겠습니다.

얼렁뚱땅 시작한 공채 지원도 이제 마지막 단계, 그리고 가장 어려운 단계만 남기고 있었습니다.
당연하게도 기술면접 경험이 없었기에 주변의 개발자들에게 조언을 많이 구했고 캐치카페와 같은 사이트도 참조하면서 기술면접을 준비했습니다.

일반적으로 기술면접은 포트폴리오에 명시한 프로젝트+CS 기본기로 진행됩니다. 저는 포트폴리오가 처참할정도로 빈약하기에 CS 기본기에 올인했습니다.

CS 기본기는 github 저장소에 정말 많은 자료들이 있습니다. 예를 들자면

1. 한재엽님의 CS 질문 저장소 : 대체적으로 많이 참고되는 저장소입니다.
2. Woovicotry님의 CS 질문 저장소 : 1번과 비교해서 상대적으로 덜 알려져 있지만 퀄리티는 뒤지지 않습니다.
   이런 저장소들을 참고해서 공부했습니다.

단, 반드시 명심해야할 것이 인터넷의 자료는 완벽하지 않고 실제로 명백하게 틀린 부분도 꽤 많아서

저는 저장소에서는 질문을 참고했고 실제 답변은 영문 공식문서나 원서를 주로 참고했습니다.

또 기술 면접은 DFS로 준비해야 한다는 말을 많이 들었습니다.

그래서 단순히 안다 or 모른다가 아니라 아래와 같은 기준으로 깊게 준비했습니다.

• 왜 이 기술이 사용되었는지
• 내부 구조는 어떻게 되어있는지
• 왜 A가 아닌 B를 선택해야 하는지
• 실제 활용은 어떻게 되는지

제가 가장 좋아하는 자료구조인 HashTable을 예로 들어서 설명드리겠습니다.

• 왜 이 기술이 사용되었는지일반적으로 $$O(1)$$ 시간복잡도로 조회,삽입,수정이 가능하다.
• 내부 구조는 어떻게 되어있는지 : hashtable은 충돌을 잘 관리해야하는데, 일반적으로 개방주소법/분리연결법이 사용된다.
• 왜 A가 아닌 B를 선택해야 하는지 : 개방주소법은 구현이 간단하고, 캐시에서의 이점이 있지만 로드팩터에 민감하고 삭제가 어렵지만 분리연결법은 로드팩터에 영향을 조금 덜 받고 hashtable의 확장이 더디게 일어나지만 추가적인 오버헤드가 있다.
• 실제 활용은 어떻게 되는지 : Python 3에서는 개방주소법,Java에서는 분리연결법을 사용한다.부족함사실 위는 꽤 자세하게 준비한 것 같지만 저는 절대적으로 부족하다고 생각합니다.
  예를 들어 개방주소법은 왜 캐시효율이 좋을까요? 또 개방주소법에서도 여러가지 기법이 있고, 그에 따른 추가적인 트레이드오프가 있습니다. 분리연결법에서도 버킷에 연결리스트를 구성하는 방법과 트리로 구성하는 방법등이 있습니다.

그러면 왜 트리를 사용할까요? 또 Java는 왜 분리연결법을 사용할까요?

Java 8 부터 사용하는 분리연결법은 트리와 연결리스트를 동시에 사용하는데, 이때 균형이진트리인 RB 트리를 사용합니다.
AVL이나 Splay도 있는데 왜 RB 트리일까요?

이렇게 준비할때도 끊임없이 하나씩 의문을 제기하면서 deep 하게 준비했습니다.

이처럼 노션을 활용해서 대략 50개 정도의 질문들 하나하나를 깊게 준비했습니다.

포트폴리오는 제가 했던 프로젝트의 설계와 DB 모델링을 다시 점검하고,

특정 기술을 사용한 이유에 대해서 고민하며 준비했지만 매우 빈약했습니다 ㅠㅠ

기술 인터뷰

기술 인터뷰 역시 화상으로 진행되었으며 1:N 방식으로 1시간 가량 진행되었습니다.

단순히 이거 알아요? 보다는 이 기술을 사용한 이유가 뭐에요? 부터 시작하는 꼬리물기 형태의 질문으로 인터뷰 전체가 흘러갔습니다.

또 포트폴리오 질문은 단순히 포트폴리오 질문이 아니라 CS로 자연스럽게 이어지는 질문이었습니다.

다만 CS 질문이 다른 계열사처럼 폭포수처럼 쏟아지지는 않았고 핵심적인 부분만 질문하셨습니다.

또 흥미로운게 제가 제출한 블로그의 글들을 보시고 그와 관련된 질문들을 하셨는데, 이것도 굉장히 깊숙히 질문하셨습니다.

인터넷에 정말 많은 기술글들처럼 단순히 글을 실어 나른것인지 가 아니라 내부구조부터 깊게 고민해보았는지 에 대한 질문들이셨습니다.

면접이 끝나고 사실 반반의 심정이였습니다. 아쉽게도 제가 준비한 모든것을 보여드리진 못했지만, 급급하게 준비한거치고는 방어를 적당히 한것 같다라는 느낌이였습니다.

꽤 긴 기다림의 시간끝에 [카카오페이] 안녕하세요. 카카오페이입니다. 라는 제목의 메일을 받게 되었습니다.

아쉽게도 결과는 불합격이었습니다. 어찌보면 당연한 결과라고 생각했습니다. 준비를 하면서 알게된 점이 입사하시는 분들의 공통점은 꾸준함과 탁월함임을 알게되었는데, 저는 두 부분 모두 빈약했던것 같습니다.

과정을 끝내고

얼렁뚱땅 시작된 공채지원이였지만, 최종면접까지 가게 되었습니다. 저는 최종탈락이라는 결과에 주목하기보다는 그 과정까지 가면서 준비하면서 제가 부족한 점이 무엇인지 확실히 깨닫게 되었습니다.
또 여러 과정, 특히 인터뷰를 하면서 카카오라는 기업이 정말 젠틀하고, 지원자 중심에서 생각해주는 기업이라는 점을 알게 되어 카카오에 입사하고 싶은 열망이 더 커지게 되었습니다.

내년에도 다시 1,2차 코테부터 할 생각하니까 아찔하긴 합니다.

3학년을 갓 마치고, 조금의 특수성은 있지만 군 복무를 마친 직후에 해본 첫 시도가 가장 챌린징스럽고 배운점이 많아 굉장히 뿌듯했습니다. 아마 이제는 복학을 준비하면서, 제가 부족했던 부분을 돌아보면서 그 부분을 개선하는 방식으로 진행할것 같습니다.

굉장히 긴 글이여서 쓰는 저 만큼이나 읽으시는 분들이 부담스러울텐데 투머치토커의 기질을 숨기기 쉽지않네요. 이 글을 읽으시는 모든 분들이 모두 원하는 회사에 합류하기를 기원합니다🙏

진짜 소집해제 한날부터 면접날까지 제대로 쉰 날이 없엇기에 이젠 좀 편하게 쉬면서 공부하려구요..