Post

프로세스 관리

Posted Updated
By idiot2222 25 min read





Process의 개념

  • 초기의 컴퓨터는 한 번에 하나의 프로그램만을 처리했다.
    • 이 프로그램은 cpu, 메모리 등의 리소스들을 혼자 독차지했다.
    • 이 프로그램은 리소스들의 접근에 대해 제한이 없었다.
  • 이제는 컴퓨터가 발전되어 한 번에 여러개의 프로그램을 메모리에 올려서 처리하게 되었다.
    • 이 때문에 프로세스라는 개념이 생겨났다.
      • 컴퓨터 시스템에서 하나의 작업 단위이다.
      • 실행중인 프로그램을 뜻한다.
    • 멀티 프로세스로 인해서 각각의 프로세스에 대한 통제가 필요하게 되었다.



프로세스의 상태


img-description 프로세스의 상태


  • New
    • 프로세스가 새로 생성된 상태
    • 프로그램이 메인 메모리로 올라온 상태
  • Ready
    • 실행 준비가 완료된 상태
    • CPU 할당을 받을 수 있으나, 아직 기다리는 상태이다.
  • Running
    • CPU를 점유중인 상태
    • I/O 작업 등을 만나면, CPU 점유를 넘기고 Waiting 상태로 바뀐다.
    • 시분할 프로그래밍으로, CPU 점유를 넘기고 Ready 상태로 바뀐다.
    • 프로세스의 작업이 끝나면, Terminated 상태로 바뀐다.
  • Waiting
    • I/O 작업 등으로 CPU 점유를 넘기고 대기중인 상태
    • 다른 작업으로 CPU 할당을 받지 않는 상태이다.
    • I/O 작업이 끝나면 Ready 상태로 바뀐다.
  • Terminated
    • 프로세스가 종료된 상태이다.



PCB

  • Process Control Block
  • 운영체제가 프로세스를 관리하기 위한 정보를 담아두는 곳이다.
    • 프로세스 상태 정보
    • PC (Program Counter)
    • 레지스터 정보
    • 메모리 내에서 번지 수 (base, limit)
    • CPU 점유 시간
    • PID (Process ID)
    • list of open files (해당 프로세스가 사용하는 파일들)
    • 등등 …
  • 하나의 프로세스 당 하나의 PCB를 생성해서 가진다.
  • 문맥 교환 시에 처리 중이던 프로세스를 PCB에 저장하여 다음 차례 때 꺼내서 쓴다.



프로세스 스케쥴링

  • 멀티 프로그래밍의 목적은 프로세스를 여러개 올려서 CPU 활용도를 최대화하기 위함이다.
  • 시분할 시스템의 목적은 프로세스 간에 CPU를 자주 전환하여 사용중인 프로세스 간의 상호 작용을 얻기 위함이다.
  • 그러나 결국 CPU의 코어 하나는 한 번에 하나의 프로세스만을 처리할 수 있다.
    • 위와 같은 목적을 달성하기 위해 프로세스 스케쥴링이 필수이다.
    • 프로세스 스케쥴링이란 결국 실행해야 하는 프로세스 목록에서 처리할 하나의 프로세스를 고르는 과정이다.



프로세스 큐


img-description 프로세스 큐


  • 여러 개의 프로세스를 처리해줘야 하니까 그때마다 동시에 모든걸 처리할 수는 없다.
    • 처리하려는 프로세스들은 대기열에 들어가고
    • 대기열에서 적절한 프로세스를 올려 처리한다.
    • 프로세스들이 기다리는 대기열을 프로세스 큐라고 한다.
  • 또 I/O bound 프로세스와 CPU bound 프로세스의 균형있는 처리를 맡는다.
    • I/O bound 프로세스는 I/O 작업을 많이하는 프로세스
    • CPU bound 프로세스는 CPU 작업을 많이하는 프로세스
    • I/O 작업에 치중된 프로세스들만 가득하다면 CPU는 놀게 된다.
    • CPU 작업에 치중된 프로세스들만 가득하다면 CPU 처리가 늦어지게 된다.

각 기기 사이마다 존재하는 프로세스 큐는 아래와 같다.

  • Job Queue
    • 서브 메모리에서 메인 메모리에 올라가기를 기다리는 큐이다.
  • Ready Queue
    • 프로세스들이 CPU 할당을 기다리는 큐이다.
  • Device Queue
    • I/O 장치를 사용하기 위해 기다리는 큐이다.
    • 각각의 I/O 장치당 하나의 큐가 있다.

스케줄러는 다음과 같이 나눌 수 있다.

  • Long-term Scheduler
    • Ready Queue로 갈 프로세스를 선택한다.
    • 메모리에 적재할 프로세스의 수를 제어한다.
    • 간단하게 말하면 메모리에 적재할 프로그램을 선별하는 애다.
  • Short-term Scheduler
    • 다음 실행될 프로세스를 선택하여 CPU에 적재한다.
    • 간단하게 다음에 처리할 프로세스를 골라주는 애다.
  • Medium-term Scheduler
    • 얘도 메모리에 올라가 있는 프로세스의 수를 제어하는건 똑같은데,
      • 이미 올라간 프로세스를 내려서 줄이는 역할을 한다.
      • 잘 쓰이지 않는 애들을 내려서 쉬게 하다가, (swap-out)
      • 다시 쓰일 때 슬그머니 올려준다. (swap-in)
    • 역할 때문에 Swapper라고도 부른다.

Context Switching

  • 우리말로 문맥 교환이라고도 한다.
  • 현대의 운영체제는 대부분 시분할 시스템을 갖고 있다.
    • 시분할 시스템은 겉으로 보기에는 여러개의 프로세스를 동시에 수행하는 것 같지만,
    • 사실은 CPU를 여러 프로세스가 조금씩 아주 빠르게 돌려가며 사용하는 것이다.
    • 이때 처리 중이던 프로세스에서 다른 프로세스로 CPU 점유가 넘어가는 것을 문맥 교환이라고 한다.
  • CPU가 처리하던 프로세스의 정보를 PCB에 저장해두고,
    • 다른 새로운 프로세스의 PCB를 참조하여 다시 처리를 시작한다.
    • 이것을 빠르게 반복한다.

문맥 교환에 고려해야 할 것들은 다음의 것들이 있다.

  • 다음에 어떤 프로세스로 스위칭 해야하는가
  • 스위칭 시에 일어나는 오버헤드를 어떻게 줄일 것인가



CPU 스케쥴링

  • 현재 프로세스가 끝나면, 다음에 어떤 프로세스를 처리해야 하는가를 결정하는 것이 CPU 스케쥴링이다.
  • Preemptive vs Non-preemptive
    • CPU 스케쥴링 알고리즘은 두 가지로 나눌 수 있다.
    • 선점 vs 비선점
      • 선점
        • 현재 프로세스가 끝나거나, I/O 작업을 만나지 않았는데
        • 다른 프로세스가 스윽 뺏을 수 있는 방식
      • 비선점
        • 현재 프로세스가 끝나거나, I/O 작업을 하지 않는 이상 절대 양보를 안하는 방식
  • 스케쥴링의 효율성을 나타내는 척도는 다음과 같은 것들이 있다.
    • CPU Utilization
      • CPU 이용률
      • CPU가 얼마나 놀지 않고 계속 일했는가
    • Throughput
      • 처리율
      • 시간 당 작업 처리 수
    • Turnaround time
      • 반환 시간
      • 프로세스가 준비된 후부터 처리가 완료되어 종료되는 시점까지의 시간
    • Waiting time
      • 대기 시간
      • CPU 점유를 위해 프로세스가 Ready Queue에서 대기한 시간
    • Response time
      • 응답 시간
      • 프로세스가 준비된 후부터 첫 CPU 점유를 받았을 때까지 걸린 시간



FCFS

  • First Come First Served
    • 먼저 온 놈 먼저 처리해주겠다는 뜻
  • 가장 간단하고 공평한 방식이다.
  • 비선점 알고리즘이다.


프로세스도착시간(s)처리시간(s)
P1020
P208
P308


img-description FCFS 예시 - 1

  • P1, P2, P3가 동시에 와서, P1-P2-P3 순으로 처리를 해주었다.
  • AWT (Average Waiting Time)을 구해보면,
    • (0 + 20 + 28) / 3 = 16
    • 한 사람 당 평균적으로 16초나 기다렸다.


img-description FCFS 예시 - 2

  • P1이 너무 오래 걸려서 P1을 맨 뒤로 보냈다. 짧은 애들을 먼저 처리해본다.
    • P2-P3-P1
  • AWT를 구해보면,
    • (0 + 8 + 16) / 3 = 8
    • 한 사람 당 평균적으로 8초만 기다리면 된다.
    • 이게 훨씬 더 효율적인 것을 알 수 있다.



SJF

  • Shortest Job First
    • 짧은 놈을 먼저 처리하겠다는 뜻
  • 증명된 최적화 알고리즘이다.
  • 그러나 현실적이지 못하다.


프로세스도착시간(s)처리시간(s)
P1012
P2016
P3014
P406


  • 먼저 위의 작업을 먼저 도착한 작업을 먼저 처리하는 FCFS로 처리해본다.
  • AWT를 구하면,
    • 동시에 왔으나 처리 시간을 고려하지 않고, P1-P2-P3-P4 순으로 처리했다고 가정한다.
    • (0 + 12 + 28 + 42) / 4 = 20.5
    • 한 사람 당 평균적으로 20.5초나 대기해야 한다.


img-description 비선점 SJF 예시


  • 먼저 온 작업을 먼저 처리하는 SFJ로 처리해본다.
  • AWT를 구하면,
    • (0 + 6 + 18 + 32) / 4 = 14
    • 한 사람 당 평균적으로 14초만 대기하면 된다.


SJF를 증명된 최적화 알고리즘이나, 현실적이지 못한 방법이라고 했었다.

  • SJF는 수학적인 계산으로는 가장 대기 시간을 줄일 수 있는 방법이다.
  • 그러나 위의 예시들처럼 항상 프로세스의 처리 시간을 정확하게 알지 못한다.
  • 그러니 이 방법은 프로세스의 처리 시간이 얼마나 될 것이라는 예측을 정말 잘해야 한다.
  • 근데 예측을 위한 오버헤드가 부담이 되기 때문에 역시 현실적이지 못하다.


프로세스도착시간(s)처리시간(s)
P1016
P218
P3218
P4310


img-description 선점 SJF 예시 - 1


  • 먼저 위의 표를 비선점 SJF 알고리즘으로 처리해본다.
    • P1-P2-P4-P3 순으로
    • 먼저 처리 중이던 프로세스가 끝나면,
    • 다음으로 가장 짧은 프로세스의 처리를 시작한다.
  • AWT를 구해보면,
    • (0 + 16 + 24 + 34) / 4 = 18.5
    • 평균적으로 18.5초나 기다려야 한다.


img-description 선점 SJF 예시 - 2


  • 이번엔 선점 SJF 알고리즘으로 처리해본다.
  • 먼저 도착한 순서대로 처리를 시작하지만,
    • 그 뒤에 도착한 작업의 길이가 더 짧다면
    • 더 짧은 작업을 우선 처리한다.
  • 처리 순서는 다음과 같다.
    1. P1이 0초에 도착해 처리를 시작한다. (0초)
    2. P2가 1초에 도착해 CPU를 선점한다. (1초)
      • P1은 (16-1)초 남았고, P2는 8초이기 때문에 더 짧은 P2가 선점한다.
      • P3가 2초에 도착했지만, 더 짧은 P2를 처리 중이라 선점하지 못한다.
      • P4가 3초에 도착했지만, 더 짧은 P2를 처리 중이라 선점하지 못한다.
    3. P2의 작업이 모두 끝나고, 지금 시점에 가능한 가장 짧은 P4의 처리(10초)를 시작한다. (9초)
    4. P4의 작업이 모두 끝나고, 지금 시점에 가능한 가장 짧은 P1의 처리(16-1초)를 시작한다. (19초)
    5. P1의 작업이 모두 끝나고, 남아있는 P3의 처리(18초)를 시작한다. (34초)
    6. 작업이 모두 끝난다. (52초)
  • AWT를 구해보면,
    • P1의 총 대기 시간: 8
    • P2의 총 대기 시간: 0
    • P3의 총 대기 시간: 32
    • P4의 총 대기 시간: 6
    • (8 + 0 + 32 + 6) / 4 = 11.5
    • 평균적으로 7초나 덜 기다려도 된다.



우선 순위 스케쥴링

  • Priority Scheduling
    • 우선 순위가 빠른 녀석을 먼저 처리하겠다는 뜻
    • 빠르다고 표현한건 priority가 작은 애가 우선이기 때문에
  • 얘도 역시 선점, 비선점이 있다.


프로세스처리시간(s)우선순위
P1103
P211
P324
P415
P552


img-description 우선 순위 알고리즘 예시


  • 우선 순위가 빠른 친구부터 먼저 처리한다.
    • 전부 동시에 도착했다고 가정한다.
  • AWT를 구해보면,
    • (6 + 0 + 16 + 18 + 1) / 5 = 8.2


그럼 우선 순위는 어떤 식으로 결정하는 걸까

  • internal
    • time limit
      • 작업 처리 시간 적은 거 우선
    • memory requirement
      • 메모리 사용량 적은 거 우선
    • I/O to CPU burst
      • I/O 작업 시간과 CPU 작업 시간을 비교해서 결정
  • external
    • amounts of funds being paid
      • 돈 많이 낸 놈 우선 결정
    • political factors
      • 정치적 요소로 중요한 거 우선 결정

우선 순위 알고리즘의 문제점

  • starvation
    • 기아 현상이라고도 한다.
    • 우선 순위가 계속 밀려나면서 CPU 점유를 받지 못하는 경우를 기아 현상이라고 한다.
    • 위의 우선 순위 예시에서는 프로세스가 몇 개 없었지만, 실제로는 계속해서 프로세스가 큐에 추가된다.
    • 예를 들어, 위에서 우선 순위가 가장 낮았던 P4는
      • 자기보다 빠른 우선 순위를 가지는 작업이 4개 밖에 없기 때문에
      • ‘언젠가는 내 차례가 오겠지 ㅎㅎ’ 라고 생각한다.
      • 그러나 계속 다른 우선 순위가 P4보다 작은 작업들이 추가되고,
      • P4가 계속 밀리고 밀려 CPU 점유를 받지 못하는 경우가 생길 수 있다.
    • aging
      • starvation을 해결하기 위한 방법이다.
      • 레디 큐에서 우선 순위가 계속 밀리는 작업들에 나이를 매겨 우선 순위를 높여주는 방식이다.



Round-Robin

  • 시분할 시스템을 위한 알고리즘
    • 작업의 우선 순위를 두지 않고
    • 일정 시간을 정해서
      • Time Quantum (Time Slice)
    • 각각의 프로세스들을 돌아가며 처리하는
    • 선점형 알고리즘이다.
      • 작업 도중에 뺏고를 반복하기 때문에 비선점일 수가 없다.


프로세스처리시간(s)
P124
P23
P33


  • Time Slice가 4s일 떄,
  • AWT를 구해보면,
    • (6 + 4 + 7) / 3 = 약 5.67


  • Time Slice가 1s일 떄,
  • AWT를 구해보면,
    • (6 + 5 + 6) / 3 = 약 5.67


  • Time Slice가 30s일 때,
  • AWT를 구해보면,
    • (0 + 24 + 27) / 3 = 17


  • Time Quantum을 어떻게 나누냐가 중요하다.
    • 너무 길게 잡았더니,
      • 위의 예시에서 보면 FCFS 알고리즘과 다를게 없었다.
    • 너무 짧게 잡는다면,
      • 문맥 교환시에 발생하는 오버헤드가 너무 잦아진다.
      • 위의 예시에서 보면 Time Slice가 4s인 경우랑 1s인 경우에 AWT가 같았다.
      • 결국 문맥 교환이 적게 일어나는 4초의 경우가 훨씬 이득이다.
  • 일반적으로는 10ms ~ 100ms 사이의 값으로 잡는다고 한다.



Multilevel Queue Scheduling

  • 프로세스의 종류나 목적에 따라서 여러 개의 프로세스 그룹을 두고 각각의 프로세스 그룹에 우선 순위를 정해둔다.
  • 프로세스 그룹은 이런식으로 나눌 수 있다.
    • System Process
    • Interactive Process
    • Batch Process
    • Student Process
  • 각각 나뉜 프로세스 그룹마다 큐를 두고, 그 싱글 큐마다 또 다른 스케쥴링 정책을 적용한다.



Multilevel Feedback Queue Scheduling

  • 얘도 역시 여러 개의 큐를 놔두고 각각 다른 정책을 사용하는 것은 똑같다.
  • 그러나 얘는 그룹을 나누지 않는다.
    • 모든 프로세스는 다 같은 입구로 들어온다. (첫 번째 큐)
    • 어느 한 프로세스가 너무 많은 CPU time 사용 시에 다음 큐로 보낸다.
    • 기아 상태가 우려될 시에 다시 우선 순위 높은 큐로 보낸다.





프로세스 생성과 종료

프로세스의 생성

  • 프로세스는 프로세스에 의해 만들어진다.
    • 부모 프로세스
      • 다른 새로운 프로세스를 생성한 프로세스
    • 자식 프로세스
      • 다른 프로세스에 의해 생성된 새로운 프로세스
    • 프로세스 트리
      • 어떤 프로세스가 생성한 모든 자손들을 그린 가계도
  • 가장 첫 번째 프로세스
    • 컴퓨터가 부팅되고, 운영체제를 로드하려 한다.
    • 운영체제의 가장 첫 번째 하나의 프로세스를 생성한다. (init)
    • 그 init 프로세스가 다른 자식 프로세스들을 생성한다.
    • 역시 자식들도 자식 프로세스들을 주주죽 생성한다.
  • PID
    • Process Identifier
    • 각 프로세스에 부여된 고유 식별자 (init은 보통 0)
    • 부모의 PID를 PPID라고 한다.
  • 그럼 생성은 어떻게 하는가?
    • 새로운 프로세스를 만드는 시스템 콜인 fork()를 호출한다.
    • 새로 만들어진 프로세스를 동작하게 하는 exec() 시스템 콜을 호출한다.
  • 프로세스 종료
    • 종료하려는 프로세스가 exit() 시스템 콜을 호출한다.
    • 종료되는 프로세스가 사용하던 모든 리소스가 반납된다.
      • 메모리, 파일 등





쓰레드

  • Thread
    • 한 프로그램 내부의 흐름
    • 하나의 쓰레드만을 가지는 프로그램을 단일 쓰레드 프로그램이라고 한다.
  • Multi Threads
    • 한 프로그램 내부에 여러 개의 쓰레드(흐름)이 존재하는 것
      • 다중 쓰레드 프로그램
    • 두 쓰레드를 빠르게 스위칭 하면서 마치 동시에 실행되는 것처럼 보인다.(Concurrent)
      • Concurrent vs Simultaneous
        • Concurrent는 시간 간격을 두고 번갈아 가며 수행해서, 동시에 수행하는듯 보이게 하는 것
        • Simultaneous는 실제로 동시에 수행하는 것
  • 멀티 쓰레드 내부 구조는
    • 프로세스의 메모리 공간을 공유한다.
    • 프로세스의 자원을 공유한다.
    • 레지스터나 스택은 서로 공유하지 않는다.





CS, OS
cs os process
This post is licensed under CC BY 4.0 by the author.