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 来选择下一个运行的进程，这个过程可以用如下代码概括：

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

after

在转变的过程中，会存下 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 结构如下图所示：

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，如以下程序所示：

pid.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);
}

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 中

示例代码如下：

fork1.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);
}

UNIX Process Management

• UNIX fork：复制当前 process，并运行复制后的 process

• UNIX exec：改变当前运行的 process，抛弃复制的内容，直接执行新的程序

• UNIX wait：等待 child process 结束

• UNIX signal：向其它 process 发送 notification 的系统调用，如 ctrl+c

wait example

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

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

signal example

下面的例子通过 signal 调用用自定义的 SIGINT handler 替换默认 handler，使得 process 能够控制用户按下 ctrl+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

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

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

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

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

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

应用通过 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 的代码示例：

file_op.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);

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

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

#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 读写数据的例子如下：

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

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 生命周期如下图所示：

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 得以实现。