1주차 회고

 나는 컴퓨터 전공생이지만 항상 CS 지식이 부족하다고 느낀다.

분명 공부했던 내용이고, 대략적인 흐름은 알고 있지만 질문이 들어온다면 명확하게 대답할 자신이 없다.

 비록 학교에서 열심히 공부했던 사람은 아니지만, 그래서 자료구조가 무엇인가에 대해 묻는다면

지난주의 나는 기억도 가물가물하고 머리속에 애매하게 남은 기억으로 명확한 개념을 제시하지 못할 것이다.

대충 배열, 연결리스트, 스택 등등... 이어지는 흐름은 기억이 나지만

그것을 다시 구현하라고 하면 코드 몇줄 끄적이다 포기하는 내가 상상된다.

 배운 것은 있지만 뭔가 어렵게 느껴지고 명확하게 대답하지 못하는 나를 보게 됐을 때 CS 스터디를 신청하게 됐다.

 처음 강의 목차를 봤을 때

학교에서 1학기라는 시간을 투자해서 공부하는 과목을 이렇게 짧은 시간동안만 가르치는게 가능한가? 싶었다.

하지만 강의를 보고 난 후, 그동안 CS를 괜히 복잡하고 어렵게만 생각했던 것 같았다.

그림을 통해서, 그것도 집중할 수 있게 짧은 시간 나눠서 핵심만 강의하는 방식에 정말 만족한다.

지금 다시 각각 자료구조들을 구현할 수 있는지, 자료구조가 무엇인지 묻는다면 명확하게 대답할 수 있다.

그럴 필요가 없었는데, 처음 자료구조를 배울 때 너무 어렵게 접근했던 것 같다.

물론 이미 한번 배웠었던 개념이기에 이해가 쉽다고 느껴질 수도 있다.

그래도 이번 1주차 강의 덕분에 CS에 대한 딱딱하고 복잡하게 접근하는 관점을 더 부드럽게 풀어는 계기가 됐다.

요약

자료구조

 배열의 읽기/쓰기와 삽입/삭제 성능을 Big-O로 알아봤다.

이를 응용하여 연결리스트를 만들었고, 배열과 연결리스트의 장단점을 비교했다.

배열은 크기가 고정되어있지만 연결 리스트는 고정되어있지 않고

데이터 참조가 자주 필요한 상황이라면 배열의 인덱스를, 데이터의 삽입/삭제가 자주 일어난다면 연결 리스트를 이용하는 것이 좋다.

 연결리스트로 스택 자료구조를 구현할 수 있다. 이는 후입선출 구조이다.

 선입 선출 구조를 갖는 큐 역시 구현할 수 있다. 삽입은 헤드로, 삭제는 가장 뒤에서부터 노드를 제거한다.

 하지만 이런 자료 구조는 앞에 노드가 뒤를 가리키는 일방적인 방향의 자료구조이기 때문에 삭제 연산이 아주 비효율적이다.

그래서 단방향 연결리스트를 응용한 이중연결 리스트를 배웠다.

 이제 tail 노드를 삭제할 때에 굳이 head 노드부터 차례대로 타고가지 않아도 바로 삭제 가능하다.

 다음으로 해시 테이블 자료구조를 배웠다.

표에 어떤 내용을 형식 순서에 따라 나타낸 자료구조인데, 이를 인덱스로 접근하다보니 빈 공간이 많이 생겨서 메모리 낭비가 발생한다.

그래서 해시함수를 통해 입력받은 데이터를 고루 분포할 수 있도록 인덱스를 부여해준다.

 해시 테이블의 장점은 배열과 마찬가지로 빠른 데이터 참조와 삽입/삭제가 있다.

하지만 메모리를 많이 차지하기 때문에 미리 공간을 많이 마련해둬야 한다.

데이터가 중복된다면 동일 인덱스에 연결리스트로 구현하여 저장했다.

 중복을 허용하고 싶지 않다면 Set 자료 구조를 이용한다.

이 자료구조는 테이블의 value 값은 사용하지 않고 key 만 사용한다. 즉, 데이터 자체가 key로 사용된다.

운영체제

 운영체제는 프로세스, 메모리, 하드웨어, 파일 등을 관리한다.

간단하게 컴퓨터의 구조에 대해 알아봤는데, 메인보드 판에서 장치간의 전송을 진행한다.

메인보드에 cpu와 메모리를 꽂아주고, 저장장치 연산장치인 하드디스크, gpu 등을 연결함으로서 서로 데이터를 전송할 수 있다.

 cpu는 중앙 처리 장치의 약자로,

산술 논리 연산장치 ALU, 제어장치, 레지스터로 이루어져 있다.

입출력이 들어오면 cpu가 (제어장치) 입출력 장치에게

언제 입출력이 완료되는지를 주기적으로 계속 확인한다. 이런 방식을 polling이라고 한다.

이런 방식은 cpu 가동률이 안좋기 때문에 인터럽트를 발생시킨다.

인터럽트를 발생시키면 cpu는 해당 입출력 명령을 놔두고, 다른 작업을 한다.

입출력 작업이 완료되면 그 때 입출력 관리자는 cpu에게 신호를 주고,

cpu는 신호를 받아서 interrupt service routine을 실행시켜서 작업을 완료한다.

비동기적이라 성능적으로 이득이다.

application이 실행 되면 메모리에 해당 프로그램이 올라간다. 이를 프로세스라고 말하는데

운영체제는 이런 프로세스들을 관리하기 위한 Process Control Block을 만들고 저장한다.

PCB들은 연결리스트로 저장된다.

덕분에 만약 프로세스가 종료된다면 해당 PCB를 쉽게 제거할 수 있다.

PCB에는 프로세스에 관련한 여러가지 정보가 있는데

CPU가 다른 프로세스에게 할당될 때 PCB는

프로세스 상태, 다음 실행할 명령어의 주소를 담고있는 프로그램 카운터, 각종 레지스터값이 변경된다.

프로그램이 실행되면 운영체제는 해당 코드영역과 데이터영역을 메모리에 로드하고 pcb를 만들어서 값을 초기화한다.

그런데 프로세스 단위로 데이터를 처리하기에는 그 수만큼 PCB를 만들어줘야 하기 때문에 메모리가 너무 무거워진다.

그래서 프로세스 내에 여러개 존재하는 쓰레드를 고안해냈다.

 하나의 프로세스 내의 쓰레드들은 그 프로세스의 pcb, 코드 , 데이터, 힙 영역을 공유한다.

스택 영역은 공유하지 않고 쓰레드마다 하나씩 갖고 있다.

 이렇게 운영체제는 프로세스가 아닌 쓰레드별로 작업을 처리한다.

추가적인 작업이 필요하다면 프로세스가 아닌 쓰레드를 복사하여 처리한다.

 프로세스는 각각 독립적이라 하나가 문제생겨도 다른것에 영향을 주지 않는다.

하지만 쓰레드는 하나의 프로세스 안에서 존재하기 때문에 모두 영향받기 때문에 안정성 면에서는 프로세스가 우수하다고 할 수 있지만

각각의 프로세스는 자원을 따로 두고 있기 때문에 서로 통신하려면 비용이 크다.

반면, 쓰레드는 자원을 공유하기 때문에 오버헤드가 굉장히 적다.

속도와 자원면에서는 쓰레드가 더 우수하다.

 이제 프로세스들에게 cpu를 할당해줘야 하는데

어떤 프로세스에게 할당해줄 것인지, 그럼 얼마나 사용하게 해줄것인지 등 고려사항이 있다.

이를 스케줄링이라고 하는데, 각 프로세스들의 평균 대기 시간을 통해 성능을 결정한다.

 FIFO 방식으로 프로세스에 cpu를 할당한다면, 타임 슬라이스가 큰 프로세스가 먼저 큐에 들어가는 경우

그 뒤에 있는 프로세스는 엄청난 시간동안 대기해야 한다.

그래서 평균 대기시간이 엄청나게 늘어나기 때문에 보통 사용되진 않는다.

 여기에서 burst time이 짧은 것을 먼저 실행시킬 때 평균 대기 시간이 짧아지는 것을 알 수 있었다.

그렇다면 짧은 작업 먼저 배치하여 FIFO로 실행하는 Shortest Job First 방법은 어떨까?

이런 방법을 사용하기에는 문제가 있는데

1. 어떤 프로세스가 얼마나 실행될지 예측이 힘들다. 즉, 종료시간 예측힘듦

2. burst time이 짧은 프로세스가 중간에 계속 들어오면 burst time 긴 프로세스는 앞에 프로세스 종료될때까지 계속 기다려야해서 영원히 실행안될수도 있다.

그래서 SJF도 사용하지 않는다.

다시 처음으로 돌아가서 FIFO 방식을 극복한 방법으로 Round Robin 방식이 있다.

FIFO는 먼저 들어온 것이 다 끝나야 다음 프로세스가 실행된다.

이를 해결하기 위해 한 프로세스에게 일정 시간만큼만 cpu를 할당한다.

할당시간이 지나면 다른 프로세스에게 강제로 일정시간 cpu를 할당한다.

강제로 cpu를 뺏긴 프로세스는 큐의 가장 뒷부분으로 이동시켜서 문제를 해결한다.

하지만 RR 방식은 FIFO와 평균 대기시간이 비슷하다면 더 비효율적이다.

큐를 뒷부분으로 이동시키는 컨텍스트 스위칭 시간이 추가되기 때문이다.

RR알고리즘의 성능은 타임 슬라이스의 값에 따라 크게 달라진다.

타임슬라이스가 무한대면 그냥 fifo이고,

적당히 5초로 설정하자니 작업들이 뚝뚝 끊기는 느낌이고,

0.0001초를 할당하자니 실행되는 프로세스 처리량보다 컨텍스트스위칭 처리량이 훨씬 커지게 된다.

이런 상황을 오버헤드가 너무 크다고 말한다.

RR 방식을 극복한 오늘날 보편적인 스케줄링 방식인 Multi Level Feedback Queue가 있다.

기본적으론 사용률이 높은 작은 크기 타임슬라이스를 선택한다.

대신, cpu 사용률이 높은 cpu bound process들에게는 타임슬라이스를 크게 할당한다.

그렇다면, 운영체제는 cpu bound process랑 i/o bound process 를 어떻게 구분할까?

cpu를 사용하는 프로세스가 실행 도중 스스로 cpu를 반납하면 cpu 사용이 적은거니, i/o일 가능성이 높다.

반대로 cpu를 사용하는 프로세스가 타임슬라이스 크기를 오버해서 cpu 스케줄러에의해 강제로 cpu를 뺏기는 상황이라면 cpu bound일 확률이 높다.

이런 아이디어를 바탕으로 우선순위를 가진 큐를 여러개 준비해둔다.

우선순위가 높으면 타임슬라이스가 작고, 낮으면 타임슬라이스 크기가 커진다.

만약 프로세스를 실행하다가 강제로 cpu를 뺏기면 원래 있던 큐보다 낮은 우선순위 큐로 이동한다.

최종적으론 무한초 타임슬라이스이기 때문에 fifo처럼 연속적으로 작업을 마칠 수 있게된다.