概述

指令的执行

最简单指令处理包含两步：读取执行、执行指令。PC保存下一次要取的指令地址。取到的指令放到IR中。指令执行的动作分为四类：

  • 从处理器到存储器传数据
  • 从处理器到IO传数据
  • 处理数据，加减
  • 控制，指定下一次指令从某个地方读取

中断

中断和指令周期

长IO等待：IO程序执行的时间太长，导致新WRITE调用来了，旧的WRITE操作还没有完全完成，所有新WRITE操作必须阻塞，等到第一次WRITE完成才行。

对于右侧的长IO等待，在IO操作未完成时，与用户指令的执行有重叠，正是这部分指令导致了效率的提高。

中断处理

中断激活了很多事件，包括处理器硬件的事件和软件的事件（要注意那些是硬件完成的，哪些是软件完成的，廖总经常强调的）。

多个中断

一种是在中断运行时禁止其他中断，只有当处理器完成当前中断时，才由处理器检查是否有中断。

另一种是定义中断优先级，允许高优先级打断低优先级中断。

存储器的层次结构

存储器的目标可以归纳为三个问题：多大容量，多快速度，多贵价格。

通常既需要快速的又需要大容量的存储器。这不能使用单一存储器来实现，而是使用存储器层次结构。

访问的局部性原理：短时间内，处理器的指令访存和数据访存呈簇状。

高速缓存通常对程序员以及处理器都不可见，高速缓存用于在内存和寄存器之间分段移动数据，以提高数据访问的性能。

磁盘

磁盘可以作为内存的拓展，即虚拟内存。（本质存在磁盘上）

在软件中可以有效地增加额外的存储层次。比如一部分内存作为缓冲区，也有时称为磁盘高速缓存（本质在内存上）。

两种方式提高磁盘性能：选择整批数据传入传出；把数据先放到缓冲区上，万一待会儿还要改呢。

高速缓存

高速缓存对操作系统不可见，但他会与其他存储管理硬件相互影响。

原理

当处理器尝试访问字节时，会先检查该字节是否在高速缓存上

  • 若在，则将该字节通过高速缓存传入CPU
  • 若不在，则将由固定数量的字节构成的内存数据读入高速缓存，然后将该字节从高速缓存读入CPU。

高速缓存包含若干槽，每个槽可以存储若干字，当需要从内存读入数据时，则从内存读取槽大小的数据到缓存的某个槽中。

直接内存存取

IO感觉应该指的是从内存读入或读出

执行IO操作主要包含三种方式：可编程I/O, 中断驱动I/O和直接内存存取。

  • 可编程I/O：CPU给某个I/O模块发命令，然后I/O模块执行命令并设置状态寄存器中的位（不会通知CPU，尤其是不会中断处理器）。因此处理器执行IO命令后需要定期检查IO模块的状态。（基本上没用这种了吧，STM32的串口都是用的中断）
  • 中断驱动I/O：区别在于，然后I/O模块执行命令后，会用中断打断处理器的执行请求服务，然后恢复处理器以前的执行过程。数据的传输会经过处理器。

这两种方式都有以下的缺陷：

  • IO传输速度受限于处理器测试设备和提供服务的速度
  • 处理器忙于管理IO传送，需要执行很多指令来完成IO传送。

更有效地技术：DMA

DMA需要控制总线来进行数据传输，CPU可能执行速度会变慢，但是也会比中断驱动IO更有效。

多处理器和多核计算机

虽然一般任务处理器按照顺序执行指令，每条指令依次取值、取操作数、执行、存储。但在微观上，在进行本条指令的执行时会进行下一条指令的取值，这其实是并行执行的例子。

常见的三种并行方式：

对称多处理器(SMP)

处理器共享IO和内存，由一个统一的操作系统控制。

有个缺陷是，多个高速缓存之间如何保证一致？硬件主导的同步。

多核计算机

又称芯片多处理器，发现

操作系统概述

目标与功能

作为接口的操作系统

常见接口：

作为资源管理器的操作系统

管理IO、存储器、处理器

操作系统的演化

  • 串行处理
  • 简单批处理：有一个监控程序常驻内存，用于加载程序，每次一个。
  • 多道批处理程序：可以加载多个程序到内存，有一个程序在等待IO时可以切换到另一个程序。
  • 分时系统，为了及时响应单个用户的请求

主要成就

进程
内存管理

微内核：是一种操作系统架构，它提供了操作系统的核心功能，如任务管理、线程管理、进程间通信（IPC）和内存管理等。在微内核架构中，大部分内核服务如文件系统、设备驱动等作为用户态的进程运行，这些服务之间通过消息传递进行通信。微内核的设计使得系统具有高度的模块化，一个服务的故障不会影响其他服务。

多线程：

线程：包括处理器上下文环境以及栈中自身的数据。

进程：一个或多个线程以及相关资源（存储器空间、打开文件与设备）的集合。

多核操作系统设计考虑因素

除了考虑同步、调度、并发进程和线程等问题，主要要考虑的是并行规模问题。对于当前的多核系统，并行分为三个层面：

  • 指令级并行，每个核心内部同时执行多个任务（比如超标量架构）
  • 处理器层次的并行，在处理器上多线程程序的执行能力
  • 多核上一个应用程序以并发多线程执行的能力

并行的实现方式：

应用层并行，虚拟机方式

其他

Linux可以动态的加载和卸载内核模块。

进程描述与控制

什么是进程

进程控制块包含了进程的充分信息，这为中断进程，再执行提供了支持。

新建态和退出态也很有用，当操作系统创建好进程的表格，进程就处于新建态，此时进程本身的程序还不在内存。程序的终止将使程序处于终止态，一些表和历史信息还是会保存在内存中，操作系统不需要了才彻底删除。

被挂起的进程

挂起：一个新的进程状态。当系统中出现大量阻塞进程影响执行新进程时，会将进程挂起，并转移到磁盘，释放空间供另一个进程使用。

  • 阻塞->阻塞挂起：需要腾出空间时
  • 就绪/挂起->就绪：内存没有就绪进程或者挂起的进程比内存进程优先级高时
  • 就绪->就绪/挂起：对于低优先级的就绪进程和高优先级的阻塞进程（并且操作系统确信他很快会就绪），则会挂起就绪进程。

挂机就等价于不在内存的进程。

进程描述

操作系统如何控制进程以及管理资源

操作系统的控制结构

为了掌握每个进程和资源的状态，需要构造并维护每个实体的信息表：内存、I/O、文件和进程

进程控制结构

属性集称为进程控制块。程序、数据、栈和属性的集合称为进程映像。

进程控制块信息包括三类：

  • 进程标识信息：PID, PPID, 用户ID（说明拥有该进程的用户）
  • 进程（处理器）状态信息：由寄存器的内容组成，包含用户可见寄存器、控制和状态寄存器以及栈指针。
  • 进程控制信息：操作系统控制和协调各种活动进程所需的额外信息。

进程控制

执行控制

一般来说，处理器有很多种执行模式，有些只能在特权模式下执行。处理器如何知道自己处于什么模式，如何切换？

PSW通常有一个指示执行模式的位，当调用系统服务或中断来触发系统例程时，执行模式被设为内核模型，返回用户进程时，被设为用户模式。（比如说，发生中断时，由硬件清空标志位，返回时，由程序员手动设置标志位）

进程创建
进程切换

什么时候切换？一旦操作系统从进程手中拿回了控制权，就可能切换。

模式切换是什么？从用户模式切换到内核模式，这里保存上下文以及恢复上下文仅需很小的开销，还是硬件完成的（ARM里面就是R1-R3，PC, SP, PSW差不多吧）。如果切换进程，则需要做很多额外的处理。

操作系统的执行

操作系统是进程吗，如何处理他和其他进程关系

无内核进程

这讲的也好复杂，看最后一句吧。

在用户进程内运行

即在用户进程的上下文执行所有操作系统软件。相当于用户调用系统函数。进程在内核模型运行时，有单独的内核栈，操作系统代码和数据位于共享地址空间。当发生中断陷阱系统调用时，需要保存模式上下文并切换模式，再切换到操作系统例程，但此时仍然是在用户进程内继续执行，不需要切换进程，只是在同一进程内切换模式。

基于进程的操作系统

鼓励模块化，有些简单的功能可以用独立的进程实现，多处理器环境可以把服务放到单独的机器上。

前面说过，进程可以通过中断陷阱系统调用访问操作系统代码，但这三个东西其实都是中断，系统调用也是通过软中断实现的嘛，中断触发后，切换处理器模式，保存上下文，然后调转到系统对应的代码运行。（可见中断的重要性，要是没有中断，程序可能就没法访问操作系统，也没法终止了，除非执行完）

线程

进程与线程

多线程

多线程指的是在单个进程内支持多个并发执行路径的能力。

线程优点：

线程的功能

线程状态：类似进程，也有运行、就绪和阻塞态。挂起态对线程没有意义，因为这类状态仅适用于进程，一个进程被挂起，所有线程都要被换出。

几个与线程状态有关的操作：

  • 派生：产生新进程时，会派生一个线程，线程可以派生另一个线程。
  • 阻塞
  • 解除阻塞
  • 结束

假设线程阻塞不会导致整个进程阻塞，则会有如下优点。（具体会不会阻塞要看后面用户级线程和内核级线程）。

可明显的加快程序的运行速度。

线程同步

与进程同步相似。

线程分类

用户级和内核级线程（ULT & KLT）后者又称为轻量级进程
用户级线程

在纯ULT软件中，管理线程的工作由应用程序完成，他需要包含创建以及销毁，保存以及恢复上下文、调度的代码。内核不知道这件事，仍然以进程为单位调度。

使用纯ULT的优点：

也有对应的缺点：

  • 执行系统调用时，会阻塞进程中的所有线程
  • 多线程不能利用多处理技术，同时刻只有一个线程被执行，无法并行。

现在有方法解决这两个问题：比如把应用程序写成多进程程序（欸，不考虑资源开销吗）；另一种方式是使用套管（jacketing）的技术。套管的目标是把产生阻塞的系统调用转化为一个非阻塞的系统调用。例如，线程不去调用系统级的IO例程，而是调用应用级的IO套管例程，这个套管例程发现IO忙时会将线程阻塞将控制权传递给另一个线程。这个线程重新获得控制权后，套管例程会再次检查IO设备。(即用应用级的方式来模拟系统调用，把事件停留在应用能处理的范围内)

内核级线程

在纯KLT软件中，管理线程的工作均由内核完成。应用级没有线程管理代码，只有一个到内核线程设施的语言编程接口。Windows就是这样。

内核级线程解决了上面ULT的两个问题，但会耗费更多时间，

混合方法

比如说，对于想要实现并行的线程，则将他们按照1:1的映射到内核线程，对于响应节约时间开销的线程，则按照N:1的方式映射到内核线程。

其他方案

线程与进程满足多对多的关系

多核与多线程

对于某一类型任务，随着核数增加，加速比会先增加后减小（任务调度和缓存一致性都会带来开销）

Windows的进程和线程管理

  • 应用程序由一个或多个进程构成，

  • 作业对象运行将一组进程作为一个单元来管理。

  • 线程池是一个工作线程集，主要用来减少应用程序线程的数量。

  • 纤程（fiber），工作在线程的上下文中。（应该是比线程还轻量级的线程）

  • 用户模型调度（UMS, 感觉和ULT很类似），以用户模型切换UMS线程。

此处省略一万字

Linux的进程与线程管理

Linux任务

这里的可中断，感觉和中断不是同一个意思。这里应该指的是能否被打断的意思。不能被打断，则会一直等到等待的事件。可以被打断，则也可以接收信号，然后做出处理。

Linux线程

传统UNIX系统支持在每个进程中只执行一个线程。

Linux使用clone命令来代替fork来创建线程。

Linux命名空间

命名空间可使一个进程（或共享同一命名空间的进程）拥有与其他命名空间下进程的不同的系统视图。命名空间和cgroups是Linux轻量级虚拟化的基础。他为一组或一个进程提供了一个错觉，认为自己是系统上唯一的进程。Linux有六种命名空间mnt、pid、net、ipc、uts和user。

并发：互斥和同步

并发会在三种上下文中出现。

  • 多应用程序
  • 结构化应用程序
  • 操作系统结构

并发其实就是加强进程互斥的能力。

互斥：软件解决方法

Dekker算法

mutex是操作系统提供的，他更高效和易用，但在一些平台，没有mutex，Dekker算法就有用了，它提供了手动实现互斥的方式。

错误示范：

  • 用一个全局变量turn，当自身id等于turn才能进入。缺陷是如果某个进程在临界区终止了，可能导致另外一个进程永远无法进入
  • 每个进程保存一个状态flag，先检查对方进程的flag，为false时将自己的flag进入临界区。缺陷是没法保证互斥，有可能同时进入，而且如过另一个进程在临界区停止，也会导致当前进程进不去。

两个进程下：有两个标志turn和flag，turn指定了都想进入临界区时的先后顺序。每个进程有个flag，代表自己是否有意愿进入临界区。当一个进程要进入临界区时，先设置flag为true，

  • 如果另一个进程flag为false，则当前进程直接进入
  • 如果另一个进程flag为true，则检查turn
    • 如果当前进程id等于turn，则等到另一个进程flag变为false时在进入，结束时再将turn置为另一个进程的id
    • 如果当前进程id不等于turn，则将进程flag变为false变为false

（貌似这个另一个进程被意外终止，导致flag和trun失效的状态？看下面，wnm）

Perterson算法

并发的原理

并发时，进程被交替执行，呈现出交替执行的状态。

在单处理器多道系统（多处理器也是一样的）下，进程的执行速度不可预测，这导致了很多问题。比如资源共享，资源分配，定位错误也非常困难。

在单处理器下，主要是因为中断可能在任何时候进行，导致访问了共享资源。在多处理器情况下，不仅同样的条件会引起问题，当两个进程在两个核上执行时，也会引发问题。这两类问题的解决方式都是一样的：控制对共享资源的访问。

操作系统并发带来新的管理问题
进程的交互

竞争进程面临三个控制问题

  • 互斥，在临界区只能允许一个程序访问（下面两个都是因为这个问题出现的）
  • 死锁，都在等待对方的资源
  • 饥饿，某些进程一直访问不到资源

共享进程也面临上面几个问题，还需要注意一致性问题。

互斥的要求

软件方法应该就是Perterson算法吧

互斥：硬件的支持

几种实现互斥的硬件方法

中断禁用

一旦禁用了中断，时钟中断、系统调用等都不会产生，就都不会将处理器交给系统，也不会导致进程调度。这种方式代价很高，同时这种方式不能用于多处理器体系结构中。因为多个进程会同时执行。

专用机器指令

在多处理器配置中，几个处理器都可以对内存进行访问，处理器之间没有支持互斥的中断机制。

处理器的设计人员提供了机器指令，用来保证两个动作的原子性，在一个取值周期完成对一个存储单一的读和写或读和测试。

这个指令的执行过程中，任何其他指令访问内存都被阻止。

from kimi

以下是在多核环境中CAS操作可能发生的情况：

  1. 原子性：CAS操作是原子的，这意味着在任何给定时间点，只有一个核心可以成功地执行CAS操作并更新内存位置。其他核心的CAS操作会检测到内存位置的值已经改变，因此它们的操作会失败。
  2. 失败重试：当一个核心的CAS操作失败时，它可以根据应用的需要决定是否重试该操作。这种机制是实现自旋锁（spinlock）的基础，其中线程或核心在失败后不断重试，直到成功为止。

最常见的两个指令（这些指令本身就支持并发，不需要程序员做处理）包括：

  • 比较和交换指令 检测一个内存区域是否等于某个值，相等则更新该内存区域。同时刻只能有一个进程能执行这个命令，其他进程会进入自旋等待，除此以外不能做任何事。(很多操作系统都用该指令支持并发)

    1
    2
    3
    4
    5
    6
    int compare_ and_ swap (int *word, int testval，int newval)
        int oldval ;
        oldval = *word
        if (oldval == testval) *word = newval;
        return oldval ;
    }

  • exchange指令

    这个指令交换寄存器和存储单元的内容，IA-64中的XCHG命令。

    1
    2
    3
    4
    5
    6
    7
    void exchange (int *register, int *memory)
    {
        int temp;
        temp = * memory;
        *memory = *register;
        * register = temp;
    }

    下面的图片展示了上述指令的使用：（这两个命令的原子性由硬件保证，即使是多核，也只能有一个指令执行。可以用它来实现锁机制）

优点&缺点

这两个指令本身不会带来死锁问题，在这两个指令的基础上实现的并发程序才可能出现死锁。

信号量

前文讲了通过软件和硬件的方式来设计并发程序，现在将介绍操作系统提供的并发机制。主要分为信号量、管城、消息传递三大类。

二元信号量和互斥量的关键区别是，互斥量只能由同一个进程加锁解锁，而二元信号量没有这个限制。

  • 强信号量，规定了进程从阻塞队列中移除顺序的信号量，保证不会饥饿
  • 弱信号量，没有规定了进程从阻塞队列中移除顺序的信号量

先把下图看懂吧。通过下图可以看出，一旦当把一个进程移出等待队列时，该进程应该就默认获得要申请的资源了，（不用再次等待了，再次运行时，应该运行的是semwait后面那条指令了）。之前讲过，进程可能处于不可中断/可中断阻塞态，如果是可中断，意味着程序能够被除等待事件的其他事件唤醒，比如如果是一个信号唤醒了程序，让他移出了等待队列，那么该进程就觉得自己等到了资源，但实际是被意外唤醒的，所以很多程序还会在semwiat后面判断一下时是否真的获得了资源。

感觉并发主要就要处理互斥，以及互斥带来的问题：饥饿与死锁

互斥

用信号量实现互斥，将信号量初始化为一，然后如下图运行。

消费者生产者问题
  • 资源数量记得用信号量保存，而不是用局部变量保存，因为局部变量可能出现同步错误
  • 先wait信号量再wait互斥量
信号量的实现

如前所述，semWait和semSignal操作必须作为原子原语实现，可以通过硬件或软件（Dekker或Peterson算法）实现，本质是互斥，只要保证任何时候只有一个进程可用semWait和semSignal控制信号量就行了。

对于单处理器系统，直接禁中断也是可以的哟。

管程

信号量是为了实现互斥和进程间的合作，操作系统提供的一种强大但原始的工具，难点在于semWati可能分布在整个程序中，很难看清效果。

管程是一种程序设计语言结构，他提供与信号量相同的功能，但更易于控制。

使用信号的管程

感觉信号量和互斥量只保证了访问是互斥的，其实要访问的资源也只是个全局变量。而管程将这个全局变量和访问方式也封装到了类里面。

  • 管程提供互斥机制，同时只能有一个进程进入管程

  • 管程包含同步处理，管程通过条件变量来支持同步，有两个函数可以操作条件变量

    • cwait，调用的进程在条件c上阻塞

    • csignal，恢复在cwait后因某些条件而被阻塞的一个进程

      与信号量的区别在于：管程中的一个进程发csignal，如果没有等待的任务，则丢弃这个信号。

管程相对于信号量的优点在于，所有的同步机制都限制在管程内部（互斥机制也是由管程提供的），因此不但易于验证同步的正确性，还容易检测出错误。如果一个管程编写正确，则所有进程对于资源的访问都是对的。如果是信号量，则要求所有访问资源的进程都被正确编写。

from kimi

管程的互斥机制是由编译器提供的。在管程的设计中，编译器确保在同一时间内只有一个进程可以进入管程执行，这样可以保证对共享资源的互斥访问，避免多个进程同时访问共享资源而引起的数据不一致问题。这种互斥是由编译器强制实施的，程序员在编写使用管程的代码时不需要显式地处理互斥问题，这简化了并发编程的复杂性。简而言之，管程作为一种高级同步机制，封装了对共享资源的访问，而编译器负责实现这种封装背后的互斥逻辑。

使用通知和广播的管程

Hoare关于管程的定义要求一个进程产生csignal信号时，当前进程立刻退出或阻塞，并运行队列中的一个进程。这有一些缺陷：

  • 导致额外的进程切换
  • 调度程序必须非常可靠

为此，Mesa语言有一种不同的管程。它使用cnotify代替csignal，cnotify会让发信号的进程继续运行，也会使条件队列得到通知，让他们在处理器可用时在运行。

  • 这里用while代替if，可以多检查一次条件变量

  • 也可以给每个添加原语添加一个计时器，不管有没有被通知，计时器超时就会唤醒等待队列的第一个进程，就算误唤醒了也有while循环再次阻塞。这可以避免饥饿状态。

  • 进程是接到通知而非强制激活，所有可以增加一个cbroadcasst原语，当不知道激活多少个进程时，不如就全部激活。

消息传递

同步让两个线程，一个运行完毕，另一个才能运行。所以同步是一种更复杂的互斥，而互斥是一种特殊的同步。

为了实现合作，进程间应该交换信息，提供这个功能的是消息传递，消息传递还有一个优点，它可以在分布式系统，多处理器系统和单处理器系统中实现。

消息传递的功能以一对原语的形式提供：

1
2
send(destination, message)
receive(source, message)

下表给出了消息传递系统的一些设计问题，后文将分析这些问题。

同步

隐含着同步的信息：一个进程发消息后，另一个进程才能接收消息。

发送方可以阻塞（知道接收方收到）也可以不阻塞，接收方可以阻塞直到等到消息或者不阻塞。可以分为三种组合：

无阻塞send很常用，但可能会导致还需要应答消息来判断对方是否收到，增加了程序员的负担。

阻塞receive很常用，但如果发送消息的进程消息丢失，则接收进程会无限期的阻塞，可以利用无阻塞receive来解决，但也可能出现消息丢失，可能的办法是

  • receive先判断有没有消息
  • 如果可以接受多个源进程的消息，。。。
寻址

  • 直接寻址

    • send，要求目标进程的标识号
    • receive，显式指定，隐式指定

  • 间接寻址，给信箱发消息，接收消息，这允许1：1，m：1，1：m的关系。

进程与信箱的关系可能是静态的（1：1很可能是静态的），也可以是动态的。m：1关系时，信箱又被称为端口，端口的所有者是接收进程，撤销接收进程时，端口也会被撤销。对于通用的信箱，可以指定信箱归创建他的进程或操作系统所有。

互斥

信箱虽然能实现同步，也能实现互斥，只允许一个进程读取该信箱。

读者写者问题

区分一下读者写者问题与一般互斥问题和生产者/消费者问题。

  • 一般互斥问题是读者写者的一般情况，之所以要关注读者写者问题，是想要制定更高效的方案
  • 生产者/消费者问题不是读者写者问题，生产者也要写（取出一个单元）。

下面分析读者写者问题的两种解决办法：

读者优先

欸，原文好难，后面看看吧。

并发：饥饿和死锁

死锁原理

可重用资源

一次仅供一个进程安全使用而不因使用而耗尽的资源。如处理器，IO, 设备。这类问题的发生可能隐藏在复杂的程序逻辑中，难以检测。

可消耗资源

指的是可被创建和销毁的资源，数量通常没有限制，用完后该资源就不存在了，如信号，中断。

死锁的必要条件
  • 资源互斥
  • 占用且等待
  • 不可抢占资源
  • 循环等待

死锁预防

  • 间接预防，阻止前三个必要条件
    • 互斥，没办法禁止呀，并发程序设计的基础就是这个
    • 占有且等待（资源状态容易恢复时，这个才work），可以一次性分配完所有要的资源
    • 不可抢占，预防不可抢占的方法有几种，比如
      • 如果占有资源的进程申请新资源被拒绝，则它应该释放所有资源
      • 一个进程请求的资源被另一个进程占有时，操作系统可以抢占另一个进程，（高优先级进程应该可以抢占低优先级进程的资源）
  • 直接预防，阻止第四个条件（循环等待）的发生
    • 给资源排序，只能先申请前面的，在申请后面的。

死锁避免

死锁预防虽然可以预防死锁，但会导致效率变低。使用死锁避免，可以明智的选择，让系统达不到死锁。两种避免方法：

  • 一个进程的请求会导致死锁，则不启动该进程
    • 实现判断进程启动后所消耗的所有资源，如果超过系统量，则不启动
  • 一个进程增加的资源请求会导致死锁，则不允许这个资源分配
    • 又名银行家算法

使用死锁避免时，必须先声明每个进程请求的最大资源，所讨论的进程必须是无关的，即他们的执行顺序没有同步的限制（那这不可能呀），分配的资源数量固定。

死锁检测

死锁检测算法

死锁检测可以在每个资源请求时发生。

恢复

  • 取消所有死锁进程

  • 回滚死锁进程到前面定义的检查点

  • 按照最小代价取消死锁进程

  • 连续抢占资源直到没有死锁

一种综合的死锁策略

哲学家就餐问题

五人五叉子，每个人要两个叉子，算法要互斥（不能用同一个叉子），也要避免饥饿和死锁。

基于信号量

如果先拿左边的，再拿右边的，会导致死锁。可以通过信号量只让四个哲学家进入。

基于管程

因为管程中的过程是不能中断的（管程），并且同时只能用一个进程进入管程，所以第一个哲学家能拿起左叉子，也能拿到右边的叉子。

UNIX并发机制

几种重要的并发机制：

管道、消息、共享内存、信号量、信号（前三种提供了进程间传输数据的方式，也就实现了同步）

  • 管道是一个环形缓冲区，允许多个进程以生产者消费者模型进行通信
  • 消息，类似于信箱
  • 共享内存，速度最快
  • 信号量，由如下元素组成：当前值，最后一个进程的id，
  • 信号，给进程发事件的机制，只有在进程被唤醒或者从系统调用返回时，才能处理信号（这话在linux中应该不对喔）。

Linux内核并发机制

包含UNIX中所有并发机制。Linux还支持一种特殊的信号，实时信号

Linux还未内核线程准备了丰富的并发机制，他们可以用在内核中。

原子操作

Linux提供了对变量的原子操作。原子操作执行时不会被打断，如果是单处理器，操作开始到结束，不能中断线程，如果是多处理，还需要锁住变量以免被其他进程访问。

  • 一种是对整数变量的整数操作
  • 另一种是针对位图中某一位的位图操作

某些体系中，有对应的汇编指令，没有汇编指令就会锁住内存主线保证原子性

自旋锁

保护临界区的技术，首先检查内存区域的一个值是否为0，为0则进入并置1，非零则一直忙等待（而不是阻塞，如果锁持有时间非常短，那他相比阻塞导致的线程切换会少花费很多时间）

  • 普通自旋锁，不改变中断状态，确信临界区代码不被中断打断或者已经关闭了中断的情况下使用
  • _irq, 与普通自旋锁类似，但会在临界区关闭中断
  • _irqsave, 执行前保存中断状态，从临界区返回时，恢复中断状态。
  • _bh, 发生中断时，
信号量
屏障

为了优化性能，部分指令编译时会交换顺序。

内存屏障可以保证之前的代码和之后的代码没办法穿过屏障。

内存管理

内存管理的需求

重定位，保护，共享，逻辑组织，物理组织

重定位

处理器硬件和软件必须以某种方式把程序代码中地址转化为实际的物理内存地址。

保护

防止访问不该访问的内存，处理器硬件才具有这个能力。

内存分区

常见的内存管理技术如下图所示，xx分区技术早已过时，简单分页/分段没有实际使用过。

前几种分区

略

重定位
  • 逻辑地址，当前数据在内存中的（与物理地址无关的）地址
  • 相对地址，相对于某些点（通常是程序的开始）的存储单元
  • 物理地址，数据在内存的实际地址

系统使用运行时动态加载的方式将相对地址的程序加载到内存，通常有一个基址寄存器保存程序的在内存的开始位置，还有一个界限寄存器指明程序的终止位置，遇到相对地址时，会将相对地址与基地址寄存器，在与界限寄存器比较，超过则触发中断。

分页

若使用大小不等的固定分区，会导致内部碎片，若使用大小可变的外部分区，会导致外部碎片。使用页时，只有进程尾部有内部碎片。

在分页中，每个进程维护一个页表，页表给出了该进程的每页所对应的页框的位置。每个逻辑地址包含一个页号和在该页中的偏移量，逻辑地址到物理地址的转换有处理器硬件完成，处理器使用页表产生物理地址（包括页框号和偏移量）。

分段

加载与链接

  • 绝对加载，在编译时就指定每个内存访问的绝对地址（静态链接，比如从0x0000000000400000开始）

  • 可重定位加载，加载前目标文件使用的是相对地址，加载器再把程序加载到内存的xxx地址时，给每个内存访问都加上xxx。（动态链接一般采用这种方式，加载时会修改.got和.plt.got段来进行重定位）

  • 动态运行时加载，程序被加载到内存中，对内存的访问也是相对地址形式的，只有实际访存时，才会计算真实地址。（为了效率使用硬件实现）

    内存涉及到换入换出，如果换入到不同的地址，可重定位加载也不可用。

如上表，链接可以在产生加载模块时链接，也可以在往内存加载模块时链接，也可以在运行时链接。

链接编辑程序是负责产生可重定位加载模块的链接器。对于可重定位的加载模块，通常会创建每个目标模块相对于总的目标模块开始处的引用，

虚拟内存

硬件和控制结构

进程要访问的地址不在内存时，处理器会产生缺页中断，系统会把进程置为阻塞态，然后将对应的内存块读入内存。

分页

每个进程有个页表，页表项包含有与物理内存中的页框所相应的页框号，以及一些控制位，P代表该页是否在内存中，M代表有没有修改该页内存。

虚拟地址 = 页号 + 偏移量

物理地址 = 页框号 + 偏移量

虚存有多少页，就要考虑如何存储这么多个页表项。

  • 大多数页表也是放到虚存而不是直接放到物理内存的，这可以避免将所有页表项加载到内存中。

  • 使用两级方案，

TLB表：

TLB高速缓存：存放TLB表的高速缓存

内存高速缓存：Cache

磁盘高速缓存：内存上的一块区域，用来从/向磁盘读写数据

通过上文的图片得到物理地址后，然后在内存高速缓存查找是否有包含这个字的块，有则返回给CPU；没有则从内存中检索这个字（这又涉及到该字在不在内存的问题）整体流程如下图所示：

虚拟地址转换为物理地址时，需要访问页表项，这个页表项可能位于TLB、内存、磁盘中，要访问的字可能位于高速缓存、内存或磁盘中。

一次访存可能产生两次缺页中断，也i沉思页表，一次是进程页

段页式

操作系统软件

操作系统的内存管理取决于三个基本的选择：

  • 是否使用虚存技术
  • 是使用分页还是分段，或者都要
  • 为各种存储管理特征采用的算法
读取策略
  • 请求分页，请求到某个单元才将其读入内存，程序启动时会有大量的缺页中断
  • 预先分页，一次读取多个页，即使某些页当前没有被用到，程序首次启动时可以使用这种方式。
放置策略

通常无关紧要

置换策略
  • 最佳，由于需要预知未来的事件，不可能实现。
  • 最近最少使用
  • 先进先出
  • 时钟
驻留集管理

固定大小？全局/局部置换？

清除策略
加载控制

控制驻留内存的进程数量，

Linux内存管理

LInux内存管理的两个主要特征：进程虚拟内存和内核内存分配。

虚拟内存

Linux使用三级页表，三类表如下所示：

  • 页目录，最顶层的表，每个进程有一个，活动进程的页目录必须在内存中
  • 页中间目录，每项指向一个页表
  • 页表，每项指向一个虚拟页

页面分配：使用伙伴系统，来一次将多个连续的页映射到连续的页框中，提升效率。

页面置换算法：

  • LInux2.6.28之前，使修改的时钟算法，缺点是周期扫描缓存，造成额外开销。

  • 之后，使用新的分割LRU算法，每个页表有PG_active和PG_referneced两个新的有效位，（之前的访问标志也应该存在）。

    PG_active=1代表短时间内访问了两次；PG_referneced=1代表最近访问了一次，如果短时间内再被访问了一次，系统会将该页PG_active设为1。PG_active=0的页面可能被一个LRU类型的算法置换。差不多是这样吧。

内核内存分配

内核内存也是通过虚存分配的吗，还一直以为是直接映射的

单处理器调度

  • 高级调度（长程调度），决定将那些作业调入内存并转化为进程
  • 中级调度（中程调度），决定将那么进程从内存移出
  • 低级调度（短程调度），处理器执行哪个进程

处理器调度的类型

调度算法

  • 面向用户，比如交互式系统响应时间
  • 面向系统，如何提高系统的利用率

具体分类太多了，略

性能比较

假设是排队论，泊松到达率以及指数服务时间

公平共享调度

在多用户系统中，一组进程如何执行。

多处理器、多核和实时调度

多处理器和多核调度

粒度（同步的频率，粒度越小，同步越频繁，数据的一致性和实时性越高）

既然是多核、多处理器，就要考虑同步问题，把进程间的同步粒度分为这些等级：

  • 粗和极粗，基本不用改动程序
  • 中等，需由程序员显示指定潜在的并行性
  • 细粒度，
设计问题

多处理器中的调度设计三个问题

  • 把进程分配到处理器，分为静态分配（每个任务只分配给一个处理器）和动态分配（所有进程放到一个公共队列中，然后分给各处理器，Linux也是这种策略）。操作系统内核可以只运行在一个内核上（会出现性能瓶颈）也可以像普通进程一样随机分配到处理器。
  • 在单处理器上使用多道程序设计
  • 一个进程的实际分派

所用的方法取决于应用程序的粒度级以及可用处理器的数量。

进程调度

多处理器情况下，调度算法之间的差别很小，很多算法并不比FCFS优秀太多，选择FCFS就行了。（应该是核太多了，让每个进程都能及时接受服务）

横坐标可以看成平均服务时间的离散程度

线程调度

在多处理器系统中，线程可开发应用程序中的真正并行性。一个应用程序在不同的处理器中运行，其性能会显著提升。几种线程调度方案：

  • 负载分配，维护一个全局队列。虽然有很多劣势，还实际还是用的挺多的。

    • 优势：简单，负载均匀的分布在处理器上
    • 劣势：
      • 全局队列可能被多个处理器查找，造成性能瓶颈
      • 一个进程的多个线程没法在同一个处理器运行

  • 组调度，专业术语，已经用来表示同时调度组成一个进程的一组线程。对与中粒度到细粒度的应用程序，组调度非常重要（同组的多个线程之间有紧闭的合作/同步关系，如果一个线程执行，而其他的不执行会严重的降低性能）。

  • 专用处理器分配， 把一组处理器分配给一个应用程序（包括很多线程），直到应用程序结束。（当线程数大于处理器数目时，加速比会降低）

多核线程调度

随着内核数量越来越多，最小化访问片外存储器比最大化处理器利用率越优先。（不要为了利用率安排内存资源毫不相关的线程运行，以免影响cache命中率）

实时调度

实时操作系统的特点
  • 可确定性，
  • 可响应性
  • 用户控制
  • 可靠性
  • 故障弱化操作

Linux调度

实时调度
非实时调度

随着中央处理器的增加，Linux2.4对于SCHED_NORMAL类的调度程序表现的不好：

  • 所有处理器都只有一个队列，不利于高速缓存
  • 一个处理器选择任务时，其他处理器只能围观
  • 任务不可抢占。

新的完全公平调度器（CFS）

为每个任务维护一个虚拟运行时间，时间越短，代表他对处理器的需求越强。

CFS调度器基于红黑树实现，

I/O管理和磁盘调度

I/O功能的组织

三种I/O技术：

  • 程序控制I/O，发出I/O命令后，一直等到设备准备好数据才执行
  • 中断驱动I/O，发出I/O命令后，设备开始准备数据，处理器在这期间仍然可以执行其他命令
    • 如果该I/O是阻塞的，则将进程阻塞并调度其他程序
    • 如果该I/O是非阻塞的，则继续执行该I/O的后续命令。（I/O是阻塞的意味着当前的I/O命令很重要，必须先于后面的命令执行）
  • 直接内存访问，由DMA控制和I/O模块的交换，在设备准备好数据、DMA传输完数据，才会给处理器发中断。
直接内存访问

操作系统设计问题

设计目标

  • 效率
  • 通用（隐藏设备特征）
I/O功能的逻辑结构

  • a，逻辑外部设备

    • 逻辑I/O，打开、关闭、读写之类的命令（所有I/O应该都差不多）
    • 设备I/O，请求的操作和数据被转换为设备对应的指令序列
    • 调度和控制，I/O的排队、调度都在这一层，（应该是直接给设备发数据命令的那一层吧）

  • b，通信端口，与a的区别是，把逻辑I/O变成了通信架构，通信架构由很多层构成，如TCP/IP。

  • c，文件系统

    • 目录管理，将文件名变成标识符，通过标识符访问文件
    • 文件系统，处理文件的逻辑结构，处理用户的操作如打开，读写。
    • 物理组织，将对文件的逻辑访问变成实际的外村地址。

I/O缓冲

执行I/O指令直接将磁盘数据加载到内存的虚拟地址空间。缺点：

  • 对应的虚拟地址单元必须保留在内存中，如果是分页，则将对应的页面锁定。
单缓冲

对于面向流的缓冲，

  • 每次传输一行，用缓冲区保存一行数据，输入期间用户进程被挂起
  • 每次传输一个字节，按照生产者消费者模型进行

如果CPU直接与IO交互，CPU的速率受限于IO，如果使用缓冲区，则可以等到缓冲区装满时再通知CPU一起处理。

磁盘调度

磁盘性能参数

寻道时间：磁头定位到磁道的时间

旋转延迟：找到磁道后，磁头到达扇区开始位置的时间为旋转延迟

存取时间：寻道时间+选择延迟

一个文件存放相邻的扇区会降低存取时间。

磁盘调度策略

SCAN（仅沿一个方向扫描），C-SCAN（访问磁道到顶后，在反向扫描）

RAID

独立磁盘冗余阵列，用多个小容量磁盘代替大容量磁盘。由于有多个磁头，可以达到更高的I/O速度，但多个设备也增大了失效的概率，所以使用奇偶校验来恢复数据。

常用 0，1，5，6

RAID 0

很多超级计算机也使用这种方案，因为成本比可靠性重要。

磁盘依次存储到RAID0的每个条带中，如果I/O请求有多个连续的条带组成，则该请求可以并行处理。

Linux I/O

磁盘调度

电梯调度有些问题，比如20，30，700， 25，如果一直有低块号请求，则700的会被延后。

读请求和写请求是不同的，写请求是异步的

  • 写请求把数据复制到缓冲区，应用程序就可以继续运行
  • 读请求会要求进程等待，直到磁盘将数据发给应用程序。

最后期限调度程序

维护一个排序的电梯队列和一个FIFO的队列，（读请求和写请求又分成了两个队列）

  • 当电梯队列的请求被服务时，会从两个队列同时移除该请求。
  • 当FIFO的头部的请求超过到期时间时，会先从该FIFO队列获取任务，也会从两个队列同时移除该任务。

预期I/O调度程序

是对最后期限调度程序的补充，分配一个读请求时，调度程序会将调度系统的执行延迟6ms，这段时间内，如果该进程又发了一个相邻区域的读请求，则会立刻接受服务，否则继续使用最后期限调度程序。

完全公平I/O调度

文件管理

要不直接去看Linux内核