[운영체제] Chapter 3: Process

[참고자료] [Operating System Concepts 에센셜] 저자(글) · Abraham Silberschatz, Peter Baer Galvin , Greg Gagne 번역 조유근, 박민규 , 고건

Chapter 3: Process

Multiprogramming

uni-programming

• 한번에 하나씩 실행하는 것
  • A의 실행이 끝나면 B의 실행 → B가 끝나면 C가 실행
• 3개의 프로그램 실행을 위해 메모리에 올려둔다. 프로그램실행(=CPU를 사용한다는 뜻)
  • A프로그램부터 실행 → CPU사용 → 입출력 (입출렬하는 동안 CPU는 사용하지 않음. CPU Idle) → 입출력 끝나면 CPU사용 → B프로그램 실행 → CPU → I/O (CPU idle) → CPU

Mulit-programming

• 실행 될 프로그램은 모두 다 메모리에
  • A가 입출력을 실행 할때 CPU사용권을 B에게 넘김, B의 입출력 시 CPU사용권을 C에게 넘김 → C의 입출력 상황 시 A,B둘다 입출력이 끝난 상태 → A에게 CPU사용권 넘김.
• Throughput (단위시간당 시행된 프로그램의 개수) : 생산성이 좋아짐.
• Utilization(CPU 활용도) : 그림에서는 전체 화살표중 굵은 화살표의 범위
• Degree of Multiprogramming : 동시 실행중인 프로그램의 개수 : 그림에서는 3

타임 쉐어링!

3.1 Process Concept

Batch system - job

time sharing system - user programs or tasks

job, process는 같은 의미다.

process

• 실행중인 프로그램
• 위의 그림에서 A,B,C는 프로세스지만 D는 아님.

Stack

• 프로그램 실행 도중 함수(파라미터, 복귀 주소, 지역변수) 등이 담겨져있다.
• 가변적이다.

heap

• “malloc” (동적 메모리 할당)
• heap 또한 가변적으로 변할 수 있음.
• heap, stack 이 충돌 할 수 있음

Data

• 전역 변수들

TEXT

• 프로그램 관련 코드

그렇다면 Process 전의 상태에서는 어떤 구성일까

• 전역변수인 text, data만 존재한다. stack, heap은 없다.

Process Concept(Cont.)

• 프로그램이 디스크(실행 파일)에 저장된 수동 엔티티이며, 프로세스가 활성화되어 있다.
• 실행 파일이 메모리에 로드되면 프로그램이 프로세스가 된다.
  • 한 프로그램을 3번 실행하면 프로세스틑 3개이다.
  • 텍스트는 동일하지만 (데이터, 스택, 힙)은 독립적으로 관리된다.

Process State

• new
  • 프로세스가 생성되고 있는 중을 뜻한다. (정식 프로세스는 아님) ↔ terminated
• ready
  • 프로세스가 프로세서(CPU)에 할당되기를 기다리는 상태.
• running
  • 프로세스가 동작하고 있는 상태
• waiting
  • 입출력 시작, 완료 되기를 기다리는 상태
• terminated
  • 실행은 끝났으나 아직 사라지지 않은 상태.

Diagram of Process State

new → ready (admitted) → Long term scheduler가 관리.

ready → running (Scheduler Dispatch)

• 운영체제가 프로세스에게 CPU를 할당해준다.

running → waiting (I/O or event Wait = SystemCall) 시스템 콜에 의해 Waiting으로 바뀐다.

• 프로세스가 입출력을 할 때

Waiting → ready (I/O or event comlietion)

• 입출력이 끝나면 다시 ready 상태로 간다.

Waiting 상태의 프로세스는 입출력 interrupt를 기다림(해당 장치로부터 interrupt 신호가 올때까지) → interrupt 처리함수 실행.

running → ready (interrupt)

• 타임 쉐어링 시스템의 경우 한번에 cpu를 짧게 쓴다.
  • 타임 쉐어링 시스템이지만 CPU를 길게 쓸 경우 강제로 누군가의 CPU를 뺏는다.
    • Timer interrupt : 독점 방지를 위해 (제한시간까지 CPU를 독점 사용), 뺏긴 프로세스는 waiting 상태.

running → terminated(exit())

• 종료 시스템 콜인 exit() 로 종료한다.

running은 3가지 상태가 가능하다.

• Waiting : 입출력
• Ready : CPU 뺏기기
• terminated : 종료

Process Control Block(PCB)

• 운영체제가 사용하는 자료구조
• 한 프로세스에 대한 모든 정보, 프로세스 당 하나씩 PCB가 있다.
• 프로세스 생성 시 PCB 생성, 종료시 삭제.
• Process state(앞의 running, waiting)등 기록
• Process ID : 프로세스 식별번호(고유 정수값)
• Program counter : cpu 레지스터 중 pc(현재 실행주소)의 복사본, 프로세스 상태가 running이 아닌 경우에만
  • Running이 아닌 상태는 가장 최근의 레지스터 값을 PCB에 저장한다
• CPU,scedugling information
• Memory management information(프로세스가 할당받아서 쓰는 메모리 위치이름)
• Accounting information : 자원 사용 기록(cpu사용시간, 각종 자원 사용한도)
• i/o status informain : 입출력 상태에 대한 모든 정보

Process Representation in Linux

• linked list형태로 각 프로세스 하나당가지고 있음.
• current: 현재 실행 중인 프로세스(Running) 를 가리키는 PCB 포인터
• pid - process id
• 스케쥴링정보
• *parent : 현재 pcb프로세스의 부모
• chlidren : 연결리스트 형태로 현재 pcb의 자식 프로세스
• *mm 메모리상에서 차지하고 있는 공간에 대한 필드
• *file : 프로세스가 사용중인 open files

3.2 Process Scheduling(=cpu scheduling, time sharing)

cpu를 멈추지 않고 사용하기 위해서.

• 프로세스 스케쥴링
  • 다음번 cpu사용 프로세스를 결정하는 일.
• 프로세스 스케쥴러
  • CPU에서 다음 실행을 위해 사용 가능한 프로세스 중에서 선택

Ready queue(레디 큐)

• 레디 상태의 프로세스들이 있다.
• 프로세스 스케쥴러는 Ready queue를 보고 다음번 실행 프로세 스를 결정하면된다.
  • Ready queue와 linked list의 pcb로 이루어져 있다.

Device queue(waiting 상태)

• 해당 디바이스의 입출력을 실행하고 입출력이 끝나기를 기다리고있다.
• 즉 상태가 Waiting인 프로세스를 의미한다.
• Ready queue는 하나지만 Device queue는 장치마다 있다.

JOB queue(모든 프로세스, ready, device에 중복가능)

• 시스템에 있는 모든 프로세스.
• job 큐에 있으면서 Ready, Device에 있는것은 가능하다.

큐가 있고 각 큐의 head,tail은 pcb의 시작과 끝을 가르키고 있다. pcb는 linked list형태.

Schedulers

• 스케쥴러는 총 3가지이다.
• 스케쥴러는 스케쥴링 큐를 보고 결정한다.(레디큐, 디바이스큐, 잡큐)
  • Short-term scheduler
  • Long-term scheduler
  • Medium-term scheduler
• Short-term scheduler(레디큐에서 동작 →running으로 만드는)
  • 다음번 실행 프로세스을 걸정하여 cpu할당한다. 한다.
  • 작은 시스템에서는 유일한 스케쥴러 일수도있다.
  • ready queue중에서 누구를 실행 시킬지 결정하는 일(Scheduler dispatch)을 한다.
    • ready → running
  • 비교적 자주, 가장 빈번히 실행되기 때문에 Short-term이라고 한다.
  • ms 단위

• Long-term scheduler(new 에있는 것을 redey (admitted) 동작)

  • 잡 스케쥴러라고도 한다.

  • 롱 텀 스케쥴러은 현재 시스템에 있는 NEW 상태의 프로세스 중에서 정식 프로세스를 선택 하는 일을 ㅎ나다.

    • New : 프로세스가 생성중인 단계, 정식 프로세스는 아닌 상태

  • 롱 텀 스케쥴러 ( new → ready) 할 때 Degree 는 1 증가한다.

    Degree of multiprogramming

    • 컴퓨터 시스템의 부하를 나타냄.
    • D o m 이 1000이다. ? 부하가 1000이다.

  • short-term 스케쥴러보다는 빈번하지 않다. (seconds, minutes)

• CPU- bound process

  • CPU bound가 많으면 입출력 장치 디바이스큐(waiting) 는 비게 된다.

• I/O bound process

  • i/O bound가 많으면 레디큐(Ready)가 비어서 cpu스케쥴러가 할일 이 적어진다.

비교

요소	I/O Bound	CPU Bound
주요 특징	입출력 작업이 많음	CPU 사용이 우선
작업 유형	파일 입출력, 네트워크 통신 등	계산 집중적 작업, 대용량 데이터 처리 등
대표적인 예시	파일 읽기/쓰기, 데이터 전송/수신	수학적 연산, 알고리즘 실행 등

Medium-term scheduler

일부 프로세스를 스왑 디바이스라고 부르는 디스크 영역으로 내쫓는 역할을 한다.

프로세스 수가 너무 많을 때, 메모리 영역이 부족하기 때문에.

프로세스를 디스크로 내쫓음으로써 Degree(부하)를 감소시키는 효과가 있다.

일반적인 동작으로는 ready → running (scheduler dispatch)를 통해 레디큐에서 cpu에 할당하게 되는데 이 이후 waiting을 돌아갈 때 waiting은 cpu를 사용하지 않기 때문에 스와핑하는 유력후보이다.

숏텀 스케쥴러 (3가지 큐를 이용하여 조절. 레디큐, 디바이스큐, 잡큐) cpu할당 조절.

롱텀 스케쥴러 (new → ready로 i/o bound process, cpu bound process양 조절.)

미디엄 텀 스케쥴러 (ready queue → CPU 후 waiting 상태로 갈때 메모리에서 디스크로 스와핑)

CPU Switch From Process to Process

P0 가 System call or interrupt 발생 시킨다. → 다음번 실행을 위해 자신의 상태를 PCB에 저장한다. → . . . 다음번 실행할 프로세스를 결정하는 일(Short-term scudeler) → 새로운 프로세스의 레지스터를 가져와서 실행한다. → 나중에 다시 저장되어있던

context switch

• 스위칭 한번에는 저장하고 복원하는 것이 한쌍이다.
• 이 그림에서는 스위칭이 2번 일어난다.
  • 컨텍 스위치를 빨리 해야하고, 일정한 구간을 놓고 봤을때 가급적이면 전체 컨텍스위치 횟수가 적은게 좋다.
• CPU가 다른 프로세스로 전환될 때, 시스템은 이전 프로세스의 상태를 저장하고 새 프로세스를 위해 저장된 상태를 로드해야 함
• 프로세스의 문맥은 PCB에 표시됨
• 문맥 전환 시간은 오버헤드임. 시스템은 전환하는 동안 유용한 작업을 수행하지 않음
  • 따라서 짧고 신속하게 하는 것이 굉장히 중요.
• OS와 PCB가 더 복잡할수록 문맥 전환 시간이 길어짐
• 시간은 하드웨어 지원에 따라 다름
• 일부 하드웨어는 CPU당 여러 세트의 레지스터를 제공하여 한 번에 여러 문맥을 로드함

3.3 Operations on Processes

• 커널이 프로세스에 대해서 제공하는 연산이있다.
  • 프로세스 생성(fork())
  • 프로세스 종료(exit())
  • 종료와 관련된 대기.(wait())
• 기존 프로세스를 복제해서 새 프로세스를 만들 때 두 프로세스를 부모, 자식이라고 한다.
• 프로세스 트리를 이루게 된다.
• process identifier (pid)
  • 새로운 프로세스가 만들어지면 자신의 PID를 부여받는다.
• 자원 공유 옵션(대부분 OS는 2번)
  1. 부모와 자녀가 모든 자원을 공유
  2. 자녀가 부모의 일부 자원을 공유
     • 복제를 통해 자식을 만들면 자식은 자유롭게 실행, 부모는 자식의 실행이 종료될때까지 기다려야함.
  3. 부모와 자녀가 어떠한 자원도 공유 안함.

Process Creation

프로세스 생성

• 프로세스는 커널이 제공하는 생성 연산을 통해 생성가능하다.(시스템콜이라는 소리죠)

• parent process, child process 로 이루어진 트리가 형성된다.

• [init_process] 트리 최상단에 위치하며 부모가 없는 유일한 프로세스
  

  • 커널이 수작업으로 직접 init을 만든다. 이후에는 init을 부모로 해서 생성을 반복한다.

• 프로세스마다 부여된 pid로 식별한다.

• OS에 따라서 부모와 자식의 모든 자원 공유, 부모와 자식의 일부 공유

Process Creation

[프로세스 생성]

부모 자식간에 메모리 주소 공간을 어떻게 할까?

많은 운영체제에서는 부모의 메모리 주소 공간을 복제하여 자식의 주소 공간으로 사용한다.

• 부모와 동일한 가상 메모리인거죠

자식은 부모와 동일한 메모리 상 이미지를 얻게된다.

UNIX examples

1단계 fork() → 2단계 exec()로 이루어짐

• fork() system call
  • fork 실행하면 똑같이 복제 된다. 부모 ⇒ 자식
• exec() system call
  • 호출한 프로세스의 주소공간(메모리 할당 영역)을 시스템 콜에서 지정한 실행파일의 내용으로 교체.
  • 새 프로세스를 생성하는 시스템콜이 아니라 프로세스가 실행중인 코드를 교체하는 시스템 콜

[프로세스 종료]

exit() - 하나의 정수 파라미터를 가지며, 이값을 wait를 통해 부모에게 전달함.

exit()를 쓰면 운영체제에 의해 모든 자원이 회수된다.

abort() 는 비정상적 종료를 의미한다. exit()는 자식 본인이 하는 반면 abort()는 부모 프로세스가 강제 종료 시킨다.

• 자식의 자원 사용이 지나치게 많은 경우
• 자식의 수행 작업이 필요 없는 경우
• 부모가 exit()먼저해서 자식만 남는걸 허용하지 않을때

---

pid → 세 프로세스의 아이디 정의

pid = fork() → fork()를 사용해서 자식 생성, 프로세스가 1개→2개 포크가 리턴하는 시점 이미 생성.

if (pid < 0) → pid 음수인경우 fork() 실패, 자식생성실패.

if pid == 0 → 자식 생성 성공. exec()으로 자신의 할당 메모리 공간을 bin/ls 프로그램 코드로 교체.

else : → else이기 때문에 pid가 양수이면 부모 프로세스를 의미. wait(NULL) 기다리긴 하는데 NULL이니깐 자식의 상태와는 상관없이 기다리면서 자식의 동작이 끝나면 자식의 exit()와는 상관없이 동작함.

win32 코드

si (윈도우 크기 등 새 프로세스의 특성을 갖음)

pi (새 프로세스의 pid = process id)

/* create child process *

새로운 프로세스를 생성하고 새로운 프로세스가 새로운 프로그램을 실행하게 하는 윈 32 함수이다.

앞서 fork(). exec()을 분리하지않고 두기능을 하나의 함수로 쓴다.

자식 프로세스는 파라미터에 있는 mspaint를 실행하게 된다.

/* parent*

WaitForSingleObject (자식의 종료를 기다린다.)

Process Termination

일부 운영체제 에서는 자식만 존재하는 것을 허용하지 않는다.

cascading termination

• 한 프로세스 종료 시점에서 자식이 존재할때 하위 트리 상 모든 프로세스 강제 종료 해야한다.

wait() - 부모프로세스는 자식의 프로세스를 기다란다.

• wait ()의 리턴값은 자식의 pid 이다.

terminated 상태 - exit()를 의미하고, 부모의 wait()함수의 리턴되면 완전히 소멸된다.

pid = wait(&status); 이 값을 통해 자식의 정확한 종료 상태를 알 수있다.

Zombie process

• 자식이 exit 했지만 부모가 wait 안할때 자식 프로세스는 좀비

Orphan

• 자식이 exit하기전에 부모가 먼저 exit 할때 자식 프로세스는 Orphan

3.4 Interprocess Communication

IPC

• 프로세스는 독립적이면서 cooperating(상호작용) 다른프로세스에 영향을 끼친다.
• cooperationg
  • 정보공유
  • 작업나누기
  • 모듈화 시스템
  • 편리함
• Cooperating 프로세스는 IPC가 필요하다.
• IPC는 2가지
  • shared memory
  • message passing

Interprocess Communication – Shared Memory

• 두 프로세스 의 공유되는 메모리 공간

• 통신은 A가 가지고 있는 것을 B로 전달하는 과정이다.

  • A가 전달하고자 하는 데이터를 shared memory 에 쓰기,

    B가 읽고자 하는 데이터 shared memory 읽기.

공유 메모리 공간을 만들때 커널이 관여, 통신에는 커널 관여 x

통신과정은 프로세스 통제로 함.

shared memory는 동기화가 필수이다.

Producer-Consumer Problem

“프로세스 동기화 문제와 연관된 문제”

생산자 소비자 문제이다.

• unbounded buffer
  • 공유 버퍼의 크기 제한없는것
• bounded buffer
  • 공유 버퍼의 크기가 제한 있는것
  • shared memory 기법은 제한이 있는 경우에 해당한다.

Bounded-Buffer – Shared-Memory Solution

링버퍼 는 공유 메모리공간에 있는 저장 형태이다.

생산자 A프로세스는 링버퍼에 쓴다. , 소비자 B프로세스는 링버퍼에서 읽는다.

in - 생산하는 위치, 생산 후 다음 번 데이터 아이템을 가르키도록 조정

out - 소비자 가 읽는 위치, 읽고 난 후 다음 번 데이터 아이템을 가르키도록 조정

Bounded-Buffer – Producer and Consumer

"""Producer"""

item next_produced;

while (true) {

/* produce an item */

while (((in+1)%BUFFER_SIZE)==out) ; //버퍼가 비워질 때(소비자) 
	
	/* do nothing */
	buffer[in] = next_produced; // -> next~~ 는 데이터를 의미.
	in = (in + 1) % BUFFER_SIZE; // (in + 1) 다음번, 링버퍼의 나머지 연산을 통해 역으로 갈 수 있도록
 }

생산자 프로세스가 소비자 프로세스의 동기화

• 소바자 프로세스가 버퍼에서 꺼내서 읽는 동작을 기다려야한다 → while문

""""consumer""

item next_consumed;

while (true) { // in의 값이 달라 질 때 달라짐. 소비자는 생산자 값을 기다림.
while (in == out)
; /* do nothing */ 

next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item */ }

자신의 동작 전에 상대편 프로세스의 동작을 whilie문 조건으로 달아 동기화 하는 과정을 포함한다.

Interprocess Communication – Message Passing

“메모리를 공유하지 않고 소통 가능”

“커널영역의 큐를 생성하여 소통”

“unbounded buffer”

• 커널 내부에 있는 메세지 큐를 통해 통신
  • 커널에 큐를 만들라고 요청.
• 프로세스 A는 메세지 큐에 메세지 넣기, 프로세스 B는 큐에서 꺼내가기
• 두 프로세스가 공유하는 공간과 무관하게 (유저 공간에서 공유하는 것이 없다.) 통신하는 방식이다.
• IPC facility provides two operations:
  • send(message)
  • receive(message)
• 메세지는 고정크기일수도 있고, 가변크기 일수도 있다.

커널안에 공간을 사용 = 메세지 패싱, 메모리 영역 사용 = shared memory

Direct Communication

• 통신 대상을 지정하는 것
• Send
  • (P, message) - P에게 메세지해라.
• Recieve
  • (Q, message) - Q로부터 받아라.
• 두 프로세스 간에만 통신을 할 수 있음. (명시적인 대상이 지정 되어 있기 때문에)
  • 단방향
  • 양방향 send(Q,message) receice(p,message) send(P,message) receive(Q,message)

Indirect Communication

“Direct Communication과 다르게 양방향 통신이 가능하다.”

“공통 mailbox(=port 라고도함)를 갖으면 다자간 통신, 한프로세스간 여러 링크가 가능하다”

P와 Q는 또 다른 링크를 통해 주고 받을 수 있다.

Send(A,message) - 통신하는 프로세스를 지정하는 것이 아니라 메일 박스를 지정한다.

receive(A,message)- 메일박스 지정

• 연산방법
  • 메일박스 생성 create mailbox(port)
  • 송수신 send, receive
  • 메일박스 제거 destroy
• Mail box sharing
  • p1,p2,p3가 mailbox를 공유하고있을때 p1.send(mailbox)하면 누가 받을까?
    • p1과 연관된 프로세스가 누구인지에따라
    • 1번에 1번만 receive 할때, p2,p3중 먼저 성공한 프로세스
    • 시스템이 임의로 결정후 p1에게 누가 받았는지 통보

Synchronization(동기화)

Synchronization(동기식)

• Blocking 방식을 사용
  • Blocking send
    • 메세지가 수신될 때까지 송신 프로세스가 대기하는 방식(waiting 상태)
    • 수신이 완료 되어야 다음 동작
  • Bloking receive
    • 메세지가 도착할때까지 수신 프로세스가 대기하는 방식(waiting 상태)
    • 수신 될때까지 기다렸다가 다음 동작

비동기식

• Non Blocking
  • Non Blocking send
  • Non Blocking receive

경우에 따라 4가지 조합이 가능하다.

Blocking send, Blocking receive를 사용하는 것을 랑데뷰 라고함.

Buffering

“송신측 송신직후부터 수신완료 까지 중간 이동 메세지를 임시저장(주고받는중의 메세지 임시저장)”

message queue의 입장에서는 3가지 경우

• zero capacity
  • 송신측이 수신측을 기다릴때 ! 즉 blocking (랑데뷰) 방식에서는 메세지 담아 놓을 필요없음 ! 버퍼링 필요없어.

• bounded capacity

  • 버퍼링 공간에 제한이 있다.

  • 큐에 n개의 메세지까지 저장할 수 있어서 큐가 가득 차면 송신측은 링버퍼처럼 기다리게 된다.

• unbouded capacity
  • 큐길이 제한이 없어서 송신측은 기다릴필요없이 계속 보내도된다.

동작 과정

먼저 메모리 부터 보면 프로세스(p1,p2,p3) + 커널 = 총 4개의 프로그램 진행중

(1) p1 execution 실행

(2) 입출력 요청 발생 ! system call! (waiting상태로 context switch가 일어나며 디바이스 큐로 간다.)

커널의 pcb에 자신의 레지스터 값저장.

(3) schedular dispatch (ready큐에 있는 프로세스중 cpu schedular=short term에 의해 cpu할당 이때, pcb의 레지스터값 cpu에 복사

(4) p2실행