1일차

운영체제 및 자료구조와 알고리즘

운영체제가 하는일

프로세스 관리

프로세스 관리는 운영체제의 핵심 기능 중 하나입니다. 여러 프로그램(예: 여러 브라우저 창)을 동시에 실행할 수 있는 이유는 운영체제가 각 프로세스를 효율적으로 관리해주기 때문입니다.

역할 : CPU의 자원을 여러 프로세스가 공평하게 사용할 수 있도록 스케줄링하고, 각 프로세스의 실행 상태를 관리합니다.
중요성 : 만약 운영체제가 프로세스를 관리하지 않으면, 특정 프로그램이 CPU를 독차지해 다른 프로그램이 실행되지 않을 수도 있습니다.

메모리 관리

운영체제는 시스템 메모리(RAM)를 효율적으로 관리합니다. 모든 프로그램은 메모리에 로드된 후 실행되기 때문에 메모리 관리는 필수적인 기능입니다.

역할 : 각 프로그램이 필요한 메모리 공간을 할당하고, 사용이 끝난 메모리를 해제합니다.
중요성 : 효율적인 메모리 관리를 통해 여러 프로그램이 원활하게 실행되며, 메모리 부족으로 인한 시스템 오류를 방지할 수 있습니다.

하드웨어 관리

운영체제는 사용자가 하드웨어에 직접 접근하는 것을 제한하고, 안정적이고 안전한 하드웨어 사용 환경을 제공합니다.

역할 : 키보드, 마우스, 디스크 드라이브, 프린터 등의 하드웨어 장치와 소프트웨어 사이의 중재자 역할을 합니다.
중요성 : 사용자가 하드웨어에 직접 접근하면, 하드디스크의 중요한 데이터를 훼손하거나 악의적인 공격을 가할 가능성이 있습니다. 운영체제가 이를 방지하고 보호합니다.

파일 시스템 관리

운영체제는 하드디스크에 저장된 파일들을 효율적으로 관리하고, 사용자가 쉽게 접근할 수 있도록 합니다.

역할 : 파일 생성, 수정, 삭제, 검색 등 파일 관련 작업을 담당합니다.
중요성 : 체계적인 파일 관리 덕분에 사용자는 원하는 데이터를 빠르게 찾고, 데이터를 안전하게 보관할 수 있습니다.

운영체제 구조

운영체제의 구조에서 가장 핵심적인 부분은 커널(Kernel)입니다.

커널은 운영체제의 중심이 되는 프로그램으로, 프로세스와 메모리, 저장 장치를 관리하는 핵심적인 기능을 담당합니다.

커널과 사용자 인터페이스

커널에 사용자가 직접 접근하는 것은 불가능하며, 인터페이스를 통해 간접적으로 접근합니다. 대표적인 인터페이스 방식은 GUI와 CLI로 나뉩니다.

GUI (Graphical User Interface): 그래픽 기반의 인터페이스로, 윈도우(Windows)나 맥OS(macOS) 같은 운영체제가 대표적입니다.
CLI (Command Line Interface): 텍스트 기반의 인터페이스로, 유닉스(Unix)나 리눅스(Linux)에서 제공하는 터미널 환경이 대표적입니다.

운영체제에서 어플리케이션은 시스템 콜(System Call)을 통해 커널에 접근합니다.

시스템 콜의 역할: 프로그램이 하드웨어 자원(CPU, 메모리, 디스크 등)에 안전하게 접근할 수 있도록 중간 역할을 합니다.

시스템 콜이 필요한 이유??

만약 시스템 콜 없이 프로그램이 하드디스크에 직접 접근할 수 있다면, 중요 데이터를 덮어쓰거나 다른 어플리케이션의 데이터를 훼손할 위험이 있습니다.

컴퓨터 하드웨어와 구조

오늘날 대부분의 컴퓨터는 **폰 노이만 구조(Von Neumann Architecture)를 기반으로 합니다.

* 폰 노이만 구조란?

컴퓨터 시스템에서 데이터와 프로그램을 같은 메모리 공간에 저장하고 CPU가 이를 처리하는 방식

CPU의 구조

CPU(중앙처리장치)는 컴퓨터에서 명령을 처리하는 핵심 장치입니다.

산술논리 연산장치(ALU): 데이터의 연산을 수행합니다.
제어장치: 모든 장치의 동작을 지시하고 제어합니다.
레지스터: 연산 중 데이터를 임시로 저장하는 고속 메모리입니다.

메모리의 종류

RAM(랜덤 액세스 메모리): 저장 위치와 상관없이 동일한 속도로 데이터를 읽습니다. 전원이 끊기면 데이터를 잃어버리기 때문에 주 메모리(Main Memory)로 사용됩니다.
ROM(읽기 전용 메모리): 전원이 끊겨도 데이터를 유지하지만, 한 번 저장된 데이터는 수정이 불가능합니다.
BIOS(기본 입출력 시스템) 등을 저장하는 데 사용됩니다.

컴퓨터의 부팅 과정

ROM에 저장된 BIOS가 실행됩니다.
BIOS가 CPU, RAM, 키보드 등 주요 하드웨어의 이상 여부를 점검합니다.
이상이 없으면 하드디스크의 **MBR(마스터 부트 레코드)에 저장된 **부트로더(bootloader)를 메모리로 로드하고 실행합니다.
부트 후 모든 응용 프로그램은 메모리에 올라와 운영체제가 관리합니다.

** MBR과 부트로더란???

MBR은 하드디스크의 첫 번째 섹터에 위치한 영역으로 하드디스크가 BIOS에 의해 처음 읽힐때

MBR을 읽어 부팅을 시작하게되는데 주요 역할로는 부트로더 위치 정보를 저장하고 디스크 파티션 정보를 저장함

부트로더는 운영체제를 메모리로 로드하고 실행하는 역할

주요 역할로는 운영체제를 로딩과 다중 부팅이 가능함

인터럽트(Interrupt)

인터럽트는 CPU와 입출력 장치 간 효율적인 작업 처리를 가능하게 합니다.

폴링 방식 : CPU가 주기적으로 입출력 장치의 상태를 확인하는 방식입니다. 비효율적입니다.
인터럽트 방식 : CPU가 다른 작업을 수행하는 동안 입출력 장치가 작업 완료 신호를 보냅니다. CPU는 **인터럽트 서비스 루틴(ISR)을 실행해 해당 작업을 처리합니다.

** 인터럽트 서비스 루틴(ISR)이란?

인터럽트가 발생했을때 호출되는 특정 목적을 처리하는 함수

예를 들면

평소에는 책 읽는 중(=메인 작업)
도중에 전화가 오면(=인터럽트 발생) 책을 잠시 덮고 전화를 받음(=ISR 실행)
문 열고 나서 다시 책 읽기(=메인 작업 복귀)

이런 느낌이다.

자료구조와 알고리즘

자료구조

자료구조(Data Structure)는 데이터를 어떤 구조로 저장하고 어떻게 사용될지를 나타냅니다. 다양한 자료구조가 존재하며, 각 구조마다 장단점과 사용 목적이 다릅니다.

대표적으로

변수: 가장 단순한 형태의 자료구조로, 하나의 데이터를 저장합니다.
배열: 같은 종류의 데이터를 순서대로 저장하는 자료구조입니다.
연결 리스트, 스택, 큐, 해시 테이블, 트리, 그래프: 보다 복잡한 구조로, 다양한 상황에서 데이터를 효율적으로 저장하고 처리합니다.

시간 복잡도

시간 복잡도는 특정 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내는데 여기서 걸리는 시간은 실제로 걸리는 시간이 아닌 입력크기(n의값)이 커졌을떄 연산횟수가 어떻게 변하는지 기준으로함

하지만 컴퓨터의 성능에 따라 실행 시간이 달라지기 때문에, 코드에서 성능에 영향을 주는 부분을 찾아 실행 시간을 예측합니다.

두 가지의 예)

반복문 사용

public class SumExample {
    public static void main(String[] args) {
        int n = 1000; // 입력 크기
        int sum = 0;
        for (int i = 1; i <= n; i++) { // n번 반복
            sum += i;
        }
        System.out.println(sum);
    }
}

수학 공식 이용

public class SumExample {
    public static void main(String[] args) {
        int n = 1000; // 입력 크기
        int sum = n * (n + 1) / 2; // 항상 3번 연산
        System.out.println(sum);
    }
}

위 방법을 비교했을때 방법1은 n번을 기준으로 반복하지만 방법2는 3번을 연산

n이 1000일 경우 방법1은 1000번을 반복해 1초가 걸리고 방법2는 3번을 연산을해 0.1초가 나왔다 가정을 했을때

만약 cpu가 고성능일 경우 두 방법 모두 0.1초가 나올 경우도 있기때문에 처리하는 실제 시간이 아닌 연산횟수를 기준으로 하게됨

위 방법을 기준으로 했을때 2번쨰 방법이 좋은 알고리즘 방법임

시간 복잡도를 평가하는 방법

반복문은 알고리즘의 성능에 가장 큰 영향을 미칩니다. 반복문의 중첩 정도와 실행 횟수에 따라 시간 복잡도가 결정됩니다.

예시: 배열 [1, 2, 3, 4]에서 숫자 1을 찾는 경우는 첫 번째에 바로 찾을 수 있지만, 4를 찾으려면 배열 전체를 순회해야 합니다. 이런 상황에 따라 성능이 달라지므로 시간 복잡도는 최선, 최악, 평균의 경우로 나눕니다.

Big-Ω (오메가): 최선의 경우 시간 복잡도.

public class BigOmegaExample {
    public static boolean findNumber(int[] arr, int target) {
        for (int num : arr) {
            if (num == target) {
                return true; // 최선의 경우: 첫 번째 요소에서 찾음
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        System.out.println(findNumber(numbers, 1)); // 최선의 경우
    }
}

Big-Θ (세타): 평균의 경우 시간 복잡도.

public class BigThetaExample {
    public static boolean findNumber(int[] arr, int target) {
        for (int num : arr) {
            if (num == target) {
                return true; // 평균적으로 배열의 절반을 탐색
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        System.out.println(findNumber(numbers, 3)); // 평균적인 경우
    }
}

Big-O: 최악의 경우 시간 복잡도.

public class BigOExample {
    public static boolean findNumber(int[] arr, int target) {
        for (int num : arr) {
            if (num == target) {
                return true;
            }
        }
        return false; // 최악의 경우: 배열 끝까지 탐색
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        System.out.println(findNumber(numbers, 5)); // 최악의 경우
    }
}

이중 Big-O 표기법이 가장 널리 사용되는데 주로 알고리즘의 성능을 평가할 때 최악의 경우를 기준으로 설명하므로 많이 사용되기 때문입니다.

알고리즘의 성능을 평가할때 최악을 경우를 기준으로 설명하는 이유

알고리즘 성능을 최악의 경우로 평가하는 이유는, 최악의 상황에서도 최소한 그 정도 시간 이상은 걸리지 않기 때문입니다. 이렇게 평가하면 평균적인 성능도 예측할 수 있고, 예기치 않은 상황에서도 안전하게 동작한다고 보장할 수 있습니다.

일상을 예로 들면

평균적인 경우: 집에서 학교까지 보통 30분 걸림
최악의 경우: 비가 오고, 차가 막히고, 사고가 나면 1시간 걸림

학교에 늦지 않으려면?

평균 30분만 보고 출발하면, 최악의 경우에 지각할 수 있습니다.
최악 1시간을 기준으로 준비하면 어떤 일이 생겨도 늦지 않게됨

Big-O 표기법의 특징

입력 크기에 따른 계산량: 빅오 표기법은 입력 크기 n이 커질 때 계산량이 어떻게 증가하는지를 나타냅니다. 이는 알고리즘의 성능을 추상적으로 표현하는 방법입니다.
상수와 낮은 차수 항을 무시함: 빅오 표기법에서는 상수나 낮은 차수 항을 무시합니다.

예를 들어, n² +2n +100n처럼 복잡한 식이 있을 때, 가장 영향을 많이 주는 항만 표기해 해당 예에선 n² 이 가장 영향을 많이 미쳐 상수 항인 100과 낮은 차수 항인 2n은 성능에 큰 영향을 미치지 않으므로 빅오 표기법에서는 이들을 생략해 O(n²) 으로 표현함

2일차

프로세스와 배열,연결리스트

프로그램과 프로세스 개념

프로그램이란?

하드디스크(HDD), SSD와 같은 저장장치에 저장된 명령문의 집합체
애플리케이션(앱)이라고도 불리며, 윈도우에서는 보통 .exe 확장자를 가짐

프로세스란?

실행 중인 프로그램을 의미
하드디스크에 저장된 프로그램이 메모리에 올라가 실행될 때 프로세스가 됨

프로그램과 프로세스의 차이

프로그램: 저장장치만 사용하기 때문에 → 수동적
프로세스: 메모리와 운영체제의 CPU 스케줄링 알고리즘에 따라 CPU 사용, 필요에 따라 입출력을 수행 → 능동적

프로세스의 구조

Code 영역: 프로그램의 실행 코드가 저장되는 영역으로, 읽기 전용이다.
Data 영역: 전역 변수와 static 변수가 저장되며, 프로그램 종료까지 유지된다.
Stack 영역: 함수 호출 시 생성되는 지역 변수와 매개변수가 저장되며, 함수 종료 시 제거된다.
Heap 영역: 프로그래머가 동적으로 메모리를 할당하는 영역

CPU가 프로세스를 실행하는 순서

데이터를 메모리에 저장 (예: 숫자 5와 7)
데이터를 레지스터(**EDX, **EAX)로 로드
제어 장치가 연산 명령 실행 → ALU(산술 논리 연산 장치)가 연산 수행
연산 결과를 EAX 레지스터에 저장 후 메모리에 다시 저장

** ALU : 데이터의 연산을 담당하는 장치

** EAX : 범용 레지스터 중 하나로, 보통 연산의 결과를 저장하는 데 사용 특히 산술 및 논리 연산에서 많이 쓰임

** EDX : 보조적인 역할을 하는 레지스터로. 곱셈, 나눗셈 같은 연산에서 EAX와 함께 사용돼서 큰 숫자를 처리하거나 나머지 값을 저장하는 데 쓰임

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

유니프로그래밍과 멀티프로그래밍

유니프로그래밍: 메모리에 하나의 프로세스만 존재
하나의 작업이 끝나야 다음 작업 시작 → CPU가 쉬는 시간(입출력 대기 시간)이 많아 비효율적
멀티프로그래밍: 메모리에 여러 프로세스가 존재
한 프로세스가 입출력 작업 중이면, 다른 프로세스가 CPU 사용 -> CPU사용 극대화 하지만 CPU가 어떤 작업을 먼저 할지(=스케줄링이 필요)

멀티프로세싱

병렬 처리를 통해 성능을 높이고 안정성을 강화하며, 빠른 응답과 확장성을 제공합니다

여러 개의 CPU가 동시에 여러 프로세스를 실행하는 방식으로 시분할 형식과는 살짝 다름
시분할 방식은 싱글코어에서 여러 프로세스를 빠르게 번갈아 실행하는 방식.
멀티프로세싱은 멀티코어에서 실제로 동시에 실행 멀티코어는 시분할과 멀티프로세싱이 동시에 가능

PCB란?

PCB는 운영체제가 프로세스를 관리하기 위해 사용하는 데이터 구조입니다.
각 프로세스마다 하나의 PCB가 생성되며 프로세스의 상태와 정보를 담고 있습니다.

연결리스트 형태로 저장되며 프로세스 종료시 PCB는 제거됩니다.

PCB 구성 요소

포인터: 부모/자식 프로세스와 자원 포인터, 상태 전환 시 저장 포인터
프로세스 상태: 생성, 준비, 실행, 대기, 완료 상태
프로세스 ID: 프로세스를 식별하는 고유 번호
프로그램 카운터: 다음 실행 명령어의 주소
레지스터 정보: 실행 중 사용한 레지스터 값
메모리 정보: 메모리 위치와 경계 레지스터 값
CPU 스케줄링 정보: 우선순위, 최종 실행 시간, CPU 점유 시간 등

프로세스의 상태

생성 상태: 프로세스 생성 요청 시 운영체제가 PCB 생성
준비 상태: CPU 할당 대기
실행 상태: CPU를 할당받아 실행 중 (CPU 수만큼 프로세스 실행 가능)
대기 상태: 입출력 요청 시 대기 (입출력 완료 후 준비 상태로 전환)
완료 상태: 프로세스 종료 및 메모리와 PCB 제거

배열,연결리스트

배열

장점: 빠른 데이터 참조(O(1)의 성능을 가짐)
단점: 고정된 크기, 중간 삽입/삭제 시 비효율적(O(n)의 성능을 가짐)

연결 리스트 (Linked List)

장점: 동적 메모리 할당, 삽입/삭제 시 효율적
단점: 느린 데이터 참조(O(n)의 성능을 가짐) 비연속적인 메모리 할당

사용 상황

배열: 데이터 변화가 적고 참조가 빈번할 때 유리
연결 리스트: 삽입/삭제가 자주 발생할 때 유리

빠른 조회가 필요한 상황이면 배열이 유리하고 데이터 추가,삭제가 자주 일어나면 연결 리스트가 유리함

연결리스트 구현 예제

class Node{
    constructor(data, next = null){
        this.data = data; // 현재 데이터 정보
        this.next = next; // 다음 데이터의 정보
    }
}

class LinkedList{
    constructor(){
         this.head = null; // 연결리스트의 head 부분
         this.count = 0; // 인덱스 카운트

    }
    printAll(){ // 현재 연결리스트의 정보 모두 출력
        let currentNode = this.head;
        let text = "[";

        while(currentNode != null){ // 현재 노드가 널일경우 반복문을 벗어남
            text += currentNode.data;
            currentNode = currentNode.next;

            if(currentNode != null){
                text += ", ";
            }
        }
        text += "]";
        console.log(text);
    }

    clear(){ // 연결리스트의 데이터를 전부 제거
        this.head = null;
        this.count = 0;
    }


    insertAt(index,data){ // 특정 위치에 데이터를 하나씩 삽입
        if(index > this.count || index < 0){ // 만약 인덱스의 크기를 넘어갈경우 알림추가
            throw new Error("범위를 넘어갔습니다.");
        }
        let newNode = new Node(data);

        if(index == 0){ // 인덱스가 0일 경우 head를 새 노드로 설정
            newNode.next = this.head;
            this.head = newNode;
        }else{ // 특정 위치에 노드를 삽입
            let currentNode = this.head;
            for(let i =0; i<index - 1; i++){
                currentNode = currentNode.next;
            }
            newNode.next = currentNode.next; // 새로운 노드의 next를 기존 노드의 next로 설정
            currentNode.next = newNode; // 기존 노드의 next를 새 노드로 설정
        }
        this.count++; // 인덱스 길이를 확인하기 위해 count 추가

    }

    insertLast(data){ // 마지막 위치에 데이터 삽입
        this.insertAt(this.count, data);
    }

    deleteAt(index){ // 특정 위치의 데이터 삭제
        if(index >= this.count || index < 0){ // 만약 인덱스의 크기를 넘어갈경우 알림추가
            throw new Error("제거할 수 없습니다.");
        }

        let currentNode = this.head;
        
        if(index == 0){ // head 노드를 삭제하는 경우
            let deletedNode = this.head;
            this.head = this.head.next;
            this.count--;
            return deletedNode;

        }else{ // 그 외의 경우
            for(let i =0;i<index-1;i++){
                currentNode = currentNode.next;

            }
            let deletedNode = currentNode.next;
            currentNode.next = currentNode.next.next;
            this.count--;
            return deletedNode;

        }


    }

    deleteLast(){ // 마지막 데이터 삭제
        return this.deleteAt(this.count - 1);
    }

    getNodeAt(index){ // 특정 위치의 데이터 조회
        if(index >= this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }
        let currentNode = this.head;
        for(let i = 0; i < index; i++){ // 전달 받은 index의 정보를 담음
            currentNode = currentNode.next;
        }

        return currentNode;


    }


}

3일차

컨텍스트 스위칭와 쓰레드, 큐 스택

컨텍스트 스위칭

컨텍스트 스위칭(Context Switching)은 실행 중인 프로세스를 저장하고 다른 프로세스를 실행하기 위해 상태 값을 교체하는 작업입니다. 컨텍스트 스위칭이 발생할 때, PCB(Process Control Block)의 내용이 변경됩니다.

실행 중인 프로세스의 작업 내용을 PCB에 저장하고, 실행될 프로세스의 PCB 내용을 기반으로 CPU가 다시 세팅됩니다.

컨텍스트 스위칭 시 PCB에 저장 및 변경되는 값은 다음과 같습니다:

프로세스 상태
프로그램 카운터 : 현재 실행 중인 프로그램에서 다음에 실행될 명령어의 메모리 주소를 나타내는 레지스터
각종 레지스터 값

컨텍스트 스위칭 과정

운영체제(OS)가 프로세스 A가 CPU를 오래 사용했다고 판단하고 인터럽트(Interrupt)를 발생시킴.
프로세스 A가 하던 일을 멈추고 현재 상태에서 나중에 재개할 수 있도록 CPU 레지스터 값을 PCB A에 저장.
PCB B를 참조하여 이전 프로세스 B의 상태로 CPU 레지스터 값을 복원.
프로그램 카운터의 값에 따라 프로세스 B의 명령어 실행.
프로세스 B가 CPU 점유 시간이 끝나면 인터럽트를 발생시켜 PCB B에 현재 상태 저장.
다시 PCB A의 내용을 불러와 프로세스 A 실행.

메모리에 있는 모든 프로세스들은 컨텍스트 스위칭을 함

컨텍스트 스위칭 발생 이유

CPU 점유 시간 만료 (타임 슬라이스 종료)
I/O(입출력) 요청
인터럽트 발생 (시스템 콜, 예외 처리 등)

프로세스 생성 과정

.exe 파일 실행 시 운영체제는 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드.
메모리에 빈 스택(Stack)과 힙(Heap) 공간 생성.
프로세스를 관리하기 위한 PCB 생성 및 초기화.

.exe 파일을 실행했을때 운영체제는 해당 프로그램의 코드영역과 데이터영역을 메모리에 저장하고
메모리에 빈 스택과 빈 힙을 만들어 공간을 확보 후 이 프로세스를 관리하기위한 PCB를 만들어
값을 초기화 해줌

부모-자식 프로세스 관계

0번 프로세스(부모): 부팅 시 한 번만 실행.
fork() 함수를 사용해 기존 프로세스를 복사하여 새로운 자식 프로세스 생성.
자식 프로세스는 부모 프로세스의 코드, 데이터, 스택, PCB 내용 복사
하지만 이렇게 되면 자식 프로세스를 실행하면 결국 부모 프로세스가 실행되는것과 다를게 없어 **exec() 함수를 사용

**exec() 함수 사용

자식 프로세스가 부모 프로세스와 완전히 다른 동작을 하도록 fork() 함수로 프로세스를 복사후 exec()함수를 실행시키면 부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어쓰게됨

좀비 프로세스

부모 프로세스가 자식보다 먼저 종료되거나 자식이 비정상 종료 시 발생.
자식 프로세스가 exit() 신호를 받지 못해 Exit Status 미수신 시 메모리 점유 지속
보통 컴퓨터를 오래 켜두면 해당 현상 발생

쓰레드(Thread)

하나의 프로세스 내에서 여러 개의 쓰레드를 생성할 수 있습니다.
쓰레드는 프로세스 내의 코드, 데이터, 힙 영역을 공유하지만 각 쓰레드는 독립적인 스택을 가집니다.
쓰레드 간 통신은 데이터를 공유할 수 있기 때문에 빠르지만 공유 자원에서 문제가 발생할 수 있습니다.

쓰레드의 장점

프로세스 내 존재, 1개 이상의 쓰레드 보유 가능.
PCB, 코드, 데이터, 힙 영역 공유.
스택은 독립적, 각 쓰레드마다 개별 보유.
**TCB(Thread Control Block) 생성으로 쓰레드 구분 가능.

** TCB란?

쓰레드 제어 블록으로, 각 쓰레드의 상태를 관리하는 데이터 구조입니다

TCB가 필요한 이유

쓰레드는 프로세스 내에서 실행되는 독립적인 작업이기 때문에 각 쓰레드의 상태와 정보를 독립적으로 관리할 필요가 있습니다.

이를 위해 TCB를 사용하여 각 쓰레드의 실행 상태를 효율적으로 관리합니다.

쓰레드 사용 예시 (웹브라우저)

기존 방식: 탭 추가 시 새로운 프로세스 복사 -> 메모리 사용 증가.
쓰레드 방식: 프로세스 내에 새로운 쓰레드 추가 -> 메모리 효율 향상.

프로세스와 쓰레드의 장단점

안정성

프로세스: 독립적, 하나의 프로세스 문제가 다른 프로세스에 영향 없음.
쓰레드: 동일 프로세스 내 문제 발생 시 모든 쓰레드 영향.

안전성은 프로세스가 우수

속도 및 자원 효율성

프로세스: 고유 자원 보유(코드,데이터,힙,스택영역을 따로 둠), IPC 필요 -> **오버헤드 크고 속도 느림.
쓰레드: 스택을 제외한 영역 공유 -> 오버헤드 적고 통신 속도 빠름.

** 오버헤드란?

어떤 작업을 수행하는 데 필요한 추가적인 비용이나 시간

스택(Stack)

First In Last Out(FILO): 먼저 들어간 데이터가 나중에 나옴.
스택은 먼저 들어간 데이터가 나중에 나오기만 하면 어떤 자료구조로 구현하던 상관이 없음

연결리스트 기반 스택 동작 예시

삽입(Push): 1 -> 2 -> 3 -> 4 순서로 삽입 시 4, 3, 2, 1 순서로 저장.
제거(Pop): 가장 마지막에 삽입된 데이터부터 제거.

사용 사례

Undo(Ctrl + Z): 그림판에서 그림을 그리다 잘못그리면 crtl+z를 사용하게되는데 컴퓨터가
작업을 스택에 저장을 하고있어 crtl+z를 누르게 되면 가장 최근에 들어온 작업을 버려버림

스택의 주요 연산

push(): 데이터 삽입.
pop(): 데이터 제거.
peek(): 데이터 참조.
isEmpty(): 비어있는지 확인.

스택 구현 예제

class Stack{
    constructor(){
        this.list = new LinkedList();
    }

    push(data){ // 스택의 맨 뒤에 데이터 삽입
        this.list.insertAt(0, data);
    }

    pop(){ // 스택의 맨 뒤 데이터 제거
        try{ // 스택이 비어있을 경우 오류 방지
            return this.list.deleteAt(0);
        }catch{
            return null;
        }
    }

    peek(){ // 스택의 맨 앞 데이터 참조
        return this.list.getNodeAt(0);
    }

    isEmpty(){ // 스택이 비어있는지 체크
        return (this.list.count == 0);
    }


}

큐(Queue)

큐는 데이터를 한쪽 끝에서 삽입하고, 다른 쪽 끝에서 제거하는 자료구조로 FIFO(First In First Out) 방식으로 동작합니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나옵니다.

큐의 동작 방식

노드가 뒤의 노드를 가리키는 단방향 연결리스트인데 이런 구조면 맨뒤에있는 데이터를 삭제하기 힘들어지게됩니다.
삽입의 경우 head를 사용해서 간단한데 제거의 경우 가장 뒤의 노드를 제거해야하기 때문에
해당 노드에 접근하기 위해서 가장 앞 노드 부터 순서대로 접근을 해야해 O(n)의 성능을 가져 느림
이를 위해 tail이라는 변수하나를 만들어 head는 가장 앞의 노드를 가르키고 tail은 가장 뒷 노드를 가르켜 O(1)의 성능으로 제거할수있음

** 하지만 변수를 추가한다고 항상 O(1)의 성능을 가지는건 아닌데 변수를 이용해 마지막 노드를 삭제하면 삭제된 이전 노드를 다시 변수를 설정해줘야함 단방향 연결리스트라 tail로 이전 노드를 참조하는건 불가능해 현재 노드가 이전 노드로 가리킬 수 있는 이중 연결리스트를 사용해야함

큐의 주요 연산

enqueue(): 데이터 삽입.
dequeue(): 데이터 제거.
front(): 데이터 참조.
isEmpty(): 비어있는지 확인.

 class Queue{
    constructor(){
        this.list = new DoublyLinkedList();
    }

    enqueue(data){  // 큐의 tail에 데이터 삽입
        this.list.insertAt(0,data);
    }

    dequeue(){ // 큐의 head 부분 데이터 제거
        try{
            return this.list.deleteLast();
        }catch(e){
            return null;
        }
    }

    front(){ // 큐의 head 데이터 참조
        return this.list.tail;
    }

    isEmpty(){ // 큐가 비었는지 확인
        return (this.list.count == 0);
    }


}

덱(Deque)

덱(Deque, Double-ended Queue)은 데이터를 양쪽 끝에서 자유롭게 삽입하거나 제거할 수 있는 자료구조입니다. 덱은 큐와 스택의 특성을 모두 갖고 있습니다.

덱의 주요 연산

printAll(): 모든 데이터 출력.
addFirst(): head에 데이터 삽입.
removeFirst(): head에서 데이터 제거.
addLast(): tail에 데이터 삽입.
removeLast(): tail에서 데이터 제거.
isEmpty(): 비어있는지 확인.

덱 구현 예제

 class Deque{
    constructor(){
        this.list = new DoublyLinkedList();
    }


    printAll(){ // 덱 정보 모두 출력
        this.list.printAll();
    }
    
    addFirst(data){ // 덱의 head부분에 데이터 삽입
        this.list.insertAt(0, data);
    }

    removeFirst(){ // 덱의 head 부분 데이터 제거
        return this.list.deleteAt(0);
    }

    addLast(data){ // 덱의 tail에 데이터 삽입
        this.list.insertAt(this.list.count,data);
    }

    removeLast(){ // 덱의 tail 부분 데이터 제거
        return this.list.deleteLast();
    }

    isEmpty(){ // 덱이 비어있는지 확인
        return (this.list.count == 0);
    }

}

4일차

CPU 스케줄링과 FIFO, 해시테이블

CPU 스케줄링

프로그램을 실행시키면 메모리에 프로세스가 생성되고, 프로세스에는 1개 이상의 스레드가 존재합니다. 프로세스들은 CPU를 차지하기 위해 운영체제의 명령을 기다리고 있으며, 운영체제는 모든 프로세스에게 CPU를 할당 및 해제하는 역할을 수행합니다. 이를 CPU 스케줄링이라 합니다.

CPU 스케줄러가 고려해야 할 사항

어떤 프로세스에게 CPU를 할당할 것인가?
- 메모리에는 수많은 프로세스가 존재합니다. 이 중 어떤 프로세스에게 CPU 사용권을 줄 것인지를 결정해야 합니다.
CPU를 할당받은 프로세스가 얼마나 오랫동안 CPU를 사용할 것인가?

현대 운영체제는 시분할 방식(Time-sharing) 을 사용하여 여러 프로세스에게 짧은 시간 동안 번갈아 가며 CPU를 할당합니다.

CPU Burst: 프로세스가 CPU를 할당받아 작업하는 시간
I/O Burst: 프로세스가 입출력 작업을 수행하는 시간

다중 큐(Multi-Queue)

프로세스 정보를 담고 있는 PCB(Process Control Block) 는 준비 상태의 다중 큐에 들어가 실행되기를 기다립니다.
CPU 스케줄러는 준비 상태 큐를 참조하여 어떤 프로세스를 실행시킬지 결정합니다.
다중 큐(Multi-Queue) 는 우선순위를 기반으로 여러 개의 큐로 나누어져 있으며 각 큐는 서로 다른 우선순위를 가질 수 있습니다.
프로세스는 자신의 우선순위에 따라 해당 큐에 배치되며, 상위 우선순위 큐가 먼저 스케줄링됩니다.
I/O 작업이 발생하면 실행 중인 프로세스는 해당 I/O 작업에 따라 분류된 큐에 들어가고, CPU 스케줄러는 이를 참조하여 스케줄링합니다.

스케줄링 목표

리소스 사용률(Resource Utilization)
- CPU 사용률과 I/O 디바이스 사용률을 최대화하는 것이 목표입니다.
오버헤드 최소화(Minimizing Overhead)
- 스케줄링 계산이 지나치게 복잡하거나 컨텍스트 스위칭(Context Switching) 이 잦아지면 오히려 성능이 저하될 수 있으므로, 이러한 오버헤드를 최소화합니다.
공평성(Fairness)
- 모든 프로세스가 공평하게 CPU를 할당받아야 합니다.
처리량(Throughput)
- 주어진 시간 내에 최대한 많은 작업을 처리하는 것을 목표로 합니다.
대기 시간(Waiting Time)
- 작업을 요청한 후 실제 작업이 시작되기 전까지의 시간을 줄입니다.
응답 시간(Response Time)
- 대화형 시스템에서는 사용자의 요청에 빠르게 반응하는 것이 중요합니다.

위 목표들은 서로 상반되는 경우가 많습니다.

처리량을 높이기 위해서는 하나의 프로세스에 CPU를 오래 할당해야 하지만,
응답 시간을 줄이려면 여러 프로세스에 CPU를 골고루 할당해야 합니다.

예를 들어:

터치스크린 기반 시스템 → 응답 시간 단축이 중요
복잡한 계산 작업 → 처리량 극대화가 중요

FIFO(First In First Out)

FIFO는 선입선출 방식의 스케줄링 알고리즘입니다.(Queue(큐)와 같음)
먼저 도착한 프로세스가 완전히 끝나야 다음 프로세스가 실행됩니다.

장점: 단순하고 직관적

단점: 실행 시간이 긴 프로세스가 먼저 도착하면, 짧은 작업이 뒤에서 기다려야 하므로 **Convoy Effect(호위 효과) 발생

** 호위 효과 : 긴 프로세스가 CPU를 점유하고 있을 때 짧은 프로세스들이 기다리는 상황

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

평균 대기 시간 계산 예시

프로세스1: Burst Time 25초
프로세스2: Burst Time 5초
프로세스3: Burst Time 4초

실행 순서: 1 → 2 → 3

프로세스1: 대기 시간 0초
프로세스2: 대기 시간 25초
프로세스3: 대기 시간 30초

평균 대기 시간: (0 + 25 + 30) ÷ 3 = 18.3초

실행 순서: 3 → 2 → 1

프로세스3: 대기 시간 0초
프로세스2: 대기 시간 4초
프로세스1: 대기 시간 9초

평균 대기 시간: (0 + 4 + 9) ÷ 3 = 4.3초

이처럼 실행 순서만 바꾸어도 평균 대기 시간이 크게 차이 납니다. 따라서 FIFO 알고리즘은 Burst Time에 따라 성능 편차가 심하여, 현대 운영체제에서는 거의 사용되지 않습니다.대신 **일괄 처리 시스템(Batch System)에서 주로 활용됩니다.

** 일괄 처리 시스템 : 사용자와의 상호작용 없이 데이터나 작업을 일정한 묶음으로 처리하는 시스템을 의미 주로 자동화된 작업이나 대량의 데이터 처리가 필요한 상황에서 사용

예시 ) 월 급여를 계산하고 지급하는 작업을 일괄적으로 처리 혹은 정해진 시간마다 데이터를 백업하고 처리

해시 테이블(Hash Table)

해시 테이블은 해시 함수를 사용하여 데이터를 키(Key) 와 값(Value) 쌍으로 저장하는 자료구조입니다.

장점

빠른 검색, 삽입, 삭제가 가능합니다.

단점

공간 효율성이 떨어집니다.
미리 많은 메모리 공간을 할당해야 하며, 해시 함수에 따라 공간 낭비가 심할 수 있습니다.

해시 테이블의 추상 자료형

set(Key, Value): 데이터 삽입
get(Key): 데이터 조회
remove(Key): 데이터 삭제

해시 테이블 구현 예제

class HashTable{
    constructor(){
        this.arr = [];
        for(let i = 0; i < 10; i ++){
            this.arr[i] = new DoublyLinkedList();
        }
    }

    hashFunction(number){ // 해시함수 설정
        return number % 10; // 나머지를 반환하여 인덱스로 활용
    }


    set(key, value){ // 해시테이블에 데이터 삽입
         // 해시 함수로 계산된 인덱스를 사용하여 해당 리스트에 데이터 삽입
        this.arr[this.hashFunction(key)].insertAt(0,new HashData(key,value));
    }

    get(key){ // 해시테이블의 키에 해당하는 데이터 조회
        let currentNode = this.arr[this.hashFunction(key)].head;
        while(currentNode != null){
            if(currentNode.data.key == key){ // 해당 노드의 키가 일치하면 값 반환
                return currentNode.data.value;
            }
            currentNode = currentNode.next; // 다음 노드로 이동
        }
        return null;
    }

    remove(key){ // 해시테이블의 키에 해당하는 데이터를 삭제
        let list = this.arr[this.hashFunction(key)];
        let currentNode = list.head;
        let deletedIndex = 0;
        while(currentNode != null){
            if(currentNode.data.key == key){ // 해당 키 삭제
                return list.deleteAt(deletedIndex);
            }
            currentNode = currentNode.next; // 다음 노드로 이동
            deletedIndex++;
        }
        return null; // 해당 키가 없으면 null 반환
    }

}

5일차

SJF와 RR MLFQ, 셋(set)

SJF(Shortest Job First)

SJF는 Burst Time이 짧은 프로세스가 먼저 실행되는 알고리즘입니다.
이론적으로 FIFO보다 성능이 좋지만 몇 가지 문제점이 있습니다.

문제점

Burst Time 예측 어려움 : 어떤 프로세스가 얼마나 실행될지 미리 예측하기 어렵습니다.
Starvation(기아 현상) : 긴 Burst Time을 가진 프로세스는 짧은 작업이 계속 들어오면 무한히 대기할 수 있습니다.

이러한 문제 때문에 SJF는 실질적으로 운영체제에서 잘 사용되지 않습니다.

RR(Round Robin)

RR은 시분할 방식(Time-sharing) 을 통해 FIFO의 단점을 보완한 알고리즘입니다.
프로세스는 타임 슬라이스(Time Slice) 또는 타임 퀀텀(Time Quantum) 이라는 일정 시간 동안만 CPU를 사용합니다.
타임 슬라이스가 지나면 강제로 CPU를 반납하고, 큐의 마지막으로 이동합니다.

예시

타임 슬라이스: 10초
프로세스1(P1): Burst Time 25초
프로세스2(P2): Burst Time 4초
프로세스3(P3): Burst Time 10초

실행 순서

P1: 10초 실행 → 큐 뒤로 이동
P2: 4초 실행 → 종료
P3: 10초 실행 → 종료
P1: 남은 15초 중 10초 실행 → 큐 뒤로 이동
P1: 남은 5초 실행 → 종료

대기 시간 계산

P1: (0 + 10 + 14 + 14 + 0) ÷ 3 = 12.67초
FIFO 방식일 경우 약 18초

RR 알고리즘은 타임 슬라이스 크기에 따라 성능이 크게 달라집니다.

타임 슬라이스 크기의 영향

너무 큰 경우 → FIFO 방식과 다를 바 없어짐.뮤직플레이어도 5초 실행하다 멈춰 굉장히 끊기게됨
만약 타임슬라이스가 5초인 시스템에서 웹브라우저와 뮤직플레이어를 실행시키면 웹브라우저가 5초 실행하다멈추고
너무 작은 경우 → 컨텍스트 스위칭이 자주 일어나 오버헤드 증가.

왜 컨텍스트 스위칭이 자주 일어나면 오버헤드가 증가할까?

컨텍스트 스위칭이 자주 일어나면 CPU가 실제 작업을 수행하는 시간을 줄이고 컨텍스트 스위칭 오버헤드가 커지기 때문에 시스템 효율성이 저하

결국 최적의 타임 슬라이스는 여러 프로세스가 동시에 실행되는 것처럼 보이면서 오버헤드가 크지 않은 값입니다.

MLFQ(Multi Level Feedback Queue)

MLFQ는 RR 알고리즘의 단점을 보완한 방식입니다.
CPU Bound Process(CPU 사용 위주)와 I/O Bound Process(입출력 위주)를 구분하여 각각 적절한 시간 배분을 수행합니다.

동작 방식

우선순위 큐 사용
- 높은 우선순위 큐: 짧은 타임 슬라이스 → 빠른 응답
- 낮은 우선순위 큐: 긴 타임 슬라이스 → 효율적 처리
큐 이동
- CPU를 오래 사용하는 프로세스 → 낮은 우선순위 큐로 이동 (Burst Time이 긴 프로세스)
- 짧은 시간만 CPU 사용 후 반납 → 높은 우선순위 큐 유지 (I/O 작업 많은 프로세스)
타임 슬라이스 조절
- 프로세스가 타임 슬라이스를 초과하여 강제로 CPU를 반납하면, 낮은 우선순위 큐로 이동
- 낮은 우선순위 큐로 이동할수록 타임 슬라이스 크기 증가
- 프로세스가 계속 CPU를 점유할 경우 점점 더 긴 타임 슬라이스가 할당됨

타임 슬라이스 크기에 따른 차이점(P1은 연산만하는 프로세스 P2는 1초 연산 후 10초동안 I/O작업)

타임 슬라이스가 100초일 경우(P2 먼저 실행의 경우)
- P2가 먼저 1초 실행 후 I/O 작업 대기
- P1이 100초 실행 중 10초 시점에서 P2의 I/O 완료 인터럽트 발생 → P2 다시 큐에 들어감
- 100초 경과 후 P2가 다시 1초 실행 후 I/O 작업 요청
- 반복
- CPU 사용률 100% / I/O 사용률 약 10%
타임 슬라이스가 1초일 경우(P2 먼저 실행의 경우)
- P2가 1초 실행 후 I/O 작업 대기
- P1이 1초 실행 → 큐가 비어 바로 재실행 반복
- P2가 10번 실행되면 I/O 완료 인터럽트 → P2 다시 큐에 들어간 후 1초 실행
- 반복
- CPU 사용률 100% / I/O 사용률 약 90%

결론: 타임 슬라이스가 작을수록 CPU와 I/O 사용률이 고르게 유지되며, 자원 낭비가 줄어듭니다.

해시 테이블(Hash Table)

해시 테이블은 해시 함수(Hash Function) 를 사용하여 데이터를 키(Key) 와 값(Value) 쌍으로 저장하는 자료구조입니다.

장점

빠른 검색, 삽입, 삭제가 가능합니다.

단점

공간 효율성이 떨어집니다.
미리 많은 메모리 공간을 할당해야 하며, 해시 함수에 따라 공간 낭비가 심할 수 있습니다.

해시 테이블의 추상 자료형

set(Key, Value): 데이터 삽입
get(Key): 데이터 조회
remove(Key): 데이터 삭제

셋(Set)

셋(Set) 은 데이터의 중복을 허용하지 않는 자료구조이고 유일한 값만을 추구함

add : 데이터 삽입
isContain(data): 데이터 체크
remove(data): 데이터 제거
clear() : 셋 비우기
isEmpty() : 셋이 비었는지 체크

printAll() : 모든 데이터 출력

셋 구현 예제

class HashSet{
    constructor(){
        this.hashTable = new HashTable();
    }


    add(data){ // 셋 데이터 삽입
        if(this.hashTable.get(data) == null){ // 만약 데이터가 존재하면 추가하지 않음
            this.hashTable.set(data, -1);
        }
    }

    isContain(data){ // 셋 데이터 체크
        return this.hashTable.get(data) != null;
    }

    remove(data){ // 셋 데이터 제거
        this.hashTable.remove(data);
    }

    clear(){ // 셋 비우기
        for(let i = 0; i < this.hashTable.arr.length; i++){
            this.hashTable.arr[i].clear();
        }
    }

    isEmpty(){ // 셋이 비어있는지 체크
        let empty = true;
        for(let i = 0; i < this.hashTable.arr.length; i++){
            if(this.hashTable.arr[i].count > 0){
                empty = false;
                break;
            }
        }

        return empty;

    }


    printAll(){ // 셋의 모든 데이터 출력
        for(let i = 0; i < this.hashTable.arr.length; i++){
            let currentNode = this.hashTable.arr[i].head;
            while(currentNode != null){
                console.log(currentNode.data.key);
                currentNode = currentNode.next;
            }
        }
    }


}

1 주차 회고

국비과정을 수료 후 기술면접을 준비하다 CS지식이 너무 부족하다 느껴 이번 인프런 워밍업 클럽을 신청하게 되었습니다.

매주 해당 요일마다 들어야할 강의를 로드맵으로 정해 듣고 매주 해당 주차 강의내용을 바탕으로 미션을 수행한다는 점에 평소 공부를 할때 강제성이 좀 필요했던 저로서는 이번 기회가 반가웠습니다.

처음 공부할때 강의 시간이 3분 5분 정도밖에 되지않아 금방 공부가 끝날줄 알았지만 하면 할수록 알아야 할 항목들이 많고 생소한 용어들이 많아 하나하나 찾아보고 정리하는 시간이 생각보다 만만찮았습니다.

이번주는 중간에 2틀정도 강의를 못듣게 됬었는데 나중에 몰아서 듣다보니 많은 양을 이해하려하니 힘들었습니다.

2주차 부터는 최대한 로드맵에 맞게 강의를 듣고 발자국 정리도 몰아서 정리가 아닌 해당 일차마다 바로바로 작성해서 정리할 예정입니다.

[인프런 워밍업 클럽 3기 CS전공지식] 1주차 발자국

1일차

운영체제 및 자료구조와 알고리즘

운영체제가 하는일

프로세스 관리

메모리 관리

하드웨어 관리

파일 시스템 관리

운영체제 구조

커널과 사용자 인터페이스

컴퓨터 하드웨어와 구조

CPU의 구조

메모리의 종류

컴퓨터의 부팅 과정

인터럽트(Interrupt)

자료구조와 알고리즘

자료구조

시간 복잡도

시간 복잡도를 평가하는 방법

Big-O 표기법의 특징

2일차

프로세스와 배열,연결리스트

프로그램과 프로세스 개념

프로그램이란?

프로세스란?

프로그램과 프로세스의 차이

프로세스의 구조

CPU가 프로세스를 실행하는 순서

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

유니프로그래밍과 멀티프로그래밍

멀티프로세싱

PCB란?

PCB 구성 요소

프로세스의 상태

배열,연결리스트

배열

연결 리스트 (Linked List)

사용 상황

연결리스트 구현 예제

3일차

컨텍스트 스위칭와 쓰레드, 큐 스택

컨텍스트 스위칭

컨텍스트 스위칭 과정

컨텍스트 스위칭 발생 이유

프로세스 생성 과정

부모-자식 프로세스 관계

좀비 프로세스

쓰레드(Thread)

쓰레드의 장점

쓰레드 사용 예시 (웹브라우저)

프로세스와 쓰레드의 장단점

안정성

속도 및 자원 효율성

스택(Stack)

연결리스트 기반 스택 동작 예시

사용 사례

스택의 주요 연산

스택 구현 예제

큐(Queue)

큐의 동작 방식

큐의 주요 연산

덱(Deque)

덱의 주요 연산

덱 구현 예제

4일차

CPU 스케줄링과 FIFO, 해시테이블

CPU 스케줄링

CPU 스케줄러가 고려해야 할 사항

다중 큐(Multi-Queue)

스케줄링 목표

FIFO(First In First Out)

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

해시 테이블(Hash Table)

해시 테이블의 추상 자료형

해시 테이블 구현 예제

5일차

SJF와 RR MLFQ, 셋(set)

SJF(Shortest Job First)

RR(Round Robin)

MLFQ(Multi Level Feedback Queue)