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

Stack

• LIFO(Last-in First-out)

  • 가장 먼저 들어온 데이터가 가장 나중에 나가는 자료 구조

  • 가장 나중에 들어온 데이터가 가장 먼저 나가는 자료 구조

• Linked List를 사용하여 Stack을 구현할 수 있다.
  
  출처 : https://www.geeksforgeeks.org/stack-data-structure/?ref=header_outind

Linked List를 사용한 구현

• head를 사용하여 스택을 간단하게 구현할 수 있다.

• 데이터 삽입을 무조건 첫 번째 인덱스에 수행한다.
  ⇒ 한쪽으로만 데이터를 삽입하고, 삭제하면 간단하게 구현할 수 있다.

Stack을 사용하는 상황

1. 웹 브라우저 방문 기록 (뒤로 가기 기능)

2. 프로그램의 실행 취소(Undo) 기능 구현

3. 역순 문자열 만들기

4. 수식의 괄호 검사

5. 후위 표기법 계산

6. 함수 호출 관리 (프로그램의 함수 호출 스택)

7. 깊이 우선 탐색(DFS) 알고리즘 구현

Stack ADT

• push() - 데이터 삽입

• pop()- 데이터 제거

• peek() - 데이터 참조

• isEmpty() - 비었는지 체크

Queue

• FIFO(First-in First-out)

  • 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료 구조

  • 가장 나중에 들어온 데이터가 가장 나중에 나가는 자료 구조

• Linked List를 사용하여 Queue를 구현할 수 있다.
  
  출처 : https://www.geeksforgeeks.org/queue-data-structure/

Linked List를 사용한 구현

• head를 사용하여 Queue를 간단하게 구현할 수 있다.

• 데이터를 뒤에서 제거하는 것을 구현해야 한다.
  → 단방향 Linked List의 경우에는 가장 마지막에 있는 Node에 접근하기 위해서는 head에서부터 순차적으로 접근해야 한다.
  → O(n)의 시간이 소요된다.
  ⇒ tail을 사용하여 가장 마지막의 노드 정보를 저장한다.
  → tail을 사용하더라도 가장 마지막의 노드 정보를 갱신하기 위해서는 head에서부터 순차 접근해야 한다.
  → O(n)의 시간이 소요된다.
  ⇒ 이중 연결 리스트를 사용하여 구현하면 O(n)을 O(1)로 개선할 수 있다.

Queue를 사용하는 상황

1. 프린터의 인쇄 대기열 관리

2. OS에 작업 요청이 들어오면 들어온 순서대로 큐에 넣고, CPU가 순서대로 꺼내서 처리한다.
   → FIFO 스케쥴링

3. 네트워크의 데이터 패킷 전송 관리

4. 실시간 시스템의 인터럽트 처리

5. 너비 우선 탐색(BFS) 알고리즘 구현

6. 캐시(Cache) 구현

7. 은행 창구와 같은 대기열 시스템 모델링

8. 동시성 프로그래밍에서의 작업 큐

Queue ADT

• enqueue() - 데이터 삽입

• dequeue() - 데이터 제거

• front() - 데이터 참조(Tail 참조)

• isEmpty() - Queue가 비었는지 확인

Deque

• 데이터의 삽입과 제거를 head와 tail에서 자유롭게 할 수 있는 자료구조

• Deque을 사용하여 Stack과 Queue를 구현할 수 있다.
  
  출처 : https://www.geeksforgeeks.org/deque-in-python/?ref=header_outind

Deque ADT

• printAll() - 리스트의 모든 데이터 출력

• addFirst() - head에 데이터 삽입

• removeFirst() - head에서 데이터 제거

• addLast() - tail에 데이터 삽입

• removeLast() - tail에서 데이터 제거

• isEmpty() - 리스트가 비었는지 체크

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

Context Switching

• 프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태값으로 전환하는 작업

• Context Switching이 발생할 때 PCB의 내용이 변경된다.

  • 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등이 변경된다.

발생하는 이유

• CPU 점유 시간의 종료

• I/O 요청

• 인터럽트가 발생한 경우

프로세스 생성

• OS가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 수행된다.
  → 그 이후에 생성되는 프로세스는 fork()를 사용하여 복사해서 사용된다.
  → 새로 생성하는 것보다 복사를 하는 것이 더 빠르기 때문

1. 실행 파일(.exe)실행

2. OS는 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드

3. 빈 스택과 빈 힙을 만들어 공간을 확보

4. 프로세스를 관리하기 위한 PCB 생성 및 초기화

exec()

• 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓸 수 있다.
  → 부모 프로세스와 다른 방식으로 동작할 수 있다.

좀비 프로세스

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

Thread

• 프로세스 내에 존재하고, 1개 이상이 존재할 수 있다.

• 하나의 프로세스 내에 있는 쓰레드들은 프로세스의 PCB, Code, Data, Heap 영역을 공유한다.

• Stack은 공유하지 않고, 쓰레드마다 하나씩 갖고 있다.

• OS에서 작업을 처리하는 단위

Thread 구분자

• Thread ID

• TCB(Thread Control Block)

Process vs Thread

안정성

• Process는 독립적이기 때문에 서로 영향을 받지 않는다.

• Thread는 하나의 Process를 공유하기 때문에 하나의 Thread에 이상이 생기면 다른 Thread에도 이상이 전파될 수 있다.
  ⇒ Process가 유리

속도와 자원

• 각각의 Process는 서로 고유한 자원을 갖는다.

  • 코드, 데이터, 힙, 스택 영역을 전부 따로 두고 있다.

  • Process간에 통신을 하려면 IPC를 사용해야 해서 오버헤드가 크고 속도가 느리다.

• 쓰레드는 하나의 Process의 자원을 스택 영역을 제외한 영역을 모두 공유하기 때문에 오버헤드가 느리다.