첫번째 발자국

'그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)'

수강생 여러분께 하고 싶은 말

• 외우려 하지 말고 이해해라

   

• 어렵다면 그림으로 풀어서 이해해라

• 당장 이해하기 어렵다면 특징만 외우고 나중에 다시 공부하기

• 이해를 했다면 기억도 오래 남고 특징들을 유추할 수 있다

자료구조와 알고리즘이란?

• 자료구조는 데이터가 어떤 구조로 저장되고 사용되는지를 나타낸다. (ex. int, float, 정적배열, 동적배열, 연결리스트 등)

  
  

• 알고리즘은 어떤 문제를 해결하기 위한 확실한 방법이다.

• 자료구조에 따라 알고리즘이 달라진다.

• 어떤 구현을 할 때 하나의 자료구조가 하나의 알고리즘만을 사용할 수 있는건 아니다.

   

• 상황에 맞는 적절한 자료구조와 알고리즘을 적용할 수 있어야 한다.

시간복잡도

• 더 좋은 알고리즘이란 무엇일까? 이는 사용자의 요구에 따라 변한다. 보통 메모리, 속도로 구분되며 일반적으로 알고리즘의 속도를 성능의 척도로 사용

• 시간복잡도란 특정 알고리즘이 어떤 문제를 해결할 때 걸리는 시간이며 사용자의 PC성능에 따라 시간 측정은 달라질 수 있으므로 코드에서 성능에 많은 영향을 주는 것을 찾아 실행 시간을 예측하는 것이다.

• 시간복잡도는 최악의 경우를 표현하는 빅 오 표기법을 사용한다.

• 빅 오 표기법은 가장 큰 영향을 미치는 항으로만 표현한다.

• 보통 자료구조의 시간복잡도는 평균, 최악의 경우를 생각한다.

자료구조

배열

연속된 메모리 공간을 할당 받는다.

운영체제는 배열의 시작 주소만 기억한다.

순차적으로 메모리가 적재되고 운영체제가 배열의 시작 주소를 알기에 인덱스를 통해 접근 가능하다.

삽입, 삭제 시 공간이 부족하거나 중간에 있는 요소를 삭제 시 데이터에 대한 이동이 필요해서 오버헤드가 많이 발생한다.

인덱스 참조 O(1) / 삭제, 삽입 성능 O(n)

연길리스트

배열의 단점을 해결하기 위해 만들어진 자료구조

저장하려는 데이터들을 메모리 공간에 분산하여 할당하고 이 데이터들을 서로 연결

이는 노드라는 것을 만들어 수행

노드의 구조는 데이터를 담는 변수 하나와 다음 노드를 가리키는 변수 하나

이러한 노드끼리 연결시킨것을 연결리스트라 한다.

연결리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 가능.

삽입, 삭제시 다음 가리키는 노드만 바꿔주면 된다. / 삽입, 삭제 O(1)

메모리 공간이 분산되어 있기에 인덱스 참조가 불가능 즉, 모든 노드 순회해야함 / 참조 O(n)

스택

First In Last Out (FILO)

먼저 들어간 데이터가 나중에 나오는 자료구조

삽입, 삭제, 참조 O(1) / 맨 위에 요소만 가능

연결리스트, 배열 등으로 구현 가능

사용 예제

• 명령 / Undo, Redo

• 문법 괄호 검사

• 큐와 병행하여 회문 검사

큐

First In First Out (FIFO)

먼저 들어간 데이터가 먼저 나오는 자료구조

삽입, 삭제, 참조 O(1) / 맨 앞에 요소만 가능

이중 연결리스트, 배열등으로 구현 가능

사용예제

• 대기열 / 마트 계산대, 게임 큐, 식당 줄 등

• 운영체제 프로세스 작업 요청 / FIFO 스케줄링

덱

데이터의 삽입과 제거를 Head와 Tail 양쪽에서 자유롭게 할 수 있는 자료구조

양방향 끝 삽입 삭제, 참조 O(1) / 가운데 O(n)

해시테이블

Key와 Value로 이루어진 자료구조

Key를 이용한 해시함수를 통해 데이터를 저장

만약 해시 충돌이 발생할 경우, 해당 인덱스의 연결리스트에 삽입

해시함수의 구현에 따라 공간의 낭비가 극대화될 수도 최적화될 수도 있다.

최고의 효율 : 참조, 삽입, 삭제 O(1)

최악의 효율 : 참조, 삽입, 삭제 O(n)

셋

데이터의 중복을 허용하지 않는 자료구조

해시 테이블을 활용하기에 해시 셋이라고도 불린다.

셋은 헤시 테이블의 Value값은 사용하지 않고 Key만 사용해 구현한다.

Key가 Key인 동시에 데이터로 사용하는 것

'그림으로 쉽게 배우는 운영체제'

운영체제 개요

• 프로세스 관리

   

• 메모리 관리

   

• 하드웨어 관리

   

• 파일 시스템 관리

운영체제의 구조

• 운영체제의 핵심 커널은 프로세스와 메모리, 저장장치를 관리한다.

• 사용자는 커널에 직접 접근할 수 없고 인터페이스를 통해 접근 가능하다. (GUI, CLI)

• 어플리케이션은 시스템 콜을 통해 커널에 접근 가능하며, 이를 통해 메모리를 사용할 수 있다.

• 하드웨어는 드라이버를 통해 커널에 접근 가능하다.

컴퓨터 하드웨어와 구조

하드웨어로 프로그램을 만들었기에 프로그램이 달라질 때마다 매번 스위치와 배선을 다시 조정해야 했다.

폰 노이만은 이를 해결하기 위해 CPU와 메모리를 두고 이들 사이는 버스로 연결한다.

버스는 데이터를 전달하는 통로이다.

• 메모리에 올라간 프로그램은 명령에 따라 처리된다.

컴퓨터 하드웨어

• 메인보드

  • 다른 하드웨어를 연결하는 장치

  • 장치 간에 데이터를 전송하는 건 메인보드의 버스가 담당.

• CPU

• 메모리

• 하드디스크

• 그래픽카드

• 마우스, 키보드, 사운드, 모니터 입출력 장치

   

•  CPU(Central Processing Unit)

  • 산술논리연산장치(Arithmetic and Logic Unit, ALU) : CPU 에서 실제로 데이터 연산을 담당

  • 제어장치 : 모든 장치들의 동작을 지시하고 제어

  • 레지스터 : CPU 내에서 계산을 위해 데이터를 임시로 보관하는 장치

     

• 메모리 종류

  • RAM(Random Access Memory)

    • 랜덤으로 데이터를 읽어도 저장된 위치와 상관 없이 읽는 속도가 같다.

    • 전력이 끊기면 데이터를 잃는다(휘발성) / 메인 메모리로 사용

  • ROM(Read Only Memory)

    • 전력이 끊겨도 데이터를 계속 보관 가능

    • 데이터를 한 번 쓰면 수정 불가능

    • 컴퓨터의 부팅과 관련된 바이오스를 저장하는데 사용

컴퓨터의 부팅과정

• ROM에 저장된 BIOS 실행

• BIOS는 전원, CPU, 메모리, 키보드, 마우스, 하드디스크 등 주요 하드웨어에 이상이 없는지 확인

• 하드디스크에 있는 마스터 부트 레코드에 저장된 부트로더를 메모리에 가져와 실행

• 설치된 운영체제 실행, 메모리에 불러온다.

• 바탕화면이 나오고 실행되는 모든 응용 프로그램은 메모리에 올라가 운영체제가 관리

인터럽트

• 입출력 처리 방식

  • 폴링

    • CPU가 주기적으로 입출력 장치의 상태를 확인하는 방식

    • 효율성이 떨어지고 자원 낭비 심함

  • 인터럽트

    • 폴링 방식을 개선한 현재 사용되는 방식

    • 입력이나 출력이 발생하면 CPU에 인터럽트를 발생

    • CPU는 현재 작업을 중단하고, 이 인터럽트를 처리하기 위해 인터럽트 처리 루틴
      (Interrupt Service Routine, ISR)로 이동 및 처리

    • 완료 후 다른 작업 수행

프로세스와 쓰레드

프로그램과 프로세스

프로그램은 저장장치에 저장된 명령문의 집합체

프로세스는 프로그램이 메모리에 올라가 실행중인 프로그램을 의미

멀티프로그래밍과 멀티프로세싱

멀티프로그래밍은 메모리에 여러 개의 프로세스가 올라간 것.

멀티프로세싱은 CPU를 시분할로 여러 개의 프로세스를 처리하면서 동시에 실행되는 것처럼 보이게 하는 것.

과거에는 메모리가 작기에 멀티프로그래밍이 불가하여 다른 저장장치에 있는 프로그램을 메모리에 올리는 스와핑을 통해 멀티프로세싱을 처리했다.

PCB

프로세스가 생성될 때 운영체제는 해당 프로세스의 정보를 가지고 있는 PCB(Process Control Block)를 만들어 저장한다.

운영체제는 PCB들을 연결리스트로 관리한다.

PCB의 구조

• 포인터 : 부모와 지식 프로세스에 대한 포인터 / 할당된 자원에 대한 포인터 / 프로세스 상태 전환시 저장하는 포인터

• 프로세스 상태 : 생성, 준비, 실행, 대기, 완료

• 프로세스 ID : 식별자

• 프로그램 카운터 : 다음에 실행될 명령어의 주소 저장 / 프로세스가 실행되던 지점 저장

• 레지스터 정보 : 프로세스가 실행될 때 사용했던 레지스터 값들

• 메모리 관련 : 프로세스가 메모리에 있는 위치 정보, 메모리 침범을 막기 위한 경계레지스터 값등 저장

• CPU 스케줄링 정보 : CPU 스케줄링에 필요한 우선순위, 최종 실행시간, CPU 점유시간 등이 저장

• 등등

프로세스 상태

운영체제는 시분할 시스템을 활용하여 여러 개의 프로세스를 빠르게 전환하며 실행시킨다.

시분할 처리를 위한 다섯가지 상태

• 생성(New) : PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태

• 준비(Ready) : CPU를 사용하기 위해 기다리는 상태

• 대기(Waiting) : 프로세스가 입출력 요청을 하면 입출력이 완료될 때 까지 기다리는 상태 / CPU는 굉장히 빠르고 입출력 작업은 상당히 느리다. 입출력 요청을 하는 프로세스가 완료될 때 까지 CPU를 기다리게 하는 것은 비효율적이기에 대기 상태가 만들어졌다.

• 실행(Running) : CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태 / 실행상태에 있는 프로세스의 수는 CPU의 개수만큼 존재할 수 있다.

• 완료(Terminated) : 프로세스가 종료된 상태 / 프로세스가 사용했던 데이터를 메모리에서 제거하고 PCB도 제거

컨텍스트 스위칭

컨텍스트 스위칭은 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업을 의미.

컨텍스트 스위칭이 일어날 때 PCB의 내용이 변경된다.

실행중인 프로세스의 작업내용을 PCB에 저장하고 실행될 프로세스의 PCB의 내용대로 CPU가 다시 세팅된다.

컨텍스트 스위칭이 일어날 때 PCB에 변경되는 값들은 아래와 같다.

• 프로세스 상태

• 프로그램 카운터

• 레지스터 정보

• 메모리 관련 정보

   

프로세스의 CPU 점유시간을 초과하거나 입출력 작업요청 등이 들어오면 인터럽트가 발생하며 컨텍스트 스위칭이 일어난다.

프로세스 생성과 종료

실행파일이 실행되면 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 로드하고

빈 스택과 빈 힙을 만들어 공간을 확보하며 이 프로세스를 관리하기 위한 PCB를 만들어서 값을 초기화해준다.

해당 프로세스 생성 과정은 운영체제가 부팅되고 0번 프로세스가 실행될 때 딱 한번 실행된다.

그 이후에 프로세스는 새로 생성하지 않고 0번 프로세스를 복사(fork함수)해서 사용한다.

새로 생성하는 것 보다 복사를 하는 게 더 빠르다.

exec함수를 통해 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓴다.

exit함수는 자식 프로세스가 부모 프로세스에게 정상 종료를 알리는 함수이다. / 부모 프로세스의 경우 종료

부모 프로세스는 자식 프로세스의 Exit Status를 읽고 자식 프로세스를 정리한다.

만약 부모 프로세스가 자식 프로세스보다 먼저 종료 되거나 자식 프로세스가 비정상적으로 종료되어 exit()신호를 주지 못해서 Exit Status를 읽지 못해 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 한다.

컴퓨터를 오래 켜두면 느려지는 현상이 발생하곤 하는데 메모리에 많은 프로세스가 올라오는 경우거나 좀비 프로세스가 메모리를 차지하기 때문이다.

컴퓨터를 껏다키면 메모리가 초기화 되기에 다시 빨라진다.

쓰레드

사용자가 운영체제에게 작업을 요구하면 그만큼 프로세스 수가 증가

프로세스는 메모리에 코드, 데이터, 스택, 힙영역, PCB를 할당해준다.

프로세스끼리의 통신은 IPC(Inter Process Comunication)를 이용 / 해당 작업은 비용이 많이 든다.

이러한 단점들을 해결하기 위해 고안된 것이 쓰레드이다.

쓰레드는 프로세스 내에 존재하는 것으로 1개 이상이 있을 수 있다.

쓰레드는 프로세스의 PCB, 코드, 데이터, 힙영역을 공유한다.

스택은 공유하지 않고 쓰레드 마다 고유하다.

한 프로세스 내에 쓰레드가 여러개 존재하기에 쓰레드 ID, TCB(Thread Control Block)가 생겼다.

이제 운영체제가 작업을 처리하는 단위는 프로세스 내에 쓰레드이다.

특징

• 안전성 : 프로세스는 서로 독립적이기에 하나의 프로세스가 문제가 있더라도 다른 프로세스는 영향을 받지 않는다.

반면 쓰레드는 하나의 프로세스 내에 존재하기에 해당 프로세스에 문제가 생기면 그 안에 모든 쓰레드에 문제가 생긴다.

• 속도, 자원 : 각각의 프로세스는 서로 고유한 자원을 가진다 / 코드, 데이터, 힙, 스택영역을 전부 따로 둔다. 프로세스간의 통신을 하려면 IPC를 이용해야해서 오버헤드가 크고 속도가 느리다.

반면 쓰레드는 한 프로세스내에서 스택영역을 제외한 영역은 모두 공유하기에 오버헤드가 굉장히 작다. 쓰레드간의 통신은 데이터를 공유할 수 있으니 쉽게 가능하지만 공유되는 공간에서 문제(공유자원 문제)가 발생할 수 있다.

CPU 스케줄링

CPU 스케줄링 개요

CPU 스케줄링은 운영체제가 모든 프로세스에게 CPU를 할당/해제하는 방식을 의미한다.

CPU 스케줄링에서 스케줄러(운영체제)가 고려해야할 사항은

1. 어떤 프로세스에게 CPU 리소스를 줘야하는가?

2. CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용해야하는가?

두 가지이다.

이 두 가지 고려사항이 컴퓨터의 성능에 굉장히 큰 영향을 미친다.

이 고려사항을 통해 여러 CPU 스케줄링 방식이 만들어진다.

CPU를 할당받아 실행하는 작업을 CPU Burst라 부른다.

입출력 작업을 I/O Burst라고 부른다.

다중큐

해당 프로세스의 우선순위를 보고 준비큐에 넣는다.

CPU 스케줄러는 준비상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스의 정보(PCB)를 선택해서 실행상태로 전환시킨다

프로세스 정보를 담고 있는 PCB가 준비상태의 다중큐에 들어가서 실행되기를 기다리고 있고

CPU 스케줄러에의해 실행상태로 전환된다.

이때 CPU 스케줄러는 준비상태의 다중큐를 참조해서 어떤 프로세스를 실행시킬지 결정

.

스케줄링 목표

• 리소스 사용률 : CPU 사용률을 높이는 것, I/O 디바이스 사용률 높이는 것

• 오버헤드 최소화 : 스케줄링을 위한 계산, 컨텍스트 스위칭 오버헤드 비용 최소화

• 공평성 : 모든 프로세스에게 스케줄링 기법에 맞춰 공평하게 CPU가 할당되어야 한다.

• 처리량 : 같은 시간 내에 더 많은 처리를 할 수 있는 방법을 목표로 한다.

• 대기시간 : 작업을 요청하고 실제 작업이 이루어지기 전까지 대기하는 시간이 짧은 것을 목표로 한다.

• 응답시간 : 응답시간이 짧은 것을 목표로 한다.

모든 목표를 만족할 수 없기에 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정해야 한다.

특별한 목적이 없을 경우, 밸런스를 유지하는게 중요.

FIFO

먼저 들어온 작업이 먼저 처리되는 스케줄링 방식

스케줄링 큐에 들어온 순서대로 CPU를 할당받는 방식 / 해당 방식은 프로세스가 완전히 끝나야만 다음 프로세스가 실행될 수 있다.

단점

• 실행중인 프로세스가 완전히 끝나야 다음 프로세스가 실행되는데, 만약 현재 실행중인 프로세스 작업이 길고, 다음 프로세스가 엄청 짧아도, 다음 프로세스는 대기해야 한다. / 효율성(처리량, 대기시간)이 떨어진다.

• I/O 작업이 있다면 해당 작업이 끝날때까지 CPU가 쉬게되어 CPU 사용률이 떨어진다.

스케줄링의 성능은 평균 대기 시간으로 평가된다.

평균 대기 시간은 프로세스들 모두가 실행되가끼지 대기시간의 평균을 의미한다.

Burst Time이 짧은게 먼저 실행되면 평균 대기 시간 짧아짐.

Burst Time이 긴게 먼저 실행되면 평균 대기 시간 길어짐.

FIFO알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나기에 현대 운영체제에서 잘 쓰이지 않고 일괄처리 시스템에 쓰인다.