[ OS ] 03. Processes

🖥️ Overview

• Process = program in execution + resource

Process State

• New: being created
• Running: in execution
  - Only one process can be running on a processor at any time
• Ready: waiting to be assigned to a processor
• Waiting: waiting for some event to occur
• Terminated

Ready / Running State

⭐️ Process Control Block (PCB)

• OS manages processes using PCB : Tree Structure
  - Process Control Block (PCB): repository for any information about process ( like 주민등록등본 )

---

🖥️ Process scheduling

• Scheduling: assigning tasks to a set of resources
  본질 : Select
• Process scheduling: selecting a process to execute on CPU
  - Only one process can run on each processor at a time
  - Other processes should wait
• Objectives(목표) of scheduling
  - Maximize CPU utilization(활용) : 가능하면 많이 일하게
  - Users can interact(교류) with each program
• Switching :
  - performance 관점에서는 적게할수록 ⬆️
  - responsive(반응) 관점에서는 많이할수록 ⬆️ Ex_ 로봇, 자율주행

Scheduling Queue

• Scheduling queue: waiting list of processes for CPU time or other resources
  - Ready queue, job queue, device queue
• Each queue is usually represented by a linked list of PCBs

Queueing Diagram

• Representation of process scheduling
  - A process migrates(이동) among various scheduling queues throughout its lifetime

Schedulers

• Scheduler selects processes from queues in some fashion(방법)
  - Long-term scheduler (job scheduler)
  - Short-term scheduler (CPU scheduler)

1. Short-term scheduler (CPU scheduler)

• 알고리즘 자체가 단순할 수 밖에 없다 → 워낙 자주 호출되기 때문
  - Executed frequently (at least once every 100 msec.).
  - Scheduling time should be very short.

2. Long-term scheduler (job scheduler)

• 레디큐의 사이즈를 조절하는 역할, 가끔씩만 돌아서 사이즈 조절을 하면 된다
• Controls degree of multiprogramming (레디큐의 사이즈)
  - In stable state, average process creation rate == average process departure(이탈) rate
• Executed less frequently
  - Executed only when a process leaves the system
• Hopefully, long-term scheduler should select a good mix of I/O-bound and CPU-bound processes
  - Vim, word, cmd - I/O bound processor : I/O에서 시간을 많이 쓰는 프로세서
  - Compiler, 동영상 인코더 - CPU bound processor
  
  
• In some systems, long-term scheduler may be absent(없거나) or minimal ➡️ 가장 많이 사용
  Ex) UNIX, Windows
  - System stability(안정성) depends on physical limitation or self-adjusting nature of human ( 불필요한 프로그램을 사용자가 끈다 )
• Some time-sharing system has medium-term scheduler
  - Reduce degree of multiprogramming by removing processes from memory

Context Switch

• Switching running process requires context switch
  - Save state (context) of current process (PCB)
  - Restore state (context) of the next process
• Context switch: the computing process of storing and restoring the state (context) of a CPU such that multiple processes can share a single CPU resource
• Context includes
  - Register contents
  - OS specific data
  • Extra data required by advanced(고급) memory-management technique
    Ex) page table, segment table, ...
• When to switch?
  - Multitasking
  - Interrupt handling
  
  
• 둘다 널리 쓰이진 않음
• Context switching requires considerable(상당한) overhead
• H/W supports for context-switching
  - H/W switching (eg. single instruction to load / save all registers)
  cf. However, S/W switching can be more selective(선택적) and save only that portion(부분) that actually needs to be saved and reloaded
  - Multiple set of register for fast switching
  Ex) UltraSPARC

---

🖥️ Operations on processes

Process creation

• Create-process system call
  - Creates a process and assigns a pid (process ID)
• Process tree
  - Parent-child relation between processes

Process Creation on UNIX

• fork(): create process and returns its pid
  - In parent process, return value is pid of child
  - In child process, return value is zero
  • Error, return negative value
• exec() family: execute a program.
  The new program substitutes(대체) the original one
  - execl(), execv(), execlp(), execvp(), execle(), execve()
• wait(): waits until child process terminates

Example of Process Creation

More About fork()

Resource of child process

• Data (variables): copies of variables of parent process - Child process has its own address space
  - The only difference is the pid of child returned from fork().
• Files
  - Opened before fork(): shared with parent
  - Opened after fork(): not shared

More About exec Family

• Functions in exec family (declared in <unistd.h>)
  - int execl(const char *path, const char *arg0, ..., const char *argn, char * NULL → 마지막을 의미); → l : list
  - int execv(const char *path, char *const argv[] → 마지막은 NULL); → v : vector
  - int execlp(const char *file, const char *arg0, ..., const char *argn, char * NULL); → p가 붙으면 Path 자동검색
  - int execvp(const char *file, char *const argv[]); → p가 붙으면 Path 자동검색
  - execle(), execve() : envirionment 다음에 설명

More About wait()

pid_t wait(int *stat_loc);

• stat_loc : an integer pointer
  - If state_loc == NULL, it is ignored
  - Otherwise: receives status information from child process
  • wait(&stat); // in parent process
  • exit(code); // in child process
  • code → stat 전달
    - code == (stat >> 8) → parent에서 복원 & 0xff
• Return value of wait
  - pid of the terminated child
  - -1 means it has no child process

Process Creation in win32

• CreateProcess()
  - Similar to fork()(+exec()) of UNIX, but much more parameters to specify properties of child process
• WaitForSingleObject() → Process or Thread
  - Similar to wait() of UNIX
• void ZeroMemory(PVOID Destination, SIZE_T Length );
  - Fills a block of memory with zeroes.

process termination

• Normal termination
• exit(int return_code): invoked by child process
  - Clean-up(정리) actions
  • Deallocate memory
  • Close files
• return_code is passed to parent process
  - Usually, 0 means success
  - Parent can read the return code

int status = 0;
wait(&status); // wait until the child is terminated. 
ret = WEXITSTATUS(status); // return_code from the child

Multiprocess Architecture – Chrome Browser

• Many web browsers ran as single process
  - If one web site causes trouble, entire browser can hang(중단) or crash
• Google Chrome Browser is multiprocess with 3 different types of processes:
  • Browser process manages user interface, disk and network I/O
  • Renderer process renders web pages, deals with HTML,
    Javascript. A new renderer created for each website opened
    - 렌더러 프로세스는 웹 사이트를 구성하는 HTML 및 CSS 코드를 구문 분석하고, 페이지에 포함된 JavaScript 코드를 실행하는 역할
  • Plug-in process for each type of plug-in
• 브라우저에서 열린 각각의 탭이나 창마다 해당 웹 사이트를 처리하는 고유한 렌더러 프로세스가 생성. 이는 여러 개의 탭이나 창을 열었을 때, 각각의 웹 사이트가 독립된 환경에서 실행되도록 하여 하나의 웹 사이트에서 발생한 문제가 다른 웹 사이트에 영향을 주는 것을 방지

---

🖥️ Inter-Process Communication (IPC)

• Goal of IPC: cooperation(협력)
  - Information sharing → Shared file, ...
  - Computation speedup → Multiple CPU or I/O
  - Modularity → Dividing system functions
  - Convenience → Editing, printing, compiling in parallel
• IPC models
  - Message passing model
  - Shared-memory model

Shared-memory Systems

• Shared-memory segment
  - Special memory space that can be shared by two or more processes.
  - Form of data and location is determined by those processes, not OS
  • Processes should avoid simultaneous(동시) writing by themselves
  • Advantage
    - Fast
    → Suitable(적합) for large amount of data
• Ex) producer-consumer problem

Producer-Consumer Problem

• Producer and consumer communicate information (item) through shared memory
  - Producer: produce information for consumer
  - Consumer: consume information written by producer
  Ex) compiler – assembler, server – client
  - Note! Producer and consumer should be synchronized
  → Discussed in chapter 6
• Unbounded buffer (사이즈 무한)
  - No practical(실질적인) limit on buffer size
  - Producer can always produce
• Bounded buffer
  - Producer must wait if buffer is full.
  - full condition : producer wait
  - empty condition : consumer wait

Producer-Consumer Problem using Bounded Buffer

• Representation of buffer
  - Buffer is represented by circular queue

#define BUFFER_SIZE 6
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0; // tail or rear 
int out = 0; // head or front

• Empty / full condition
  - Empty : in == out
  - Full : ( in + 1 ) % BUFFER_SIZE == out
  - Cf. Buffer can store at most BUFFER_SIZE – 1 items

Circular Queue

• Circular queue: fixed-size buffer whose logical structure is circular
  • Last element is followed by first element
• Inserting an item- buffer[in] = newItem;
  - in = (in + 1) % n;
• Extracting(뽑아내다) an item - item = buffer[out]
  - out = (out + 1) % n;

Producer-Consumer Problem using Bounded Buffer

• Producer

item nextProduced; // local에 존재, 나머지는 shared memory!
  
while (1) {
	// produce an item in nextProduced
	while (((in + 1) % BUFFER_SIZE) == out); // waiting, full condition
	buffer[in] = nextProduced; // Queue insertion
	in = (in + 1) % BUFFER_SIZE;
}

• Consumer

item nextConsumed; // local에 존재, 나머지는 shared memory!
  
while (1) {
	while (in == out); // waiting, empty condition
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE; // Queue deletion
	// consume the item in nextConsumed
}

Message-Passing Systems

• Process communication via passage-passing facility provided by OS
• Advantage
  - No conflict → 동시에 write해도 OS가 arrange해줌
  → Suitable(적합) for smaller amounts of data
  - Communication between processes on different computer
• But slower than shared memory
  대용량은 Shared momory가 더 좋음

• For message passing, communication link should be exist between the processes
• Essential operations
  - send
  - receive
• (Logical) Implementation methods
  - Direct / Indirect
  - Synchronous / Asynchronous
  - Buffering (How to)
  • Zero / bounded / unbounded capacity

Direct / Indirect Communication

• Direct communication: connection link directly connects processes
• Indirect communication: processes are connected via mailbox

Buffering

• During communication, messages are stored in temporary queue (buffer)
• Three kinds of buffer capacity(용량)
  • Zero capacity: only blocking send is possible
    - 대기열의 최대 길이가 0, 링크에 대기 중인 메시지가 있을 수 없다
  • Bounded capacity: buffer has finite length n
    - If buffer is full, sender must be blocked
    - Otherwise, sender can resume
  • Unbounded capacity: buffer has infinite capacity
    - Sender never blocks

---

🖥️ Example of IPC system

[System V] Shared-Memory

✔️ shmget() – Create shared memory

int shmget(key_t key, int size, int shmflg);
return seg_id, if fail return -1

➡️ 주소는 절대적인 주소가 아닌, process안에서만 통용된다. physical주소로 mapping

➕ Parameter

key : Key of shared memory segment

• IPC_PRIVATE : key를 IPC_PRIVATE로 설정하면, key값은 중복되지 않는 임의의 값으로 자동으로 생성

size : memory block size

• 할당할 메모리의 byte단위 크기, 주로 Buffer size

shmflg : flags

• S_IRUSR : User readable
• S_IWUSR : User writable
• IPC_CREAT : key에 해당하는 메모리가 없으면 공유메모리를 생성 ( 0666 )
• IPC_EXCL : key 값에 해당하는 공유 메모리가 있다면 실패 반환, 접근 막음

✔️ shmat() – Attach shared memory to address space of a process

: 공유 메모리를 마치 프로세스의 몸 안으로 첨부

void* shmat(int shmid, char *shmaddr, int shmflg);
return memory address, if fail return -1

➡️ void* : 특정 type에 국한 x

➕ Parameter

shmid : shmget() 리턴으로 얻은 shmid(seg_id)
shmaddr : mapping 위치 ( NULL : kernel이 알아서 지정 )
shmflg : attach flags

✔️ shmdt() – Detach shared memory from address space of process

: 프로세스에 첨부된 공유 메모리를 프로세스에서 분리

void shmdt(char *shmaddr);
return 0, if fail return -1

✔️ shmctl() – Controls and deallocate a shared memory block

: 공유 메모리 정보 확인 / 변경 / 제거

shmctl(shmid, IPC_RMID, NULL);
IPC_RMID : RM(remove)ID

➡️ 명령 직후 삭제 x, 쓰는 process가 없을 때 (shm_attach == 0) 삭제 예약

[POSIX] Shared Memory

• IPC POSIX Producer
• IPC POSIX Consumer
• shm_open(): 성공시 file descriptor를 return
• shm_unlink(): 공유 메모리를 제거
  → 공유 메모리는 커널이 종료되기 전까지는 제거되지 않음
• ftruncate(): 실제 공유되고 있는 메모리 사이즈로 shm_fd의 크기를 조절
• mmap(): fd로 지정된 파일에서 offset을 시작으로 length바이트 만큼을 start 주소로 mapping
• munmap(): 지정된 주소 공간에 대한 mapping 해제
  → process 종료 시 자동으로 unmap
  
  

[POSIX] Message Passing

• msg struct

struct {
   long  data_type;
   char  data_buff[BUFF_SIZE];
}

✔️ msgget() - create a message queue

int msgget( key_t key, int msgflg );
return 메시지 큐 식별자, if fail return -1

➕ Parameter

key : 시스템에서 다른 큐와 구별되는 번호
msgflg : 옵션

snd_queue = msgget((key_t)snd_key, IPC_CREAT | 0666);
rcv_queue = msgget((key_t)rcv_key, IPC_CREAT | 0666);

✔️ msgsnd() - send a message to a message queue

int msgsnd( int msqid, const void *msgp, size_t msgsz, int msgflg );
return 0, if fail return -1

➕ Parameter

msqid : 메시지 큐 식별자
msgp : 전송할 자료

msgsz : 전송할 자료의 크기

struct {
 	long  data_type;
 	char  data_buff[BUFF_SIZE];
}

• 전송 데이터는 long 값을 첫번째에 가지고 있어, 원하는 데이터만 걸러낼 수 있다. 따라서, 데이터의 크기에 long 값이 반드시 들어가기 때문에 type을 나타내는 long크기는 제거한다.
  ➡️ sizeof(msg) - sizeof(long)

msgflg : 동작 옵션

• 전송 실패시 0은 큐에 공간이 생길 때까지 wait
• IPC_NOWAIT은 바로 -1을 리턴

if(-1 == msgsnd(snd_queue, &msg, sizeof(msg) - sizeof(long), IPC_NOWAIT)){
	perror("msgsnd error: ");
}

✔️ msgrcv() - receive a message from a message queue

ssize_t msgrcv( int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg );
return data size, if fail return -1

➕ Parameter

msqp : 수신한 데이터

msgtyp : 메시지 큐에 있는 데이터 중 어떤 데이터를 읽어 들일지에 대한 옵션

• 0이면 큐의 첫번째 자료를 read
• 양수일 경우, 양수로 지정한 값과 동일한 데이터 타입의 자료 중 첫번째 Read
• 음수일 경우, 음수 값을 절대 값으로 바꾼 후, 이 절대값과 같거나 가장 작은 데이터 타입의 데이터를 Read

msgflg : 동작 옵션

• 전송 실패시 0은 큐에 공간이 생길 때까지 wait
• IPC_NOWAIT은 바로 -1을 리턴

msgrcv(rcv_queue, &rcv_data, sizeof(msg) - sizeof(long), 0, IPC_NOWAIT);

✔️ msgctl() – control/deallocate message queue

메시지큐 상태 정보 · 변경 · 삭제

int msgctl ( int msqid, int cmd, struct msqid_ds *buf )
return 0, if fail return -1

➕ Parameter

cmd

• IPC_RMID : 메시지 큐를 삭제 ➡️ buffer가 필요없으므로 0으로 지정
• IPC_STAT : 현재 상태를 buf에 저장
• IPC_SET : 현재 상태를 buf 값으로 변경

buf : 메시지 큐 정보를 받을 버퍼

msgctl(snd_queue, IPC_RMID, 0);
msgctl(rcv_queue, IPC_RMID, 0);

→ 지금까지 같은 컴퓨터 안의 communication

---

🖥️ Communication in client-server systems

• Socket : logical endpoint for communication
  • Data communication
• RPC (Remote Procedure Call)
  • Procedure call between systems
    - Procedural(절차적) programming
• Pipes
  - Often used for Input / output redirection
• RMI (Remote Method Invocation) of JAVA
  - Invocating method of object in other system
  • Object oriented programming

Socket

• Identified by <ip address>:<port #>
• Each connection is identified by a pair of sockets
  
  
• Port: logical contact point(접점) to a computer recognized by TCP and UDP protocols
  - A computer may have multiple ports (0 ~ 65535)- Well-known services have their own ports below(미만) 1024
  Ex) telnet: 23, ftp: 21, http: 80
  → Server always listens corresponding port
  - Ports above 1024 can be arbitrary(임의로) assigned for network communication
• Server opens a port to accept connection request.
• Initiating connection
  - Client arbitrary assigns a port above 1024
  Ex) a client 146.86.5.20 assigned a port 1625
  - Client request a connection to server.
  Ex) a web server 161.25.19.8 (port # of web service: 80)
  - If server accepts request, connection is established
  Ex) <146.86.5.20:1625> - <161.25.19.8:80>

Java Socket

• Socket classes
  - ServerSocket: accepts request for connection → open port
  - Socket: in charge(담당) of actual communication

Remote Procedure Calls (RPC)

• RPC: procedure call mechanism between systems
  ➡️ 네트워크를 통해 다른 컴퓨터나 프로세스에서 실행 중인 함수나 프로시저를 호출하는 프로그래밍 기술
• On server, RPC daemon listens a port
• Client sends a message containing identifier of function and parameters
• RPC is served through stubs
  - Client invoke remote procedure as it would invoke a local procedure call
• Stub: a small program providing interface to a larger program or service on remote side
  - Client stub / server stub
  - Locate port on server
  - Marshal / unmarshal parameters
• Parameter marshaling
  Motivation: each system has its own data format
  ➔ Parameter should be transferred in machine-independent standard representation
  - Ex) XDR (eXternal Data Representation)
  • Marshalling: Packaging (native format ➔ standard format)
  • Unmarshalling: Unpackaging (standard format ➔ native format)

Pipes

• IPC에 속함, 가상의 data 통로
• Pipes acts as a conduit(도관) allowing two processes to communicate
• Ordinary pipes
  - Unidirectional(단방향) communication between parent and child
  - Typically, a parent process creates a pipe and uses it to communicate with a child process that it created.

Ordinary Pipes

• Ordinary pipes allow unidirectional communication in standard producer-consumer style
  - Producer writes to one end (the write-end of the pipe)
  - Consumer reads from the other end(the read-end of the pipe)
  - Require parent-child relationship between communicating processes
• Windows calls these anonymous(익명) pipes
  

Remote Method Invocation (RMI)

• RMI: Java feature to invoke method on remote object
  ➡️ Java 애플리케이션에서 로컬 객체처럼 원격 객체에 접근하여 메서드를 호출

HGU 전산전자공학부 김인중 교수님의 23-1 운영체제 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.