day15 🌕

장미·2022년 6월 28일
0

오늘의 성과

목록 보기
15/129
post-thumbnail

정보처리기사 공부 (~2과목 2장까지 공부, 기출문제 1회 풀어보기)

알고리즘 - 정렬 진짜 끝내기...

운영체제 4챕터 마저 보기...

+) 22. 06. 30. 추가 완!!

스케줄링의 개요

CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.

스케줄링의 단계

  • 고수준 스케줄링(high level scheduling)
    • 가장 큰 틀에서 이루어지는 CPU 스케줄링.
    • 고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다.
    • 고수준 스케줄링에서는 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다.
    • 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총개수가 정해진다.
  • 저수준 스케줄링(low level scheduling)
    • 가장 작은 단위의 스케줄링.
    • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.
  • 중간 수준 스케줄링(middle level scheduling)
    • 고수준과 저수준 사이에서 일어나는 스케줄링.
    • 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다. (보류 상태로 보낸다.)

스케줄링의 목적

  • 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 한다.
  • 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
  • 안정성: 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
  • 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
  • 반응 시간 보장: 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
  • 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.

선점형 스케줄링(preemptive scheduling): 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식.

  • 대표적인 예: 인터럽트
  • 장점: 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
  • 단점: context switching 같은 부가적인 작업으로 인해 낭비가 생긴다.

비선점형 스케줄링(non-preemptive scheduling): 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식.

  • 장점: CPU 스케줄러의 작업량이 적고 context switching의 오버헤드가 적다.
  • 단점: CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다.

  • CPU 집중 프로세스(CPU bound process): CPU를 많이 사용하는 프로세스. 즉, CPU 버스트가 많은 프로세스다.

  • 입출력 집중 프로세스(I/O bound process): 입출력을 많이 사용하는 프로세스. 즉, 입출력 버스트가 많은 프로세스다.

위의 두 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다.
→ 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있다.

입출력 집중 프로세스가 CPU 집중 프로세스보다 먼저 실행 상태에 들어가는 경우를 사이클 훔치기(cycle stealing)라고 한다.

  • 전면 프로세스: 화면의 맨 앞에 놓인 프로세스. 현재 입력과 출력을 사용하는 프로세스다.

  • 후면 프로세스: 사용자와 상호작용이 없는 프로세스. (예: 압축 프로그램)

CPU 스케줄링 시 고려 사항

우선순위 높음우선순위 낮음
커널 프로세스일반 프로세스
전면 프로세스후면 프로세스
대화형 프로세스일괄 처리 프로세스
입출력 집중 프로세스CPU 집중 프로세스

다중 큐

프로세스의 우선순위를 배정하는 방식에는 고정 우선순위(static priority) 방식과 변동 우선순위(dynamic priority) 방식이 있다.

  • 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는다.
    → 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다.
  • 변동 우선순위 방식: 프로세스 생성 시 받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.
    → 구현하기 어렵지만 시스템의 효율성을 높일 수 있다.

준비 상태의 다중 큐와 대기 상태의 다중 큐는 차이가 있다.
준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 PCB를 동시에 꺼내 준비 상태로 옮긴다.
동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터(interrupt vector)라는 자료 구조를 사용한다.

스케줄링 알고리즘

구분종류
비선점형 알고리즘FCFS, SJF, HRN
선점형 알고리즘라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐
둘 다 가능우선순위 스케줄링

스케줄링 알고리즘의 선택 기준

  • CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법.

  • 처리량: 단위 시간당 작업을 마친 프로세스의 수. 이 수치가 클수록 좋다.

  • 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간. 이 시간이 짧을수록 좋다.

  • 응답 시간: 프로세스 시작 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간. 짧을수록 좋다.

  • 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간. (= 대기시간 + 실행 시간)

→ 사용률과 처리량은 계산하기 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.

1. FCFS(First Come First Served) 스케줄링

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식.
초기의 일괄 작업 시스템에서 사용되었다.
처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어진다. 이를 콘보이 효과(convoy effect)라고 한다.
또 다른 단점은, 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.

2. SJF(Shortest Job First) 스케줄링

준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식.
작은 작업을 먼저 실행하기 때문에 시스템의 효율성이 좋아진다. 하지만 다음과 같은 이유로 사용하기가 힘들다.

  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.

  • 공평하지 못하다. 만약 작은 작업이 계속 들어온다면 먼저 들어왔던 큰 작업은 계속 연기되어 아사(starvation) 현상에 빠질 것이다.

이 때문에 SJF 스케줄링은 잘 사용하지 않는다.

3. HRN(Highest Response Ratio Next) 스케줄링

SJF에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘.

  • 우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

우선순위를 정할 때 대기 시간을 고려함으로써, 스케줄링 방식에 에이징을 구현한 셈이다.
그러나 여전히 공평성이 위배되어 많이 사용되지 않는다.

4. Round Robin 스케줄링

한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가, 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.
선점형 알고리즘 중 가장 단순하고 대표적이다.

RR이 효과적으로 작동하려면 context switching에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 한다.

  • 타임 슬라이스가 큰 경우
    타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다. 이 경우 FCFS와 다를 게 없다.
  • 타임 슬라이스가 작은 경우
    타임 슬라이스를 너무 작게 설정하면 시스템의 전반적인 성능이 떨어진다.
    context switching이 너무 자주 일어나 많은 시간을 낭비하기 때문이다.

→ 결론적으로 타임 슬라이스는 작게 설정하되 context switching에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

5. SRT(Shortest Remaining Time) 스케줄링

SJF와 RR을 혼합한 방식. SJF의 선점형 버전이라고 할 수 있다.
CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택한다.
SJF와 마찬가지로 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

6. 우선순위 스케줄링

우선순위를 반영한 스케줄링 알고리즘.
비선점형 방식과 선점형 방식 모두 적용할 수 있다.

  • 고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정된다.
    → 효율성이 떨어진다.

  • 변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변한다.
    → 효율적인 운영이 가능하다.

공평성을 위배하고 아사 현상을 일으킨다는 것이 문제이다.
또한 준비 큐에 있는 프로세스의 순서를 무시하고 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨린다.
하지만 프로세스의 우선순위는 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정된다. (커널 프로세스가 일반 프로세스보다 중요한 것처럼)

7. 다단계 큐(multilevel queue) 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용하는 방식.
우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있고, 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수도 있다.

8. 다단계 피드백 큐(multilevel feedback queue) 스케줄링

우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다.
다단계 피드백 큐 스케줄링의 경우 CPU를 사용하고 난 프로세스의 우선순위가 낮아진다.
CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다. 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 얻는다.
오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 예다.

계산기 🛠🛠 이거 진짜 오늘 커밋 올리기

일단 올렸다!! 근데 네이밍이랑 리드미 부분은... 어떻게 해야 할지 잘 모르겠어서 좀 난감하다. 올리긴 올렸는디... 올리면서도 이게 맞나 싶네.

⬇️ 아래는 수정한 버전.

public class Main {
    public static void main(String[] args) {

        Input input = new Input();
        Split split = new Split();

        String[] str = input.inputDataSplit();
        split.split(str);

        List<String> operators = split.getOperators();
        List<Integer> numbers = split.getNumbers();

        int sum = Calculator.calculate(numbers, operators);

        Output output = new Output();
        output.output(sum);

    }
}

➡️ 메인이 좀 더러운 것 같은데... 이거 어떻게 못 고치나?

public class Input {

    public static String input() {
        System.out.print("입력값: ");
        return new Scanner(System.in).nextLine();
    }

    public String[] inputDataSplit() {
        String[] data_arr = input().split(" ");
        return data_arr;
    }

}

➡️ 값을 입력 받고 공백 기준으로 분리하여 배열에 넣는다.

public class Split {

    private List<String> operators;
    private List<Integer> numbers;

    public void split(String[] str_arr) {

        operators = new ArrayList<>();
        numbers = new ArrayList<>();

        for(int i = 0; i < str_arr.length; i++) {
            if (i % 2 == 0) {
                validateNumber(str_arr[i]);
            }
            else {
                validateOperator(str_arr[i]);
            }
        }

    }

    public void validateNumber(String str) {
        if(!(str.matches("^[0-9]*$"))) {
            throw new RuntimeException("숫자가 아닙니다.");
        }
        numbers.add(Integer.parseInt(str));
    }

    public void validateOperator(String str) {
        if(!(str.matches("[-+*/]"))) {
            throw new RuntimeException("부호가 아닙니다.");
        }
        operators.add(str);
    }

    public List<String> getOperators(){
        return operators;
    }

    public List<Integer> getNumbers(){
        return numbers;
    }

}

➡️ 배열에 저장된 값을 숫자와 연산자로 분리해 리스트에 넣는다.
이 때, 홀수 번째 값과 짝수 번째 값으로 구분하여 유효성 검사(숫자가 맞는지, 부호가 맞는지)를 진행한 뒤 리스트에 넣는다.

public class Operation {
    public static int Operate(int sum, int num, String operator) {

            switch (operator) {
                case "+": return sum + num;
                case "-": return sum - num;
                case "*": return sum * num;
                case "/": return sum / num;
                default: throw new RuntimeException("잘못되었습니다.");
            }

    }
}

➡️ 입력 받은 연산자에 맞게 계산하는 클래스.

public class Calculator {

    public static int calculate(List<Integer> numbers, List<String> operators) {
        int sum = numbers.get(0);

        for(int i = 0; i < operators.size(); i++) {
            sum = Operation.Operate(sum, numbers.get(i+1), operators.get(i));
        }

        return sum;
    }

}

➡️ 직접적인 연산을 수행하는 클래스.
근데 이게 맞나 모르겠다. 뭔가 Operation이랑 겹치지 않나?! 싶은...

public class Output {

    public void output(int sum) {
        System.out.println("결과값: " + sum);
    }

}

➡️ 결과값을 출력하는 클래스.

코테 1문제 풀어보기

[스프링 핵심 원리 - 기본편] 섹션 1 수강

섹션 1. 객체 지향 설계와 스프링 수강 완료!!
오늘 시간 좀 남으면 섹션 2도 들어봐야지... 섹션 1은 객체 지향 관련한 OT 느낌이었다.

여태껏 정리했던 토픽 복습!!

profile
장미
김뉴비
이전 포스트

day14 🌕

다음 포스트

day16 🌕

0개의 댓글

관련 채용 정보