<style>
.red {
color: red;
font-weight: bold;
}
</style>

# Processes

Process: A program in execution

## Process Concept

### The Process

- Program counter
- The memory layout of a process is typically divided into multiple sections (Fig 3.1)
- Text section
- Data section
- Heap section
- Stack section
- **Program** is **passive** entity
- **Process** is **active** entity


### Process State

A process may be in one of the states:

- **New**: The process is being created
- **Running**: Instructions are being executed
- **Waiting**: The process is waiting for some event to occur
- **Ready**: The process is waiting to be assigned to a processor
- **Terminated**: The process has finished execution


==（重要）==

### Process Control Block

Each process is represented in the OS by **PCB** (process control block).

It contains the information associated with a specific process, including

- Process state
- Program counter
- CPU registers
- CPU scheduling information
- Memory-management information
- Accounting information
- I/O status information


### Threads

- A program performing a single thread
- A process to have multiple threads of execution and thus to perform more than one task at a time
- Is beneficial on **multicore** system
- Multiple threads can run in **parallel**
- The PCB is **expanded** to include information for each thread

## Process Scheduling

- Process scheduler
- **selects** among available processes for program execution on a core
- Degree of multiprogramming
- I/O-bounded process
- CPU-bound process

### Scheduling Queues


- Ready Queue
- Wait Queue

---

- Queueing Diagram

### CPU Scheduling

- CPU scheduler
- Swapping

### Context Switch

- Context
- PCB (Process Control Block)
- Fig 3.2
- Context switch
- State save
- State restore

## Operations on Processes

### Process Creation

- Tree
- Process identifier (pid)


- When a process creates a new process, two possibilities for execution
- The parent continues to execute **concurrently** with its children
- The parent **waits** until some or all of its children have terminated
- Two address-space possibilities for new process
- The child process is a **duplicated** of the parent process
- The child process has a **new program** loaded into it


### Process Termination

- Process termination
- `exit()`
- `wait()`
- De-allocate the resources
- The parent may terminate the execution of the child
- The child has exceeded its usage of some of the resources that it has been allocated
- The task assigned to the child is no longer required
- If parent is exiting, and the OS does not allow child to continue if its parent terminates
- Cascading termination
- Zombie
- Process 結束到資源被完全清除前仍會佔用
- <https://zh.wikipedia.org/zh-tw/僵尸进程>
- Orphan
- Parent 因意外（如崩潰）比 child 先結束
- <https://zh.wikipedia.org/zh-tw/孤儿进程>

#### Android Process Hierarchy

- **Importance** hierarchy of processes
- 依照重要程度排序（不同系統可能順序不同），優先度較高的可以得到較好的資源或先被執行。
- The hierarchy of process classifications
- Foreground process
- Visible process
- Service process
- Background
- Empty process

## Interprocess communication

- Independent
- A process **cannot** affect or affected by the other processes executing in the system.
- Cooperating
- A process **can** affect or affected by the other processes executing in the system.
- The reasons to cooperate
- Information sharing
- Computation speedup
- Modularity（模組化）
- Cooperating processes requires an **i**nter**p**rocess **c**ommunication (IPC) mechanism
- Two models of IPC
- Shared memory
- Message passing


## IPC in shared memory system

==考點：演算法填空或選擇題==

- Producer-consumer problem
- Producer
- (3.12) The producer process using shared memory.

      item next_produced;

      while (true) {
          /* produce an item in next produced */

          while (((in + 1) % BUFFER SIZE) == out)
              ; /* do nothing（等待直到 buffer 有空間） */

          buffer[in] = next produced;
          in = (in + 1) % BUFFER SIZE;
      }

- Consumer
- (3.13) The consumer process using shared memory.

      item next consumed;

      while (true) {
          while (in == out)
              ; /* do nothing（等待直到有東西為止） */
          next consumed = buffer[out];
          out = (out + 1) % BUFFER SIZE;
          /* consume the item in next consumed */
      }

- Two types of buffer
- Unbounded buffer
- Bounded buffer

## IPC in Message-Passing Systems

### Naming 指名

==考點：選擇題（要能看懂）==

- Direct communication
- Send (P, message)
- Receive (Q, message)
- Properties:
- **A** link is established automatically between every pair of processes that want to communicate. The processes need to know **only each other's identity** to communicate.
- A link is associated with **exactly** two processes
- Between each pair of processes, there exists exactly **one** link.
- Symmetry
- **Both** the sender and the receiver must **name the other** to communicate
- Send (P, message)
- Receive (Q, message)
- Asymmetry
- Only the sender names the **recipient**. **Recipient** is not required to name the sender.
- Send (P, message)
- Receive (id, message)
- Indirect communication
- The messages are sent to and receive from mailboxes or ports
- Send (A, message)
- Receive (A, message)
- Properties:
- A link established between a pair of processes only if both members of the pair have a **shared mailbox**.
- A link may be associated with **more than two processes**.
- Between each pair of communicating processes, **a number of** different links may exist, with each link corresponding to one mailbox.

### Synchronization

- Blocking (synchronous) and non-blocking (asynchronous)
- Blocking send
- The sending process is block **until the message is received** by the receiving process or by the mailbox.
- 確認對方收到才會繼續傳送
- Non-blocking send
- The sending process **sends the message and resumes operating**.
- 只傳送，不管有沒有收到
- Blocking receive
- The receiver blocks until the message is available.
- 僅接收有效的訊息
- Non-blocking receive
- The receiver blocks retrieves either a valid message or a null
- 就算是空的訊息也會接收
- Rendezvous
- Both `send()` and `receive()` are blocking
- The producer-consumer problem
- (3.14) The producer process using message passing.

      message next produced;

      while (true) {
          /* produce an item in next produced */

          send(next produced);
      }

- (3.15) The consumer process using message passing.

      message next consumed;

      while (true) {
          receive(next consumed);

          /* consume the item in next consumed */
      }

### Buffering

- Three ways to implement the queues
- Zero capacity（當場完成）
- Bounded capacity（常見）
- Unbounded capacity

## Communicating in Client-Server Systems

### Sockets

- A socket is defined as an endpoint for communication.
- A socket is identified by and **IP address** concatenated with a **port number**.


### Remote Procedure Calls

- The **RPC** was designed as a way to abstract the procedure call mechanism for use between systems with network connections.

<font class="red">（流程可能會考）</font>