프로세스 관리

프로세스의 정의

  • 프로세서에 의해 처리되는 실행중인 프로그램을 의미

  • 운영체제에서는 job , task라고 한다.

  • 프로세스의 종류

    • PCB를 가진 프로그램
    • 실기억장치에 저장된 프로그램
    • 프로세서가 할당되는 실체
    • 프로시저가 활동중인 것
    • 비동기적 행위를 일으키는 주체
    • 지정된 결과를 얻기 위한 일련의 계통적 동작
    • 목적 또는 결과에 따라 발생되는 사건들의 과정

PCB(Process Control Block)(job control block)

  • 운영체제가 프로세스에 관한 중요한 정보를 저장해 놓은 곳
  • 각 프로세스가 생성될 때마다 고유의 pcb가 생성되고, 프로세스가 완료되면 제거된다.
  • PCB에 저장된 정보
    • 프로세스의 현재 상태
    • 포인터
    • 프로세스 고유 식별자
    • 스케쥴링 및 프로세스의 우선 순위
    • CPU 레지스터 정보
    • 주기억장치 관리 정보
    • 입출력 상태 정보
    • 계정 정보

프로세스 상태 전이

  • 프로세스가 시스템 내에 존재하는 동안 프로세스의 상태가 변하는 것을 의미

프로세스 상태

  • 제출(Submit)
    • 작업 처리를 위해 사용자가 작업을 시스템에 제출한 상태
  • 접수(Hold)
    • 제출된 작업이 디스크(스풀 공간)에 저장된 상태
  • 준비(Ready)
    • 프로세스가 프로세서를 할당받기 위해 기다리고 있는 상태
    • 프로세스는 준비상태 큐(스케쥴링 큐)에서 실행을 준비 중
    • 접수 상태에서 준비 상태로의 전이는 Job 스케줄러에 의해 수행된다
    • 준비 리스트에 있는 프로세스는 각각 우선순위가 주어진다.
  • 실행(Run)
    • 준비상태 큐에 있는 프로세스가 프로세서를 할당받아 실행되는 상태
    • 프로세스가 수행 완료전 프로세서 할당시간이 종료되면 프로세는 준비 상태로 전이
    • 실행중인 프로세스에 I/O가 필요하면 실행중인 프로세스는 대기 상태로 전이된다
    • 준비 상태에서 실행 상태로의 전이는 CPU(프로세서) 스케줄러에 의해 수행된다.
  • 대기,보류,블록
    • I/O 처리가 완료 될 때 까지 프로세스가 중단되어 대기하는 상태
    • 대기 리스트에 있는 프로세스는 우선순위가 주어지지 않는다.
  • 종료
    • 프로세서 실행이 완료되고 프로세스 할당이 해제 된 상태

프로세스 상태 전이 관련 용어

  • Dispatch
    • 준비 상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당받아 실행 상태로 전이되는 과정
  • Wake up
    • I.O 작업이 완료되어 프로세스가 대기 상태에서 준비 상태로 전이 되는 과정
  • 교통량 제어기(Traffic controller)
    • 프로세스의 상태에 대한 조사와 통보 담당

스레드

  • 프로세스 내에서의 작업 단위, 여러 작업을 할당받아 실행하는 프로그램의 단위

    • 단일 스레드 , 멀티 쓰레드
    • 프로세스의 일부 특성을 갖고 있어 경량 프로세스라 함
    • 자신 만의 스택과 레지스터 를 갖으며 독립된 제어흐름을 갖는다.

  • 스레드의 분류

    • 사용자 수준 : 사용자가 만든 라이브러리를 사용하여 스레드 운용, 속도는 빠르지만 구현이 어려움
    • 커널 수준 : 운영체제 커널에 의해 운용, 구현은 쉬우나 속도가 느림

  • 스레드 사용의 장점

    • 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성 증진 가능
    • 하드웨어, 운영체제의 성능과 응용 프로그램의 처리율을 향상시킬 수 있다.
    • 응용 프로그램의 응답시간을 줄일 수 있음
    • 실행 환경을 공유시켜 기억장소 낭비 가 줄어든다.
    • 프로세스들 간의 통신이 향상
    • 스레드는 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신

스케줄링

스케줄링의 개요

  • 프로세스가 생성되어 실행될 때 필요한 자원을 해당 프로세스에게 할당하는 작업
  • 스케줄링의 종류
    • 장기 스케줄링
      • 어떤 프로세스가 시스템 자원을 차지할 것인가를 결정, 준비상태 큐로 보내는 작업 의미
      • 작업 스케줄링(job scheduling), 상위 스케줄링이라고 하며 , 작업 스케줄러에 의해 수행
    • 중기 스케줄링
      • 어떤 프로세스들이 cpu를 할당받을 것인지 결정하는 작업
      • cpu를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류 시킨후 활성화해 시스템 부하 조절
    • 단기 스케줄링
      • 프로세스가 실행되기 위해 cpu를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미
      • 프로세서 스케줄링, 하위 스케줄링이라고도 함
      • 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행

스케줄링의 목적

  1. 공정성
  2. 처리율 증가
  3. cpu 이용률 증가
  4. 우선순위 제도
  5. 오버헤드 최소화
  6. 응답 시간 최소화
  7. 반환시간 최소화
  8. 대기시간 최소화
  9. 균형있는 자원의 사용
  10. 무한 연기 회피

스케줄링 기법

  • 대기 시간 : 바로 앞 프로세스까지 진행시간으로 계산
  • 반환 시간 : 프로세스의 대기 시간과 실행 시간의 합

비선점 스케줄링

  • 이미 할당된 cpu를 다른 프로세스가 강제로 빼앗을 수 없다.
  • 프로세스가 cpu를 할당 받으면 해당 프로세스가 완료될 때까지 cpu를 사용한다.
  • 모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.
  • 프로세스 응답 시간 예측이 용이하며, 일괄 처리 방식에 적합

선점 스케줄링

  • 우선순위 존재
  • 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템, 온라인 응용에 사용
  • 많은 오버헤드를 초래
  • 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클럭이 필요

비선점 스케줄링

FCFS(First come first service) = FIFO

  • 준비 상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
  • 공평성은 유지되나 효율성이 떨어질 수 있음

SJF(short job first, 단기 작업 우선)

  • 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
  • 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
  • 실행 시간이 긴 프로세스가 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무기한 연기 상태가 될 수 있다.

HRN(HIGHEST RESPONSE-RATIO NEXT)

  • SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행)시간을 이용하는 기법이다.
  • 우선순위 계산 공식을 이용해 우선순위를 부여 후 CPU에 할당
    • (대기시간 + 서비스 시간)/서비스 시간

기한부(DeadLine)

  • 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
  • 제한 시간 초과시 제거하거나 처음부터 다시 실행 시킴
  • 시스템은 프로세스에게 할당할 정확한 시간을 추정해야 하며, 사용자는 이를 위해 프로세스에게 정확한 정보를 제공 해야한다.
  • 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡, 프로세스 실행 시 집중적으로 요구되는 자원 관리에 오버헤드가 발생

우선순위

  • 준비 상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 cpu를 할당하는 기법
  • 우선순위가 동일 할 경우 : FCFS 기법으로 CPU 할당
  • 우선순위는 외부적, 내부적 요인에 따라 다르게 부여 될 수 있다.
  • 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태 발생 가능

선점 스케줄링

SRT(Shortest remaining time)

  • 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법, 선점 SJF라 하기도 함
  • 현재 실행 중인 프로세스의 남은 시간과 준비 상태 큐에 새로 도착한 프로세스의 실행시간을 비교하여 짧은 시간을 요구하는 프로세스에게 CPU를 할당.
    • 시분할 시스템에 유용
  • 준비 상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가

RR(round robin)

  • 시분할 시스템을 위해 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형한 기법
  • FCFS처럼 준비 상태 큐에 먼저 들어온 프로세스가 먼저 CPU할당 받으나 시간 할당량 동안에만 실행후 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐 제일 뒤로 이동
  • 할당 되는 시간이 클 경우 FCFS, 작을 경우 문맥 교환 및 오버헤드가 자주 발생

다단계 큐

  • 프로세스를 특정 그룹으로 분류 후 각기 다른 준비 상태 큐를 이용하는 방법
  • 일반적으로 프로세스 우선순위에 따라 시스템 프로세스 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 순으로 우선순위가 높음
  • 각 준비 상태 큐는 독자적인 스케줄링을 가지고 있고 그룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있다.
  • 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없다.
  • 하위 단계 준비 상태 큐에 있는 프로세스를 실행 중이더라도 상위 단계 준비상태 큐에 프로세스가 들어오면 CPU를 넘겨야한다.

다단계 피드백 큐

  • 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비 상태 큐 사이를 이동할 수 있도록 개선한 기법
  • 각 준비 상태 큐마다 시간 할당량을 부여하여 그 시간 동안 완료하지 못한 프로세스는 다음 단꼐의 준비 상태 큐로 이동
  • 상위 단계 일수록 우선순위가 높고 시간 할당량이 적다.
  • 요구 시간이 적은 프로세스, 입 출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스를 기준으로 높은 우선순위를 할당
  • 마지막 단계 큐에서는 작업이 완료될 때까지 RR스케줄링 기법을 사용

병행 프로세스와 상호배제

병행 프로세스

  • 두 개 이상의 프로세스들이 동시에 존재하여 실행 상태에 있는 것을 의미한다.
    • 한정된 컴퓨터 하드웨어나 자원으 공유하고, 동시에 작업을 수행하기 위해 사용하는 개념
    • 여러 프로세스들이 독립적으로 실행되는 것을 독립적 병행 프로세스, 서로 협력하며 동시에 실행되는 것을 협동적 병행 프로세스
    • 병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요한 개념으로 이용

임계 구역

  • 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유자원(영역)의미

  • 임계 구역의 특징

    • 하나의 프로세스만 접근 가능
    • 특정 프로세스가 독정 할 수 없다.
    • 임계 구역 내에서의 작업은 신속하게!
    • 임계 구역에 현재 실행되는 프로세스가 없어도 구역 사용을 기다려야함, 약간 허락 받는 느낌

  • 임계 구역의 문제를 해결하기 위해서는 상호배제 한계대기 진행 3가지 조건을 충족해야한다.

상호 배제 기법

  • 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어
  • 여러 프로세스가 공유자원을 사용할 때 각 프로세스가 번갈아가며 공유자원을 사용하도록 하는 것, 임계 구역을 유지하는 기법
  • 상호 배제 기법을 구현하기 위한 방법은 하드웨어, 소프트웨어적 구현이 있다.

소프트웨어적 구현 방법

  • 두 개의 프로세스 기준 : Decker 알고리즘, Peterson 알고리즘
  • 여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘

하드웨어적 구현 방법

  • Test_And_Set 기법과 Swap 명령어 기법

동기화 기법

  • 두 개이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 처리 순서를 결정 하는 것으로 상호 배제의 한 형태이다.

동기화 구현 방법

세마포어

  • 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법
  • 다익스트라가 제안, P와 V라는 두 개의 연산에 의해서는 동기화를 유지시키고 상호 배제의 원리를 보장
  • 세마포어의 종류
    • 이진 세마포어
    • 산술 세마포어
  • 세마포어에 대한 연산은 처리중에 인터럽트되어서는 안된다

모니터

  • 모니터는 동기화를 구현하기 위한 특수 프로그램 기법
    • 특정 공유 자원을 프로세스에게 할당하는데 필요한 데이터, 이 데이터를 처리하는 프로시저로 구성
  • 자료 추상화와 정보 은폐의 개념을 기초로 공유자원을 할당하기 위한 병행성 구조로 이루어져있다.
  • 외부의 프로시저로는 직접 액세스 할 수 없다.
  • 모니터의 경계에서 상호 배제가 시행된다.
  • 모니터의 한순간에 하나의 프로세스만 진입하여 자원을 사용할 수 있다.
  • 모니터에서는 WAIT와 SIGANL 연산이 사용된다

교착 상태(Deadlockf)

  • 상호배제에 의해 나타나는 문제점, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 잇는 자원을 요구하며 무한정 기다리는 현상

교착 상태 발생의 필요 충분 조건

  • 하나라도 충족 되지 않으면 교착상태가 발생하지 않는다.

  • 상호 배제 : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

  • 점유와 대기 : 최소 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야한다.

  • 비선점 : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

  • 환형 대기 : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야한다.

예방 기법

  • 자원 낭비가 가장 심한 기법

  • 상호 배제 부정

  • 점유와 대기 부정

  • 비선점 부정

  • 환형 대기 부정

회피 기법

  • 주로 은행원 알고리즘이 사용된다

은행원 알고리즘

  • Dijkstra가 제안, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법
  • 안전상태, 불안정 상태로 구분 : 교착 상태 발생 유무와 프로세스가 완료될 수 있는가
  • 자원의 양 = 사용자(프로세스) 수가 같아야함
  • 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장한다.
  • 대화식 시스템에는 적용 안됨

발견 기법

  • 시스템에 교착 상태가 발생했는지 점검
  • 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.

회복 기법

  • 프로세스 종료
  • 자원 선점