week 2. 자료구조와 알고리즘, 운영체제

작성일: 2025-03-15

1. 강의 진도표

CS (3/10~3/14)

Day 6 프로세스 동기화

• 알고리즘 Section 3 (1)
• 운영체제 Section 4

Day 7 데드락

• 알고리즘 Section 3 (2)
• 운영체제 Section 5

Day 8 데드락

• 알고리즘 Section 3 (3)
• 운영체제 Section 6

Day 9 메모리

• 알고리즘 Section 3 (4~5)
• 운영체제 Section 7

Day 10 중간 점검

• 온라인 세션

---

2. 운영체제 week 2

1. 프로세스 동기화

프로세스 간 통신 방법

1. 프로세스는 파일과 운영체제가 생성한 파이프를 이용해 컴퓨터 내부에서 실행되는 다른 프로세스와 통신 가능합니다.

2. 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와 통신 가능합니다.(소켓통신, RPC)

3. 한 프로세스 내부에서 쓰레드의 전역변수와 힙을 이용해 통신할 수 있습니다.

공유자원과 임계구역

• 공유자원 : 프로세스 통신시 공동으로 이용하는 변수 또는 파일을 뜻합니다. 프로세스의 접근 순서에 따라 결과값이 달라질 수 있습니다.

• 임계구역 : 프로세스 동시 사용시 동기화 문제가 일어날 수 있는데 이를 방지하기 위해 상호배제 메커니즘을 사용해 둘 이상의 프로세스가 접근하지 못하게 막는 기법입니다.

세마포어

상호배제 메커니즘의 한 가지로, 공유자원 사용시 운영체제가 프로세스를 대기시켜 하나의 프로세스만 사용할 수 있게 만드는 기법입니다.

모니터

운영체제가 아닌 프로그래밍 언어로 프로세스를 제어하는 방식으로 함수를 호출해 상호배제를 실현시킵니다.

---

2. 데드락

여러 프로세스가 공유자원 사용시, 하나의 프로세스의 작업이 끝나길 기다리는 도중 어떤 프로세스도 작업하지 못하는 교착상태 현상을 일컫습니다.

해결방안

• 교착상태 회피 : 운영체제에서 각 프로세스가 현재 요구할 수 있는 예상 자원을 도출하고 시스템 총 자원량에서 할당하는 방식입니다.

• 교착상태 해결 : 자원할당 그래프를 사용해 프로세스에서 교착상태 발생시, 프로세스를 강제종료 시키고 체크포인트로 롤백시키는 방식입니다.

---

3. 메모리

메모리 종류

• 레지스터 : CPU 내부에 있는 고속 저장 장치로 연산을 처리할 때 사용되며, 매우 빠르고 적은 용량을 수용합니다.

• 캐시 : CPU와 메모리 사이에 위치하여, 자주 사용되는 데이터를 임시로 저장하여 CPU가 빠르게 접근할 수 있도록 도와줍니다.

• 메인메모리 : 실제 운영체제와 다른 프로세스들이 올라가는 공간으로, 실행중인 프로그램만 올립니다.

• HDD,SSD : 전원이 공급되지 않아도 데이터가 지워지지 않는 비휘발성 메모리입니다. 속도가 느린 대신 많은 용량을 수용할 수 있습니다.

메모리와 주소

멀티 프로그밍 환경에서 여러 프로세스가 할당된 메모리를 관리하기 위해 주소를 지정해 관리합니다.

• 물리 주소 공간(절대 주소) : 메모리를 컴퓨터에 연결하면 0x0 번지부터 시작하는 공간입니다. 실제 프로세스가 할당된 주소를 뜻합니다.

• 논리 주소 공간(상대 주소) : 사용자 관점에서 바라본 주소 공간으로 CPU에게 명령시 사용하는 주소의 이름입니다.

메모리 할당방식

• 가변 분할 방식 : 연속 메모리 할당이라고도 불리며, 프로세스의 크기에 따라 메모리를 나누는 방식입니다. 남는 메모리 공간 없이 사용 가능합니다. 공간 할당시 크기가 맞지 않는 메모리를 사용할 수 없어 많은 공간의 메모리가 낭비될 수 있습니다.

• 고정 분할 방식 : 비연속 메모리 할당이라고도 불리며, 프로세스의 크기와 상관없이 메모리를 정해진 크기로 나누는 방식입니다. 구현이 간단하고 오버헤드가 적어지지만, 남는 메모리 공간이 생길 수 있습니다.

• 버디 시스템 : 두 분할 방식을 혼합한 것으로 총 메모리를 2의 승수로 메모리를 분할해 할당하는 방식으로 가변 분할 방식을 사용하면서도 낭비하는 공간이 적어집니다.

---

3. 운영체제 과제 week 2

FIFO 스케줄링의 장단점이 뭔가요?

단순하고 직관적이지만 먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스가 실행되기 때문에 작업 순서에 따라 대기 시간이 달라집니다.

SJF를 사용하기 여러운 이유가 뭔가요?

짧은 작업을 먼저 실행시키기 위한 방법이지만 프로세스 종료 시간은 예측하기 어렵고 처리시간이 긴 프로세스는 짧은 프로세스가 모두 실행될 때까지 기다려야 하기 때문입니다.

RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?

프로세스에 작업 시간을 할당해 시간을 초과하면 강제로 다른 프로세스가 작업하도록 하는 방식으로(컨텍스트 스위칭), 너무 작게 할당하면 컨텍스트 스위칭 처리량이 많아져 오버헤드가 커지게 됩니다.

운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?

최적의 타입슬라이스를 설정해 실행시키는 방식으로, 작업 시간 할당량을 초과해 CPU 스케쥴러에게 강제로 뺏기는 조건으로 구분합니다. CPU 사용량이 많으면 CPU Bound Process 입니다.

공유자원이란무엇인가요?

프로세스 통신시 공동으로 이용하는 변수 또는 파일을 뜻합니다. 프로세스의 접근 순서에 따라 결과값이 달라질 수 있습니다.

교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요?

여러 프로세스가 하나의 공유자원을 사용해야하는 상황이 발생하야 합니다. 상호 배제, 점유와 대기, 비선점, 순환 대기의 조건을 만족하면 데드락이 발생할 수 있습니다.

---

4. 알고리즘 week 2

1. 재귀

function factorial(number) {
    if(number == 1 || number == 0){
        return 1;
    } else{
        return number * factorial(number - 1);
    }
}

어떠한 것을 정의할 때 자기 자신을 참조합니다. 특정 상황에서 종료하는 탈출 조건이 필요합니다.

---

2. 재귀 - 히노이 탑

특정 조건에 맞지 않으면 다른 함수를 호출하는 형태로 스택에 순서대로 쌓인 순서대로 프로세스를 실행할 수 있는 예제입니다.

3. 정렬 - 버블 정렬(시간 복잡도: O(n²))

배열에서 인접한 두 원소를 비교하여 크기가 잘못된 순서라면 교환하고, 이러한 과정을 배열의 끝까지 반복하면서 점차적으로 큰 값(또는 작은 값)을 끝으로 밀어내는 방식입니다.

4. 정렬 - 선택 정렬(시간 복잡도: O(n²))

배열에서 가장 작은(또는 큰) 원소를 찾아서 배열의 맨 앞에 위치시키는 방식으로 정렬을 진행하는 알고리즘입니다.

---

4. 알고리즘 과제 week 2

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?

함수가 종료되지 않고 무한히 자기 자신을 호출하거나, 콜스텍이라는 메모리 공간이 가득차서 자동으로 종료(스택 오버플로우)될때까지 실행됩니다.

0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.

function sumOdd(n) {
    if (n < 1) {
        return 0;
    }
    if (n % 2 !== 0) {
        return n + sumOdd(n - 2); 
    } else {
        return sumOdd(n - 1); 
    }
}

console.log(sumOdd(10)) // 25

다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.

const fs = require("fs"); // 파일을 이용하는 모듈
const path = require("path"); // 폴더와 파일의 경로를 지정해주는 모듈

function traverseDirectory1(directory){
    const stack = [directory]; // 순회해야 할 디렉토리를 저장할 스택
  
    while (stack.length > 0) { // 스택이 빌 때까지 반복
        const currentDir = stack.pop(); // 현재 디렉토리
        const files = fs.readdirSync(currentDir); // 인자로 주어진 경로의 디렉토리에 있는 파일or디렉토리들
    
        for (const file of files) { // 현재 디렉토리의 모든 파일or디렉토리 순회
            const filePath = path.join(currentDir, file); //directory와 file을 하나의 경로로 합쳐줌
            const fileStatus= fs.statSync(filePath); // 파일정보 얻기
      
            if (fileStatus.isDirectory()) { // 해당 파일이 디렉토리라면
                console.log('디렉토리:', filePath);
                stack.push(filePath);
            } else { // 해당 파일이 파일이라면
                console.log('파일:', filePath);
            }
        }
    }
}

traverseDirectory1("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

function traverseDirectory1(directory) {
    const files = fs.readdirSync(directory);


    // for (const file of files) { 
    //     const filePath = path.join(currentDir, file); 
    //     const fileStatus= fs.statSync(filePath); 
    //
    //     if (fileStatus.isDirectory()) { 
    //         console.log('디렉토리:', filePath);
    //         stack.push(filePath);
    //     } else { 
    //         console.log('파일:', filePath);
    //     }
        
    for (const file of files) { 
        const filePath = path.join(directory, file);
        const fileStatus = fs.statSync(filePath); 

        if (fileStatus.isDirectory()) { 
            console.log('디렉토리:', filePath);
            traverseDirectory(filePath);
        } else { 
            console.log('파일:', filePath);
        }
    }
}

---

5. 중간 점검

• 자주 사용되는 패턴과 프로그램에서 사용하는 알고리즘을 예를 들어 이해를 돕는 형식의 내용이고, 이후 Q&A를 통해 다른 참가자들이 궁금해하는 내용을 답변해주셨습니다.

---

후기

펼치기

Liked : 좋았던 점은 무엇인가?

• 이해하기 쉬운 강의
  • 비전공자도 쉽게 이해할 수 있는 방식으로 강의를 진행해 속성으로 배우기 편한 강의입니다.

Lacked : 아쉬웠던 점, 부족한 점은 무엇인가?

• 단편적으로 알고 있음
  • 컴퓨터 지식을 알고 있다고 해도 여전히 템플릿을 사용해 프로덕트를 제작하는 것이 편하기 때문에 동작 원리만 이해하고 있습니다.

Learned : 배운 점은 무엇인가? (깨달은것, 인사이트, 기억하고 싶은 것 등)

• 문제에 운영체제 지식 적용
  • 평소 문제를 해결할 때 동작하는 기능을 만들기 위해 코드를 작성했는데, 이 코드가 어떤 방식으로 실행되며, 왜 그렇게 만들어야 했는지 깨닫게 되었다.

Longed for : 앞으로 바라는 것은 무엇인가? (앞으로 어떤 행동을 할것인지)

• 자주 복습하기
  • 스택과 메모리는 프로덕트를 생산하는 과정에서 매우 중요하게 작용하기 때문에 잊지 않기 위해 시간이 날 때마다 복습이 필요합니다.