스미스요원

알고리즘 성능 비교 기준

• CPU 사용률

• 처리량 (단위 시간당 완료된 프로세스의 개수)

• 총 처리 시간 (준비 큐에서 대기한 시간 + CPU에서 실행하는 시간 + I/O 시간)

• 대기 시간 (준비 큐에서 대기하는 시간)

• 응답 시간 (요구를 제출한 후 첫번째 응답이 나올 때 까지 걸린 시간)

FCFS (First Come First Served)

• 선입 선처리 스케줄링 (First Come, First Served Scheduling)

    ◦  CPU를 먼저 요청한 프로세스가 먼저 할당받는다.

    ◦  선입선출(FIFO) 큐를 이용해 구현할 수 있다.

• 장점

    ◦  가장 간단한 알고리즘으로 구현하기 쉽고 이해하기도 쉽다.

    ◦  기아현상이 발생하지 않는다.

    ◦  프로세서가 지속적으로 프로세스를 처리하므로 처리율 자체는 높다.

• 단점

    ◦  대기시간이 최소가 됨을 보장하지 못한다. (호위 효과(convoy effect))

         -  예) 실행 시간이 짧은 프로세스부터 처리할 때 보다 대기 시간이 현저히 길어질 수 있다.

    ◦  비선점 방식이므로 대화식 프로세스에는 부적합하다.

SJF (Shortest Job First)

• 최단 작업 우선 스케줄링 (Shortest Job First Scheduling)

    ◦  실행 시간이 짧은 프로세스부터 CPU를 할당받는다

• 장점

    ◦  평균 대기 시간이 최소가 되는 알고리즘이다.

• 단점

    ◦  프로세스를 실행해보기 전에는 얼마의 시간이 소요되는지 알 수 없기 때문에(예측 불가능한 I/O 대기시간까지 실행시간에

         포함되므로) 이론적으로만 구현 가능한 알고리즘이다.

• 프로세스 실행 시간을 예측하는 방법

    ◦  다음 프로세스 실행 시간을 이전의 프로세스 실행 시간들의 지수평균으로 예측하곤 한다.

    ◦  양 변에 T’n+1 과 T’n 이 있는 재귀식임을 알 수 있다.

         -  t’n = n번째 프로세스의 길이

         -  T’n+1 = 다음 프로세스의 길이

SRF (Shortest Remaining Time First)

• 최소 잔여 시간 우선 스케줄링 (Shortest Remaining Time First Scheduling)

    ◦  프로세스가 실행되고 있는 도중에 새로운 프로세스가 Ready Queue 에 도착할 수 있다.

    ◦  이 때 새로운 프로세스의 실행 시간이 실행중인 프로세스의 잔여 시간보다 짧다면 현재 프로세스를 중단하고

         더 짧은 프로세스를 실행시킨다.

    ◦  도중에 중단된 프로세스는 잔여 시간만큼의 길이로 다시 Ready Queue 에 들어간다.

    ◦  프로세스가 Ready Queue 에 도착한 시기와 각 프로세스의 길이 정보를 고려해야 한다.

• 장점

    ◦  SJF 보다 더 짧은 평균 대기 시간을 갖는다.

• 단점

    ◦  SJF와 동일한 이유로 실 상황에서 구현이 불가능하다.

Round Robin

• 라운드 로빈 스케줄링 (Round Robin Scheduling)

    ◦  프로세스가 도착한 순서대로 실행하되, 정해진 실행 시간 제한을 프로세스에 둔다.

         -  시간 할당량 또는 타임 슬라이스 라고 부른다.

         -  CPU 스케줄러는 할당량이 끝나면 인터럽트를 걸도록 타이머를 설정한다.

    ◦  할당된 시간보다 먼저 완료되는 경우 프로세스가 CPU를 자발적으로 반납한다.

    ◦  할당된 시간 안에 완료되지 못한 프로세스는 Ready Queue 의 맨 마지막에 배치된다.

• 장점

    ◦  특정 프로세스가 CPU 를 독점하지 않고 공평하게 이용할 수 있다.

• 단점

    ◦  대기시간이 최소가 됨을 보장하지 못한다.

    ◦  시간 할당량이 너무 크면 FCFS 알고리즘과 다를게 없어진다.

    ◦  시간 할당량이 너무 작으면 문맥 교환 빈도수가 늘어나고, 그만큼 오버헤드가 누적된다.

         -  적절한 시간 할당량을 잘 정하는 것이 중요하다.

         -  일반적으로 한 프로세스 집합의 80% 정도가 시간 할당량보다 짧거나 같으면 좋다.

Priority Scheduling

• 우선순위 스케줄링 (Priority Scheduling)

    ◦  정해진 우선순위에 따라, 가장 높은 우선순위의 프로세스부터 CPU를 할당한다.

    ◦  우선순위는 다양한 내/외부적 기준에 따라 세워질 수 있다.

         -  시간 제한 / 메모리 요구 / 열린 파일의 수 / I.O 대기시간과 실행 시간의 비율 / 프로세스의 중요성 등

    ◦  새로 도착한 프로세스의 우선순위가 현재 실행중인 프로세스 보다 높은 경우

         -  선점형 : 새로 도착한 프로세스가 CPU를 할당받고, 실행되던 프로세스는 준비 큐로 들어간다.

         -  비선점형 : 선점 없이 Ready Queue 의 맨 앞쪽에 배치된다.

• 장점

    ◦  각 프로세스의 중요성에 따라 작업을 수행하므로 합리적이다.

    ◦  실시간 시스템에서 사용 가능하다.

• 단점

    ◦  기아 상태(Starvation)(무한 봉쇄) 문제

         -  낮은 우선순위의 프로세스가 영원히 실행되지 못하는 문제가 발생할 수 있다.

    ◦  노화(Aging) 기법으로 해결하기

         -  Ready Queue 에서 대기하고 있는 프로세스들의 우선순위를 점차 증가시키는 방법

         -  예) 주기적으로 1초마다 대기중인 프로세스의 우선순위를 1씩 증가시킨다.

MLQ (Multilevel Queue)

• 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

    ◦  우선순위마다 별도의 큐를 가지는 구조

    ◦  각 큐마다 서로 다른 스케줄링 알고리즘이 사용될 수 있다.

    ◦  프로세스가 큐에 한번 할당되면 다른 큐로 이동하지 않는다.

• 장점

    ◦  단일 큐로 프로세스를 관리할 때 드는 O(n) 검색 시간을 단축할 수 있다.

• 단점

    ◦  큐 내부의 프로세스 뿐만 아니라 큐와 큐 사이에서도 스케줄링 필요하다.

         -  고정 우선순위의 선점형 방식으로 스케줄링 될 수 있다.

         -  각 큐마다 CPU 선점 가능 시간을 정해두는 방식으로 스케줄링 될 수 있다. (기아현상 예방)

MFQ (Multilevel Feedback Queue)

• 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

    ◦  프로세스가 다른 큐로 이동하는 것을 허용한다.

• 장점

    ◦  융통성있는 프로세스 관리가 가능하다.

         -  프로세스가 CPU 시간을 너무 많이 쓰면 낮은 우선순위 큐로 이동시킨다. (시간 할당량)

         -  낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동시킨다.

    ◦  Aging 기법을 통해 기아현상을 예방할 수 있다.

• 단점

    ◦  프로세스가 큐를 이동하는 과정에서 오버헤드가 발생할 수 있다.

    ◦  결정해야할 요소가 많아 복잡한 판단이 요구된다.

         -  큐의 개수

         -  각 큐에 적용할 스케줄링 알고리즘

         -  특정 프로세스를 높은 우선순위 큐로 올려줄 시기

         -  특정 프로세스를 낮은 우선순위 큐로 내려줄 시기

         -  새로운 프로세스가 들어갈 큐를 선택하는 방법

참고자료

CPU 스케줄러

• 어떤 프로세스에 CPU 자원을 할당할지 결정하는 운영체제 커널의 모듈

• 프로세스를 선택할 때에는 응답시간/처리량/효율성 등을 증대시킬 수 있는 방법을 고려해야 한다.

    ◦  응답시간 : 첫 응답이 나올 때 까지 걸리는 시간

    ◦  처리량 : 단위 시간 내에 완료시켜준 프로세스가 몇 개인지

    ◦  효율성 : 문맥교환이 적절히 일어나는지

장기 스케줄링

• 어떤 프로세스를 Ready Queue 에 삽입할지 결정하는 작업

    ◦  작업 스케줄링이라 부르기도 한다.

    ◦  디스크에서 어떤 프로그램을 가져와 커널(Ready Queue)에 등록할지 결정하는 작업

       -  디스크에서 가져온 프로그램을 커널에 등록하면 프로세스가 된다.

    ◦  새로운 프로세스 생성 단계 (new)

• 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 작업도 포함

• 호출 빈도수가 적기 때문에 상대적으로 속도가 느린 것이 허용된다.

• 요즘 운영체제에서는 잘 사용하지 않는다.

    ◦  과거에는 메모리 크기가 작아 너무 많은 프로세스가 커널에 올라오면 프로세스당 할당해줄 수 있는 메모리가 적어졌기 때문에,

         이를 해결하기 위해 장기 스케줄링이 사용되었다.

    ◦  요즘은 하드웨어가 발달해 메모리를 신경 쓸 필요가 없어졌다. 프로세스가 시작되면 장기 스케줄링을 거치지 않고 바로 메모리를

         할당받은 다음 Ready Queue 에 들어간다.

단기 스케줄링

• Ready Queue 에 있는 프로세스 중 무엇을 다음 번에 실행 상태로 만들 것인지 결정하는 작업

    ◦  CPU 스케줄링이라 부르기도 하며, 일반적으로 스케줄러라 함은 단기 스케줄러를 의미한다.

    ◦  미리 정해둔 스케줄링 알고리즘에 따라 CPU를 할당할 프로세스를 선택한다.

    ◦  프로세스 준비 단계 (new → ready)

• ms 이하의 시간 단위로 매우 빈번하게 호출되기 때문에 수행 속도가 충분히 빨라야 한다.

중기 스케줄링

• 메모리에 적재된 프로세스의 수를 관리하는 작업

    ◦  장기 스케줄러와 역할이 비슷하다.

    ◦  필요한 이유 : 메모리에 너무 많은 수의 프로세스가 적재되면 프로세스 당 보유하고 있는 메모리량이 극도로 적어지면서

                             디스크 I/O 가 수시로 발생하게 되는데, 이는 심각한 시스템 성능 저하를 초래한다.

• 스왑 아웃(swap out)

    ◦  메모리에 올라와 있는 일부 프로세스에서 메모리를 통째로 빼앗아 디스크의 스왑 영역에 저장하는 행위

    ◦  봉쇄 상태의 프로세스가 제일 먼저 스왑 아웃 대상이 된다.

       -  봉쇄 상태의 프로세스는 당장 CPU를 획득할 가능성이 없기 때문

    ◦  그 다음으로 타이머 인터럽트가 발생해 Ready Queue 로 이동하는 프로세스가 스왑 아웃 대상이 된다.

• 중기 스케줄러의 등장으로 프로세스의 상태에 Suspended 상태가 추가 되었다.

    ◦  메모리를 통째로 빼앗기고 디스크로 스왑 아웃된 상태를 의미

       -  Suspended Blocked : 봉쇄 상태에 있던 프로세스가 디스크로 스왑 아웃

       -  Suspended Ready : 준비 상태에 있던 프로세스가 디스크로 스왑 아웃

       -  Suspended Blocked 상태가 특정 조건을 만족하면 Suspended Ready 상태가 된다.

디스패처

• CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈

• 디스패치

    ◦  준비 리스트에 있던 프로세스 중 하나를 선택(스케쥴링)해 실행하는 것

    ◦  이 때 Context Switching이 일어난다.

       -  자발적 문맥 교환 : 사용 불가능한 자원(blocked 등)을 요청했으므로 프로세스가 CPU 사용을 포기

       -  비자발적 문맥 교환 : 시간 제한이 만료되었거나 우선순위가 더 높은 프로세스에 의해 CPU를 뺏김

• 프로세스 Context Switching 이 일어날 때 마다 디스패처가 호출되므로, 가능한 빠르게 수행되어야 한다.

• 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 까지 소요되는 시간을 디스패치 지연(Dispatch Latency)

    이라고 부른다.

참고자료

운영체제란?

운영체제(operating system)란, 컴퓨터 하드웨어를 관리하는 소프트웨어이다.

운영체제는 컴퓨터 하드웨어를 관리할 뿐만 아니라, 컴퓨터 시스템의 자원들을 효율적으로 관리하고, 응용 프로그램과 하드웨어 간의 인터페이스로써 다른 응용 프로그램이 유용한 작업을 할 수 있는 환경을 제공해준다.

즉, 운영 체제는 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있는 환경을 제공하는 시스템 소프트웨어라고 할 수 있다.

개발자는 운영체제를 왜 공부해야 할까? 기업에서는 왜 그렇게 운영체제 이론을 강조하면서 기술질문을 하는 것일까?

우선 내가 만든 프로그램, 혹은 내가 사용하는 프로그램이 컴퓨터에서 어떻게 수행되는지를 알아야 에러가 발생했을 때 빠르게 원인을 찾아
해결할 수 있고, 프로그램의 실행 속도나 메모리 성능을 지속적으로 개선하는 등 서비스를 확장해 나갈 수 있기 때문이다.

더불어 운영체제를 잘 이해하면 프로그램을 만들기 전에 개발 난이도, 비용, 성능 등을 예측할 수 있다.
이걸 사전에 파악하는 것은 한정된 시간과 비용으로 서비스를 개발해야 하는 기업 입장에서는 매우 중요할 것이다.

나 역시 처음 웹 개발 공부를 시작할 때에는 웹 개발에 운영체제 지식이 왜 필요해? 그건 임베디드 하는 애들한테나 중요한거 아니야?
라는 생각을 하곤 했지만... 웹 서비스를 배포하거나 서버 트래픽 관리, DB 쿼리 최적화 작업만 해도 수많은 프로세스 에러를 만나게 되면서
운영체제를 공부해야 한다고 주변에 외치고 다녔더랜다.

이러한 운영체제의 종류에는 Windows, Linux, UNIX, MS-DOS 등이 있으며 각각 장단점이 있으므로 사용하고자 하는 용도에 알맞게 선택하여 사용하는 것이 좋다.

프로세스 관리

운영체제의 역할 중 하나는 프로세스 관리 이며, 운영체제에서 작동하는 응용 프로그램을 관리하는 기능이다.

컴퓨터 CPU가 한번에 처리할 수 있는 양은 제한적이다. 따라서 여러 응용 프로그램이 동시에 CPU을 사용하려고 한다면 운영체제는 이를 적절히 배분해 줄 수 있어야 할 것이다. 즉 프로세스 관리는 프로세서(CPU)를 관리하는 것이라고 볼 수도 있다.

운영체제는 현재 CPU를 점유해야 할 프로세스를 결정하고, 실제로 CPU를 프로세스에 할당한 다음, 이 프로세스의 공유 자원 접근 및 통신 등을 관리한다. 이러한 작업을 우리는 스케줄링, 동기화, IPC 통신 이라고 부르는 것이다.
(각각이 어떤 작업을 의미하는지는 이후 포스팅에서 알아보자)

프로세스와 스레드

프로세스란, 특정 프로그램이 메모리 상에서 실행중인 작업 이다. 이 때 프로세스 안에서 실행되는 여러 흐름 단위를 스레드 라고 한다.

프로세스가 생성될 때, 기본적으로 하나의 스레드가 함께 생성된다. 즉 프로세스마다 최소 1개 이상의 스레드가 존재할 수 있다.

하나의 프로세스에는 Code, Data, Heap 이라는 세가지 메모리 영역이 존재한다.

• Code : 코드 자체, 프로그램 명령 등이 저장되는 영역

• Data : 전역변수, 정적변수, 배열 등이 저장되는 영역

    -  초기화 된 데이터는 data 영역에 저장된다.

    -  초기화 되지 않은 데이터는 BSS(Block Started by Symbol) 영역에 저장된다.

• Heap : 동적 할당된 데이터(new, malloc 등)가 저장되는 영역

이 때 하나의 프로세스에 여러개의 스레드가 존재하는 경우, 각 스레드에는 별도의 Stack 영역이 독립적으로 주어지지만

Code, Data, Heap 영역은 소속된 프로세스의 것을 공유하여 사용한다.

• Stack : 지역변수, 매개변수, 리턴 값 등이 저장되는 영역 (임시 메모리 영역)

즉 프로세스는 자신만의 고유 공간과 자원을 할당받아 사용하는데 반해,

스레드는 프로세스 내부에서 다른 스레드와 공간, 자원을 공유하면서 사용한다는 점에서 공간/자원 사용 측면의 차이가 있다.

멀티 프로세스

멀티 프로세스란 여러개의 프로세스가 동시에 병렬적으로 처리되는 상황을 의미한다.

보통 하나의 컴퓨터에 여러개의 CPU를 장착해야 가능하다. 단일 코어 CPU는 한번에 하나의 프로세스만 처리할 수 있기 때문이다.

• 장점 : 안전성 (메모리 침범 문제를 OS 차원에서 해결해준다)

• 단점 : 프로세스가 각각 독립된 메모리 영역을 갖고 있기 때문에, 작업량이 많을수록 오버헤드가 발생할 수 있다.

              또한 Context Switching 으로 인한 성능 저하가 발생한다.

• Context Switching

    -  프로세스의 상태 정보를 저장하고 복원하는 일련의 과정

    -  프로세스는 동작 상태와 대기 상태를 반복한다. 동작 중인 프로세스가 대기 상태가 되면 해당 프로세스의 정보는 보관되어야 한다.
       이후 대기 상태에서 다시 동작 상태가 되면 보관중이던 정보는 다시 복원되어야 한다. 이 과정이 바로 Contect Switching 이다.

    -  프로세스는 각각 독립된 메모리 영역을 할당받아 사용하기 때문에, 캐시 메모리 초기화처럼 무거운 작업이 진행될 때 오버헤드가
       발생할 수 있다.

멀티 스레드

멀티 스레드란 하나의 프로세스에서 여러 스레드가 각각 별개의 작업을 하나씩 처리하는 것을 의미한다.

즉 멀티 스레드를 이용하면 하나의 프로세스만 가지고 여러 작업을 동시에 처리할 수 있다.

멀티 프로세스로 여러 작업을 동시에 처리하는 것 보다 하나의 프로세스에서 멀티 스레드로 여러 작업을 동시에 처리하면

메모리 공간과 시스템 자원 소모를 줄일 수 있다.

또한 하나의 프로세스에 속한 스레드들은 Code, Data, Heap 공간을 공유하기 때문에

별개의 Code, Data, Heap 공간을 사용하는 멀티 프로세스 방식 보다 통신 방법이 간단하고 속도 역시 빠르다.

• 장점 : 멀티 프로세스 방식 보다 시간, 자원 손실이 적으며 쓰레드끼리 전역 변수와 정적 변수를 공유할 수 있다.

• 단점 : 안전성의 문제가 발생할 수 있다. 메모리 공간을 공유하기 때문에, 하나의 스레드가 메모리를 훼손하면, 모든 스레드의 작동이
              불가능해진다. 이러한 문제는 Critical Section 에 동기화 기법을 적용하여 방지할 수 있다.

• Critical Section

    -  특정 데이터에 둘 이상의 쓰레드가 동시에 접근해서 연산을 실행하는 경우 문제가 발생할 수 있다.
       이러한 문제를 일으키는 코드 블록을 Critical Section 이라고 한다. 즉 한 순간에 하나의 쓰레드만 접근해야 하는 공유 리소스 영역
       (전역 변수 등)에 접근하는 코드 블록을 Critical Section 이라고 한다.

    -  동기화 기법을 이용하면 임계 영역에는 한번에 단 하나의 쓰레드만 접근하도록 제한할 수 있다.

• 동기화 기법의 종류

    -  크리티컬 섹션(Critical Section) 기반 동기화 (유저 모드 동기화)

    -  인터락 함수(Interlocked Family Of Function) 기반 동기화 (유저 모드 동기화)

    -  뮤텍스(Mutex) 기반 동기화 (커널 모드 동기화)

    -  세마포어(Semaphore) 기반 동기화 (커널 모드 동기화)

    -  이름있는 뮤텍스(Named Mutex) 기반 프로세스 동기화 (커널 모드 동기화)

    -  이벤트(Event) 기반 동기화 (커널 모드 동기화)

동기화 기법마다 사용해야 하는 경우가 특별하게 정해져 있는 것은 아니지만,
목적에 적합한 동기화 기법을 잘 선택해서 사용하면 간결하고 정확한 코드를 작성할 수 있다.

참고자료