---
# System prepended metadata

title: 'Ch03: Processes'
tags: [OS]

---

<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

![](https://hackmd.io/_uploads/Sy4jSuifT.png =300x)

### 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

![](https://hackmd.io/_uploads/rJ-16lKgp.png)

==（重要）==

### 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

![](https://hackmd.io/_uploads/BJpOaltl6.png)

### 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

![](https://hackmd.io/_uploads/H1AQXZKgp.png)

- Ready Queue
- Wait Queue

---

- Queueing Diagram
  ![](https://hackmd.io/_uploads/H1RLXbKep.png)


### CPU Scheduling

- CPU scheduler
- Swapping

### Context Switch

- Context
  - PCB (Process Control Block)
  - Fig 3.2
- Context switch
  - State save
  - State restore
  ![](https://hackmd.io/_uploads/SJFHCxYlp.png)
  
## Operations on Processes

### Process Creation

- Tree
- Process identifier (pid)

![](https://hackmd.io/_uploads/B1yOoWFxT.png)

- 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

![](https://hackmd.io/_uploads/BJVInWFgp.png)

### 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

![](https://hackmd.io/_uploads/HyKGIPsZ6.png)

## IPC in shared memory system

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

- Producer-consumer problem
  - Producer
    - (3.12) The producer process using shared memory.
      ```c=
      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.
      ```c=
      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.
      ```c=
      message next produced;

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

          send(next produced);
      }
      ```
    - (3.15) The consumer process using message passing.
      ```c=
      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**.

![](https://hackmd.io/_uploads/SyseS_iWT.png =400x)

### 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>

![Figure 3.29 Execution of a remote procedure call (RPC).](https://hackmd.io/_uploads/r1KjU_iWT.png =600x)
