프로세스 관리

프로세스

● 프로그램 vs 프로세스 (program vs process)
– process, task, job …
– program in execution(프로세스는 실행중에 있는 프로그램): text + data + stack, pc(program counter), sp, registers, …
– 무덤 속 프로그램(아무 일도 안함), 살아 움직이는 프로세스
● 프로세스 상태
– new(메인 메모리에 올라온 상태), ready(모든 초기화를 끝나고 실행될 준비가 된 상태), running(실제 실행 상태가 됨), waiting(CPU가 그 다음 프로세스로 넘어감), terminated(프로그램이 끝난 상태) (그림)
– 프로세스 상태 천이도 (process state transition diagram) – 상태 천이는 언제 발생?

• time sharing 시스템은 일정 시간이 되면 자동적으로 ready가 됨

PCB

● Process Control Block (PCB)
– Task Control Block (TCB) – 프로세스에 대한 모든 정보

• process, task는 비슷한 의미임
• 블락안에는 테스크에 대한 모든 정보가 들어 있음
  – process state(상태정보) (running, ready, waiting, …), PC, registers,MMU info (base, limit), CPU time (얼마나 사용했는지), process id(프로세스마다 번호를 붙이는 것), list of open files(어떤 파일을 사용하고 있는지), …
  – 사람과 비유? : 개인의 정보를 다 가지고 있는 정부와 비슷

Queues

● Job Queue( 하드 디스크의 수 많은 잡들이 메인 메모리에 올라가기 위해서는 기달려야 함.)
– Job scheduler (어느 잡을 먼저 올려줄 것 인가) – Long-term scheduler (스케줄러 시간이 김)
● Ready Queue
– CPU scheduler(줄서서 기다리는 서비스 중에 어느 서비스를 잡아서 실행해줄 것인가) – Short-term scheduler (스위치가 빨리 돌아감)
● Device Queue
– Device scheduler(어느 디스크를 잡아서 먼저 해줄 것인가)

Multiprogramming

• 메인 메모리 여러 프로세스를 올린 것
  ● Degree of multiprogramming
  - 메인 메모리에 프로세스가 몇 개 올라가져 있는가
  ● i/o-bound(주로 i/o와 관련된 것) vs CPU-bound process(주로 CPU와 관련된 것, 슈퍼 컴퓨터-일기예보)
  ● Medium-term scheduler : 하나의 서버의 컴퓨터에 여러 사용자가 있고 각각 메모리가 할당되어 있음 => 한 사용자가 사용하고 있지 않을 때, 할당된 메모리는 아무 것도 안하게 됨=> 효율성이 떨어져 메모리에서 디스크로 이동됨(Swap) => 비어있는 메모리에 다른 것을 할당함
  – Swapping
  ● Context switching (문맥전환)
  – Scheduler(어느 프로세스를 선택) – Dispatcher(상태나 레지스터상태를 바꿔주는 것,새로운 컨텐츠를 스위칭해주는 것) – Context switching overhead(할 때 마다 부담하기 때문에 자주할수록 overhead 횟수가 많아짐)

CPU 스케쥴링

CPU Scheduling

• 다음에 어떤 프로세스를 설정해서 실행해야 하는 걸까?
  ● Preemptive vs Non-preemptive
  – 선점 (先占) : 비선점(非先占)
• 선점(미리 점유) = 서비스를 실행하고 있는데 강제로 쫓아내고 점유할 수 있는 것
• 비선점 = 프로세스가 점유하고 있으면 I/O 끝나기 전까지는 끝나지 않는 것(병원)
  ● Scheduling criteria (비교/척도)
  – CPU Utilization (CPU 이용률:CPU가 놀지 않고 부지런히 일하는 가) – Throughput (처리율:시간 당 몇 개의 작업을 처리할 수 있는가) – Turnaround time (반환시간:들어오는 시간 부터 작업이 끝나고 나올 때까지 걸리는 시간, 짧을 수록 좋음 단위: sec 등,) – Waiting time (대기시간:얼마나 기달려야 하는 가) – Response time (응답시간:인터렉티브 시스템에서 필요) – …

CPU Scheduling Algorithms

● First-Come, First-Served (FCFS)
● Shortest-Job-First (SJF) : 작업 시간 짧은 것을 먼저
– Shortest-Remaining-Time-First
● Priority
● Round-Robin (RR)
● Multilevel Queue : 큐를 여러 개
● Multilevel Feedback Queue

First-Come, First-Served (선착순)

• 병원, 은행 예제
  ● Simple & Fair => 꼭 좋은 성능을 나타내는 것은 아님
  ● Example: Find Average Waiting Time(평균 대기 시간, 척도)
  – AWT = (0+24+27)/3 = 17 msec cf.(6+3+0)/3 = 3 msec!
  ● Gantt Chart
  ● Convoy Effect (호위효과) : 앞에 일이 있다면 기다리면서 뒤에서 따라 다녀야 함
  ● Nonpreemptive scheduling (비선점)

Shortest-Job-First (1)

● Example: AWT = (3+16+9+0)/4 = 7 msec
– cf. 10.25 msec (FCFS)
● Provably optimal
● Not realistic; prediction may be needed: 가장 큰 문제는 비현실적임, 사실상 CPU 시간을 얼마나 사용할지 잘 모름. 컨텍스트 스위칭이 자주 일어나기 때문.

Process Burst Time (msec)
P1 6
P2 8
P3 7
P4 3

Shortest-Job-First (2)

• 도착 시간까지 고려
  ● Preemptive or Nonpreemtive
  – cf. Shortest-Remaining-Time-First (최소잔여시간 우선)
• 남아 있는 시간이 얼마나 되는지에 다름
  ● Example
  – Preemptive: AWT = (9+0+15+2)/4 = 26/4 = 6.5 msec
  – Nonpreemptive: 7.75 msec
  Process Arrival Time Burst Time
  (msec)
  P1 0 8
  P2 1 4
  P3 2 9
  P4 3 5

Priority Scheduling (1)

● Priority (우선순위): typically an integer number (일반적으로 정수값)
– Low number represents high priority in general (Unix/Linux) (숫자값이 낮은 것이 우선순위 임)
● Example
– AWT = 8.2 msec

Priority Scheduling (2)

● Priority (우선 순위 정하는 방법)
– Internal: time limit(짧은 시간), memory requirement(메모리 차지 용량), i/o to CPU burst(i/o 시간 또는 CPU 시간이 짧은 것), …
– External: amount of funds being paid, political factors(정치적 요소) , …
● Preemptive or Nonpreemptive
● Problem
– Indefinite blocking: starvation (기아/우선순위가 높은 프로세스가 자꾸 들어오면 자기 차례가 안 올수도 있음 - 실행될 수 없음) – Solution: againg (오래 머물고 있다면 우선순위를 조금씩 올려줌)

Round-Robin (1)

• 수건 돌리기처럼 돌면서 스케쥴링
  ● Time-sharing system (시분할/시공유 시스템)
  ● Time quantum 시간양자 = time slice (10 ~ 100msec) / 1초동안 10~100번 정도 스위칭
• 타임 퀀텀의 사이즈에 따라 시간의 결과가 다르게 나옴
  ● Preemptive scheduling
  ● Example
  – Time Quantum = 4msec
  – AWT = 17/3 = 5.66 msec

Round-Robin (2)

● Performance depends on the size of the time quantum

• 퀀텀을 어떻게 설정하느냐에 따라 성능이 완전히 달라짐
  – ∆ → ∞ FCFS
  – ∆ → 0 Processor sharing (* context switching overhead)
  ● Example: Average turnaround time (ATT)
• 반응 시간(turnaround time) : 들어가서 끝날 때가지 시간
  – ATT = 11.0 msec (∆ = 1), 12.25 msec (∆ = 5)
• 델타, 타임 퀀텀을 값을 결정하여 최적의 시간을 잡는 것이 중요함

Multilevel Queue Scheduling

● Process groups
– System processes (가장 긴급하게 처리해야 함)
– Interactive processes (게임, 대화하는 프로세스 / 대조적으로 반대의 예는 컴파일러)
– Interactive editing processes (예. 워드 프로세스)
– Batch processes (비대화형)
– Student processes
● Single ready queue → Several separate queues
– 각각의 Queue 에 절대적 우선순위 존재
– 또는 CPU time 을 각 Queue 에 차등배분
– 각 Queue 는 독립된 scheduling 정책 (round-robin, priority)

Multilevel Feedback Queue Scheduling

● 복수 개의 Queue
● 다른 Queue 로의 점진적 이동
– 모든 프로세스는 하나의 입구로 진입
– 너무 많은 CPU time 사용 시 다른 Queue 로
– 기아 상태 우려 시 우선순위 높은 Queue 로

프로세스 생성과 종료

Process Creation

● 프로세스는 프로세스에 의해 만들어진다! – 부모 프로세스 (Parent process) – 자식 프로세스 (Child process)

• 예. init 프로세스가 여러 다른 프로세스를 만들어냄 => 그 자식 프로세스가 또 다른 자식 프로세스를 만들어냄
  ● cf. Sibling processes
  – 프로세스 트리 (process tree)
  ● Process Identifier (PID)
• 맨 처음 만들어지는 것은 0
• process ID가 중복되지 않음
  – Typically an integer number
  – cf. PPID
  ● 프로세스 생성
  – fork() system call – 부모 프로세스 복사
  – exec() – 실행파일을 메모리로 가져오기

예제: Windows 7 프로세스 나열

예제: Ubuntu Linux 프로세스 나열

• ps(process status)

Process Termination

● 프로세스 종료

– exit() system call(종료를 하게 됨) – 해당 프로세스가 가졌던 모든 자원은 O/S 에게 반환
(메모리, 파일, 입출력장치 등)