[CS 스터디] 2주차 발자국

강의

https://www.inflearn.com/course/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EB%B3%B8

https://www.inflearn.com/course/%EB%B9%84%EC%A0%84%EA%B3%B5%EC%9E%90-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C

미션

운영체제

FIFO 스케줄링의 장단점이 뭔가요? 장점: 단순함, 단점: burst time에 따라 성능이 좌우됨. 운빨..
SJF를 사용하기 여러운 이유가 뭔가요? 종료시간을 예측하기 힘듬. 그리고 시간이 긴애들은 계속해서 기다려야 함
RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요? 컨텍스트 스위칭이 자주 발생해서 오버헤드 가능성이 생김
운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요? 우선순위 큐를 여러개 두어 구분함
공유자원이란무엇인가요? 프로세스 동기화 시 여러 프로세스가 같이 사용하는 자원
교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요

상호배제 ,
비선점 ,
점유와 대기 ,
원형 대기

자료구조와 알고리즘

재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요? 콜스택 무한 적재.. OOM!

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

public class OddSum {
    public static void main(String[] args) {
        int n = 10; // 예시로 n을 10으로 설정
        int sum = sumOddNumbers(n);
    }

    public static int sumOddNumbers(int n) {
        // n이 0보다 작으면 종료
        if (n < 1) {
            return 0;
        }
        // n이 홀수일 경우 n을 더하고, 짝수일 경우 n-1을 더함
        if (n % 2 == 1) {
            return n + sumOddNumbers(n - 2);
        } else {
            return sumOddNumbers(n - 1);
        }
    }
}

자료구조

재귀

탈출(종료) 조건이 꼭 있어야 함

콜스택? 함수가 호출되면서 올라가는 메모리 영역 (==스택)

먼저 들어온 데이터가 먼저 나간다.. FILO

다음 함수를 종료조건에 맞지 않으면 계속 콜스택을 쌓아감

for문으로 쓸 만한걸 재귀를 쓰면 메모리 손해가 생김, 오히려 성능이 안좋을때가 많음

근데 왜 쓰냐? 팩토리얼 같은 문제

단순한 반복실행 (성능? 은 별로)
하위문제의 결과를 기반으로 상위문제를 해결 (ex 팩토리얼)
1. for문: 상향식
2. 재귀: 하향식

하노이의 탑 : 재귀적 사고..!!

버블정렬

쉽지만 그닥 성능은 별로..

앞과 옆 숫자를 비교해서 자리를 바꿈

4, 2, 3, 1

2, 4, 3, 1

2, 3, 4, 1

2, 3, 1, 4 (다음은 마지막 원소 빼고, 이미 정렬되었기 때문)

2, 3, 1, 4

2, 1, 3, 4 (3, 4 빼고)

1, 2, 3, 4

성능: O(n^2)

선택정렬

4, 2, 1, 3 (가장 작은 값 체크하고==1 이를 1번 자리에 4와 교환)

1, 2, 4, 3 (가장 작은 값 2, 이를 교환하지 않아도 됨)

1, 2, 3, 4

성능: O(n^2)

운영체제

cpu 스케줄링 방법 이어서...

SJF

Shortest Job First

큐의 특성상 Burst time이 짧은게 먼저 실행되기 때문에 먼저 보내면 평균 대기시간이 짧아짐 -> 짧은거 먼저?!

이론상 fifo보다 성능은 좋음

근데 프로세스 종료 시간을 예측하기 힘듦... 또 긴 애들은 먼저 와도 계속 밀릴 것.. ㅠㅠ

RR

Round Robin

fifo는 앞이 다 끝나야 다음게 실행 됨 -> 하나의 프로세스를 시간을 주고 그 시간동안만 실행하게 함 -> 시간이 끝나면 프로세스 안끝나도 다른 애한테 줌 -> 원래 프로세스는 큐 맨뒤로...

왔다 갔다.. 라운드 로빈!!

즉 타임 슬라이스

근데 타임 슬라이스가 큰 경우에는 계속 끊기지 않을까? -> 아주 작게 설정하면 동시에 실행하는 것같겠지만 컨텍스트 스위칭이 너무 자주 발생함 -> 오버헤드?

MLFQ

Multi Level Feedback Queue

제일 많이 쓰임 .. RR의 상위호환

프로세스마다 중요하게 생각하는 애들이 다름

IO실행시 인터럽트 발생 -> 짧게 넘김 -> 다음 프로세스 ...

손해보는 프로세스가 생김

우선순위 큐 여러개 만들어 둠.. 우선순이 낮을 수록 타임 슬라이스 높아지게!

프로세스 동기화

통신 종류

파일- 파이프 : 하나의 파일
쓰레드 : 한 프로세스 내에서 힙 이용
네트워크: 소켓통신, RPC 등

공유자원, 임계구역

공유 자원 동기화 문제 발생

-> 여러 프로세스가 동시에 사용하면 안되는 영역:: 임계구역

상호 배제 매커니즘 필요

세마포어

상호 배제 매커니즘 종류 중 하나