[인프런 워밍업 클럽 CS 2기] 2주차 발자국 - 자료구조/알고리즘

손준석 1개월 전

운영체제

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

     

    • 장점:

      • 알고리즘 구현이 간단하다.

    • 단점:

      • 프로세스의 Burst Time이 긴 프로세스가 먼저 대기 큐에 들어온다면, 평균 대기 시간이 길어지게 된다.

      • 프로세스의 도착 순서에 따라 성능의 편차가 크다.

     

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

    • Burst Time이 짧은 프로세스를 우선 실행하는 알고리즘이다. 하지만 운영체제 입장에서 각 프로세스의 실행 예상시간을 파악하기가 어렵다.

    • 또한 Burst Time이 긴 프로세스의 경우 CPU 스케줄링에 의하여 CPU 사용 우선수위가 계속 후순위로 밀려서 영원히 실행되지 않는 차별을 겪을 수 있다.

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

    • Robin Round는 CPU 스케줄링에 의하여 타임 슬라이스에 따라 인터럽트를 발생하여 각 프로세스 별로 일정시간 동안 CPU 사용권한을 준다. 이때 타임슬라이스가 매우 작으면 CPU에서 프로세스의 코드를 실행시키고 작업하는 것보다 컨텍스트 스위칭을 수행하는 비용이 커져서 overhead가 발생할 수 있다.

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

    • CPU 스케줄러는 우선순위 별로 여러 queue를 생성한다. 우선순위가 높은 queue의 타임슬라이스는 짧다.

    • CPU Bound Process의 경우 I/O Bound Process 보다 CPU 점유 시간이 길다. 이때 해당 프로세스가 현재 우선수위 큐의 타임슬라이스 시간까지 작업을 마치지 못하고 CPU 스케줄러에 의해 인터럽트가 발생한다면, 해당 프로세스는 우선순위가 낮은 queue에 포함이 되고 CPU Bound Process일 확률이 높아진다.

    • I/O Bounde Process는 CPU 사용 시간 보다 I/O 작업이 끝나길 기다리는 시간이 많기 때문에 대체적으로 CPU 점유 시간이 짧다.

      따라서 MLFQ에서는 다양한 우선순위 큐를 바탕으로 I/O Bound Process와 CPU Bound Process를 구분한다.

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

  • 공유자원은 한 프로세스 내의 스레드에서 공통으로 사용하는 자원 혹은 프로세스가 공통으로 접근가능하고 활용할 수 있는 자원을 의미한다.

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

  • 상호배제: 먼저 자원을 차지하면 다른 프로세스는 해당 자원을 사용하지 못한다.

  • 비선점: 다른 프로세스가 차지한 자원을 다른 프로세스에서 가져갈 수 없다.

  • 점유와 대기: 어떤 프로세스가 리소스 A를 가진 상태에서 다른 리소스 B를 기다리는 상태이다.

  • 원형 대기: 점유 대기를 하는 프로세스의 관계가 원형을 이룬다.

 

자료구조와 알고리즘

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

  • 스택 overflow 문제가 발생한다.

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

function sumOdd(n) {
    if (n <= 0) {
        return 0;
    }

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

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

 

회고

가장 인상 깊은 부분은 재귀함수를 설명하는 부분입니다. 재귀함수의 특징으로 하위 문제의 결과를 기반으로 상위 문제를 해결 이라는 설명이 가장 와 닿았고 이후 재귀를 이해하고 활용하는 것에 큰 도움이 되었습니다!

댓글을 작성해보세요.

채널톡 아이콘