OS) Chapter 3. Processes

Chapter 3. Processes

Process Concept

-       Operating System은 program의 종류들을 실행시킨다. (Batch system – jobs, Time-shared systems – user programs or tasks)

-       Process – 실행중인 program을 말함. (System에 load된 program)

-       Multiple parts

n  Text Section: Program code (Program Counter를 포함한 현재 activity, processor registers)

n  Stack: Containing temporary data (Function parameters, return addresses, local variables)

n  Data Section: Containing global variables

n  Heap: Containing memory dynamically allocated during run time

Process State

-       new: Process가 생성됨

-       running: Instruction이 진행중임

-       waiting: event나 I/O occurrence를 기다리는 중임

-       ready: processor에 assign되는 데에 있어 기다리는 중임

-       terminated: process가 execution을 끝냄

Process Control Block (PCB) : 각 Process들의 정보들의 집합체이다.

-       Process state – running, waiting, etc

-       Program Counter – location of instruction to next execute

-       CPU registers – contents of all process-centric registers

-       Etc..

CPU Switch from Process to Process

Threads: Process has a single thread of execution

-       만약 각 process마다 복수의 program counter를 갖고 있다면, 한 번에 다양한 location이 실행 가능하다.

Process Scheduling

-       CPU 사용을 극대화하여, time sharing을 위해 CPU상의 processes들을 빠르게 switch하여야 한다.

-       Process scheduler는 사용 가능한 process들 중에서 CPU에서 다음 execution에 사용될 process를 선택한다.

-       Process의 scheduling queue를 유지한다.

n  Job queue – 시스템의 모든 process들을 설정한다.

n  Ready queue – 실행되길 기다리는 main memory에 남아있는 모든 process들을 설정한다.

n  Device queue – I/O device를 기다리는 process들을 설정한다.

위의 그림에서 ready queue는 main memory에서 실행되는 것을 기다리는 process들의 집합체이고, 나머지는 device queue로써 I/O device의 요청을 기다리는 process들을 말한다.

이들을 합쳐 Job Queue라고 부른다.

Representation of Process Scheduling: ready queue, device queue로 대표된다.

-       새로운 process는 초기적으로 ready queue에 들어간다. 그 후 그것이 execution이 되거나 dispatch(준비 리스트의 맨 앞에 있던 프로세스가 CPU를 점유하게 되는 것, ready -> running)가 될 때까지 queue에서 기다린다.

-       프로세스가 CPU에 할당되어 실행이 될 때 몇 가지 event들이 발생할 수 있다.

n  Process가 I/O 요청을 하여 I/O queue로 배정될 수 있다.

n  Process가 새로운 child process를 만들어 child의 termination의 종결을 기다릴 수 있다.

n  Process가 interrupt 결과와 같이 CPU로부터 강제적으로 제거될 수 있는데, 이 때, Ready queue로 다시 돌아간다.

Schedulers

-       Short-term scheduler (or CPU scheduler): 다음에 실행될 process를 선택하고 CPU에 할당한다.

n  가끔 system에서 존재하는 유일한 scheduler이다.

n  Short-term scheduler는 millisecond 단위로 매우 빠르게 호출되어야 한다.

-       Long-term scheduler (or Job(시간에 따른 process 일괄 처리) scheduler): 어떠한 process들을 ready queue로 가져올지 결정해야만 한다.

n  Long-term scheduler는 즉시 불러오지 않아도 된다.

n  Long-term scheduler는 multiprogramming의 degree를 제어한다.

-       Medium-term scheduler: multiprogramming의 degree를 줄여야 할 필요가 있으면 medium-term scheduler가 더해지기도 한다: memory로부터 process를 제거하고, disk에 저장하고 연속적인 실행을 위해 disk로 돌아가기도 한다 (Swapping)

Context Switch

-       CPU가 또 다른 process로 넘어갈 때, context switch를 통해 old process의 상태를 저장하고, 새로운 process의 저장된 상태를 불러들인다.

-       PCB에서 표현된 process: Context

-       Context-switch time이 overhead이기 때문에 switch하는 동안 유용한 일을 하지 않는다. (보다 복잡한 OS와 PCB에서 보다 긴 context switch가 사용된다.)

-       Hardware support에 시간 의존적이다.

Operations on Processes

Process Creation

-       Parent process는 process tree를 형성하며 다른 process로 전환하는 children process를 생성한다.

-       보통 process는 process identifier에 의하여 identify되고 관리된다.

-       Resource sharing option

n  부모와 자식은 같은 resource를 공유할 수 있다.

n  자식은 부모 resource의 일부만 공유할 수도 있다.

n  자식과 부모간에 공유하는 resource가 존재하지 않을 수도 있다.

-       Execution options

n  부모와 자식은 병렬적으로 실행될 수 있다.

n  자식이 종결될 때까지 부모가 기다릴 수 있다.

Process Termination

-       Process는 last statement를 실행시키고, OS에 exit() system call을 이용하여 그것을 삭제할 것인지 묻는다.

n  자식으로부터 부모에게 상태 data를 return한다.

n  Process의 resources를 OS에 의해 해제시킨다.

-       Parent는 abort() system call을 이용하여 자식 process의 실행을 종결시킨다. 실행이 종결되는 경우는 다음과 같다:

n  자식이 할당받은 resource를 초과할 때

n  자식에게 assign된 task가 더 이상 필요하지 않을 때

n  OS가 부모가 종결되더라도 자식에게 계속 실행되라고 하지 않을 때, 부모가 종결될 경우

-       몇몇 OS는 부모가 종결되더라도 자식이 존재하는 것을 허락하지 않는다. Process가 종결되더라도 그 자식들은 또한 무조건 종결되어야 한다.

n  Cascading termination: All children, grandchildren, etc. are terminated.

n  OS에 의해 종결이 시행된다.

-       부모 process는 wait() system call을 이용하는 것으로 자식 process의 종결을 기다린다. 그 call은 상태 정보와 종결된 process의 pid를 return한다.

-       만약 기다리는 부모 process가 없다면 zombie라고 부르고, wait 호출 없이 부모가 종결되면 orphan이라 부른다.

-       Zombie process: 자식이 종결될 때의 상태를 부모가 받아야 하는데, 부모가 wait() 호출이 없을 경우 그 자식 process는 상태를 전달할 때까지 잠시 떠도는 데, 이 process를 zombie process라 한다.

-       Orphan(고아) process: 자식이 종결되기 전에 부모가 먼저 종결되어 상태를 전달할 곳이 없는 process. 부모가 종결될 경우 PID가 1(init)로 변경되기 때문에 시스템에서 추적을 하여 종결시키기 때문에 성능저하를 불러들이킬 수 있음

-       pid = wait(&status)와 같은 wait() system call 함수를 사용하여야 memory 상에서 남아있는 child process state information을 삭제할 수 있지만, zombie process같은 경우 pid = 1도 아니고 wait() 함수를 불러들이지도 않기 때문에 memory 상에 잔여 찌꺼기가 남아있음.

Interprocess Communication (IPC)

-       System내에서의 process는 independent하거나 cooperating한다.

-       Cooperating process들은 공유 데이터를 포함하여 다른 process에 의해 영향을 받거나 영향을 끼친다.

-       Cooperating process를 위한 이유는 다음과 같다: 1) 정보 공유 2) 계산 속도 향상 3) 모듈성 4) 편리성

-       Cooperating process는 process간 communication인 IPC를 필요로 한다.

-       IPC의 두 모델: Shard memory, Message passing

Producer-Consumer Problem: Producer는 information을 생성하고, Consumer는 정보를 소비한다.

-       Unbounded-buffer는 버퍼의 사이즈에 제한없이 놓는다.

-       Bounded-buffer는 fix된 buffer size에 놓는다.

Bounded-Buffer (Shard-Memory Solution) (Circular Queue => Buffer_size – 1 elements만 사용할 수 있음)

IPC – Shared Memory

-       서로 communicate하길 원하는 process들은 memory 지역을 서로 공유한다.

-       Communication은 OS가 아닌, user process의 제어 아래서 진행된다.

-       Major issue는 user process들이 shard memory에 접근할 때 그들의 행동을 동기화하도록 하는 mechanism을 제공하는 것이다.

IPC – Message Passing

-       Processs들의 행동을 동기화하고 communicate하기 위한 mechanism이다

-       공유된 variable을 재정렬하지 않고 process들을 communicate할 수 있다.

-       IPC 기능은 두 가지 operation을 제공한다: send(message), receive(message)

-       Message 사이즈는 고정되거나 variable이다.

-       프로세스 P와 Q가 communicate하기를 원할 경우:

n  그들 사이에 communication link를 생성한다.

n  Send/receive를 통해 message를 교환한다.

Direct Communication

-       Process는 explicitly하게 서로 naming을 해야한다.

n  send (P, message): send a message to process P

n  receive (Q, message): receive a message from process Q

-       Properties of communication link

n  Link는 자동으로 설정된다.

n  Link는 정확히 communicating하는 process의 한 쌍만 associated된다.

n  각각의 pair는 정확히 하나의 link만 나타난다.

n  Linke는 단방향성일 수도 있지만, 보통 양방향성이다.

Indirect Communication

-       Messages는 mailbox로 송신되고 수신된다. (일종의 port로써 referred됨.)

n  각각의 mailbox는 unique한 id를 갖고 있는다.

n  Process들은 만약 그들이 mailbox를 공유하고 있을 때에만 communicate할 수 있다.

-       Operations

n  새로운 mailbox (port)를 만든다

n  Mailbox를 통해 message를 주고 받는다

n  Mailbox를 파괴한다.

-       Mailbox sharing problem (one sender, two receivers)

n  최대 두 개의 process만 link를 설정해야만 한다.

n  한 time에 오직 하나의 process만 receive할 수 있게 해야만 한다.

n  Sender가 receiver가 누구인지 가리켜 receiver를 선택해야한다.

Synchronization

-       Message Passing은 blocking이나 non-blocking 종류이다.

-       Blocking은 synchronous(동기화)를 고려한 것이다.

n  Blocking send같은 경우 message를 받을 때까지 sender를 block하는 것

n  Blocking receive같은 경우 message 사용이 가능할 때까지 receiver를 block하는 것

-       Non-blocking은 asynchronous를 고려한 것이다.

n  Non-blocking send: sender가 message를 보내고 계속 진행한다.

n  Non-blocking receive: receiver는 valid message를 받거나 null message를 받는다.

이는 Receiver가 받을 것이 없는데도 메시지를 요청하거나 receiver가 message를 받지 않았음에도 sender가 message를 보내는 것을 방지하기 위한 기법이다.

만약, send와 receiver가 모두 block되어 있는 상황이면, rendezvous라고 부른다.

Buffering

-       Message의 Queue는 link와 붙어 있다.

-       이는 세 가지 중 하나의 상태로 implement된다.

n  Zero Capacity – link에 queueing되어 있는 message가 없는 상태. (Sender는 receiver를 위해 기다려야만 한다.)

n  Bounded Capacity – n개의 message의 유한한 길이. Sender는 link가 꽉 차있으면 기다려야만 한다.

n  Unbounded Capacity – Sender가 절대 기다리지 않는 무한한 길이

3.1 Line A에서의 Output은 무엇인가?

Parent Process와 Child Process간 Communication이 없기 때문에 data 정보를 나누지 못하기 때문에 parent process의 value는 그대로 5다.

3.2 Initial parent process를 포함하여 얼마나 많은 process가 program에 의해 생성되는가?

8개

(fork() system call이 실행되고 나서, 해당하는 child process는 다음 system call() instruction의 다음instruction부터 수행)

3.5 process가 fork() operation을 이용하여 새로운 process를 생성했을 때, parent process와 child process사이에 어떠한 상태가 공유되는가?

오직 shared memory segment만 공유된다. Stack과 heap은 새로운 process에서 복사되는 것일 뿐이다.

3.9 두 개의 process사이에서 kernel에 의해 context-switch가 일어날 때 어떠한 action이 발생하는가?

1) Clock interrupt에 반응하여 OS는 현재 진행중인 process의 Program counter와 user stack pointer를 저장하고 kernel clock interrupt handler에 제어 전달

2) clock interrupt handler가 process PCB에 있는 나머지 정보들 저장

3) scheduler에 다음 실행할 process 요청

4) OS가 해당하는 process의 pcb를 받아 다음 process의 state를 펼치고, register를 재저장함.