日常学习

现代操作系统

May 24, 2021
oslinux

现代操作系统：

抽象是管理复杂性的关键， 好的抽象可以把一个 不可能管理的任务 分为 两个可管理的部件。 抽象的定义和实现 + 用这些抽象解决的问题。
操作系统的任务 就是 创建好的抽象 并实现和管理它所创建的抽象对象。抽象内容是理解操作系统的关键。

作为资源管理者的操作系统：

资源管理包括 以下两种不同方式实现 多路复用（共享）资源：时间上 复用 + 空间上复用 。

网络操作系统 与 分布式 操作系统： 网络操作系统 与 单处理器的操作系统没有本质区别。 分布式操作系统 则 与 集中式系统 有本质的区别，用户根本不知道自己的文件存储在什么地方，任务在那个机器上运行，网络中的通信延迟导致 分布式算法必须能够适应信息不完备、信息过时、信息错误的情况。这与 单机形成对比， 单机系统中操作系统掌握着完全的信息。因此 需要更复杂的处理器调度算法 来获得 更大的并行度。

处理器：

超标量CPU： 此设计中， 存在多个执行单元比如： 1个CPU 用于整数计算 + 1个cpu用于浮点数计算。 该设计 可能导致 程序中的指令 经常不按照 顺序执行。在多数情况下， 硬件负责 保证这种运算结果与顺序执行指令的结果相同，但是，应有部分 复杂情形 需要操作系统 来处理。

内核态 + 用户态： PSW 中存在 二进制 位 控制该模式，内核态： cpu 可执行 指令集中的任何一条命令， 用户态： 则 只能执行指令集的一个子集。（比如IO 操作） 为了从操作系统获得服务， 用户必须 使用 系统调用 以陷入内核 调用 操作系统。TRAP 指令 从用户态切换到内核态。

计算机使用陷阱 而非 一条指令来执行 系统调用， 而其他的多数陷阱 是由硬件引起的，用于 异常的发生，比如 除以 0。

多线程 和 超线程： 多线程允许 cpu 保持两个不同的线程状态， 然后在纳秒级别内进行切换，多线程并非真正的并行处理， 在同一时刻 只有一个进程运行，但是线程的切换时间 为纳秒级别

多核CPU

存储器系统： 寄存器 高速缓存 主存 磁盘

通常通过 所引用内存地址的 高位地址 计算应该使用的缓存行。比如 对于64字节的 4096个缓存行 以及32位地址， 其中 6-17位 用来定位缓存行，而 0-5 则用来确定缓存行中的字节

IO 设备包括： 设备控制器 + 设备本身， 控制器 从操作系统接受指令，完成数据的处理。 控制器的任务是为操作系统提供一个简单的接口， 来处理 设备提供的数据。
驱动程序
将设备驱动程序 装载到 操作系统有三个方法：
  1. 将内核与驱动程序重新链接， 然后重启操作系统
  2. 在操作系统文件中设定一个入口，并通知该文件需要一个设备驱动程序， 然后重启系统， 在启动中， 操作系统 去寻找所需的设备驱动程序 并将其装载 （Windows 工作方式）
  3. 操作系统在运行时 接受新的设备驱动程序 并立即 将其安装好， 无需重启， 即是热插拔， USG IEEE 1394设备。
输入+输出的三种方式：
  1. 忙等待： 用户程序发出一个系统调用，内核将其翻译成对应的 设备驱动程序 调用， 然后设备驱动程序 在一个连续不断的循环中检查设备，查看该设备是否万和城呢够了工作， 当IO 接手后， 设备驱动程序 将数据送到指定的地方， 并返回，然后操作系统将控制返回给 调用者，确定为 占据CPU， CPU 会一直轮训 设备知道对应的IO操作完成。
  2. 设备驱动程序 启动设备并且让该设备在操作完成时 发出一个中断， 设备驱动程序在这个时候 返回， 操作系统 阻塞调用者，并进行其他工作， 当设备驱动程序 检测到该设备完成时候，将发出一个中断通知操作完成。其中中断是一个非常重要的概念，IO 分为三步， 1） 设备驱动程序 通过写设备寄存器通知设备控制器做什么，然后 设备控制器 启动该设备， 当设备控制器完成操作 2） 使用特定的总线发送信号给中断控制器芯片
  3. 中断控制芯片 接受中断，他会在CPU芯片的一个管脚上声明，
  4. 中断控制器将该设备的编号 放到总线上，这样 CPU可以读取总线，并指导那个设备完成了操作。 中断 处理程序： … d第三种） 使用特殊的直接存储器访问 (Direct Memory Access, DMA) 芯片， 它可以 控制内存和某些控制前 之间的位流， 而无需 持续的CPU 干涉，cpu 对dma芯片 进行设置， 说明 需要传送的字节数、有关设备、和内存地址 以及操作方向， 接着启动DMA 当DMA芯片完成时，它会 引发一个中断，。

中断： 中断会发生在非常不合适的时刻， 比如另外一个中断程序正在运行时发生，如果此时接受中断 可能导致 中断程序的递归处理。所以cpu 会关闭中断并在稍后在开启中断，中断关闭时： 任何已经发出中断的设备，可以继续保持其中断信号，但是cpu不会被中断，直到中断再次启用为止， 如果多个设备发生了中断，则 中断控制器 将决定先处理那个中断， 通常这取决于 事先赋予每个设备的静态优先级，最高优先级的设备得到优先处理，其他的设备则等待。

总线以及其演变
操作系统分类：
  1. 大型机操作系统 主要面向多作业的同时处理， 多数这样的作业 需要大量的IO能力， 系统主要提供三类服务： 批处理、事务处理、分时。事务处理系统负责大量小的任务， 比如航班预订任务， 每个业务量很小，但是 系统需要每秒处理上千个业务。在部分领域 大型机系统 正在被 Linux 取代
  2. 服务器操作系统： 服务器可以是 大型的个人计算、工作站、甚至是大型机， 他们通过网络为若干个用户服务，。
  3. 多处理器操作系统： 将大量CPU链接成单个系统。 根据连接和共享方式的不同，这些系统称为 并行计算机 、多计算机、多处理器。个人计算机也开始普及 多核芯片。
  4. 个人计算机操作系统
  5. 掌上计算机操作系统：
  6. 嵌入式操作系统
  7. 传感器节点操作系统： 许多用途需要微小传感器的节点网络。比如森林火灾探测，气象探测器。 此类传感器 能源资源有限。 每个节点上运行一个小型但是真实的操作系统，通常操作系统是事件驱动的，可以相应外部事件 或者基于内部的时钟进行周期性检测，该系统必须小而简单，InyOS 是一个知名的该类操作系统
  8. 实时操作系统： 系统的特征是将时间作为关键参数，比如工业过程控制系统，焊接机器人 焊接的太早 或者太晚 都有可能造成物品 损坏，所以需要在规定的时间内进行操作， 这就是硬实时系统。另一个则是软实时系统， 即： 偶尔的超时是可以接受的。
  9. 智能卡系统： 比如包含一块cpu芯片的信用卡
操作系统周边概念:
  1. 进程： 正在执行的程序，容纳一个程序所需要的所有信息的容器。包括相关的地址空间（存放 可执行程序， 程序数据，以及堆栈 ） + 进程相关的资源集 + 寄存器 + 打开的文件清单 + 信号 等 以及 运行进程需要的其他的信息。
  2. 进程表： 操作系统中存储 每一个进程有关的所有信息 放在一张表中：进程表。
  3. 系统调用： 创建进程 、 申请内存、等待进程结束 etc
  4. 信号： 无论进程在做什么，进程将被暂时挂起， 然后运行进程信号处理器， 这些信号 是软件模拟的硬件中断。
  5. 系统管理授权； 启动进程的用户UID， GID group id
    地址空间： 虚拟内存技术， 本质上 操作系统创建了一个地址空间的抽象，作为进程可以引用地址的集合， 改地址空间与物理内存解耦，可能大于也可能小于 物理空间。 对地址空间和物理空间的管理组成了操作系统功能的一个重要部分。
    文件系统：
    • 文件： 支持操作系统的另一个关几年概念。 一项重要功能 即是：隐藏磁盘和其他IO设备的细节特性， 提供一个良好的清晰的独立与设备的抽象文件模型。
    • 目录： 将文件分类成组。 目录中的目录项可以使文件或者目录， 从而产生了一个层次结构—-文件系统。
    • 进程和文件层次都可以组成为树状结构，但是： 一般进程的树状结构 不会超过三层， 而文件结构 则 不受控制， 进程树 是暂时的，而目录层次则是 永久的。
    • 每个进程 有一个 工作目录， 对于 非绝对路径 都将 从该工作目录下 开始寻找，
    • 安装文件系统： 如果安装一个 DVD光盘 时候，我们需要mount 系统调用 来讲Cd-rom上的我呢间系统连接到程序所希望的根文件系统上。
    • 特殊文件： 提供特殊文件是为了是IO设备看起来 想文件一般。 这样就可以使用系统调用 来读写文件， IO 设备也可以通过同样的系统调用 来进行读写，包含： 块特殊文件， 字符特殊文件。 可以随机存储区的块组成的设备，比如磁盘。 字符特殊文件 用于打印机， 调制解调器，输出为字符流的设备。 按照惯例，特殊文件 放在/dev 目录下。
    • 管道： 虚拟文件， 可以连接两个进程，通过在管道上写读 来进行进程间通讯。
    • 保护： 管理系统的安全依靠 操作系统。 例如文件只能授权用户使用。 在文件系统中，对每个文件 富裕一个 9位 的 二进制保护码
操作系统体系结构：

虚拟机： todo

进程 + 线程：
相关概念
线程：
进程间通讯：
#define N 100
int count = 0;

void producer(void)
{
    int item;
    while(true){
        item = produce_item(); 
        if（count == N） sleep(); // 缓冲区满 则 休眠
        insert_item(item);
        count = count + 1;
        if (count == 1) wakeup(consumer); // 缓冲区
    }
}


void consumer(void) 
{
    int item;
    while(true) {
        if(count == 0) sleep(); // 缓冲区空，则进入休眠状态
        item = remove_item(); 
        count = count + 1;
        if(count == N - 1) wakeup(producer); // 缓冲区满，则 唤醒 生产者
        consume_item(item);
    }
}

此代码结构中存在两个问题：1） 共同修改的count变量 未进行访问保护 2） 消费者 在逻辑上 未进行睡眠时，生产者的wakeup 信号丢失了。情况如下： 在 count 为0时，消费者 进行消费，读取了count 为0。此时调度器 决定执行 生产者，生产者 生产完毕，并执行 wakeup。因为消费者没有sleep所以生产者的wakeup信号丢失了，之后 消费者执行，count == 0 sleep操作。消费者将阻塞。而生产者 则一直生产 直到缓冲区已满 也阻塞起来。

信号量：Dijkstra 提出来的算法， 使用整型变量累计唤醒次数，供以后使用
互斥锁: 不需要 信号量的计数功能, 将信号量的初始数值设定为1， 即 保证只有一个进程能够进入 临界区，称为 二元信号量,即为互斥锁。又称为互斥量。

#define N 100

typedef int semaphore;
semaphore mutex 1; // 将 信号量的数值设置为1，即为 二元信号量，互斥锁.
semaphore full 0;
semaphore empty N;


void producer(void)
{
    int item;
    while(true) {
        item = produce_item();
        down(&empty); // 将 空槽位 数量 - 1
        down(&mutex); // 获取互斥锁
        insert_item(item);
        up(&mutex); // 释放互斥锁
        up(&full);  // 将 满槽数 + 1
    }
}


void consumer(void)
{
    int item;
    while(true) {
        down(&full); //将 满槽数 - 1
        down(&mutex); // 获取互斥锁
        item = remove_item();
        up(&mutex); // 释放互斥锁
        up(&empty); // 将 空槽位 数量 + 1
        consume_item(&item);
    }
}

解释: 其中信号量 full以及 empty 作为 同步使用，即保证 消费者 与 生产者 按照 正确的顺序发生。而mutex 则 互斥进入临界区。

快速用户互斥量 futex： 结合了 自旋锁 与 信号量的 优点。
条件变量:

#include <stdio.h>
#include <pthread.h>
#define MAX 1000000

pthread_mutex_t the_mutex;

pthread_cond_t condc,condp;

int buff = 0;


void *producer(void *ptr)
{
    int i;
    for(i = 1; i < MAX; i++){
        pthread_mutex_lock(&the_mutex);
        while(buff != 0) pthread_cond_wait(&condp, &the_mutex);
        buff = i;
        pthread_cond_signal(&condc);
        pthread_mutex_unlock（&the_mutex）;
    }
    pthread_exit(0);
}


void *consumer(void *ptr)
{
    int i;
    for(i =1; i<= MAX; i++){
        pthread_mutex_lock(&the_mutex);
        while(buff == 0) pthread_cond_wait(&condc, &the_mutex);
        buff = 0;
        pthread_cond_signal(&condp);
        pthread_mutex_unlock(&the_mutex);
    }

    pthread_exit(0);
}


int main(int argc, char **argv)
{
    pthread_t pro,con;
    pthread_mutex_init(&the_mutex, 0);
    pthread_cond_init(&condc, 0);
    pthread_cond_init(&condp, 0);

    pthread_create(&con, 0, consumer, 0);
    pthread_create(&pro, 0, producer, 0);

    pthread_join(pro, 0);
    pthread_join(con, 0);

    pthread_cond_destroy(&condc);
    pthread_cond_destroy(&condp);

    pthread_mutex_destroy(&the_mutex);
}

管程: 高级同步原语 其重要的特性为： 任一时刻 管程 中 只能有一个活跃的线程。 这一特性使管程能够有效的完成互斥。管程是编程语言的基本组成部分，编译知道如何 处理对管程的调用。 进入管程的互斥 通常由编译器负责。其通常的的做法为使用一个 互斥量。但是 依然存在问题， 在上面的例子中，我们使用 条件变量来使线程从 阻塞状态中恢复。所以 我们 也需要同样的 同步机制 。即 我们在管程中引入了 条件变量。

  1. 当一个管程过程发现自己 不能够继续进行下去的时候， 它将会在某个条件变量上进行wait操作，该操作将导致线程阻塞，并释放临界区的锁，导致其他的管程进入临界区域，并等待其他线程在条件变量上的唤醒操作。
  2. 当一个线程对阻塞在条件变量进行唤醒操作时， 即发送signal时，为了避免管程中同时存在两个活跃线程，我们需要一条规则来确定 唤醒操作 之后 应该怎么办：
  3. 两个方法： 1）让新唤醒的线程运行，而挂起另外一个。2）执行signal的线程立即退出管程，即signal应该为函数的最后一条语句。
  4. Java中的管程实现： 使用sychronized 标记管程函数，也不使用显示的条件变量，而是提供了对应的函数wait,notify。
总结：信号量的提供已经很好地解决了，线程之间的临界区同步，以及发生顺序问题，确 为什么依然 要提供 互斥量 + 条件变量的组合呢？
  1. 现实的情况比较复杂，. 信号量是一个比较高级的操作原语，其可以使用互斥量 + 条件变量 + counter来实现。对程序暴露出更低级的操作 是非常有必要的。
  2. 互斥量 可以简单地 实现 1个互斥量 + n个条件变量 的 组合实现。即 在临界区中 可以实现多种情况的 wait 与 signal
  3. 互斥量 + 条件变量 与 信号量 的使用 规则形式不同。信号量 需要先 down(full) 然后才 down(mutex) 进入临界区。而 互斥量 +条件变量的使用 ，则 是 先 lock(&mutex) 然后 根据条件 进行条件变量 的wait。
  4. 管程模式 导致 管程 中确实需要 条件变量。 因为管程 优先锁定互斥量进入临界区。
消息传递： message passing, 使用两条 通信原语：send receive，他们是 信号量而不像管程，是系统调用 而不是语言成分。
屏障： 用于同步进程组，一些应用中划分了若干阶段，并且规定，除非所有的进程 都准备就绪，否则任何进程都不能进入下一个阶段。 可以通过在每一个阶段的结尾安置 屏障 来实现此类型行为。 当一个进程到达屏障时，他就被阻拦，直到所有进程都到达 该屏障为止。屏障用于一组进程的同步，

调度： 当计算机同时存在多个进程或者线程同时竞争cpu，只要有两个或更多的进程处于就绪状态，如果只有一个cpu发生，那么就必须选择下一个要运行的进程，在操作系统中完成选择工作的这一部分称为 调度程序。该程序使用的算法称为 调度算法。

场景目标：
批处理系统： 吞吐量- 每小时做大作业量， 周转时间- 从提交到终止间的最小时间， CPU利用率- 保持cpu始终忙碌。
交互式系统： 响应时间–快速响应请求，均衡性– 满足用户的期望。
实时系统–满足截止时间： 避免丢失数据，可预测性- 在多媒体系统中避免低品质。

吞吐量与 周转时间之间的冲突： 例如 对于确定的短作业 与长作业 的一个组合。 总是运行短作业而不是长作业，会获得出色的吞吐性能。但是其代价为 长的作业周转时间较差。即得到了较高的吞吐量 ，但是 平均周转较差。

交互式系统的不同指标： 最小响应时间： 从命令到得到响应之间的时间。均衡性： 用户对于一件事情完成需要多少时间 总是一个固定的期望。

实时系统： 特点是 必须满足截止时间要求。

批处理中的调度算法：

先来先服务：first-come first-serverd 算法。该算法 按照 进程请求cpu的顺序 使用cpu， 可以想象有一个 就绪进程的队列， 产生新作业时，新进程排在就绪队列 尾部。 当正在运行的进程由 就绪变为阻塞时，就绪队列中的第一个进程运行，当被阻塞的进程变为就绪状态时，就像一个新来的作业进程一样，排到就绪队列的末尾。 该类算法 实现起来比较简单。但是存在一个明显的缺点，即： 对于IO密集型进程不太友好，没有很好的考量 是系统中的 设备是否充分利用。 考虑 两个进程，一个cpu密集型进程 每次运行1s的cpu计算 和一个 IO密集型进程，很少利用cpu，但是需要都要运行1000次的磁盘读写操作才能完成任务。 如果 按照该类调度算法 的话，则IO密集型进程需要运行1000s才能够运行完成，但是如果 使用抢占式 调度算法的话，则可以 没10ms进行一次抢占调度，则 IO密集型进程将在10s内完成，而对于 cpu密集型进程 则没有太大影响。

最短作业优先： 适用于一种运行时间预知的非抢占式调度算法。 即：作业按照 完成时间 从小到大排列，即 shortest job first.
考虑有4各作业。其运行时间 分别为 a ,b,c,d 其平均周转时间为 (4a + 3b + 2c + d)/4，可见第一个作业a的完成时间，对于 平均周转 影响最大，而 吞吐量 同样为最大。 又必须要指出， 只有在所有的作业都可同时运行的情况下，最短作业优先算法才是最优的。反例： 5各作业，A-E,运行时间分别为：2,4,1,1,1 他们到达系统的时间分别为 0,0,3,3,3， 系统在开始时 只能选择A与B， 按照 该调度算法的排序 为A,B,C,D,E 其平均周转时间为4.6，但是按照 B,C,D,E,A的调度安排，时间为4.4，优于 最短作业优先。

最短剩余时间优先： 最短作业优先的抢占式调度版本。 调度程序总是选择 剩余运行时间 最短的那个进程 进行运行。当新加入的进程的剩余时间最短时，则当前进程就被挂起，运行新的进程。

交互式系统中的调度：

轮转调度（round robin）： 简单公平的调度算法， 每个进程被分配一个时间段，称为时间片。 （quantum）

即允许 进程在该时间段内运行，如果在时间片结束时候该进程还在运行 则剥夺cpu并分配给另一个进程。如果该进程在时间片内 阻塞或者结束 则 cpu将立即切换。

轮转调度算法 实现非常简单，即维护一个 可以运行的进程列表。不断的从列表头上取出进程运行，时间片用完后，将进程放到列表队尾。

关于时间片的长度设定： 从一个进程切换到另一个进程 即 进程切换 也称为 上下文切换。 其中需要 保存和装入寄存器数值，更新各种列表，清除和重新调入内存 高速缓存等 操作。

如果时间片设定为4ms 而进程切换需要 1ms，则 cpu时间将花费 20% 的时间在进程的切换上。
如果将时间片设定为100ms，则cpu时间将花费1%在进程间的切换上。但是 可以想见的是，排在队尾的进程将在很久之后才能得到cpu的时间，对于交互式系统用户而言，将是缓慢的。
如果将时间片设置为长于平均的cpu突发时间，那么将不会经常发生抢占，相反 多数进程将在时间片内发生 阻塞操作，从而引起进程切换，抢占的消失改善了性能，因为进程只有在逻辑上需要的时候发生了切换，即：进程确实不能够在继续进行下去。

总结：时间片设定的太短，导致cpu利用率的降低，时间片设定的太长，导致交互请求的响应变长，普遍间时间片设定为 20-50ms范围内 。

优先级调度：

在轮转调度中 存在一个隐藏的假设，即： 所有的进程是同样重要的。实际上 进程的优先级是可以调整的。即进程之间存在重要性的差异。比如 在屏幕上显示视频的进程 比 后台发送邮件的进程具有较高的优先级。

从此可以看到 时钟滴答 与 时间片 是不同的概念。这里面的时钟中断 应该是 linux中 可以控制的时钟周期，即cpu频率保持不变，但是在 配置的滴答个数 可以 进行时钟中断，而 时间片的概念呢？是建立在 时钟中断上的吧？

两种方法：
为了防止 高优先级的进程一直无休止的运行下去，调度程序可能在每个时钟滴答（时钟中断）降低当前进程的优先级，如果这一行为导致该进程的优先级低于此高级优先级的进程，则进行进程切换。
给每个进程赋予一个允许运行的最大时间片。 当用完这个时间片 则 此高优先级的进程 便能获得运行机会，即进行进程切换。

优先级 可静态确定 或 动态确定。 比如 按照行政等级 确定 等级高的人 的任务具有更高的优先级。

动态确定： 的比如，将IO密集型进程设定更高的优先级，算法 1/f，f为进程在上次的时间片上用的时间片。IO密集型进程 其多数时间 用来等待 IO结束，当这样的进程需要CPU时候，应该立即分配给他，以便让其 启动下一个 IO请求，以充分利用cpu与IO设备。一个在50ms时间片中花费 1ms 时间的 进程 将获得 50的优先级，一个进行 2mscpu运算的进程将获得25的优先级。

多级队列： 优先级调度 中优先级之间 改变优先级 的另外一种方法： 设立优先级类，将最高优先级类的 进程运行一个时间片，此高级优先级的进程 运行 2个时间片， 下一个优先级的进程类运行 4个时间片。 以此类推，当一个进程用完分配的时间片之后，将被移到下一个优先级类。 这样的规则将导致 cpu密集型进程将获得更低的优先级，更大的时间片进行运行。 这里面的存在的缺陷在于，没有将 优先级提升的方法，如果 交互式进程因为 偶尔的 用完时间片的行为 将导致 不断的惩罚，将导致 降低为 低优先级。

最短进程优化：

再批处理系统中 使用 最暖进程优先算法是非常好的。 然而如何将其 应用在交互式系统中 则成为问题，因为 如何从当前进程中找到运行时间 最短的那个进程。 交互式 进程通常的模式 为： 等待命令、执行命令、等待命令、执行命令 如此往复。
一种办法为： 根据进程过去的行为进行推测。使用时间老化算法来估算 进程运行时间。 假设进程 之前进程运行的时间 为 T0，当前估计时间 T1，本次 实际时间 为 T0/2 + T1/2 则 aT0 + (1 - a) T1 通过选择 a，可以决定 尽快忘掉老的运行时间。当 a = 1/2时，我们可以得到如下的队列：

T0， T0/2 + T1/2， T0/4 + T1/4 + T2/2， T0/8 + T/8 + T2/4 + T3/2 在 3此过后 T0的权重 降低为 1/8

我们把 这种通过当前预测值 + 先前估计值 加权平均 而得到 一个 估计值 的技术 成为 老化技术。

保证调度： 向用户做出明确的性能保障，然后去实现它。一个简单的保证为： 如有n各用户登录，则保证用户将获得 1/n 的计算能力。 即系统 需要追踪 系统的运行参数， 诸如 用户进程 实际占用的cpu运行时间，以及 应该占用的cpu时间。其数值比率 大 则说明 获得时间多，而数值小 则说明 获得cpu时间少。 该算法 将优先调度 数值小的 进程 ，已实现 性能保证要求。

彩票调度： 保证调度 很难实现，一种近似实现 为 彩票调度（lottery scheduling） 基本思想为 为进程提供 各种系统资源 的彩票。 需要做出调度决策时，就随机抽取一张彩票，拥有该彩票的进程获得调度。
如果cpu出售了1000张彩票 ，某个进程 持有 20张，则每一次抽奖 该进程就有20%的几率 获得cpu， 在较长的运行时间中，该进程将获得20%的cpu。与 优先级调度 相比较，很难解释进程的优先级为 20 是什么意思，也更难预测 进程将获得与 优先级相关的多少cpu时间。而彩票调度 则 非常明确，拥有 f分彩票 进程 大约得到 系统资源的f份额。

彩票调度 可以用来解决一些 难题，比如 视频流服务器， 服务器上若干进程 为用户提供 帧速率 为10，20，25 的视频流， 只需要 分配 进程 对应的 彩票份额，10， 20，25 即可。

公平分享调度： 需要具体考虑 公平 的定义，用户公平的调度 则需要考虑 在 进程调度 期间 用户的进程 分配 cpu占用问题。

策略和机制： 调度机制 与 调度策略 分离开来。调度机制位于内核，而调度策略 则由用户进程 决定。

线程调度： 若干进程 由多个线程 时候，系统中就存在两个层次的并行： 进程和线程， 在这样的系统中 调度 处理 有本质上的差别。当然这取决于线程 的实现： 即 用户级线程 还是内核级线程。

在 用户级别线程下： 由于内核并不知道线程的存在 ，所以 内核 依然 按照 进程调度，即 用户线程调度 决定 选择那个一个线程。 调度算法 选取中 可以选用上面的任何一种，但 轮转调度 和优先级 调度更为常用。 缺陷则是缺乏 一个时钟中断中断运行时间 过长的线程，但是因为线程之间 为合作关系，所以通常并不是问题。
内核级线程： 对于内核 可以考虑优先调度同属于一个进程的线程，以为同进程间的线程调度 代价要小于 进程之间的调度。其他方面 则与 进程间调度没有什么不同。Linux中 线程与进程同为 调度实体。

用户级线程 与 内核级线程 之间的差别在于 性能： 用户级线程的线程切换 需要较少的机器指令，而内核级线程 切换 则需要 完整的上下文切换、修改内存映像、高速缓存失效（而同样归于同进程的线程 则是不需要） 等操作，这导致了数量级别的延迟。

用户级线程 可以使用 特定优化的调度算法，以为 应用程序 知道自己的应用场景，而 内核级线程 内核从来不了解 每个线程的作用。一般而言，应用定制的线程调度算法 能够比内核 更好的满足 应用的需要。

经典的IPC问题： 哲学家就餐问题， 读者-写者问题

哲学家就餐问题：

直观的解法： 显然是错误的，如果 五位哲学家 同时执行（拿起 左边的筷子 、拿起右边的筷子） 将会导致 没有人能够拿起 右边的筷子， 从而导致死锁。 一个简单的解决方法为： 在哲学家拿起 左边的筷子时候，查看右边的筷子 是否可用，如果不可用，则先放下左边的筷子 ， 等一段时间，再重复这个过程。 但这个解法同样存在问题。 尽管原因不同，同一时间 所有的哲学家 都开始进行 该算法，同时 拿起左边的筷子，同时 查看右边筷子是否可用，放下，等待。 如此运行下去 所有的进程都在运行，但是却无法取得进展，该现象 我们称之为饥饿。
我们简单的将 上述 中的等待时间 设定为一个 动态的随机时间，而不是等待一个固定的时间 。这样发生饥饿的可能性就非常小了， 几乎在所有的程序中，稍后再试的办法并不会演化成为一个问题。例如 ： 在流行的以太网上， 如果两台计算机同时发送包 ，那么每台计算机会稍等一哥随机时间之后 再次尝试，在实践中 该方案工作良好。 少数的程序中， 人们希望一种总是能够工作的方案，他不会因为一串 随机数字而失败。

#define N 5


vodi philosopher(int i)
{
  while(true) {
  think();
  take_fork(i);
  take_fork((i + 1) % N);
  eat();
  put_fork();
  put_fork((i + 1) % N);
  }
}

最优的解法： 这里应该搜索，没有理解其代码意思。

void philosopher(int i)
{
  while(true) {
  
}
}

void take_forks(int i)
{
  down(&mutex);
  state[i] = hungry;
  test(i);
  up(&mutex);
  down(&s[i]);
}

void put_forks(int i)
{
  down(&mutex);
  state[i] = thinking;
  test(LEFT);
  test(RIGHT);
  up(&mutex);
}

void test()
{
  if(state[i] == hungry && state[LEFT] != EATING && state[RIGHT] != EATING) {
    state[i] = EATING:
    up(&s[i]);
}
}

读者-写者问题：一个数据库访问模型： 多个进程可以同时读取数据库，但是如果一个进程 正在更新 写数据库，则所有的其他进程 都不能够访问数据库。

下面是一个读者优先访问示例代码：

typedef int semaphore;
semaphore mutex = 1;
semaphore db = 1;
int rc = 0;

void reader(void)
{
  while(true {
    down(&mutext);
    rc = rc + 1;
    if (rc === 1) down(&db);
    up(&mutex);
    read_data_base();
    down(&mutex);
    rc = rc - 1;
    if (rc == 0) up(&db);
    up(&mutex);
    use_data_read();
  }
}


void write(void)
{
  while(true)
  {
   think_up_data()  ;
   down(&db);
   write_data_base();
   up(&db);
  }
}

该解法中 隐含着一种情况：即 数据库当前存在一个读者 时候，另一个读者来了 以及 更多的读者来了，同样允许。这时 一个写者到来 由于写者是拍他的，不允许进入数据库，导致被挂起。需要等待所有的读者处理完成之后 才能开始进行处理写操作。即 读者比 写者拥有更多高的优先级， 写总是排在读后面，如果读者多的情况下 将导致 写 迟迟不能完成操作。

写优先的解法 需要查找 courtois等人的相关资料。

总结：
进程问题已经有了成熟的解决方案，几乎所有的系统都将进程视为一个容器， 用以管理相关的资源，比如地址空间、线程、打开的文件描述符等。 不同的系统管理进程资源的基本想法大致相同。 只是在工程处理上略有差异。
线程是比进程新的概念，但是也经过了深入了的研究。
进行执行过程的 记录和重放 也是一个非常活跃的研究领域。 重放技术 可以帮助开发者 追踪一些难以发现的程序漏洞。
调度问题 也是研究者感兴趣的问题。 一些研究主题包括移动设备上的低能耗调度， 超线程级调度 和偏执意识调度 。 智能手机的计算量 增加 因为电池容量有限。 一些研究者提出 可能的时候将进程迁移到云上某个更强大的服务器上执行。但实际系统的设计者 很少会因为没有合适的线程调度算法 而苦恼。所以这是一个由 研究者推送而不是 需求推动的研究类型。总而言之， 进程，线程 与调度已经不再是研究热点了，功耗管理 、虚拟化、云计算 、与安全问题 成为了热点主题。

习题答案 ：（部分重要）

当代计算机中，为什么中断处理程序中 至少部分是由汇编程序来编的？
答： 高级语言不允许访问 必要的cpu资源，比如 一个中断处理程序中 可能需要开启、禁止 中断。 此外 中断处理程序 需要尽可能的快。

中断 或 系统调用 将控制权 转移到 操作系统时，为什么 通常会 用到与 被中断进程 的栈分离的 内核栈？
答： 为内核使用单独的堆栈有几个原因。 其中两个如下。 首先，您不希望操作系统崩溃，因为编写得不好的用户程序不允许有足够的堆栈空间。 其次，如果内核在从系统调用返回时将堆栈数据留在用户程序的内存空间中，恶意用户可能能够使用这些数据来查找有关其他进程的信息。

内存管理 ：

不管存储器多大，程序都可以将其填满。

分层存储器体系： 在这个体系中，存在 MB 的快速、昂贵、易失性的高速缓存，GB的速度价格适中的同样易失的内存 ，以及 TB的低速、廉价、非易失的磁盘存储。

操作系统的工作之一 就是 将层次存储系统体系 抽象成为一个 有用的模型 并管理这个抽象。

分层存储器系统称为 存储管理系统： 他的任务是 有效的管理内存，即记录哪些 内存是正在使用的，哪些 是空闲的， 在进程需要时候为其分配内存 ，不需要时释放内存。

探索 内存抽象方案 的步骤：

无存储器抽象： 最简单的存储器抽象 即 没有抽象。 早期的大型机 小型计算机 都没有存储抽象。 每一个程序 都直接访问物理内存。
因此 那时候呈现给编程人员的存储器 即是： 从0到某个上限的地址集合，每个地址 对应一个 可容纳 一定数目的二进制数据，通常是 8位。
指令 MOve Register1， 100 即：将 100的物理内存的内容，转移到 register1中。

改种方案下， 系统中同时运行两个程序 是不可能的。如果进程 A在 地址 100位置写入数据，进程 2 在稍后的时间中 对地址 100进行了改写，可能导致 进程A的崩溃。

在该模式 内存的布局方式有以下三种：

操作系统位于 RAM 的底部
操作系统位于内存顶端 的ROM（只读存储器） 中
设备驱动程序位于顶端的ROM中，操作系统位于底端的RAM中

第二种方案 经常用在 一些掌上电脑，和嵌入式系统中。
第三种方案 用于早期的个人计算机中， ROM中的系统部分 为 BIOS（basic input output system）

在没有存储器抽象的情况下 同时运行多个程序。

操作系统 只需要 把当前的内存中的内容 保存到磁盘上 ，然后将下一个程序 读入到内存中 再次运行即可。 只要在同一时刻 内存中只有一个程序 即可。

IBM 360 的做法：
内存被划分为 大小2KB的块。 每个块 分配一个 4位的保护键， 保护键存储在cpu的特殊寄存器中， PSW中存在一个 4位码， 一个运行中的进程如果访问保护码 与 PSW中的不同的内存，硬件将会捕获该事件。 因为只有系统可以修改保护键，这样就可以放置用户进程 之间、用户和操作系统之间的相互干扰。

静态重定位技术： 即便 存在保护键，依然无法解决 两个进程 使用重复的绝对地址的问题，我们希望每个进程使用一套自己私有的内存地址来进行内存访问。IBM 360 采用的方法 即：在第二个 程序 装载到内存 100地址时， 常数100将被 加到 每一个 程序地址上。

缺少存储器抽象在嵌入式系统中 依然非常常见， 比如 洗衣机 微波炉 此类 设备 都已经完全被ROM形式的软件控制。 这种情况下，软件都采用 绝对地址寻址的方式，以为 所有的运行的程序 都可以被事先确定， 用户不需要运行自己的软件。

存储器抽象：地址空间

直接暴露物理地址的问题： 1） 用户程序可以简单的寻址内存地址，很容易地破坏 操作系统。 2） 同时运行多个程序将非常困难。

地址空间的概念：

要多个应用程序 同时处于内存 而不互相影响 需要解决两个问题： 1）保护 2）重定位 。

IBM 360的办法 实际效果并不好，因为 其 静态重定位 技术，不仅缓慢，还需要 额外的标记 来确定 那些地址 需要被加。

就像 进程的概念 创造了 cpu的抽象 为 进程使用 一样。

地址空间 为程序 创造了 一种抽象 的内存，地址空间 是一个进程可以用于寻址内存的地址集合。每个进程 都有自己的 地址空间，独立于 其他的 进程 地址空间。

地址空间的概念非常常见： 比如 电话号码、url等。
简单实现：动态重定位： 给cpu配置两个寄存器： 基址寄存器 、界限寄存器。 使程序 装载期间 无需 重定位。当一个进程运行时 程序的起始地址 装载到 基址寄存器中，程序的长度 装载到 界限寄存器中。每次 进程访问内存，取一条指令、读写一个内存地址时， cpu硬件会将 地址发送到内存总线前， 自动把基址寄存器的数值 + 进程发出的地址上。 同时检查 结果是否在 界限寄存器 范围内。 超过了 界限 则捕获错误。

基址寄存器 16384， 界限寄存器： 17000 指令 jmp 28 被翻译成 jmp 16412

此方法可以简单实现存储器抽象。

内存管理技术：

1）交换技术： 两种处理内存超载的方法： 最简单的策略 是 交换技术， 即 将把进程完整的调入内存中，使该进程运行一段时间，然后把他 存回磁盘。 虚拟内存： 使程序只有一部分被调入内存的情况下 运行。

空闲内存管理：

动态分配内存时， 操作系统 必须 对其进行管理 ，一般有两种办法： 1） 位图 2） 空闲去链表，

  1. 使用位图的存储管理： 内存可能被划分为 几个字 或 几千字的分配单位，每个分配单位 对应于图中的一位。0表示空闲，1表示占用。分配单元的大小是一个重要的设计元素， 分配单元小 则位图大，位图占用的内存空间的比例就会提升。分配单元大 ，则位图小。但进程分配的存在更多的浪费。

位图主要的问题是： 再决定分配一个 大小 为k个分配单元的进程调入内存时，存储管理器 必须搜索位图 已找到 k个连续的0串，因为 位图中该串可能跨越字的边界。 查找位图中 制定长度的连续0串是一个耗时操作。

使用链表的存储管理：

维护一个记录已分配内存段和空闲内存段的链表。

有几种方法 为 新创建的进程 分配内存：
1） 首次匹配算法： 沿着链表进行搜索， 直到找到一个足够大的空闲区间。 除非空闲空间与 需要分配的空间大小一样，否则将该空闲区分为两部分，一部分供进程使用，一部分 成为新的空闲区。 速度非常快的算法，因为它可以尽可能少的搜索节点。

2） 最佳适配算法：搜索整个链表， 找到能够容纳新进程的最小空闲区间。该算法试图找到最接近实际需要的空闲区。
其他算法： 快速适配法

虚拟内存： 虽然 基址寄存器 + 界限寄存器 能够很好的 应对 内存抽象管理要求，但是 随着软件的膨胀 需要运行的程序往往大到内存 无法容纳， 而系统必须能够支撑起多个程序的同时运行， 即使内存仅仅 可以满足其中一个的程序需要。

总体来看 程序对内存的需求 超过了实际内存大小。 交换技术 并不是一个很好的方案，因为 一个典型的SATA磁盘的峰值传输效率 只有几百兆每秒，这意味着需要好几秒 才能换入 一个1GB的程序。

该类问题 很早就出现了，初始的简单解决办法 成为 ：覆盖 （overlay） 把程序分割成为许多片段， 程序开始，将覆盖管理模块转入内存，该管理模块立即 装并运行程序的片段0，在系统需要时 将由 管理模块 程序片段1装载到内存中，覆盖管理模块允许多个 片段 同时在内存中，部分在磁盘上，在需要时候动态的换入换出。

虽然 有管理模块来负责 换入换出操作，但是 依然需要程序员将程序 分割成多个片段，最后人们将这种费事重复性的操作 交给了计算机去做。

采用的这个方法 称为虚拟内存。 基本思想为： 每个程序拥有自己的地址空间，这个空间被分割成为多个块，每一块称作一页或页面（page）， 每一页 都有连续的地址范围，这些页面被影射到 物理内存， 但并不需要所有页面都在内存中才能够运行程序， 当程序引用到一部分在物理内存中的地址空间时， 由硬件执行必要的映射， 当程序引用到 一部分不在物理内存中的地址空间时， 由 操作系统负责将缺失的部分程序装入到 物理内存并重新执行失败的指令。

分页： 大部分 虚拟内存使用的技术。

Mov reg, 1000 将内存地址 1000 的内存复制到 reg中，其中的1000地址 可以由 索引、基址寄存器、段寄存器 或其他方式产生。

由程序产生的地址称为虚拟地址（virtual address） 它们构成了一个虚拟地址空间。 没有虚拟内存的计算机上，虚拟地址 就是 内存物理地址， 使用虚拟内存的情况下， 虚拟地址 并不直接传送到内存总线上，而是 先传到 内存管理单元（memory management unit MMU） mmu将虚拟地址映射称为 物理内存地址 ，在传送到物理内存地址总线上。

虚拟地址 按照固定大小划分为称为 页面 （page）的单元， 物理内存中对应的为 页框（page frame） RAM与磁盘之间的交换总是以整个页面为单元进行的。

转换：

程序执行 指令 MOV REG， 0 将虚拟地址 0 送到MMU， MMU 看到u虚拟地址落在页面0，根据映射结果 该页面对应得是页框是2（8192-12287） 因此 MMU把地址变换为8192 并将地址 8192发送到总线上，内存对MMU一无所知，他知道看到一个读写地址 8192 的请求并执行它，MMU从而有效的将 程序虚拟地址空间0-4095 映射到 8192-12287。

通过且当的设定 MMU，可以讲16个虚拟页面，映射到 8个页表框中的任何一个。但是这并没有解决 虚拟地址空间大于物理内存空间的问题。 当程序需要访问 第9个页面的时候，会发生什么情况呢？ MMU注意到 第9个页面并没有被影射到内存中， 于是使cpu陷入到操作系统 ，称为缺页中断 或者缺页错误。 操作系统找到一个很少使用的页框 并把他的内容写入到磁盘中，随后把需要访问的页面 读到刚才 回收的页框中，修改映射关系，然后重新执行引起缺页中断的指令。

缺页处理的具体步骤为：
1） 如果操作系统决定放弃页框1， 将虚拟页面8 装入物理地址4096，然后对MMU做两处修改，
1） 将虚拟页面1 标记为未映射，以便 以后任何对于 虚拟地址 4096-8191的访问 都会导致 缺页中断
2） 将虚拟页面8的标记页框为1，因此在重新执行引起缺页中断的指令时，能够将虚拟地址 32780 映射为物理地址 4108

MMU内部结构如下：

可以将16位的虚拟地址，划分为 4位的 页号 + 12 位的便宜里那个。 4位的页号 可以表达16个 页面 ， 12位的偏移地址 可以为一页内部的全部4096个字节编码。
使用页号作为页表的索引。以找出对于该虚拟页面的页框号， 如果 不在 则 引发一个缺页中断， 如果在 ，则 将在页表中查找到的 页框号 + 虚拟地址的偏移量 构成一个 物理地址。 输出到物理内存地址总线上。

页表：