# Processes, Fork, I/O, Files

从第二课的讨论中，我们已经了解：

* 在 user processes 与 kernel 之间切换
* kernel 可以切换不同的用户进程，实现并发
* 保护 user processes 之间，以及 user processes 与 kernel 之间互不干扰

但你可能会有很多疑问：

* OS 如何表示进程？
* OS 如何选取下一个运行的进程？
* OS 在切换进程时，如何记录进程的运行时信息？
* kernel 的 stack、heap 是怎样的？
* 大量切换进程，同时记录它们的运行时信息，会不会浪费内存？

本节我们就将进入这些细节中了解 OS 中的进程。

## Process Scheduling

### **Process Control Block (PCB)**

在 Kernel 中用于表示用户进程的数据结构叫作 PCB。PCB 包含进程的重要信息，如：

* 进程状态 (running, ready, blocked, ...)
* 寄存器状态
* Process Id (PID)、用户、优先级……
* 执行时间……
* 内存空间、地址转化信息……

这些信息足够用来开始、恢复一个程序的执行。

### **Kernel Scheduler**

Kernel Scheduler 将这些 PCB 组织起来，利用一些 scheduling algorithms 来选择下一个运行的进程，这个过程可以用如下代码概括：

```c
while (true) {
    if (readyProcesses(PCBs)) {
        nextPCB = selectProcess(PCBs);
        run(nextPCB);
    } else {
        run_idle_process();
    }
}
```

代码中的 selectProcess，就隐藏着五花八门的调度策略。但不论是哪种调度策略，都需要考虑**公平与效率**，这在现实生活中也是如此。

### System Call

#### **Safe Kernel Mode Transfers**

* kernel 拥有自己的 kernel stack，kernel stack 与 user stack 不可以有公用的部分
* 转变的过程必须完全可控，包括用户进程运行时环境的保存，system call 的参数移动（从 user space 到 kernel space）、参数检查以及运行结果从 kernel space 返回到 user space 的过程

为了防止恶意程序利用 kernel mode 或者破坏 kernel 本身，操作系统必须要在进程从 user mode 转变成 kernel mode 的过程中做足安保工作。实现 user mode 到 kernel mode 的安全转变，需要许多细节来保证：

转变的例子如下图所示：

![before](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_2URQjdM9aum-aytFs%2F-L_2Xc1Vfgo5RxKZ8xC4%2FScreen%20Shot%202019-03-03%20at%208.32.15%20PM.jpg?alt=media\&token=637814ca-4dc4-4325-a9c4-e6d47368a400)

![after](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_2URQjdM9aum-aytFs%2F-L_2XhoXy97qv3N-TDIO%2FScreen%20Shot%202019-03-03%20at%208.32.41%20PM.jpg?alt=media\&token=6b6835bc-8bc1-4dc6-a0d3-bb29eb38c34e)

在转变的过程中，会存下 user-level process 的相关信息，如寄存器中的数据，然后将参数复制到 kernel stack，切换到 kernel mode 执行系统调用，完毕后再返回 user mode。

#### Kernel System Call Handler

操作系统定义了一系列 subroutines （system call vector）提供给 user-level process 调用。操作系统记录着 system call number 到 handler 地址的映射关系，每当 user-level process 调用系统进程时，处理步骤如下：

1. 定位调用参数，在寄存器或 user stack 中
2. 复制调用参数，将参数从 user memory 移动到 kernel memory 中，保证 kernel 不被入侵
3. 验证调用参数
4. 执行系统调用 subroutine，并将结果复制回 user memory

### Interrupt

#### System Call vs. Interrupt

system call 和 interrupt 都是进入 kernel operation 的机制。每当 user-level process 想要执行一些需要更高权限的操作时，就需要请求执行系统调用；每当外部装置（CPU 的外部）需要请求处理时，则通过制造一个 Interrupt 来请求系统处理。前者为主动、同步调用，后者为被动、异步调用，前者通常与当前程序息息相关，而后者通常与当前程序无关。

#### Interrupt Control

Interrupt 的处理应当对 user process 无感知。 interrupt handler 执行时操作系统会先 disable  interrupts，等待 interrupt handler 执行完毕后才 re-enable interrupts，每个 interrupt 处理的过程都是一次从头执行到尾，无中断，无等待。只有 kernel 有权限 enable/disable interrupts，否则就没有王法了。Interrupt Controller 结构如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_2URQjdM9aum-aytFs%2F-L_2k9xv5KCLg9pxMNmy%2FScreen%20Shot%202019-03-03%20at%209.31.17%20PM.jpg?alt=media\&token=bde244a6-43a5-4ea4-bdf4-72ae02ad3862)

#### Interrupts Safely

类似 system call：

* 操作系统维护 interrupt vector，后者将 interrupt number 映射到 kernel 中相应的 subroutine
* Kernel 维护 interrupt stack，与 user stack 完全独立
* Interrupt Masking：保证 interrupt 能够不被中断
* Atomic transfer of control
* Transparent restartable execution，user process 对此无感知

### Operations on Process

之前我们一直在讨论 process 中执行的内容，那么是否有一些操作是针对 process 本身的？

* 创建 process
* 杀死 process
* ...

#### pid

操作系统根据 pid 唯一确定一个 process，如以下程序所示：

{% code title="pid.c" %}

```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>

#define BUFSIZE 1024
int main(int argc, char *argv[])
{
  int c;
  
  pid_t pid = getpid();
  
  printf("My pid: %d\n", pid);
  
  c = fgetc(stdin);
  exit(0);
}
```

{% endcode %}

#### create a process from a process

系统调用 fork 可以创建复制当前 process，创建一个新的 process。fork 之后的程序实际上会被两个 processes 执行，每个 process 根据 fork 的返回值来判断自己是在 parent process 还是 child process：

```
> 0: 在 parent process 中，且返回值为 child process 的 pid
= 0: 在 child process 中
< 0: fork 失败，在原 process 中
```

示例代码如下：

{% code title="fork1.c" %}

```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>

#define BUFSIZE 1024
int main(int argc, char *argv[])
{
  char buf[BUFSIZE];
  size_t readlen, writelen, slen;
  pid_t cpid, mypid;
  pid_t pid = getpid();
  printf("Parent pid: %d\n", pid);
  cpid = fork();
  if (cpid) > 0) {
    mypid = getpid()
    printf("[%d] parent of [%d]\n", mypid, cpid);
  } else if (cpid == 0) {
    mypid = getpid();
    printf("[%d] child\n", mypid);
  } else {
    perror("Fork failed");
    exit(1);
  }
  exit(0);
}
```

{% endcode %}

#### UNIX Process Management

* UNIX fork：复制当前 process，并运行复制后的 process
* UNIX exec：改变当前运行的 process，抛弃复制的内容，直接执行新的程序
* UNIX wait：等待 child process 结束
* UNIX signal：向其它 process 发送 notification 的系统调用，如 ctrl+c

*wait example*

```c
//
cpid = fork();
if (cpid > 0) {
  mypid = getpid();
  printf("[%d] parent of [%d]\n", mypid, cpid);
  tcpid = wait(&status);
  printf("[%d] bye %d\n", mypid, tcpid);
} else if (cpid == 0) {
  mypid = getpid();
  printf("[%d] child\n", mypid);
}
//
```

*shell example*

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_2URQjdM9aum-aytFs%2F-L_2y4mEsb6M7pzAT95t%2FScreen%20Shot%202019-03-03%20at%2010.32.16%20PM.jpg?alt=media\&token=afe7b07f-cff5-4f80-9704-e078ddbe1f2a)

shell 就是一个 job control system，每次执行命令 shell 会 **fork** 一个 child process，然后立即 **exec** 相应的程序，同时 shell process 会 **wait** child process。

*signal example*

下面的例子通过 signal 调用用自定义的 SIGINT handler 替换默认 handler，使得 process 能够控制用户按下 ctrl+c 后的行为。

```c
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>

#include <unistd.h>
#include <signal.h>

void signal_callback_handler(int signum)
{
  printf("Caught signal %d - phew!\n", signum);
  exit(1);
}

int main() {
  signal(SIGINT, signal_callback_handler);
  
  while (1) {}
}
```

#### Process races

```c
if (cpid > 0) {
  mypid = getpid();
  printf("[%d] parent of [%d]\n", mypid, cpid);
  for (i=0; i<100; i++) {
    printf("[%d] parent: %d\n", mypid, i);
  }
} else if (cpid == 0) {
  mypid = getpid();
  printf("[%d] child\n", mypid);
  for (i=0; i>-100; i--) {
    printf("[%d] child: %d\n", mypid, i);
  }
}
```

## How Does Kernel Provide Services

### UNIX System Structure

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_5Ld4Uxse3osecrymn%2F-L_5MDBm08_tE5GPe9A_%2FScreen%20Shot%202019-03-04%20at%209.41.18%20AM.jpg?alt=media\&token=69ff68a1-e0f8-4cf0-8bdd-b6a37bb0cc9e)

虽然应用需要通过 syscall 获取操作系统提供的服务，但我们通常看不到 syscall 本身，因为它被包装在编程语言的 runtime library 中，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_5Ld4Uxse3osecrymn%2F-L_5MgjLmp2gE0_eYTr1%2FScreen%20Shot%202019-03-04%20at%209.43.23%20AM.jpg?alt=media\&token=29c524d2-dd92-47a1-9dba-0fe46dfd6fe4)

同样的程序要在不同平台上兼容，依赖于 system call interface 的统一，有点类似网络层在 OSI 网络模型中的 narrow waist 地位，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_5Ld4Uxse3osecrymn%2F-L_5NdpgDD-82KNWvdgP%2FScreen%20Shot%202019-03-04%20at%209.47.34%20AM.jpg?alt=media\&token=c21fa3ff-b740-4c2a-b851-a87d70250963)

### Key Unix I/O Design Concepts

Unix I/O 接口的设计有自己的一套哲学，总结如下：

* Uniformity
  * 文件操作、设备 I/O、进程间通信都通过 open、read/write、close 来实现
  * 允许程序之间 I/O 的 composition：如 "find | grep | wc" ...
* Open before use
  * 提供访问控制和仲裁逻辑
  * 初始化内部结构
* Byte-oriented
  * 尽管大部分数据都是以 block 为单位传输，但可以按 byte 寻址
* Kernel buffered reads
  * Streaming and block devices looks the same
  * read blocks process, yielding processor to other task
* Kernel buffered writes
  * Completion of out-going transfer decoupled from the application, allowing it to continue
* Explicit close

### I/O & Storage Layers

读文件的过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_5Ld4Uxse3osecrymn%2F-L_5P90QXTTWju0mpJ4W%2FScreen%20Shot%202019-03-04%20at%209.54.08%20AM.jpg?alt=media\&token=5b4deab5-9d25-4450-9217-64846f7dac7f)

应用通过 High Level I/O api 访问程序语言的 library，后者通过 syscall 访问 file system，file system 访问 I/O Driver，然后程序进入等待状态。数据读取完毕后，经由 I/O driver、file system 返回到 syscall 中缓存，最后经过 low level I/O 和 high level I/O 最终返回到应用。

写文件与读文件的主要不同在于，write 操作通常只把数据写到 library 的缓冲区，必须执行 flush 操作后数据才会写入 kernel 的缓冲区，但这实际上还未落盘，kernel 会在合适的时期或者接受到 sync 命令后执行落盘操作。

#### C High Level I/O

以下是 C 语言中 high level file api 的代码示例：

{% code title="file\_op.c" %}

```c
#include <stdio.h>
// character oriented
int fputc(int c, FILE *fp);
int fputs(const char *s, FILE *fp);
int fgetc(FILE *fp);
char *fgets(char *buf, int n, FILE *fp);
// block oriented
size_t fread(void *ptr, size_t size_of_elements,
             size_t number_of_elements, FILE *a_file);
size_t fwrite(const void *ptr, size_t size_of_elements,
              size_t number_of_elements, FILE *a_file);

// formatted
int fprintf(FILE *restrict stream, const char *restrict format, ...);
int fscanf(FILE *restrict stream, const char *restrict format, ...);

// stream positioning
int fseek(FILE *stream, long int offset, int whence);
long int ftell(FILE *stream);
void rewind(FILE *stream);
```

{% endcode %}

利用这些 api 读写文件的代码示例如下：

```c
#include <stdio.h>

#define BUFLEN 256
FILE *outfile;
char mybuf[BUFLEN];

int storetofile() {
  char *instring;
  outfile = fopen("/usr/homes/testing/tokens", "w+");
  if (!outfile) {
    return (-1);
  }
  while (1) {
    instring = fgets(*mybuf, BUFLEN, stdin);
    
    if (!instring || strlen(instring) == 0) break;
    
    if (fputs(instring, outfile) < 0) break;
  }
  fclose(outfile);
}
```

#### C Low Level I/O

用户通过 file handle 来操作 file，实际上 file handle 就是一个 int。

```c
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>

int open (const char *filename, int flags [, mode_t mode])
int creat (const char *filename, mode_t mode)
int close (int filedes)

ssize_t read (int filedes, void *buffer, size_t maxsize)
// returns bytes read, 0 => EOF, -1 => error
ssize_t write (int filedes, const void *buffer, size_t size)
// returns bytes written
off_t lseek (int filedes, off_t offset, int whence)

int fsync (int fildes)
// wait for i/o to finish
void sync (void)
// wait for ALL to finish
```

当 write 执行完毕后，data 只是处于落盘的过程中，但已经可以被读取，但此时它并不一定已经持久化。

使用 Low Level I/O 读写数据的例子如下：

```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>

#define BUFSIZE 1024

int main(int argc, char *argv[])
{
  char buf[BUFSIZE];
  ssize_t writelen = write(STDOUT_FILENO, "I am a process.\n", 16);
  ssize_t readlen = read(STDIN_FILENO, buf, BUFSIZE);
  ssize_t strlen = snprintf(buf, BUFSIZE, "Got %zd chars\n", readlen);
  writelen = strlen < BUFSIZE ? strlen : BUFSIZE;
  write(STDOUT_FILENO, buf, writelen);
  exit(0);
}
```

#### Syscall Level

low level api 的参数准备完毕后，调用 syscall，进入 kernel mode 中的 subroutine 运行，后者调用 file system 层 api 后进入等待状态。

#### File System Level

File System 内部维护者描述文件的数据结构，这些描述信息包括：

* 它的位置
* 它的状态
* 如何访问它

#### Lower level Driver

与计算机所使用的存储硬件本身相关，在启动时将这些 api 注册到 kernel 中：

```c
struct file_operations {
  struct module *owner;
  loff_t (*llseek) (struct file *, loff_t, int);
  ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
  //...
}
```

这些 api 需要复合 kernel 与 driver 之间的标准协议。Drivers 通常可以被分成两部分：

* 上半部分：向 system calls 提供接口支持
  * 实现一些 standard, cross-device 调用，如：open(), close(), read(), write(), ioctl(), strategy() 等
  * 上半部分会启动硬件 I/O 操作，然后将线程置于 sleep 状态
* 下半部分：interrupt routine，当硬件 I/O 完毕后，发送中断信号，系统处理后唤醒相关线程。

一个 I/O 生命周期如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GoGy2q1AGY68-R2Nx%2F-L_GmMr4N4B1hZ-smumX%2FScreen%20Shot%202019-03-06%20at%202.55.42%20PM.jpg?alt=media\&token=d304aac8-b73a-4615-9b72-77abaf9e333c)

### Connecting Processes, Filesystem, and Users

默认每个 Process 都可以通过绝对路径（Absolute Paths）访问文件，同时每个 Process 都有一个 current working directory，因此也支持相对路径（Relative Paths）访问文件；此外由于 Process 属于执行用户，因此也支持相对该用户的 home 路径的相对路径访问。访问相对路径访问的过程很简单，就是把 current working directory/home directory 与相对路径拼接得到绝对路径，再访问。

### C API Standard Streams

每个程序执行时，都有 3 个 streams 默认被打开：

* FILE \*stdin：normal source of input, can be redirected
* FILE \*stdout：normal source of output, can too
* FILE \*stderr: diagnostics and errors

其中 STDIN 和 STDOUT 的存在使得 UNIX 中的 composition 得以实现。