---
# System prepended metadata

title: 'Operating System Concepts, Ch. 3: Processes'

---

# Operating System Concepts, Ch. 3: Processes

## Process Concept

- General process memory layout. Also refer to [C Memory Layout](https://www.geeksforgeeks.org/memory-layout-of-c-program/).
![](https://hackmd.io/_uploads/r1X4dimph.png)
- Process running state:
![](https://hackmd.io/_uploads/ryTtKoXTn.png)
- OS-managed **Process Control Block (PCB)**. There are also CPU-scheduling information here.
![](https://hackmd.io/_uploads/SyBpYj7a3.png)

## Process Scheduling

- **Degree of Multiprogramming**: the number of processes currently in memory.
- A process can either be **CPU-bound** or **I/O-bound**.
- A number of queues are used to manage processes.
![](https://hackmd.io/_uploads/HJqgxh76n.png)
- **CPU Scheduler** chooses processes to run from the wait queue with its strategies.
- **Swapping**: remove a process from memory for it to be run later (reducing the degree of multiprogramming).
- **Context Switch** is pure overhead. Its time depends heavily on hardware.

## Operations on Processes

- In Linux, the process `systemd` is the root of all processes directly created. Process listing requires a traversal of this tree.
- Child processes may need to request resources directly from the OS, or it may be restricted to use only a fraction of those of its parent's (thus preventing system overloading by #children).
- Parents can wait for their children to terminate, or run concurrently.
- Children may duplicate parent memory contents, or have new programs loaded.
- Children may terminate before its parent calls `wait` (e.g. to retrieve its status). In this case, the children's process table must remain, and the process is known as a **zombie process**.
- If instead, the parent never calls `wait` and exits, its children become **orphans**. Traditional UNIX deals with this situation by assigning orphans as the children of `init`, the root process. `init` periodically calls `wait` to terminate orphans.
- Android terminates un-important processes when resources are insufficient by their **importance order** (foreground > visible > ...). If development guidelines are followed, even if a process is terminated, a user can still resume its saved state.

## Inter-Process Communication

There are multiple reasons to support process cooperation,
- Information sharing (such as memory)
- Parellel speedup (for multiple cores)
- Modularity (a function is divided into several processes or threads)

There are generally two ways for IPC, (a) **Shared Memory**, and (b) **Message Passing**. Shared memory can be faster than message passing, but the latter is better at trasmitting small amounts of data, as no conflicts occur.
![](https://hackmd.io/_uploads/HyRNphma2.png)

## IPC Implementations

- **Shared Memory**: Harder to control. Requires well-written programs, & well-behaving processes.
    - **Excercise**: implement a circular queue with an array, a `QUEUE_SIZE`, and two integers `in` and `out`. The queue must hold a maximum of `QUEUE_SIZE` elements.
- **Message Passing**: no address sharing. useful in distributed environments.
    - **Direct Comms**: Processes explicitly refer to each other. Pair-wise, unique links must be established. Links are symmetric. Hard-coded identifier.
    - **Asymmetric Links**: Alternatively, only one process needs to name another. Hard-coded identifier.
    - **Indirect Comms**: Adopt intermediate **mailboxes**, or **ports**. A process can access multiple mailboxes, but two process can communicate only if they have a shared one. A mailbox can be used by multiple pairs, and a pair can use mulitple mailboxes. Mailboxes attach to an owner (recipient) or the OS.
- In message passing, both `send` and `recv` can be **blocking** or **non-blocking**. A blocking `send` paired with a blocking `recv` results in a **rendezvous**, and a trivial situation in the producer-consumer problem.
- The message queue can have zero-capacity (always blocks), bounded-capacity (conditionally blocks), or unbounded-capacity (never blocks).

## IPC System Examples

### POSIX Shared Memory

- Create a shared memory mapped file with `shm_open`, and specify arguments including `name`, and configure its size with `ftruncate`. Finally, map it to a file with `mmap`.
- Shared Memory coding excercise at the end of this chapter.

### Mach Message Passing

- Mach uses unidirectional ports for transmitting messages (potentially multiple senders, but only one receiver).
- Port owner can set port permissions.
- Each task (process) has a port to send message to kernel, and a notify port to receive events from kernel.
- Each task can register its ports to a bootstrap server, for other tasks to look up and send messages (system-wide).
- Tries to avoid message copying (slows down message passing) with virtual memory techniques.

### Windows

- Provides several operating environments, or **subsystems** that applications can interact with via message passing.
- Message passing in Windows is called **Advanced Local Procedure Call (ALPC)**.
    - **Connection Ports**: Owned by the server and public to all. Can be used to establish a channel.
    - **Communication Ports**: A channel consists of two such private ports.
- Small messages are copied across processes. Medium messages pass through a shared **section object**. Large messages turns to shared memory.
- For application programmers, ALPC is not visible nor accessible at the surface level. Use standard RPC (Remote Procedure Call) instead.
- Many kernel services use ALPC.

### Pipes

- Early IPC mechanisms in Unix. 
    - Unidirectional / Bidirectional
    - Half Duplex / Full Duplex ([Reference](https://zh.wikipedia.org/zh-tw/%E9%9B%99%E5%B7%A5))
    - Parent-child Relationship?
    - Networked Transmission / Same Machine?
- **Ordinary Pipes**: Unidirectional, standard P-C Problem. A parent should create a pipe to communicate with its children. Ceases to exist when processes die or the comms in finished. They are called **anonymous pipes** in Windows.
- **Named Pipes**: Can be bidirectional, multi-process usage (e.g. several writers), and can continue to exist after processes / comms end.
    - They are called **FIFO** in Unix, and can be created with `mkfifo`. Bidirectional, half duplex. It only supports same-machine comms. Otherwise, use **sockets**.
    - On Windows, they are full duplex, and processes can be on different machines.

## Communication in Client-Server Systems

### Sockets

**Socket**: An endpoint of communication (`<IP>:<PORT>`). Two processes hold one socket each. All connections are unique. They are considered rather low-level, as only byte streams are allowed.
![](https://hackmd.io/_uploads/BkywvJSTh.png)

### Remote Procedure Calls (RPCs)

- Each message is addressed to an RPC daemon listening to a port on a remote system. Each RPC contains the function name and parameters, and returns well-structured data.
- When a client invokes an RPC, the system calls the appropriate **stub**, and pass parameters to it. The stub locates the port and **marshals** the parameters. Afterwards, it transmits a messages to the server with message passing. A similar stub at the server then receives this message and invokes the actual procedure on the server.
- **Marshaling** addresses data representation disparities (such as **endianess**).
- Due to its nature, RPCs are more prone to failures and duplicates. ACK and timestamp mechanism can address such issues (exactly once & at most once).
- Two systems must bind with each other, usually with fixed port numbers. For more flexibility, **matchmakers** are used. A matchmaker reside on a fixed port, and can return port numbers when queried with an RPC name.

### Android RPCs

- In Android's **binder** framework, a process can request services of others iva RPCs.
- **Application Component**: The basic building block that provides utility to an app. They can be combined in an app. One such component running in the background is **services**.
- Clients can bind to services with `bindService()`, and the latter provides a one-way `Messenger` so that the client can send messages.
- To create RPCs, the service can instead return a interface to a method call (a stub, actually).