운영체제

프로그램과 프로세스

• 프로그램: 저장장치에 저장된 정적인 코드

• 프로세스: 실행 중인 프로그램 (메모리에 로드됨)

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

• 멀티프로그래밍: 여러 프로그램을 메모리에 동시에 올려두고 실행

• 멀티프로세싱: 여러 프로세서(CPU)가 여러 프로세스 동시 처리

프로세스 상태

• 생성(New): 프로세스 생성됨

• 준비(Ready): CPU 할당 대기

• 실행(Running): CPU 할당받아 실행 중

• 대기(Waiting): I/O 등 이벤트 대기

   

• 종료(Terminated): 실행 완료

컨텍스트 스위칭

• 실행 중인 프로세스를 바꾸는 작업

• PCB 정보 저장/복원 필요

• 오버헤드 발생

쓰레드

• 프로세스 내의 실행 단위

• 특징:

• 같은 프로세스의 자원 공유

• 빠른 생성과 컨텍스트 스위칭

• 병렬 처리 가능

PCB (Process Control Block)

• 프로세스 관리를 위한 정보 저장 블록

• 포함 정보:

• 프로세스 ID

• 프로세스 상태

• 프로그램 카운터

• 레지스터 정보

• 메모리 정보

CPU 스케줄링

• 목표

   

  • 리소스 사용률: CPU 사용률을 높이는 것을 목표로 할 수도 있고, I/O 디바이스의 사용률을 높이는 것을 목표로 할 수도 있음

  • 오버헤드 최소화

  • 공평성: 모든 프로세스에게 공평하게 CPU 할당. 특정 프로세스에게만 CPU가 계속 할당되지 않게

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

  • 대기시간: 작업을 요청하고 실제 작업이 수행되기까지 대기하는 시간이 짧은 것을 목표로 함

  • 응답시간: 사용자의 요청에 얼마나 빨리 반응하는지

     

    서로 상반되는 목적을 지니기 때문에 목적에 따라 적절히 목표를 변경해야함

• 주요 알고리즘

  • FIFO(First In First Out)

    • 먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스 실행

  • SJF(Shortest Job First)

    • 어떤 프로세스가 얼마나 실행될지 예측하기가 힘듦

    • Burst Time이 긴 프로세스는 아주 오랫동안 실행되지 않을 수도 있음

  • RR(Round Robin)

    • FIFO의 경우 시분할 처리 시스템에서 사용하기 힘들고, SJF 알고리즘은 프로세스의 종료시간을 예측하기가 힘듦.

    • FIFO 알고리즘에서 단점을 해결하기로 함

    • 프로세스에 정해진 시간만큼만 할당할 수 있게 함(타임 슬라이스, 타임 퀀텀)

    • 타임 슬라이스를 작게 설정하는 경우 동시에 실행되는 느낌을 받을 수 있지만 컨텍스트 스위칭을 처리하는 양이 훨씬 커져 비효율적임(오버헤드가 너무 커짐)

  • MLFQ(Multi Level Feedback Queue)

    • RR 알고리즘의 업그레이드 된 버전

    • CPU 사용률과 I/O 사용률 전체를 생각하면 타임 슬라이스가 더 작은 값이 좋음

      MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함

    • CPU Bound Process에는 타임 슬라이스를 크게 주고,

      I/O Bound Process에는 타임 슬라이스를 작게 줌.

알고리즘&자료구조

시간복잡도

알고리즘의 성능을 평가하는 척도

• 입력 크기(n)에 따라 알고리즘이 실행되는 시간을 나타냅니다.

• 빅오(Big-O) 표기법을 주로 사용합니다.

배열 (Array)

• 연속된 메모리 공간에 데이터 저장

• 인덱스로 빠른 접근 가능 (O(1))

• 크기가 고정적

연결리스트 (Linked List)

• 노드가 다음 노드를 가리키는 구조

• 삽입/삭제가 용이 (O(1))

• 접근은 처음부터 순차적으로 (O(n))

스택 (Stack)

• LIFO (Last In First Out)

   

큐 (Queue)

• FIFO (First In First Out)

   

덱 (Deque)

• 양쪽 끝에서 삽입/삭제 가능

• 스택과 큐의 기능 모두 수행 가능

해시테이블 (Hash Table)

• 키-값 쌍으로 데이터 저장

• 평균적으로 빠른 검색/삽입/삭제 (O(1))

셋 (Set)

• 중복을 허용하지 않는 컬렉션

• 빠른 검색과 중복 제거

• 합집합, 교집합 등 집합 연산 가능

회고

과제도 생각보다 시간이 걸려서 다음엔 좀 더 넉넉잡아 시작해야할거 같다.

노션에 따로 정리해놓은 것도 중요한 내용들만 간략하게 정리해놓았다 보니 누락되는 것들이 있어 과제와 회고때 더 디테일하게 작성하지 못한 점이 아쉽다.