---

title: Book | Operating System Concepts Part 1
date: 2018-4-2
categories: Book
tags:

• OS
• Design

---

Part 1 Overview(概述)

第1章 导论

1.1 操作系统做什么

计算机系统分为4个组成部分：计算机硬件、操作系统、系统程序与应用程序、用户。

操作系统是一直运行在计算机上的程序，通常称为内核。

1.2 计算机系统组织

当打开电源或重启时，计算机会运行一个初始化程序。该初始化程序或引导程序(bootstrap program)比较简单，通常位于ROM或EEPROM(电可擦可编程只读存储器)中，称为计算机硬件中的固件。

事件的发生通常通过硬件或软件中断(interrupt)来表示，硬件可随时通过系统总线向CPU发出信号触发中断，软件通过执行特别操作如系统调用(system call)(也称为监视器调用(monitor call))来触发中断。

中断必须将控制转移到合适的中断处理程序，处理转移的简单方法时调用一个通用子程序以检查中断信息。中断处理子程序的指针表通常位于低地址内存，包含了各种设备的中断处理子程序的地址。这种地址的数组或中断向量(interrupt vector)可通过唯一设备号来索引，以提供设备的中断处理子程序的地址。

一个典型指令执行周期(冯诺依曼体系)，首先从内存中获取指令，并保存在指令寄存器(instruction register)中。接着指令被解码，并可能从内存中获取操作数或将操作数储存到内部寄存器中。对操作数完成执行后，其结果可以存回内存中。

辅存(secondary storage)作为内存的扩充，需要能够永久地存储大量的数据。

• SCSI(small computer system interface)控制器：小型计算机系统接口
• DMA(direct memory access)：直接内存访问

1.3 计算机系统体系结构

• 多处理器系统：也称并行系统(parallel system)或紧耦合系统(tightly coupled system)
• 适度退化(graceful degradation)：提供能与正常工作的硬件成正比的服务的能力
• 容错(fault tolerant)：系统超出适度退化的能力
• 非对称多处理(asymmetric multiprocessing)：每个处理器都有各自特定的任务，主从关系
• 对称多处理(symmetric multiprocessing, SMP)：每个处理器都要完成操作系统中的所有任务
• 刀片服务器(blade server)：每个刀片处理器独立启动并运行各自的操作系统
• 集群系统(clustered system)：两个或多个独立的系统耦合起来
• 非对称集群(asymmetric clustering)：一台机器处于热备份模式(hot standby mode)，另一台运行应用程序。
• 对称集群(symmetric clustering)：主机都运行应用程序，互相监督

1.4 操作系统结构

多道程序设计通过组织作业使CPU总有一个作业可执行，从而提高了CPU的利用率。分时系统(或多任务)是多道程序设计的延伸，切换频率很高。

• 进程(process)：装到内存并执行的程序
• 作业调度(job scheduling)：作业需要调入内存但没有足够的内存，系统必须在作业中做出选择决策

1.5 操作系统操作

操作系统采取提供硬件支持的方法以允许区分各种执行模式。至少需要两种独立的操作模式：用户模式(user mode)和监督程序模式(monitor mode)(也叫管理模式supervisor mode、系统模式system mode、特权模式privileged mode)。在计算机硬件中添加一个称为模式位(mode bit)的位以表示当前模式。

一旦出现陷阱或中断，硬件会从用户模式切换到内核模式(即将模式位设为0)。双重模式操作提供了保护操作系统和用户程序不受错误用户程序影响的手段，其方法为将能引起损害的机器指令作为特权指令(privileged instruction)。

必须确保操作系统能维持对CPU的控制，也必须防止用户程序陷入死循环或不调用系统服务，并且不将控制权返回到操作系统。为了实现这一目标，可使用定时器(timer)。可变定时器(variable timer)一般通过一个固定速率的时钟和计数器来实现。

1.6 进程管理

处于执行中的程序被称为进程，可以将进程视为作业或分时程序。程序不是进程，程序是被动的实体，进程是活动的实体。

进程是系统工作的单元。操作系统负责下述与进程管理相关的活动：

• 创建和删除用户进程和系统进程
• 挂起和重启进程
• 提供进程同步机制
• 提供进程通信机制
• 提供死锁处理机制

1.7 内存管理

内存是现代计算机系统操作的中心。内存通常是CPU所能直接寻址和访问的唯一大容量存储器，硬盘必须先通过CPU生成的I/O调用传送到内存。

操作系统负责下述有关内存管理的活动：

• 记录内存哪部分正在被使用及被谁使用
• 当有内存空间时，决定哪些进程可以装入内存
• 根据需要分配和释放内存空间

1.8 存储管理

操作系统负责下列有关硬盘管理的活动：

• 空闲空间管理
• 存储空间分配
• 硬盘调度

三级存储(tertiary storage)：CD/DVD驱动器、光盘。

高速缓存一致性(cache coherency)：必须确保在一个高速缓存中对A值的更新马上反映在所有其他A所在的高速缓存中。

I/O子系统包括如下几个部分：

• 一个包括缓冲、高速缓存和假脱机的内存管理部分
• 通用设备驱动器接口
• 特定硬件设备的驱动程序

1.9 保护和安全

绝大多数操作系统维护一个用户和相关用户标识(user ID, UID)的链表，在Windows NT中，这称为安全ID(Secure ID, SID)。用户有时需要升级特权(escalate privilege)来获取对一个活动的额外特权。

1.10 分布式系统

分布式系统包括两种模式的组合，FTP和NFS。

• 局域网：local-area network, LAN
• 广域网：wide-area network, WAN
• 城域网：metropolitan-area network, MAN
• 小域网：small-area network, SAN，由蓝牙(Blue Tooth)和802.11实现

1.11 专用系统

• 实时嵌入式系统
• 多媒体系统
• 手持系统

1.12 计算环境

• 传统计算
• 客户机-服务器计算
• 对等计算
• 基于Web的计算

第2章 操作系统结构

2.1 操作系统服务

• 用户界面(user interface, UI)：command-line interface(CLI)、graphical user interface(GUI)
• 程序执行：系统必须能将程序装入内存并运行
• I/O操作
• 文件系统操作
• 通信：进程之间交换信息
• 错误检测
• 资源分配
• 统计
• 保护和安全

2.2 操作系统的用户界面

命令解释程序的主要作用是获取并执行用户指定的下一条命令。

2.3 系统调用

BOOL WINAPI ReadFile(
  _In_        HANDLE       hFile,
  _Out_       LPVOID       lpBuffer,
  _In_        DWORD        nNumberOfBytesToRead,
  _Out_opt_   LPDWORD      lpNumberOfBytesRead,
  _Inout_opt_ LPOVERLAPPED lpOverlapped
);

Win32函数CreateProcess()实际上调用了Windows内核中的NTCreateProcess()系统调用。

向操作系统传递参数有三种方法：

• 通过寄存器来传递参数
• 参数存在内存的块和表中，并将块的地址通过寄存器来传递(Linux、Solaris)
• 通过程序放在或压入堆栈中，并通过操作系统弹出

2.4 系统调用类型

系统调用大致可分成5类：进程控制、文件管理、设备管理、信息维护、通信。

控制卡是一个批处理系统概念，它是一个管理进程执行的命令。如果程序非正常终止，它可能需要定义一个错误级别。

Solaris 10操作系统包含了dtrace动态跟踪工具，可以动态探测运行的系统。

通信有两种模型：消息传递模型(message-passing model)、共享内存模型(shared-memory model)。

2.5 系统程序

• 文件管理
• 状态信息：日期、可用内存等等
• 文件修改
• 程序语言支持
• 程序装入和执行
• 通信

2.6 操作系统设计和实现

设计目标：用户目标和系统目标

策略(policy)和机制(mechanism)是重要原理，机制决定如何做，策略决定做什么。

2.7 操作系统结构

内核和系统程序独立组成，内核进一步分成一系列接口和驱动程序。

系统模块化可用分层法，即操作系统分成若干层，最底层是硬件，最高层是用户接口。

Mach操作系统采用了微内核(microkernel)技术来模块化内核，这种方法将所有非基本部分从内核中移走，并将它们实现为系统程序或用户程序。

2.8 虚拟机

虚拟机本身只能运行在用户模式，所以要模拟出虚拟用户模式和虚拟内核模式。

• VMware
• Java JVM
• .NET CLR

2.9 系统生成

对于某个特定的计算机场所，必须要配置和生成系统，这一过程有时称为系统生成(system generation, SYSGEN)。

2.10 系统启动

引导程序(引导装载程序)能定位内核，将它装入内存，开始执行。

第3章 进程

3.1 进程概念

进程包括程序代码(文本段)、当前活动(通过程序计数器的值和寄存器的内容来表示)、进程堆栈段、数据段、堆。

程序是被动实体，进程是活动实体。

每个进程在操作系统内用进程控制块(process control block, PCB, 也叫任务控制块)来表示：

• 进程状态
• 程序计数器
• CPU寄存器
• CPU调度信息：包括进程优先级、调度队列的指针和其他调度参数
• 内存管理信息：基址、界限寄存器的值、页表或段表
• 记账信息：CPU时间、实际使用时间、时间界限、记账数据、作业或进程数量
• I/O状态信息：分配给进程的I/O设备列表、打开的文件列表

3.2 进程调度

多道程序设计中，进程调度选择一个可用的进程到CPU上执行。

就绪队列通常用链表来实现，其头节点指向链表的第一个和最后一个PCB块的指针，每个PCB包含一个指向就绪队列的下一个PCB的指针域。

// Linux的进程控制块
struct task_struct {
  pid_t pid; /* process identifier */
  long state; /* state of the process */
  unsigned int time_slice; /* scheduling information */
  struct files_struct* files; /* list of open files */
  struct mm_struct* mm; /* address space of this process */
};

等待特定I/O设备的进程列表称为设备队列。

进程分配到CPU执行时，发生下面的事件之一：

• 进程可能发出一个I/O请求，并被放到I/O队列中
• 进程可能创建一个新的子进程，并等待其结束
• 进程可能会由于中断而强制释放CPU，并被放回到就绪队列中

进程选择是由相应的调度程序(scheduler)来执行的：长期调度程序(long-term scheduler)或作业调度程序(job scheduler)从缓冲池中选择进程，并装入内存以准备执行。短期调度程序(short-term scheduler)或CPU调度程序从准备执行的进程中选择进程，并为之分配CPU。两者的主要区别在于它们的执行频率。

有的系统没有长期调度程序，UNIX和Windows的分时系统只是简单地将所有新进程放在内存中以供短期调度程序使用。这些系统地稳定性依赖于物理限制(如可用的终端数)或用户的自我调整。

有的系统如分时系统引入了中期调度程序(medium-term scheduler)，其核心思想是能将进程从内存或CPU竞争中移出，从而降低多道程序设计的程度。进程能被重新调入内存，并从中断处继续执行，这种方案叫做交换(swapping)。

上下文切换(context switch)：将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态。

3.3 进程操作

进程能通过创建进程系统调用(create-process system call)创建多个新进程，从而形成进程树。大多数操作系统根据一个唯一的进程标识符(process identifier, pid)来识别进程，pid通常是一个整数值。

在Solaris系统里面，树顶端的进程是标识符为0的Sched进程。Sched进程生成几个子进程，包括pageout和fsflush，分别负责内存管理和文件系统。Sched进程还生成init进程，作为所有用户进程的根进程。

命令ps -el可以列出系统所有当前活动进程的完整信息。

#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

int main(void) {
    pid_t pid = fork();
    if (pid < 0) {
        fprintf(stderr, "Fork Failed\n");
        exit(-1);
    } else if (pid == 0) {
        // child process
        execlp("/bin/ls", "ls", NULL);
    } else {
        // parent will wait for the child to complete
        wait(NULL);
        printf("Child Complete");
        exit(0);
    }
}

#include <windows.h>
#include <stdio.h>

int main(void) {
    STARTUPINFO si;
    PROCESS_INFORMATION pi;

    // allocate memory
    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    // create child process
    if (!CreateProcess(NULL, 
        "C:\\Windows\\system32\\mspaint.exe",
        NULL,
        NULL,
        FALSE,
        0,
        NULL,
        NULL,
        &si,
        &pi)) {
        fprintf(stderr, "Create Process Failed");
        return -1;
    }
    WaitForSingleObject(pi.hProcess, INFINITE);
    printf("Child Complete");

    // close handles
    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);
}

进程可以通过适当的系统调用来终止另一个进程，比如Win32的TerminateProcess()，但是只有被终止进程的父进程才能执行这以系统调用。

级联终止(cascading termination)：父进程已终止的情况下，某些系统不允许子进程再存在，子进程的终止由操作系统进行。

3.4 进程间通信

操作系统内并发执行的进程可以是独立进程或协作进程。独立进程不能影响其他进程或被其他进程所影响，协作进程能影响其他进程或被其他进程影响。

使用进程协作的理由：

• 信息共享
• 提高运算速度，子任务
• 模块化
• 方便

协作进程需要一种进程间通信机制(inter process communication, IPC)来允许进程相互交换数据与信息。通信基本模式：共享内存、消息传递。

缓冲：无限缓冲(unbounded-buffer)、有限缓冲(bounded-buffer)。

通信需要通信线路(communication link)，该线路有多种实现方法：

• 直接或间接通信
• 同步或异步通信
• 自动或显式缓冲

直接通信：send(P, message)、receive(Q, message)。

间接通信：send(A, message)、receive(A, message)。

同步异步通信：阻塞send、非阻塞send和阻塞receive、非阻塞receive组合。

缓冲：零容量(阻塞send)、有限容量、无限容量。

3.5 IPC系统的实例

POSIX共享内存：

进程必须首先用系统调用shmget()创建共享内存段，想访问共享内存段的进程必须采用shmat()系统调用来将其加入地址空间，然后使用shmat()返回的指针来访问共享内存。当进程不再需要访问共享内存段时，将指针传递给系统调用shmdt()分离共享内存段。shmctl()用于删除共享内存段。

Mach：

• msg_send()：向邮箱发送消息
• msg_receive()：接收消息
• msg_rpc()：远程过程调用(RPC)，能发送消息并只等待来自发送者的一个返回信息
• port_allocate()：创建新邮箱并为其消息队列分配空间

Windows XP：

Windows XP的消息传递工具称为本地过程调用(LPC)工具。端口消息传递最多能发送256B消息，更大的消息需要通过区段对象(构建共享内存)来传递消息。

Windows XP的LPC工具并不是Win32 API的一部分，应用程序应该使用Win32 API调用标准用的远程过程调用。

3.6 客户机-服务器系统通信

• Socket：服务器监听指定端口，客户端发送Socket连接。
• 远程过程调用(RPC)：RPC语义允许客户机调用位于远程主机上的过程，需要定义数据的机器无关表示
• 远程方法调用(RMI)：类似RPC的Java特性，远程指JVM不同，基于对象

第4章 线程

4.1 概述

线程是CPU使用的基本单元，它由线程ID、程序计数器、寄存器集合和栈组成。它与属于同一进程的其他线程共享代码段、数据段和其他操作系统资源。

多线程编程有下列优点：

• 响应度高，即使有阻塞和执行较冗长的操作，程序仍能继续执行
• 资源共享
• 经济，不用执行创建进程所需要的内存和资源的分配工作
• 多处理器体系结构的利用，加强并发功能

4.2 多线程模型

有两种不同方法来提供线程支持：用户层的用户线程、内核层的内核线程。用户线程受内核支持，而无需内核管理；而内核线程由操作系统直接支持和管理。

多对一模型将许多用户级线程映射到一个内核线程。线程管理是由线程库在用户空间进行的，因而效率比较高。但如果一个线程执行了阻塞系统调用，那么整个进程会阻塞。因为任一时刻只有一个线程能访问内核，多个线程不能并行运行在多处理器上。Green thread(Solaris所应用的线程库)和GNU可移植线程(GNU Portable Threads)就是使用了这种模型。

一对一模型将每个用户线程映射到一个内核线程。缺点是每创建一个用户线程就需要创建一个相应的内核线程。Linux和Windows使用一对一模型。

多对多模型多路复用了许多用户线程到同样数量或更小数量的内核线程上。多对多模型没有两者的缺点：开发人员可以创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行。IRIX、HP-UX、Tru64 UNIX等操作系统支持多对多模型，Solaris 9之前支持二级模型，之后开始使用一对一模型。

4.3 线程库

线程库(thread library)为程序员提供创建和管理线程的API，有两种方法实现线程库：

• 在用户空间中提供一个没有内核支持的库，库的代码和数据结构都存在用户空间中。
• 执行一个由操作系统直接支持的内核级的库，库的代码和数据结构都存在内核空间中。

目前常用的三种线程库：

• POSIX Pthread：作为POSIX标准的扩展，可以提供用户级或内核级的库。
• Win32：适用于Windows的内核级线程库。
• Java：线程API允许线程在Java程序中直接创建和管理，通常采用宿主系统上的线程库来实现。

Pthread是由POSIX标准(IEEE 1003.1c)为线程创建和同步定义的API，这是线程行为的规范，而不是实现。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int sum;
void* runner(void* param);

int main(int argv, char* args[]) {
    pthread_t tid;
    pthread_attr_t attr;
    if (argv != 2) {
        fprintf(stderr, "usage: ./a.out <integer value>\n");
        return -1;
    }
    if (atoi(args[1]) < 0) {
        fprintf(stderr, "%d must be >= 0\n", atoi(args[1]));
        return -1;
    }
    pthread_attr_init(&attr);
    pthread_create(&tid, &attr, runner, args[1]);
    pthread_join(tid, NULL);
    printf("sum = %d\n", sum);
}

void* runner(void* param) {
    int upper = atoi(param);
    sum = 0;
    for (int i = 1; i <= upper; i++) {
        sum += i;
    }
    pthread_exit(0);
}

Windows32线程库创建线程的技术与Pthread很相似。

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

DWORD sum;
DWORD WINAPI Summation(LPVOID param);

int main(int argv, char* args[]) {
    DWORD threadId;
    HANDLE threadHandle;
    int param;
    if (argv != 2) {
        fprintf(stderr, "usage: ./a.exe <integer value>\n");
        return -1;
    }
    param = atoi(args[1]);
    if (param < 0) {
        fprintf(stderr, "%d must be >= 0\n", atoi(args[1]));
        return -1;
    }
    threadHandle = CreateThread(NULL, 0, Summation, &param, 0, &threadId);
    if (threadHandle != NULL) {
        WaitForSingleObject(threadHandle, INFINITE);
        CloseHandle(threadHandle);
        printf("sum = %d\n", sum);
    }
}

DWORD WINAPI Summation(LPVOID param) {
    DWORD upper = *(DWORD*) param;
    for (DWORD i = 1; i <= upper; i++) {
        sum += i;
    }
    return 0;
}

Java程序中有两种创建线程的技术：一种是创建一个新的类，它从Thread类派生，并重写其run()；另一种方法是定义一个实现Runnable接口的类。

public final class JavaThread {
    private JavaThread() {
        // Do nothing
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            int upper = Integer.parseInt(args[0]);
            if (upper < 0) {
                System.err.println(args[0] + " must be >= 0");
            } else {
                Sum sum = new Sum();
                Thread thrd = new Thread(new Summation(upper, sum));
                thrd.start();
                try {
                    thrd.join();
                    System.out.println("sum = " + sum.getSum());
                } catch (InterruptedException ie) {
                    System.err.println(ie.toString());
                }
            }
        } else {
            System.err.println("usage: java JavaThread <integer value>");
        }
    }
}

final class Sum {
    private int sum;

    public int getSum() {
        return sum;
    }

    public void setSum(int value) {
        this.sum = value;
    }
}

final class Summation implements Runnable {
    private int upper;
    private Sum sumValue;

    public Summation(int upper, Sum sumValue) {
        this.upper = upper;
        this.sumValue = sumValue;
    }

    public void run() {
        int sum = 0;
        for (int i = 1; i <= upper; i++) {
            sum += i;
        }
        sumValue.setSum(sum);
    }
}

4.4 多线程问题

有的UNIX系统有两种形式的fork()，一种复制所有的线程，另一种只复制调用了系统调用fork()的线程。如果一个线程调用了系统调用exec()，那么exec()参数所指定的程序会替换整个进程，包括所有线程。

线程取消(thread cancellation)是在线程完成之前来终止线程的任务。要取消的线程通常称为目标线程，目标线程的取消可在如下两种情况下发生:

1. 异步取消(asynchronous cancellation)：一个线程立即终止目标线程。
2. 延迟取消(deferred cancellation)：目标线程不断地检查它是否应终止，这允许目标线程有机会以有序方式来终止自己。

异步取消线程并不会使所需的系统资源空闲，相反采用延迟取消时，需要一个线程检查一个标志以确定它是否应该取消。Pthread称这些点为取消点(cancellation point)。

信号在UNIX中用来通知进程某个特定事件已发生了，可以同步或异步接收。每个信号都有一个默认信号处理程序(default signal handler)，当处理信号时在内核中运行。

单线程程序的信号总是发给进程，多线程程序中，同步信号需要发送到产生这一信号的线程，而异步信号情况就不是那么清楚了。有些异步信号如终止进程信号(Ctrl+C)应该发送给所有线程。

UNIX信号发送：

• kill(pid_t pid, int signal)：标准的发送信号的UNIX函数
• pthread_kill(pthread_t tid, int signal)：POSIX Pthread提供的函数，允许发送到指定线程

Windows不明确提供对信号的支持，但是能通过异步过程调用(asynchronous procedure call, APC)来模拟。APC只发送特定线程而不是进程。

线程池(thread pool)的主要思想是在进程开始时创建一定数量的线程，并放入到池中以等待工作。当服务器收到请求时，它会唤醒池中的一个线程(如果有可以用的线程)，并将要处理的请求传递给它。

线程池的优点：

• 通常用现有线程处理请求要比等待创建新的线程要快。
• 线程池限制了在任何时候可用线程的数量。

许多实现多对多模型或二级模型的系统在用户和内核线程之间设置一种中间数据结构，通常是轻量级进程(LWP)。对于用户线程库，LWP表现为一种应用程序可以调度用户线程来允许的虚拟处理器，每个LWP与内核线程相连。

一种解决用户线程库与内核间通信的方法被称为调度器激活(scheduler activation)。内核提供一组虚拟处理器(LWP)给应用程序，应用程序课调度用户线程到一个可用的虚拟处理器上。进一步说，内核必须告知与应用程序有关的特定事件，这个过程被称为upcall。

4.5 操作系统实例

• Windows XP线程：提供了fiber库的支持，该库提供了多对多模型的功能。
• Linux线程：传统进程复制fork()、创建线程clone()，Linux不区分进程和线程，通常称之为任务。

第5章 CPU调度

5.1 基本概念

CPU的成功调用依赖于进程的如下属性：进程执行由CPU执行和I/O等待周期组成。

每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序(short-term scheduler)或CPU调度程序执行。就绪队列不必是先进先出(FIFO)队列。

CPU调度决策在4种环境下发生：

• 当一个进程从运行状态切换到等待状态(如I/O请求)
• 当一个进程从运行状态切换到就绪状态(如中断发生)
• 当一个进程从等待状态切换到就绪状态(如I/O完成)
• 当一个进程终止时

1、4两种情况没有选择只有调度，称调度方案是非抢占的(non-preemptive)或协作的(co-operative)。2、3两种情况可以选择，称调度方案是抢占的(preemptive)。

抢占调度对访问共享数据是有代价的，对内核的设计也有影响。

与CPU调度功能有关的另一个部分是分派程序(dispatcher)。分派程序是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。功能：

• 切换上下文
• 切换到用户模式
• 跳转到用户程序的合适位置，以重新启动程序

分派程序停止一个进程而启动另一个所要画的时间称为分派延迟(dispatch latency)。

5.2 调度准则

• CPU使用率
• 吞吐量
• 周转时间
• 等待时间
• 响应时间

5.3 调度算法

• 先到先服务调度(first-come, first-served(FCFS) scheduling algorithm)

FCFS策略可以用FIFO队列来容易地实现，但是平均等待时间通常较长。(护航效果convoy effect)

FCFS调度算法是非抢占的。

• 最短作业优先调度算法(shortest-job-first(SJF) scheduling algorithm)

SJF策略是最佳的，因为平均等待时间最小，但是真正困难是如何知道下一个CPU区间的长度。

SJF调度经常用于长期调度。SJF算法可能是抢占的或非抢占的，抢占SJF调度有时称为最短剩余时间优先调度(shortest-remaining-time-first scheduling)。

• 优先级调度算法(priority scheduling algorithm)

SJF算法可作为通用优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU，具有相同优先级的进程按FCFS顺序调度。

优先调度可以是抢占的或者非抢占的。优先级调度算法的一个主要问题是无穷阻塞(indefinite blocking)或饥饿(starvation)。低优先级进程无穷等待问题的解决之一是老化(aging)，逐渐增加在系统中等待很长时间的进程的优先级。

• 轮转法调度(round-robin, RR)

轮转法调度算法是专门为分时系统设计的，类似于FCFS调度，但是增加了抢占以切换进程。定义一个较小时间单元，称为时间片(time quantum, or time slice)，将就绪队列作为循环队列，设置定时器在一个时间片之后中断。

RR算法的性能很大程度上依赖于时间片的大小。如果时间片很小，那么RR算法称为处理器共享，每个进程对于用户都有它自己的处理器。这种方法用在Control Data Corporation(CDC)的硬件上，可以用一组硬件和10组寄存器实现10个外设处理器。

根据经验，80%的CPU区间应该小于时间片。

• 多级队列调度(multilevel queue scheduling algorithm)

多级队列调度算法将就绪队列分成多个独立队列，根据进程的属性，如内存大小、进程优先级、进程类型，一个进程被永久地分配到一个队列中。

每个队列有自己的调度算法，队列之间通常采用固定优先级抢占调度。

• 多级反馈队列调度(multilevel feedback queue scheduling algorithm)

多级反馈队列调度算法允许进程在队列之间移动，主要实现是根据不同CPU区间的特点以区分进程。

5.4 多处理器调度

• 非对称多处理(asymmetric multiprocessing)：让一个处理器处理所有的调度决定、I/O处理以及其他系统活动。
• 对称多处理(symmetric multiprocessing, SMP)：每个处理器自我调度。

处理器亲和力是指SMP系统试图避免将进程从一个处理器移至另一个处理器，而是努力使一个进程在同一个处理器运行。

• 软亲和性(soft affinity)：一个操作系统具有设法让一个进程保持在同一个处理器上运行的策略，但不能做任何保证。
• 硬亲和性(hard affinity)：运行进程指定它不允许移至其他处理器上。

负载平衡通常有两种方法：push migration和pull migration。负载平衡常会抵消处理器亲和性的优点。

对称多线程(SMT)：提供多个逻辑处理器，也被称为超线程技术(hyperthreading)。

5.5 线程调度

• 进程竞争范围(process-contention scope, PCS)：用户级线程
• 系统竞争范围(system-contention scope, SCS)：内核线程

#include <pthread.h>
#include <stdio.h>

#define NUM_THREADS 5

void* runner(void* param);

int main(int argv, char* args[]) {
    int scope;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    if (pthread_attr_getscope(&attr, &scope) != 0) {
        fprintf(stderr, "Unable to get scheduling scope.\n");
    } else {
        if (scope == PTHREAD_SCOPE_PROCESS) {
            printf("PTHREAD_SCOPE_PROCESS\n");
        } else if (scope == PTHREAD_SCOPE_SYSTEM) {
            printf("PTHREAD_SCOPE_SYSTEM\n");
        } else {
            fprintf(stderr, "Illegel scope value.\n");
        }
        pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
        for (int i = 0; i < NUM_THREADS; i++) {
            pthread_create(&tid[i], &attr, runner, NULL);
        }
        for (int i = 0; i < NUM_THREADS; i++) {
            pthread_join(tid[i], NULL);
        }
    }
}

void* runner(void* param) {
    printf("Hello, world\n");
    pthread_exit(0);
}

5.6 操作系统实例

• Solaris调度

Solaris采用基于优先级的线程调度，根据优先级不同，有4类调度：实时、系统、分时、交互。

调度类别	全局优先级	调度顺序	运行队列
实时	最高	先	实时LWP的内核线程
系统	中级	中	内核服务线程
交互、分时	最低	后	交互和分时LWP的内核线程

进程默认的调度类型是分时，分时调度方法采用多级反馈队列，动态地调整优先级和赋予不同长度地时间片。Solaris 9引入了两种新的调度类型：固定优先级(fixed priority)、公平共享(fair share)。

• Windows XP调度

Windows XP采用基于优先级的、抢占调度算法来调度线程，调度程序使用32级优先级方案以确定线程执行的顺序。优先级分为两大类型：可变类型(variable class)包括1~15优先级的线程，实时类型(real-time class)包括16~31优先级的线程，优先级0的线程用于内存管理。

如果没有就绪线程，那么调度程序会执行一个称为空闲线程(idle thread)的特别线程。

• Linux调度

在2.5版本之前，Linux内核运行传统的Unix调度算法，不提供对SMP系统足够的支持，以及当系统任务数量增加时不能按比例调整。2.5版本之后，调度程序被分解，内核提供在固定时间内运行的调度算法。

Linux调度程序是抢占的、基于优先级的算法，具有两个独立的优先级范围：从0_{99的**real-time**范围和从100}140的nice范围。与Solaris和Windows XP在内的其他许多系统的调度程序不同，Linux给较高的优先级分配较长的时间片，给较低的优先级分配较短的时间片。

5.7 算法评估

• 分析评估法(analytic evaluation)：使用给定算法和系统负荷，产生一个公式或数字，以评估对于该负荷算法的性能。
• 确定模型法(deterministic modeling)：采用特殊预先确定的负荷，计算在给定负荷下每个算法的性能。

第6章 进程同步

6.1 背景

多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为竞争条件(race condition)。为了避免竞争条件，需要一定形式的进程同步(process synchronization)和协调(coordination)。

6.2 临界区问题

每个进程有一个代码段称为临界区(critical section)，在该区中进程可能改变共同变量、更新一个表、写一个文件等。当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区执行。

临界区问题(critical-section problem)是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区，实现请求的代码段称为进入区(entry section)，临界区之后有退出区(exit section)，其他代码为剩余区(remainder section)。

临界区问题的解答必须满足如下三项要求：

• 互斥(mutual exclusion)：如果进程在其临界区内执行，那么其他进程都不能在其临界区内执行。
• 前进(progress)：如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那些不再剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟。
• 有限等待(bounded waiting)：从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区的次数有上限。

处理操作系统内的临界区问题：

• 抢占内核(preemptive kernel)：允许处于内核模式的进程被抢占，适合实时编程，响应更快。
• 非抢占内核(non-preemptive kernel)：不允许处于内核模式的进程被抢占，从根本上不会导致竞争条件。

6.3 Peterson算法

Peterson算法适用于两个进程在临界区与剩余区间交替执行。

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    // 临界区
    flag[i] = false;
    // 剩余区
} while (true);

i是执行的进程，j是另一个进程，ture标识哪个进程可以进入其临界区，turn、flag是内存共享的。

6.4 硬件同步

任何临界区问题都需要一个简单工具——锁。

do {
    // 请求锁
    // 临界区
    // 释放锁
    // 剩余区
} while (true);

许多现代计算机系统提供了特殊硬件指令以允许能原子地(不可中断地)检查和修改字地内容或交换两个字的内容(作出不可中断的指令)。

比如指令TestAndSet()的定义：

bool TestAndSet(bool* target) {
    bool rv = *target;
    *target = true;
    return rv;
}

使用TestAndSet()的互斥实现：

do {
    while (TestAndSet(&lock));
    // critical section
    lock = false;
    // remainder section
} while (true);

6.5 信号量

信号量(semaphore)用于解决TestAndSet、Swap使用复杂的问题。信号量S是个整数变量，除了初始化外，只能通过两个标准原子操作wait()和signal()来访问，这些操作被称为P(荷兰语proberen测试)和V(荷兰语verhogen增加)。

wait(S) {
    while (S <= 0);
    S--;
}

signal(S) {
    S++;
}

操作系统区分计数信号量与二进制信号量，计数信号量的值域不受限制，而二进制信号量只能为0或1。通常称二进制信号量为互斥锁，因为可以提供互斥。

这里所定义的信号量的主要缺点是都要求忙等待(busy waiting)，这种类型的信号量也称为自旋锁(spinlock)。自旋锁的优点是，进程在等待锁时不进行上下文切换。

为了克服忙等待，可以修改信号量操作，使得进程不是忙等而是阻塞自己。这里信号量定义应该为如下结构体：

typedef struct {
    int value;
    struct process* list;
} semaphore;

死锁(deadlocked)：两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。

无限期阻塞(indefinite blocking)：饥饿(starvation)，即进程在信号量内无限期等待。

6.6 经典同步问题

• 有限缓冲问题：通常用来说明同步原语地能力。
• 读者-写者问题：写者对共享数据库有排他地访问。
• 哲学家进餐问题：并发控制、同步问题，死锁与饥饿的典型例子。

6.7 管程

当信号量不正确地用来解决临界区问题时，会很容易地产生各种类型的错误。为了处理这些类型的错误，研究者提出高级的同步构造——管程(monitor)类型。

管程类型提供了一组由程序员定义的、在管程内互斥的操作。管程类型的表示包括一组变量的声明(这些变量的值定义了一个类型实例的状态)和对这些变量操作的子程序和函数的实现。管程类型的表示不能直接为各个进程所使用，在管程内定义的子程序只能访问位于管程内那些局部声明的变量和形式参数。类似地，管程的局部变量只能被局部子程序访问。

管程结构确保一次只有一个进程能在管程内活动。对于特定同步方案，需要定义一些额外的同步机制，这些可由条件(condition)结构来提供。

6.8 同步实例

• Solaris同步

为了控制访问临界区，Solaris提供了适应互斥、条件变量、信号量、读写锁和十字转门。

Java为线程同步提供一个类似于管程的并行机制，Java中的每一个对象都有一个单独的锁。当方法声明为synchronized时，调用方法要求拥有对象的锁。

public class SimpleClass {
    public synchronized void safeMethod() {
        /* ... */
    }
}

SimpleClass sc = new SimpleClass();

调用sc.safeMethod()要求拥有对象实例sc的锁，如果锁被其他线程所有，则调用同步方法的线程阻塞，并被放入对象锁的进入集合中。

Java提供wait()和notify()方法，类似于管程的wait()、signal()的功能，在java.util.concurrent包中为信号量、条件变量、互斥锁还有其他并发机制提供API支持。

适应互斥(adaptive mutex)保护对每个临界数据项的访问。在多处理器系统中，适应互斥以自旋锁实现的标准信号量而开始，请求锁的线程可以选择自旋并等待锁可用，也可用阻塞进入睡眠直到锁释放被唤醒。在单处理器系统中，请求锁的线程总是睡眠而不是自旋，因为某一时刻只有一个线程可以运行。

Solaris使用适应互斥方法以保护那些为较短代码段所访问的数据，如果代码较长，那么自旋等待就极为低效了。

读写锁用于保护经常访问但通常是只读访问的数据，在这种情况下，读写锁比信号量更为有效。因为多个线程可以同时读数据，而信号量只允许顺序访问数据。读写锁实现代价要大，通常只用于很长的代码段。

Solaris使用十字转门以安排等待获取适应互斥和读写锁的线程链表。十字转门(turnstile)是一个队列结构，包含阻塞在锁上的线程。Solaris不是将每个同步对象与一个十字转门相关联，而是给每个内核线程一个十字转门。用于第一个线程阻塞于同步对象的十字转门成为对象本身的十字转门，以后阻塞于该锁上的线程会添加到该十字转门上。最终释放锁时，会从内核所维护的空闲十字转门中获得一个新的十字转门。

为了防止优先级倒置，十字转门根据优先级继承协议来组织。如果较低优先级的线程拥有一个较高优先级线程锁阻塞的锁，那么该低优先级线程会暂时继承较高优先级线程的级别。在释放线程之后，线程会返回到它原来的优先级。

• Windows XP同步

在单处理器中，Windows XP访问全局资源时，会暂时屏蔽所有可能访问该全局资源的中断处理程序的中断。在多处理器中，Windows XP采用自旋锁来保护对全局资源的访问。与Solaris一样，内核只使用自旋锁来保护较短代码段。由于效率原因，内核会确保拥有自旋锁的线程决不会被抢占。

对于内核外线程的同步，Windows XP提供了调度对象(dispatcher object)。采用调度对象，线程可根据多种不同机制，包括互斥、信号量、事件和定时器等来进行同步。

调度对象可以处于触发状态(signal state)或非触发状态(non-signal state)。触发状态表示对象可用且线程在获取它时不会阻塞，非触发状态表示对象不可用且当线程试图获取它时会阻塞。

• Linux同步

Linux内核提供自旋锁和信号量(还有着两种锁的读者-写者版本)，以进行内核加锁。Linux提供两个简单系统调用preempt_disable、preempt_enable用来禁止与允许内核抢占。

• Pthread同步

Pthread API为线程同步，提供互斥锁、条件变量、读写锁。

6.9 原子事务

数据库系统关注于数据的存储和提取及数据的一致性。

执行单个逻辑功能的一组指令或操作称为事务(transaction)。处理事务的主要问题是不管出现什么计算机系统的可能失败，都要保证事务的原子性。

从用户观点来看，事务只是一系列read操作和write操作，并以commit操作或abort操作终止。已成功完成执行的终止事务称为提交(committed)；否则，称为撤销(aborted)。被中止的事务所访问的数据状态必须回复到事务刚刚开始执行之前，即这个事务已经回退(rolled back)。

确保原子性的一种方法是在稳定存储上记录有关事务对其访问的数据所做各种修改的描述信息，实现着种形式记录最为常用的方法是先记日志后操作。

为了避免出错时搜索整个日志，引入了检查点(checkpoint)的概念。系统定期执行检查点，执行下列步骤：

1. 将当前驻留易失性存储的所有日志记录输出到稳定存储上。
2. 将当前驻留易失性存储的所有修改数据输出到稳定存储上。
3. 在稳定存储上输出一个日志记录<checkpoint>。

事务的并发执行必须相当于这些事务按任意顺序串行执行，这一属性称为串行化(serializability)。

• 串行化能力
• 加锁协议
• 基于时间戳的协议