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