操作系统复习

操作系统复习

第一章 操作系统导论

什么是操作系统？

操作系统位于计算机用户和计算机硬件之间，主要目的是提供环境来方便帮助用户执行程序。简单来说，操作系统就是管理硬件资源和控制程序执行的系统软件。

计算机系统的组成

由用户、应用、操作系统、硬件组成。（从上往下看）image-20240626201011862

计算系统

基本元素为：CPU、主存、IO、系统总线…

  1. CPU：中央处理器，负责计算机的计算。
  2. 主存：你知我知。断电后内容会消失。
  3. IO：在计算机和外部环境之间移动数据。
  4. 系统总线：提供CPU、主存与I/O模块之间的通信通道。

中断

中断就是打断当前执行的进程，立即处理比较紧急的进程，然后再返回当前进程继续执行。

中断机制的出现是为了协调处理器与外部设备速度不一致的问题，以提高处理器的利用率。
试想我们打开了文本编辑器，处理器就不干活了，等着键盘输入，这会浪费多少处理器计算资源？
另一种方式是处理器忙自己的，等有输入时再通知处理器。

  1. 中断机制的主要原因是提高性能。（因为cpu计算的时间和IO的时间差距很大）
  2. 中断分类：分为硬件中断和软件中断。
    • 硬件中断：通常我们说的中断都是硬件中断。例子：敲击键盘、移动鼠标、timer。完成硬件中断后会返回一个signal提醒处理器。
    • 软件中断：异常和系统调用(system call)。例子：system call函数或者除以0。
  3. 中断实现：
    • 中断向量表：中断向量表存储了每种可能的中断类型对应的中断处理程序的起始地址。

存储

按照层次分类。image-20240626203649171

磁盘可以随机读取，可是磁带只能顺序读取。

IO结构

  1. 简单理解成要数据要传输了。
  2. 通用计算机都由CPU和多个设备控制器组成，通过总线连接，每个设备管理某一特定类型的设备。
  3. 通过中断来执行IO：image-20240626204437935、

这个设计使得cpu和io设备可以并行执行。

操作系统执行

  1. 引导程序，找到操作系统的代码，并加载简单的内核代码（在硬件层面）。
  2. 加载内核。
  3. 启动系统服务
  4. 用户登录
  5. 用户执行程序

批处理操作系统

计算机要处理的一个计算问题称为作业。

就是一次处理多个作业，把多个作业加载到内存，所以CPU总是有一个作业要执行。

在作业执行时，用户不能直接干预。

效率快，因为减少了调作业进内存的时间（一次调一批作业）而且cpu比较少时间空闲。

image-20240626204946402

分时操作系统

有点类似RR算法，就是频繁切换作业，每个用户的作业跑一个时间片被换出。

所以多个用户们可以交互。

实时操作系统

实时操作系统通常用于需要对任务执行时间有严格要求的应用领域。

响应时间保证：实时操作系统能够保证任务在其要求的时间内完成或响应。

任务调度机制：实时操作系统使用特殊的任务调度算法，如优先级调度和周期性调度，以确保高优先级任务能够及时执行，而不会被低优先级任务阻塞。

应用于飞行控制系统等等。

双重模式

包括内核模式和用户模式。

image-20240626205303231
  • 硬件会提供一个模式位(bit)来判断当前是内核还是用户。
  • 当用户调用系统函数或中断时，会自动变成内核模式，返回后改回用户模式。
  • 有些函数只有内核态才能调用。image-20240626205754059

题目

书本题目1.8：中断和陷阱的区别，用户程序能否有意产生陷阱，如果能，为什么？

答：陷阱是用户程序产生的软件中断，所以它是同步的；中断是由硬件发出的信号，接收到信号后需要异步的停止当前进程，然后执行对应中断的程序；用户程序能产生陷阱，例如像屏幕输出就是用户程序产生陷阱。

陷阱是由用户程序发出的信号，指示操作系统立即执行某些功能。相反，中断是由硬件发出的给CPU的信号，表示需要立即处理的事件。

  1. cpu只能读取主存和cpu内的寄存器。

第二章 操作系统结构

操作系统提供的服务

  1. 程序执行的环境
  2. 提供用户服务：
    • 用户界面
      • 用户界面、图形用户界面(GUI)
    • 程序执行
      • 系统必须把程序加载到内存并执行
    • IO操作
    • 文件系统操作
    • 通信
      • 进程在同一台计算机上交换信息
    • 资源分配

操作系统如何提供服务

操作系统通过**系统调用(system call)**来向用户提供服务。image-20240626215521162

系统调用是一种中断。

分层思想

将操作系统像洋葱一样分成多层，第0层为硬件(最底层)，第N层为用户(最高层)。

每一层仅使用更低一层的功能和服务。image-20240626221509216

操作系统分层：设备管理、文件管理、处理器管理、存储管理、作业管理。

内核结构

  • 宏内核

    宏内核是大而全的管理者。

    宏内核，也被称为单体内核，是一种把所有的服务都集中在一起的内核设计。

    它的优点是性能高，因为所有服务都在内核中运行，调用过程简单，效率高。

    这种设计也有缺点，如果内核中的一个服务出现问题，可能会影响到整个系统的稳定性。

    操作系统代表：Linux、Unix。

    就像一个城市的交通系统，所有的道路、桥梁、交通信号灯都是由一个中央指挥系统控制。这种方式的优点是效率高，因为所有的交通运输都在同一个系统内部进行调度，所以调度速度快，交通流畅。然而，缺点也很明显，如果中央指挥系统出现问题，那么整个城市的交通都可能会受到影响，导致严重的交通拥堵。

  • 微内核

    微内核是小而美的服务商。

    微内核，只提供最基本的服务，如进程调度、内存管理等。

    设计优点是结构简单，容易理解和修改，如果一个服务出现问题，也不会影响到其他服务。

    设计缺点是性能较低，因为服务之间的调用需要在内核和用户空间之间进行切换，效率较低。

    微内核提供了一种消息传递机制，让系统程序和用户程序进行交互。

    就像一个城市的交通系统中，只有最基本的道路和桥梁是由中央指挥系统控制，其他的如公交、出租车等都是由各自的调度系统进行管理。这种方式的优点是稳定性好，因为即使一个服务出现问题，也不会影响到其他的服务。然而，缺点是效率较低，因为服务之间的调度需要在内核和用户空间之间进行切换，这就像各个调度系统之间需要进行协调，导致交通运输的效率降低。

​ 操作系统代表：Mach、鸿蒙。image-20240626221142031

题目

  1. 在现代操作系统中，最里层是硬件，最外层是用户，中间是软件系统（不是操作系统）
  2. 操作系统执行完中断后，会采取调度算法从就绪队列中选择下一个进程（不是被打断的进程）
  3. 在操作系统的分层管理中，处理器管理是在最内层，作业管理是最外层。
  4. 在层次结构中，外层依赖于内层。

补充 中断和异常

中断分成硬件中断和软件中断。

  • 硬件中断：就是平时讲的中断。
  • 软件中断：分成异常和系统调用(system call)。

前面介绍的陷阱是异常的一种。

区别：

  • 来源：
    1. 中断：外设
    2. 异常：用户的程序
    3. 系统调用：用户的程序
  • 响应方式：
    1. 中断：异步
    2. 异常：同步
    3. 系统调用：同步
  • 当前指令：
    1. 中断：与当前指令无关
    2. 软件中断：与当前指令有关

cpu每执行完一条指令就去查看有没有中断信号。

内核态 to 用户态：执行完特权指令后操作系统主动让出cpu资源

用户态 to 内核态：只能依靠中断，任意三种中断都可以转换成内核态

中断是计算机实现并发的原因。

1.1.5 中断的概念和作用、内部中断、外部中断、中断机制的基本原理_中断的定义-CSDN博客

第三章 进程

什么是进程？

进程是执行的程序。

一个进程由 程序、数据集合、PCB组成。

我们强调，程序本身不是进程。程序是被动实体（可执行文件），进程是活动体。

当一个可执行文件加载到内存时，程序变成进程。

进程是cpu分配资源的最小单位。

一个程序可以是多个进程。

  • 进程的组成

    由栈、堆、数据段、文本段、PC等等组成。

    image-20240627130158500

  • 进程的状态

    1. 新建：进程在被创建。
    2. 运行：进程在被执行中。
    3. 等待：进程在等待发生某个事件（如IO完成）。
    4. 就绪：等待被调度。
    5. 结束：进程已经完成。

    image-20240627131031378

    图上的中断(interrpt)应该是硬件中断，例如像**时间片(timer)**到了，进程就会到就绪队列。

    当一个进程申请了IO，这个进程就会到等待队列，等待IO完成再回到就绪队列等待调度。(可以和第一章笔记的IO结构对应着看)

    需要掌握：在什么情况下进程的状态会发生什么变化。

  • 挂起进程

    简单来说，就是暂时被淘汰出内存的进程；被操作系统调出主存到磁盘里，当主存内存空间足够再调用回主存。

  • PCB(进程控制块)

    是进程的表示，PCB存于内核内存中。

    由以下部分组成：

    1. 进程状态：当前进程的状态是什么。
    2. 进程编号(PID)：进程对应的一个唯一的编号。
    3. PC：表示当前进程执行到哪一条指令。(如果是多线程可能有多个PC)
    4. CPU寄存器
    5. CPU调度信息：例如像当前进程的优先级。
    6. …image-20240627133213907

    getpid()的原理：用户调用getpid()函数 – 操作系统转到内核态 – 访问当前进程PCB的PID – 转回用户态并返回PID。

什么是线程

因为每个进程可以有多个PC(多线程)，所以每个进程可以执行多个线程。

每个线程共享进程的堆、文本段、数据段。

每个进程独立的有PC、栈、寄存器。

之后会详细介绍。

image-20240627134128488

进程调度

选择下一个在CPU上运行的进程。

目标：最大化CPU的利用率。

调度队列：分为就绪队列和等待队列。

  1. 就绪队列：里面存放着等待被调度的进程。

  2. 等待队列：等待某件事情(IO)发生的进程。

    image-20240627135342369

上下文切换

中断机制会导致CPU从执行当前的任务变成执行系统内核的任务，所以当中断发生时，我们要保存好当前执行的任务，以便在处理中断之后能够复原当前的任务。

把进程的PCB称为进程的上下文。

上下文切换步骤：

  1. 保存当前的上下文(PCB)。
  2. 加载新的要执行的进程上下文。

上下文切换是一个单纯的开销。

image-20240627142142920

  • 模式切换 VS 上下文切换

    模式切换不一定会上下文切换：例如当发生中断之后，模式切换成内核态，可是当前进程没变。

    模式切换开销比上下文切换小。

进程操作

利用PID来标识进程。

父进程的PID小于子进程的PID。

  • 进程创建

    使用fork()函数来创建新进程。并且父进程的fork()返回值为子进程的PID。子进程的fork()返回值为0。并且子进程拥有和父进程一样的资源。

  • 进程执行

    可以父进程和子进程并发执行或者父进程使用wait()等待子进程执行完再执行。

    值得一提的是，如果子进程调用了exec()的函数，那么会新创一个program，把exec()下的代码全部覆盖了。

  • 进程终止

    使用wait()或者exit()。像下图的例子，父进程使用wait()阻塞自己，等待子进程完成执行后调用exit()像父进程发出一个signal，然后父进程再执行。image-20240627144014620

进程创建的小题目：当fork遇上for循环的问题分析 & fork函数_循环中使用forok-CSDN博客 要记得，fork()之后子进程连buffer内的数据也复制了。

孤儿进程

父进程没有调用wait()就终止了，导致子进程的系统资源无法回收。成孤儿了。

解决方法：操作系统的根进程会**定期调用wait()**函数，回收孤儿进程的资源。

僵尸进程

当子进程终止可是父进程**还未调用wait()**函数回收资源。

通常所有进程终止的瞬间都会过渡到僵尸进程，但是一般只是短暂的存在，当父进程调用wait()就会回收资源了。

进程通信

进程根据与其他进程之间的关系分成独立和协作的。

  • 独立进程：不与其他进程共享数据的进程。
  • 协作进程：可以被其他进程影响或者影响其他进程的进程。

协作进程之间的通信分为 共享内存和消息传递。

image-20240627192901128

  • 共享内存

    希望通信的进程之间共享的内存区域，通信双方需要同时映射共享内存到自己的进程内。

    通信是由用户自己控制的，不是由操作系统控制。

    • 生产者-消费者问题

      生产者和消费者进程共享一个buffer(循环数组)和两个逻辑指针in(指向buffer的下一个空位)和out(指向buffer的第一个满位)。

      • 生产者进程代码：image-20240627193530453
      • 消费者进程代码：image-20240627193556549

    • Posix系统中常用的共享内存的函数：

      • shm_open：创建一个共享的内存区域对象。
      • ftruncate：给这个对象分配内存。
      • mmap：在自己的代码内对这个共享内存区域对象进行映射。

  • 消息传递

    基本操作为send(发送消息)和receive(接收消息)。

    • 直接通信

      进程之间必须明确命名：

      • 发送（P，消息）–向进程P发送消息
      • 接收（Q，消息）–从流程Q接收消息

    • 间接通信

      通过邮箱或者端口来发送和to接收消息

      • 每个邮箱都有一个唯一的id

      • 发送（A，消息）–将消息发送到邮箱A

      • 接收（A，消息）–从邮箱A接收消息

  • 同步

    消息传递可以是阻塞或者是非阻塞的。

    • 阻塞发送：在接收进程或者邮箱收到消息之前，发送进程阻塞。

    • 阻塞接收：在消息可用之前，接收进程将被阻塞。

    • 交会：若发送和接收两个操作都是阻塞的，则双方进程会产生一个交会。

    • 非阻塞操作是异步的。

  • 管道

    把一个进程连接到另一个进程的一个数据流称为一个“管道”，通常是用作把一个进程的输出通过管道连接到另一个进程的输入。

    管道内的接收和发送信息操作都是阻塞的。

    • 普通管道

      无法从创建它的进程外部访问。通常是父进程用普通管道和子进程进行沟通。只能用于血缘关系的进程。

      普通管道数据的流向是单向的。要么父进程写，子进程读；要么父进程读，子进程写。

      使用pipe()函数创建管道。

      **注意：父、子进程哪个功能不用就关闭。**例如：父进程关闭fd[0]（读端）,子进程关闭fd[1]（写端）

      image-20240627201459408

    • 命名管道

      命名管道比普通管道功能更强大。

      通信是双向的。

      通信进程之间不需要父子关系。

      使用**mkfifo()**创建一个文件来交换数据。

  • 套接字

    每个套接字都由IP地址和端口号组成。

    套接字161.25.19.8:1625：IP：161.25.19.8，端口：1625。

题目

  1. 共享内存和消息传递的区别

    效率：共享内存更好

    安全：消息传递更好

    传输数据大小：共享内存更大

    实现难度：共享内存更难实现

  2. 互相举命名管道和普通管道更好的例子

    普通管道更好：父子进程间通信的时候，可以不用调用mkfifo去创建文件。

    命名管道更好：当两个无关系的进程需要通信时，很明显命名管道更好。

  3. shell中的’|'是普通管道还是命名管道

    普通管道

  4. fork()之后，父进程和子进程有什么是共享的，什么是不共享的。

    答：共享的有代码段和已经打开的文件；不共享的有内存空间(写时复制)。

第四章 多线程编程

什么是线程？

线程是CPU调度和上下文切换的基本单位。

进程 = 共享内存 + 多个线程。

进程是相互独立的，而线程是不独立的(共享数据)。

线程和线程间关系

  • 独立：CPU寄存器、栈、PC、TID。
  • 共享：进程的数据段、堆、文本段、文件。

线程对比进程更加经济。

多线程：操作系统在单个进程内支持多个线程并发执行的能力。

image-20240627204511454

简单来说，就是把一个应用程序(进程)的任务拆分了多个小任务，变成一个线程执行一个小任务。

并行和并发

  • 并发：在单核上多个线程交互的执行。制造并行的假像。image-20240627205151645

  • 并行：在多核上同时执行多个线程。image-20240627205226462

  • 区别：可以看出，单核是不能并行的。并行一定是并发的，但并发不一定是并行的。

  • Amdahl定律：并行下计算效率提升多少。

    speedup=1S+1−SNspeedup = \frac{1}{S + \frac{1 - S}{N}}

    S是串行执行的部分，1 - S是并行执行的部分，N为核数。

  • 数据并行：将相同的数据的子集分布在多个核上，并在核上执行相同操作。(每个核数据不一样，任务一样)

    例子：考虑对内存大小为N的数组进行求和

    假设对于双核系统，在核A上计算下标为0到N/2的和，在核B上计算下标为N/2 + 1到N的和。image-20240627210817105

  • 任务并行：将任务而不是数据分配到多个计算核心，每个线程执行唯一的操作，不同线程可以操作相同的数据，也可以操作不同的数据。(每个核数据一样，任务变了)image-20240627210839397

线程控制块(TCB)

由TID、线程状态、PC、CPU寄存器、指向父进程的指针组成。

image-20240627211127882

多线程模型

线程分成用户级线程和内核级线程。

  • 用户级线程

    所有的线程管理工作都由应用程序负责 (包括进程切换)。

  • 内核级线程

    线程管理工作由内核负责。

  • 用户级线程通过调用内核级线程使用硬件资源。

  • 多对一模型

    • 多个用户级线程（ULTs）映射到一个内核级线程（KLT）。

    • 在该模型中，线程的切换可以在用户态下完成，无需操作系统的干预。

    • 操作系统感受不到用户级线程的存在。

    • 如果用户级线程被阻塞，那么整个进程都会被阻塞。这是因为从操作系统来看，只有内核一个进程，所以如果这个线程被阻塞，内核会把整个进程都阻塞。

    • 无法利用多核处理器的并行性，因为从操作系统来看只有一个线程。

      image-20240627214628856

  • 一对一模型

    • 每个用户级线程（ULT）映射到一个独立的内核级线程（KLT）。

    • 线程创建、管理和调度都由内核负责。

    • 一个线程阻塞不会影响其他线程，真正并行执行。

    • 线程创建和切换开销较大，因为涉及内核操作。

      image-20240627214741776

  • 多对多模型(结合上面两个的优点)

    • 多个用户级线程（ULTs）映射到多个内核级线程（KLTs）。
    • 线程调度可以在用户空间和内核空间之间共享，提供更高的灵活性和效率。
    • 用户级线程的创建和管理灵活，同时可以利用多处理器并行能力。
    • 一个用户级线程阻塞时，其他线程可以继续执行。

线程库

两种实现：

  1. 在用户空间提供一个没有system call的库。（这意味着创造线程只是调用一个函数）
  2. 实现操作系统支持的内核级的库。

Pthreads库

image-20240627215446976

fork()全局变量不共享，pthread_create()全局变量共享。

就是线程内改了主线程的变量，主线程也会一起改动，因为数据是共享的。

通常在主线程调用pthread_join()类似父进程调用wait()。

多线程问题

  • 线程调用fork()函数：有两种情况，第一种复制所有线程；第二种只复制调用fork()的线程。

  • 线程调用exec()函数：除了调用exec()的线程之外，其他所有线程都将立即消失。并且直接执行exec()函数。

  • 信号处理：

    • 信号用于通知进程某个特定事件已经发生。
    • 信号传送给进程
      • 使用kill(pid, signal)来传递信号
    • 在多线程的进程内，信号传递有三个选项：传给所有线程、传给某些线程、传给某个线程。
      • 线程传递信号使用pthread_kill(tid, signal)信号

  • 线程撤销：在线程结束之前终止它。调用pthread_cancel(tid)这个函数终止线程。

隐式多线程

随着线程数量的增加，程序的正确性变得越来越困难。

所以希望线程的创建和管理不是由程序员自己控制，而是交由编译器自动处理。

以下是几个方法：

  • 线程池：

    主要思想：在进程开始的时候创建一定数量的线程，并加到池里等待工作。

    使用现有线程处理请求通常比创建新线程快一点；允许将应用程序中的线程数限制到池的大小。

题目

  1. 什么时候多线程编程性能比单线程低

    答：当要处理的数据比较小时，多线程编程会因为频繁的上下文切换而导致性能比单线程差。

  2. 在什么情况下，采用多核多线程方法比单处理器系统的单线程提供更好的性能？

    答：当任务可以被分成多个子任务时，很明显多线程性能更好；当碰到IO密集型的任务，单线程只能进行阻塞，可是多线程可以一个线程阻塞跑去执行另一个线程先。

    多线程就一定比单线程快吗？_多线程一定比-CSDN博客

  3. 有可能并发但却无并行吗？

    答：可能，例如时间片轮转算法，就是单核中不停切换，在单核中实现多任务并发，可是却没有并行。

  4. 什么是多道程序设计系统？

    答：一次性把一批计算问题同时装入主存并行执行的系统，就叫做多道程序设计系统。

  5. 多道程序设计提高了系统的吞吐量．但可能会延长某些程序的执行时间。

第五章 进程调度

什么是进程调度？

从进程的角度观看：进程总是在CPU执行和IO请求中来回切换。

进程调度：通过多道程序设计获得最大CPU利用率。

简单来说，就是如果有个进程申请IO(等待)时，操作系统就调度一个进程接管CPU，使得CPU一直都是有活干的。

CPU调度程序

分成长程调度、中程调度、短程调度。

调度的频率：长程 < 中程 < 短程。

主要介绍短程调度程序(分派程序)：

  • 短程调度是指从就绪队列中选择一个或多个进程，将处理器分配给它们，以便立即执行。
  • 分派程序包括：切换上下文、切换到用户模式(模式切换)、跳转到用户程序合适的位置，以便重启程序。
  • 这个程序要尽可能的快，因为每次切换进程都要使用；分派程序停止一个进程而启动另一个可用线程的时间叫分派延迟(调度延迟)。

抢占调度

需要进行CPU调度的四种情况：

  1. 运行态–阻塞态(发生IO请求)
  2. 运行态–就绪态(时间片轮转)
  3. 阻塞态–就绪态(IO完成)
  4. 进程终止

如果调度只发生在第一和第四种情况的话，该CPU调度就是不可抢占式的；否则，称为可抢占式的。

在非抢占式调度下，一旦CPU分配给进程，进程将保持CPU， 直到终止或切换到等待状态释放CPU为止；

调度准则

  • CPU利用率：要让CPU尽可能的忙碌起来。
  • 吞吐量：在一个时间单元内，进程完成的数量。
  • 周转时间：从进程提交到完成的时间。
  • 等待时间：进程在就绪队列中等待被调度的时间之和。
  • 响应时间：对于交互系统，周转时间并不是最优准则；响应时间是系统提交请求到产生第一次响应的时间。

调度算法

要会画甘特图

先到先服务(FCFS)

  • 非抢占的

  • 使用FIFO队列实现

  • 例子：turnaround time是周转时间，例如像P3是时刻2来到的，可是时刻30才完成，所以周转时间为28。

image-20240628112653761
  • 例子：可以发现，不同的到达顺序结果会有很大的差异。
image-20240628112946884

最短作业优先(SJF)

  • 可以是抢占的或者非抢占的
  • 最优的算法
  • 例子：非抢占的image-20240628113756942
  • 例子：抢占的 注意！等待时间是进程在就绪对列等待的时间(看P1等待时间)image-20240628115320441
  • 观察到可抢占式的平均等待时间和平均周转时间都比非抢占式低，可是抢占式需要频繁上下文切换，会有不同的开销。

轮转调度(RR)

  • 为分时系统所设计的
  • RR = FCFS + 抢占式
  • 每个进程给定一个较小的时间单位成为时间片，时间片用完后， CPU选择另外一个进程调度执行
  • 如果进程的执行时间少于时间片，进程执行完直接释放CPU。
  • 假设有n个进程，时间片长度为q，则每个进程等待获得下个CPU时间片的时间不会超过(n-1)*q时间。
  • 假设有5个进程，时间片长度为20ms，则每个进程每100ms就会获得不超过20ms的CPU使用时间。
  • 例子： image-20240628121446945
  • RR和SJF对比，虽然RR表现不好，可是它可以实现并发，就是让每个作业都感觉自己被分配了CPU。image-20240628121548619

优先级调度

  • 分成抢占式和非抢占式的。
  • CPU优先分配资源给具有最高优先级的进程。
  • SJF是一个特殊的优先级调度。
  • 问题：可能会饥饿，就是某个进程优先级太低导致一直分配不到资源。
  • 例子： image-20240628163911802

多级队列调度

  • 是优先级调度(队列间)与RR(队列内)结合。

  • 通常**前台进程(与用户交互的进程)**会比后台进程优先级更高。

    image-20240628164530777

多级反馈队列

image-20240628164720837

线程调度

  • 在支持线程的操作系统中，内核线程才是操作系统所调度的。
  • 用户线程是由线程库管理的，内核并不知道。
  • 用户线程 – 内核线程 – 硬件资源

用户线程调度

采用进程竞争范围(PCS)：因为通常用户线程的竞争都是发生在同个进程内的。

内核线程调度

采用系统竞争范围(SCS)：与所有的线程(整个系统)竞争。

  • API允许创建线程的时候选择哪种竞争范围：
  • PTHREAD_SCOPE_PROCESS：使用PCS调度来调度线程；
  • PTHREAD_SCOPE_SYSTEM：使用SCS调度来调度线程；

多处理器调度

  • 刚刚的讨论都是基于一个处理器的。

  • 非对称多处理

    • 让其中一个处理器处理所有的调度决定、IO处理。
    • 这样这个处理器会压力很大。

  • 对称多处理(SMP)

    • 每个处理器自我调度
    • 所有进程可能处在一个共同的就绪队列或者每个处理器有自己的就绪队列。

  • 处理器亲和性

    • 尽量让进程一直运行在同一个处理器上。

实时系统调度

调度算法必须满足抢占式和优先级。

因为该系统要求高安全性和立马响应。

目标是最小化中断延迟和调度延迟。

  • 中断延迟：是从CPU收到中断到中断处理程序开始的时间。
  • 调度延迟：调度程序从停止一个进程到开启一个新进程的时间

实时系统分成软和硬。

  • 软实时系统
    • 保证关键进程比非关键进程先跑
    • 不保证在ddl内跑完
  • 硬实时系统
    • 保证一定在ddl内跑完

实时系统的进程一般是具有周期性的。周期为p，截至时间是d。

image-20240628172910826

准入调度：保证进程完成，就承认进程；不能保证进程在ddl前完成，拒绝进程。

单调速率调度

  • 抢占式 + 静态优先级
  • 进程的优先级为周期的倒数；即周期短的进程总是被优先执行。
  • 由上一点可知，该调度是最优的。
  • 例子：image-20240628174047888

最早截至期限优先调度

  • 抢占式 + 动态优先级
  • 进程的优先级为截止期限；即截至期限越近的进程总是被优先执行。
  • 例子： image-20240628174456118

题目

  1. 为什么区分io密集型进程和cpu密集型进程对调度程序是重要的？

    答：可以资源利用率更大化，因为io密集型进程主要都是在执行IO，会执行比较少的计算；cpu密集型也一样。与此同时，io密集型进程(前台)主要都是与用户交互，所以需要优先去处理，才能给用户更好的体验，cpu密集型进程主要是后台进程。

  2. 什么是饥饿？

    在优先级调度算法中，高优先级的进程总是优先执行。如果系统中不断有高优先级的进程到达，那么低优先级的进程可能永远无法获得CPU时间片，从而陷入饥饿状态。

  3. 下面哪种算法会导致饥饿：a. fcfs b.sjf c.rr d.priority schedule

    答：最短作业和优先级会导致饥饿。

  4. 题目：image-20240628185403693

    ![f5eaa1eb0ca210a2da9c9ad41fe1bbe](C:\Users\tam15\Documents\WeChat Files\wxid_canjzsfhjgsb22\FileStorage\Temp\f5eaa1eb0ca210a2da9c9ad41fe1bbe.jpg)

  5. 题目：image-20240628191710831

第六章 同步

什么是同步?

进程同步的主要任务是希望并发的进程们可以有效的共享资源和合作。

什么是竞争条件？

多个进程并发且访问同一个共享数据，并且该共享数据的值与进程访问顺序有关。

甚至连两个线程并发执行count++指令都会出现竞争：image-20240628194029709

临界区问题

每个进程都有一段代码，称为临界区。

临界区是并发进程中与共享资源有关的程序。

重要的是，当一个进程在它的临界区执行时，其他进程不能在他们的临界区执行。

临界区解决方案要包括以下三个要求：

  1. 互斥：如果进程P在临界区内执行，其他进程都不能在其临界区内执行。
  2. 进步(无死锁)：要保证在临界区内的进程P有干活，就是临界区内的进程一定要有进展。这样等待的进程们不会无休止的等待。也可以理解成，如果没有进程在临界区内，需要选择一个进程进入临界区，并且这种选择不能无限推迟。
  3. 有限等待：当一个进程提交了进临界区的请求，在该进程前进入临界区的进程存在上界。

Peterson解决方案(软件解决)

  • 数据结构(共享)

    1. bool flag[2]：一个布尔类型数组，表示线程是否想进入临界区。
    2. int turn：一个整型变量，表示哪个线程可以进入临界区。

  • 简单思想

    就是把自己的flag设置为1，然后把turn设置为对方，让对方先进入临界区。image-20240628200249825

硬件解决方案

主要利用原子性(不可中断的指令)来实现。

以下两个是例子：

  • test_and_set() （函数实现是原子的） image-20240628205829894

  • compare_and_swap()（函数实现是原子的） image-20240628205933905

互斥(自旋)锁

最简单解决临界区问题的工具。

要求一个进程进入临界区前要aquire()获得锁；退出临界区要release()释放锁。image-20240628202411825

aquire()和release()操作必须是原子性的。

  • aquire() image-20240628202236154

  • release() image-20240628202313057

这种实现方法称为自旋锁。

可能会浪费CPU资源，可是自旋时没有上下文切换；如果等待锁的时间比较短，互斥锁还是很有用的。

信号量

广义上的互斥锁。

信号量S定义为整数变量。

信号量分成二进制信号量(0,1)和计数信号量(>=0)。

只能通过**wait()(P)和signal()(V)**两个原子操作访问。

  • wait()定义 image-20240628202939968

  • signal() 定义 image-20240628203012713

可以发现这样的信号量实现也是自旋的。

为了避免自旋，我们可以创建一个跟信号量相关的等待队列，把发生阻塞的进程添加至这个队列(并把状态设置为阻塞)，然后让出CPU资源。

管程

是一种资源管理模块。

管程是一种高级语言的数据结构，跟信号量差不多，但是更好管理和控制。

管程内是共享数据和对这些数据进行操作。

image-20240628211207864

管程提供的功能

  1. 互斥访问：管程确保多个线程对共享变量的访问互斥，即同一时间只有一个线程可以访问共享资源，以避免竞态条件和数据不一致性问题。
  2. 条件等待和通知：管程提供了等待线程满足特定条件的机制，线程可以通过条件变量等待某个条件满足后再继续执行，或者通过条件变量通知其他线程某个条件已经满足。

可以将管程理解为一个房间，这个房间里有一些共享的资源，比如变量、队列等。同时，房间里有一个门，只有一把钥匙。多个线程或进程需要访问房间内的资源时，它们需要先获得这把钥匙，一次只能有一个线程或进程持有钥匙，进入房间并访问资源。其他线程或进程必须等待，直到当前持有钥匙的线程或进程释放钥匙，才能获得钥匙进入房间。

此外，管程还提供了条件变量，类似于房间内的提示牌。线程在进入房间后，如果发现某个条件不满足（比如队列为空），它可以通过条件变量来知道自己需要等待，暂时离开房间，并将钥匙交给下一个等待的线程。当其他线程满足了等待的条件（比如向队列中添加了元素），它可以通过条件变量通知告诉正在等待的线程，使其重新获得钥匙进入房间，并继续执行。

条件变量操作

假设定义了condition x;

  1. wait()

    调用x.wait()后会把调用操作的进程挂起。

  2. signal()

    调用x.signal()会恢复一个挂起进程。

image-20240628212233396

经典同步问题

生产者消费者问题

  • 数据结构(信号量)
    1. mutex 互斥锁
    2. empty 缓冲区中空位数量
    3. full 缓冲区中内容数量
  • 生产者代码 image-20240628213812765
  • 消费者 image-20240628213832802

读者作者问题

一个数据集在多个并发进程之间共享。

  • Readers—仅读取数据集；它们不执行任何更新
  • Writer — 既能读又能写

问题–允许多个读者同时读取

  • 只有一个写者程序可以同时访问共享数据;
  • 写者在访问数据时，不允许读者访问数据；

主要考虑第一读者-作者问题(即读者优先)

  • 数据结构

    1. 信号量 wsem = 1(作者的锁)
    2. 信号量 x = 1(用来更改readcount的锁)
    3. 整型 readcount = 0

  • 作者代码 image-20240628214946284

  • 读者代码image-20240628215046422

    读者先看看有多少个读者进程，然后把读者进程数加加；如果是第一个读者进程，则申请作者的锁，如果作者还在写，第一个读者进程就阻塞；与此同时其他的读者进程(如果有的话)会被阻塞在x这个锁上；如果没有作者在写，则读者拿了作者的锁，作者就写不了了。

哲学家就餐问题

哲学家坐在圆桌旁，中间放着一碗米饭。吃饭需要拿到左右2根筷子才能吃饭，然后在完成后释放。

对于5位哲学家，一碗饭（数据集）；信号量筷子[5]初始化为1；

代码如下：

image-20240628215552486

很明显，上述代码可能会产生死锁，如果五个哲学家同时拿起自己左边的筷子，就会死锁；

  • 解决方案：只有当chop[i]和chop[i+1%N]为正时，才拿起自己左边的筷子(chop[i])。

题目

  1. 信号量和互斥锁的区别

    答：互斥锁是用在多线程互斥上的，主要是避免多个线程同时访问某个共享变量，即我访问了你就不能访问；信号量是用在多线程同步上的，它是多个进程互相告诉其他线程，我干了什么事情，让其他线程再执行某些动作。互斥锁是单个线程获取锁和释放锁，信号量是多个线程wait和signal。

  2. 互斥和同步的区别

    答：同步侧重于协调线程的执行顺序，而互斥侧重于保护共享资源的安全访问。

  3. 进程间的互斥与同步分别表示了各个进程间的 (竞争与协作 )。

  4. 记得是不同的信息image-20240629161445985

第七章 死锁

什么是死锁？

当一组进程中的每个进程都在等待某事件(请求资源)，而仅有该组进程中被阻塞的其他进程可以触发某事件，就称为死锁。 image-20240629133258736

死锁的必要条件

死锁有四个必要条件：

  1. 互斥：一次只有一个进程使用一个资源, 其他进程不能访问分配给其他进程 的资源；
  2. 非抢占：不能强行抢占进程已占有的资源；
  3. 占有并等待：当一个进程等待其他进程时，继续占有已分配的资源；
  4. 循环等待：存在一个闭合的进程链， 每个进程至少占有此链中下一个进程所需的一个资源；

资源分配图

  • P为进程，R为资源，R的小点数量为该种资源R的数量。
  • 如果是P指向R，代表进程P申请资源R。
  • 如果是R指向P，代表进程P获得资源R。 image-20240629135150815

如果无环则必定不会存在死锁。

如果有环则可能发生死锁。

如果有环且每个资源只有一个实例，必定发生死锁。image-20240629135517156

死锁处理方法

鸵鸟算法：完全忽略死锁这个问题，并假设系统永远不会出现死锁。

  • 死锁避免：银行家算法，在分配资源前得到当前使用资源的额外信息，再判断是否分配资源。
  • 死锁预防：打破死锁四个必要条件的一个。
  • 死锁检测：利用检测算法检测是否存在死锁。

死锁预防

互斥、占有并等待、非抢占都比较难打破。

  • 打破互斥

    共享数据不互斥就不会有死锁了

  • 打破占有并等待

    要求请求其他资源时，一定不能获得资源。

  • 打破非抢占

    假设进程A申请资源a需要等待，则进程A的资源可以被其他进程抢占。

  • 打破循环等待

    把所有的资源类型进行一个递增的排序，并且要求进程申请资源的时候以递增顺序。

  • 缺点

    系统性能差，因为每次获取资源都要顺序。

死锁避免

需要知道每个进程的每种类型资源的最大声明数量。

  • 安全状态

    是指系统能够按某种进程序列为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的执行完成。

    进程序列被称为安全序列。

  • 非安全状态

    不存在安全序列就称为非安全状态。

安全状态一定没死锁；非安全状态可能有死锁。image-20240629142003333

银行家算法(我说必考)
  • 每个进程都必须先验地给出最大需求资源的数量；
  • 当进程请求资源时，如果不能进入安全状态，它必须等待；
  • 当一个进程获得所有资源时，它必须在有限的时间内返回它们；

假设有n个进程和m种资源

存在MAX矩阵、已分配allocate矩阵、还需要Need矩阵、available向量。

时间复杂度为O(n^2 * m)

算法流程：

  1. 合理性检查：检查请求是否小于available向量。
  2. 试探性分配：假设分配资源后，看看是否处于安全状态；如果是安全状态，则分配；如果是不安全状态，回到一开始的值。
  • 死锁避免缺点：必须要提前声明每种类型资源的最大申请数。

死锁检测

死锁检测算法，和银行家差不多。

  • 死锁恢复

    当检测到死锁时，如何恢复。

    1. 终止所有死锁进程：代价很大
    2. 一次终止一个进程，直到解决死锁问题。
    3. 不断抢占一些进程的资源以便给其他进程使用，直到打破死循环。

题目

  1. 饥饿和死锁的区别？

    答：饥饿是一直分配不到资源，例如在优先级调度中，低优先级一直被高优先级的进程抢占；死锁是一组进程在相互等待组内其他进程的资源。死锁一定是饥饿，饥饿不一定是死锁。

  2. 可抢占的资源分配策略可以避免死锁(死锁预防)，但是只适用于主存和处理器。

  3. 什么是相关临界区？在进程并发中与涉及相同共享资源的程序段。

第八章 内存管理

CPU可以直接访问的通用存储是内存和CPU内的寄存器。

程序必须从(磁盘)放入内存，CPU才能运行。

基地址和限制地址

每个进程都需要一个单独的内存空间。

为每个进程提供一个基地址寄存器和限制寄存器。 image-20240629193815616

CPU寻址访问流程：image-20240629194016757

地址绑定

通常，程序被放在磁盘上。如果执行程序，则需要把程序调入内存。

调入内存时，需要把程序"绑定"在某个内存地址。

绑定地址可以在编译时、加载时、执行时进行。

  • 编译时绑定

    如果在编译程序的时候，就已经知道进程在内存的地址，那么编译器可以生成绝对代码。如果内存地址更改，则需要重新编译代码。

  • 加载时绑定

    如果在编译程序的时候，不确定进程的地址，编译器生成可重定位代码，绑定拖到加载时。如果地址发生更改，程序要重新加载。

  • 执行时绑定

    如果程序在执行的时候要从内存中移动，那么绑定要等到执行的时候才进行。(需要硬件支持)

逻辑地址空间和物理地址空间

CPU生成的地址为虚拟地址。

硬件看到的地址为物理地址。image-20240629200043490

内存管理单元(MMU)

CPU输入逻辑地址到MMU转换出物理地址。

考虑下面一个简单的例子，设一个重定位寄存器(值为14000)，输入一个逻辑地址346，转换出物理地址为14346。 image-20240629200529930

站在用户角度，内存空间为(0 ~ Max)(逻辑地址)，实际上时(R ~ R + Max)(物理地址)。

动态加载

假设如果要整个程序和数据都在内存内才能执行，内存空间利用率不高。

动态加载就是以可重定位代码保存在磁盘内。

只有一个程序被需要的时候，才会被加载。

例如一个2000行的代码，里面某几行调用了一个函数，那么一开始这个函数可以不在主存内，直到调用这个函数再把该函数的代码调入主存。而不是一开始把2000行代码全都调入主存，浪费内存空间。

交换

进程必须要在内存执行，不过可以把暂时不用的进程"交换"到备份存储(磁盘)中，这样实现可能让所有进程的物理空间大于真实的物理空间。image-20240629201419571

连续内存分配

整个进程的内存是连续的。

固定分区

先把内存空间划分成多个"区"，然后每个区一个进程。划分的"区"可以是一样大的或者不等大的。

一般采用顺序分配。

会有内部碎片。

缺点：因为区数是一开始就决定好的，不够灵活。 image-20240629202832967

可变分区(蔡国扬实验)

使用一个表记录可用内存和已用内存。

会有外部碎片。

  • 首次适应：分配首个满足的空间给进程。
  • 最优适应：分配最小的满足的空间给进程。
  • 最差适应：分配最大的空间给进程。

image-20240629203244118

碎片

  • 内部碎片

    存在于进程内存内部。

  • 外部碎片

    存在于进程内存之间。

解决方式：把所有的空闲的空间通过移动结合成一大块可用内存空间。

分段(不连续内存分配)

没有内部碎片，有外部碎片。

把程序分成多个段，例如代码、全局变量、堆、栈等等。

每个段的大小不一，并且不需要连续存储。

逻辑地址由段号和偏移组成。(需要检查偏移是否小于limit值)image-20240629204555029

分页(不连续内存分配)

没有外部碎片，有内部碎片。

进程的物理地址空间可以是不连续的；

把物理空间分成大小相同的帧；逻辑空间分成大小相同的页。页和帧大小是一样的。

如果执行一个进程需要n个页，在物理内存空间需要对应有n个帧。

CPU生成的逻辑地址由页码和页偏移组成 。 image-20240629205556712image-20240629212226640

物理地址转换：image-20240629205808679

  • 页表：保存在内存中，并且使用一个页表基址寄存器指向页表地址。

  • 在这种情况下，访问数据需要两次访存。(第一次是查页表拿数据地址，第二次是取数据)

TLB

采用了缓存的思想。

TLB每一项由页码和帧码组成。页表只由帧码组成(把页码当下标)。

当CPU产生一个逻辑地址后，如果该逻辑地址的页码存在于TLB，则直接找到对应的帧码，然后执行。(访存一次)

若页码不在TLB中(TLB miss)，则按照上面，需要访存两次；并且把这次逻辑地址的页码加入TLB。(时间局部性)image-20240629211338718

  • 有效内存访问时间：

    \begin{equation} \text{Time} = P \times T_m + (1 - P) \times 2 T_m \end{equation}

    Tm是访存时间，P为TLB命中率。

内存保护

在页表条目中增加一个"有效位"。 image-20240629211926499

页表结构

假设虚拟内存空间位32位，页大小为12位，那么就有2^20个页，假设每个页表条目为4Byte，那么页表需要4MB存储。我们不想在主存中为每个进程都连续分配4MB存储页表。

分层分页

假设为k层页表，访问一个数据需要访存k + 1次。

像刚刚的假设，我们可以将刚刚的页表拆分成两个页表。image-20240629213327704

image-20240629213408488

假设32位虚拟地址为0x12345678，分层分页的具体过程如下：

  1. 虚拟地址分解：
    • 页目录索引：0x12
    • 页表索引：0x34
    • 页内偏移量：0x5678
  2. 查找顶级页表：
    • 使用0x12从页目录中找到二级页表的基址。
  3. 查找二级页表：
    • 使用0x34从二级页表中找到物理页框的基址。
  4. 形成物理地址：
    • 将物理页框基址与偏移量0x5678结合，得到最终物理地址。

哈希页表

每个哈希页表条目都是一个链表(解决碰撞)

每个哈希页表元素为虚拟页码、物理帧号、指向链表下个元素的指针。

以虚拟页号作为哈希函数的输入，然后映射，再在映射的链表上面一一对照页码来找寻对应的帧号。

image-20240629214009967

倒置页表

刚刚描述的页表都是每个进程一个，现在是一个系统只有一个页表。

虚拟地址为PID、虚拟页号、偏移组成。

页表条目由PID和虚拟页号组成。

image-20240629214142856

题目

  1. 请指出内部碎片和外部碎片的区别

    答：首先内部碎片是在进程本身内部的很难被使用(很小)的内存空间，外部碎片是进程间的很难被使用(很小的)内存空间。

  2. 题目

​ ![50d5b59f1488b30588acc3ce987569b](C:\Users\tam15\Documents\WeChat Files\wxid_canjzsfhjgsb22\FileStorage\Temp\50d5b59f1488b30588acc3ce987569b.jpg)

  1. 题目image-20240629221817976

    ![ef536a6fefef00768e0ecf4b3782588](C:\Users\tam15\Documents\WeChat Files\wxid_canjzsfhjgsb22\FileStorage\Temp\ef536a6fefef00768e0ecf4b3782588.jpg)

  2. 页表分页的目的是什么？

    节省内存中存储页表的空间。

  3. 题目image-20240629223233453

  4. 固定分区分配适合多道程序，但是有内部碎片。

  5. 固定分区分配地址转换公式：下限寄存器 <= 绝对地址(下限寄存器加逻辑) <= 上限寄存器

  6. 可变分区地址转换公式：基址寄存器 <= 绝对地址(逻辑加基址寄存器) <= 基址加限长寄存器

  7. 可变分区地址越界：逻辑地址 > 限长寄存器。

  8. 页式分配转换地址公式：绝对地址 = 帧号 * 帧长度 + 页内偏移

  9. 题目image-20240630143024076

  10. 固定分区是采用静态重定位，可变分区是采用动态重定位。

  11. 某个作业在执行过程中正在等待________，则该作业不能移动。IO

  12. 页式存储管理提供___________逻辑地址，而段式存储管理中段间的逻辑地址是________。 连续的，不连续的

  13. 题目image-20240630142533176

  14. 题目image-20240629223730381

第九章 虚拟内存管理

因为进程执行时应该处于物理内存，策略都倾向要求每个进程在执行前应完全处于内存。

但是很少用到整个程序，所以是很浪费的。

虚拟内存

虚拟内存：将用户逻辑内存与物理内存分离。

逻辑地址空间可以比物理地址空间大得多。

这是因为：可以执行程序的时候不把整个程序都装入物理内存，而是使用到的时候才装。所以给进程感觉自己拥有很大的内存空间。

  • 进程看自己的存储视角：通常从地址0开始，连续地址直到空间结束。
  • 同时，物理内存按照页帧组织，分配给进程的物理帧可以不连续;

虚拟地址和物理地址转换靠MMU。

image-20240629230520984

请求(按需)调页策略

请求(按需)调页：只有在需要这个程序的时候才加载页面。是一种策略

类似带交换的分页系统。

使用调页程序来把进程要使用的页调入内存。

image-20240629231422880

如果进程试图访问尚未调入内存的页(即页表有效位为无效)，则会发生缺页中断。

缺页中断处理流程

  1. 先确认是否内存引用是否有效
  2. 然后查看页表的有效位，确认该页表在磁盘而不在内存，并发出缺页中断。
  3. 在物理内存中找个空闲帧(例如使用空闲帧链表)
  4. 从磁盘复制该页到空闲帧
  5. 更新页表和TLB
  6. 重新跑一次被中断的指令

image-20240629232301318

请求(按需)调页有效访问时间：T = (1 - P) * Tm + P * 缺页错误时间

通常缺页错误时间要远远大于访存时间，所以缺页率P越低越好。

写时复制

回想一下，如果进程使用fork()函数，那么子进程要完完全全复制父进程在内存中的页吗？

其实是不需要的，只有发生改动的时候才创建一个副本。

image-20240630012025257 image-20240630012046460

Belady异常

一般来说，帧数越多，缺页率会越低。Belady异常的意思是，随着帧数的增加，缺页率可能会增加。

页面置换算法

FIFO页面置换

有Belady问题。

image-20240630005424400

最优页面置换OPT

  • 置换最长时间不会使用的页面。

效果最好，缺页率最低，可是最难实现。因为要知道未来信息。

没有Belady问题。

image-20240630005626076

最久未使用页面置换LRU

  • 置换最长时间没有使用的页

效果不错，用的是过去的数据。image-20240630005809225

没有Belady问题。

可以用计数器和堆栈实现。

帧分配

所分配的帧必须小于可用帧的数量。

如果进程的帧减少，那么缺页率会增加，进程效率变低。

分配算法

  • 平均分配

    n个进程，m个帧，每个进程分到m/n个帧。

  • 比例分配

    有点像轮盘赌，拥有更多页的进程分配的帧更多。

全局分配和局部分配

  • 全局分配：进程在选替换帧的时候，可以从整个系统的帧集中选择。
  • 局部分配：进程在选替换帧的时候，只可以从自己分配的帧集选择。

系统抖动

因为进程被分配到的帧不够多，导致一直在缺页，一直在页面置换，最终页面置换的时间大于执行时间称为系统抖动。CPU利用率很低。

系统抖动的原因

操作系统实时监控CPU利用率，如果太低，就增加多道程度；可是如果多道程度太大，就会导致新进程从其他进程抢帧来执行，导致其他进程也会缺页。导致CPU利用率更低。

0b50b9577872eb869ee25805ac9da3b

工作集

利用时间局部性原理来评断。这个Δ要选的好一点，如果太大就会整个进程的页，太小就体现不出局部性。image-20240701003309983

假设D为i时刻所有进程的工作集总和，如果D > M(可用帧数)的话，将会发生抖动。因为会有进程分不到帧，一直缺页中断。

分配内核内存

伙伴系统

就是一直两个两个分下去，直到分到适合的大小。

例如：一个21kb的请求image-20240630012643697

image-20240701001241796

题目

  1. 题目 image-20240630014055226

    9EF -> 0EF

    111 -> 2EF

    700 -> D00

    0FF -> EFF

  2. 题目image-20240630015325112

  3. 题目 image-20240630021131799

​ (a) 已经在抖动了。

​ (b) 提高多道程度

​ © 提高多道程度

  1. 存储管理的目的是方便用户和增加主存利用率。

  2. 一个被置换出的页面一定要写回外存吗？

    答：不一定，如果没有被更改就不写了。看修改位。

  3. 使用虚拟内存的原因：逻辑上扩展可使用的主存。

第十二章 大容量存储结构

主要讲述的是二级存储。image-20240630024058951

磁盘结构

image-20240630024307267

每个盘片有两个盘面，每个盘面有多个圆形磁道，每个磁道又分成多个扇区。

下图计算磁盘的大小。image-20240630025317616

读取数据：先找到对应的磁道，再透过旋转到对应扇区读取。

随机读取耗时很久，因为需要旋转。

TIO=T寻道时间+T旋转延迟+T传输速率T定位时间=T寻道时间+T旋转延迟T_{IO} = T_{寻道时间} + T_{旋转延迟} + T_{传输速率} \\ T_{定位时间} = T_{寻道时间} + T_{旋转延迟}

磁盘调度

目标：最小化磁头移动的距离 。因为磁头距离主要被寻道时间影响，也可以看成最小化寻道时间。

FCFS

image-20240630030145530

最短寻道时间优先SSTF

可能会导致饥饿。

每次选择距离最近的那个柱面。image-20240630030344405

SCAN调度(电梯)

磁臂从磁盘的一端开始，向另一端移动；在移动到每个柱面时处理请求。当到达磁盘的另一端时，磁头移动方向反转。image-20240630030702033

C-SCAN调度

当到达磁盘的另一端时，磁臂移动到另一端并且磁头移动方向不反转。image-20240630031013878

LOOK调度

跟SCAN算法类似，但是不用走到磁盘的一端，只需要走到一个方向的最远请求磁盘移动方向改变。image-20240630031151535

C-LOOK调度

一样，磁头方向不改变。image-20240630031252299

题目

  1. 要确定磁盘上一个块所在的位置必须给出三个参数：______ 、和 。柱面号，磁头号，扇区号
  2. 磁盘输入输出时，______是磁头在移动臂带动下移动到指定柱面所花的时间；______是 指定扇区旋转到磁头下所需的时间。它们与信息在______有关。寻找时间（寻道时间）， 延迟时间，磁盘上的位置
  3. 为了减少磁盘移动臂移动所花费的时间，每个文件的信息不是按盘面上的______顺序 存放满一个盘面后，再放到另一个盘面上，而是按______存放。磁道，柱面
  4. 存储型设备用块作传输，IO设备用字符。
  5. 题目 image-20240630221210666

第十三章 IO系统

计算机的两个主要工作是计算和IO。很多时候，主要工作是IO，而不是计算，例如查看网站时。

IO硬件

有关IO基本硬件有设备、设备控制器、总线。

控制设备的内核模块称为设备驱动程序(Device Driver)。image-20240630145752151

IO端口

由四个寄存器组成，分别是输入寄存器、输出寄存器、状态寄存器、命令寄存器。

控制器与主机交互

  • 轮询

    1. 从状态寄存器读取忙位，直到该位清零；
    2. 主机设置读或写位，如果写入，则将数据复制到数据输出寄存器中；
    3. 主机设置命令就绪位；
    4. 控制器设置忙位；
    5. 控制器读取命令寄存器，并看到命令。从数据输出寄存器中 读取一个字节，并向设备执行I/O操作；
    6. 传输完成时，控制器清除忙位、错误位、命令准备位；

    有点像自旋锁，很浪费时间。 image-20240701010029911

  • 中断

    当设备准备好服务的时候，再通知CPU，让设备通知CPU准备好的机制为中断。

    当CPU收到用户的IO请求，就告诉IO处理器，让他准备好，然后CPU执行其他进程。

    在执行其他进程时，每执行一条指令就查看是否有中断信号。

    如果有中断信号，根据中断向量表找到对应的中断处理程序。

    处理完后再执行进程。

    image-20240630150737522

​ image-20240630151150386

设备和内存的数据传输

可以用程序控制IO来传输，或者用DMA控制器来传输。

DMA控制器

DMA可以数据传输绕过CPU(从而减轻CPU的负担)，直接让I/O设备与内存进行数据传输。

简单来说，就是专门有一个处理器DMA来帮助CPU控制传输数据。

当DMA占用内存总线时，CPU被暂时阻止访问内存。可是CPU可以执行其他工作并且可以访问cache。

image-20240630152020136

阻塞与非阻塞IO

**阻塞型IO：**当应用程序执行阻塞型时，自己会被调回等待队列，直到该系统调用完成再回到执行。

**非阻塞型IO：**一个例子是用户接口，用来接收键盘输入并同时显示在荧幕上。

image-20240630153430966

Spooling

就是把外设输出的buffer储存起来，例如一台打印机，我们希望多个进程同时使用，可是我们不希望打印的结果是一张进程A，一张进程B的，所以要把进程A的输出buffer储存起来，先打印完进程A，再打印进程B。

buffer和高速缓存

  • 高速缓存

    在内存中开个区域，来放置磁盘平时传输的数据，下次IO传输时，就可以先看看高速缓存内有没有这个数据。

    逻辑上是磁盘的，实际上是内存。

  • buffer

    就是高速设备和低速设备数据如果要传输数据的时候，就把数据放到一个buffer，让另一方去读。

  • 区别

    image-20240701140226307

题目

  1. 试述外围设备与主存储器之间的DMA数据传送控制方式。

    答：当IO设备准备好，通知DMA控制器，DMA控制器占用内存总线，并且开始数据传输。这段期间，CPU是可以进行计算的，当DMA传输完成后，向CPU发出一个中断信号。

  2. 设备的独立性是指用户程序使用的设备与实际使用哪台设备无关的一种特性。

  3. 中断机制传输和DMA传输区别

    答：中断机制传输传输完一次数据之后就要中断，而DMA处理器可以传输一大批数据。中断机制传输说到底还是CPU完成的，DMA传输不是。

  4. 阻塞型IO和非阻塞型IO区别

    **阻塞IO：**在阻塞IO中，一个进程发起一个IO操作后，如果数据还没有准备好，进程就会被挂起（阻塞），直到数据准备好为止。这就像是你在电话中等待对方的回答，你无法做其他的事情。

    **非阻塞IO：**在非阻塞IO中，一个进程发起一个IO操作后，如果数据还没有准备好，进程不会被挂起，而是立即返回，进程可以继续做其他的事情。这就像是你在发短信，你发送完短信后，不需要等待对方的回复，你可以做其他的事情。

第十章 文件系统

什么是文件？

操作系统对存储设备的物理属性加以抽象，从而定义的逻辑存储单位。

是逻辑记录的一个序列。

人话：就是拿来存储的。

再人话：他是二级存储的抽象，我们不需要知道计算机怎么存储的，只需要知道把存储的东西放在文件里面。

文件的属性

  • 文件名称
  • 文件标识符(Inode)
  • 文件类型
  • 文件位置
  • 文件大小

文件操作

  • 创建文件
  • 写文件：系统保留写指针。
  • 读文件：系统保留读指针。
  • 删除文件
  • 重定位文件(lseek)
  • 截断文件：就是把内容清空，但是不删除文件。

目录

用于管理文件系统中的文件和其他目录。

目录的主要作用是提供一种层次结构，使得文件和目录可以有条理地组织起来，方便用户和程序进行文件的查找、访问和管理。

接下来，说下目录的结构：

单级目录

所有文件包含在同一个目录。所以必须要有唯一的名称。

image-20240630162110406

二级目录

每个用户都有自己的用户文件目录。不同用户可以拥有相同命名的文件，只要主文件目录中的文件名是唯一的。

这个结构可以有效的让用户隔离，如果用户之间要合作会比较麻烦。

image-20240630162332765

树形目录

将二级目录进行推广。允许用户创建自己的子目录和文件。

不能共享文件或目录。

image-20240630162720120

无环图目录

要求目录不能有环。

允许用户之间可以共享目录。两个程序员可以更好的合作。

  • 使用软链接和硬链接进行目录共享。
  • 软链接：创建一个新文件(新Inode)，内容是path1.
  • 硬链接：等价于一个Inode有path1和path2。

可是搜索和删除变得更加复杂了。

image-20240630163219387

通用型目录

在共享文件时更加方便。

image-20240630163725766

题目

  1. 题目对顺序文件进行读文件操作时，总是从 ( ) 按顺序读出信息。 A．文件头部向后 B．文件尾部向前 C．文件中部开始 D．当前位置开始 答案是D
  2. 文件管理实际上是对辅助存储空间管理。
  3. 打开文件的步骤
    1. 用户使用open函数
    2. 系统拿着file_name去目录找对应的Inode(FCB)
    3. 找到FCB之后，更新进程的已打开文件表
    4. 为该文件分配一个文件描述符。
    5. 返回fd，之后可以用fd对文件进行操作。
  4. 题目 image-20240630221457916

第十一章 文件系统实现

为了提高IO效率，内存和磁盘之间的IO传输是以块为单位的。

一个块为多个扇区。

什么是文件系统

文件系统提供高效的磁盘访问，实现对文件的按名访问。

文件系统本身由很多层组成。每层设计用更底层的功能来创建更高层的服务。

从外到内：应用程序 – 逻辑文件系统 – 文件组织模块 – 基本文件系统 – IO控制 – 设备

image-20240630190736078

文件系统实现

在磁盘上，文件系统包括如何启动存储在那里的操作系统、总的块数、空闲块的数量和位置。

  • 引导控制块：包含该卷引导操作系统的所需信息。(就是上电之后启动操作系统)
  • 卷控制块：如分区块的大小、空闲块的数量和指针、空闲的FCB数量。
  • 目录结构：其实就是一个链表，<filename, inode>。
  • 每个文件的FCB。
  • 等等

类似进程一样，每个文件都有一个FCB(唯一的标识号)。

  • FCB文件控制块包括：文件权限、文件日期、文件所有者、文件大小、文件数据块。image-20240630193751751

在内存里，文件系统包括安装表、目录缓存、系统的打开文件表、进程的打开文件表。

目录实现

目录的操作有查找、增加、删除。

目录实质上是文件名和Inode的映射。

所以要实现按名存取和让用户更好的共享。

线性列表

就是文件名和数据块指针的线性列表。

你妈的就是拿name去找对应的inum。

image-20240630201451936

哈希表

key为filename去映射。

image-20240630201555893

文件分配空间

为文件在磁盘分配的常用方法为连续、链接、索引。

连续分配

有点类似可变分区算法(可是这是在磁盘)

连续分配要求，每个文件在磁盘上占有一组连续的块。

因为每个文件的块都是紧邻着的，所以寻道时间是最短的。

支持顺序访问和直接访问。

缺点：难以在磁盘中找到对应的空间。image-20240630203014236

链接分配

链接分配解决了连续分配的问题。

链接分配，每个文件是磁盘块的链表。

容易增加文件(只需要找到空闲块并加入链表尾部即可)

缺点：只能顺序访问文件，需要为指针分配额外空间。

image-20240630203427208

链表分配一个重要的变种是文件分配表FAT的使用。

FAT表的使用与链表相同，优点是查询的时候不用再移动磁头来查询下一个磁盘块的位置，直接查表即可。特别是如果把FAT表加在缓存中。

可以很好的改善随机访问的时间。(可以查完表之后就知道哪一块)image-20240630203945904

索引分配

索引分配：每个文件把指针放在一个索引块。

支持直接访问。

缺点：专门用一个索引块来储存指针开销很大，会比链表指针大，特别是一个文件只有两三个磁盘块的时候。image-20240630204324189

因为每个文件都需要一个索引块，索引块应尽可能小。可是如果太小，它不能为大的文件提供足够的指针。

用多级索引来解决这个问题。

image-20240630204752913

  • 要会计算每种块指针能索引多少文件块。文件最大的大小要会算。

  • 直接地址索引的表示的文件大小 = 直接地址索引数 * 数据块大小

  • 一级间接地址索引表示的文件大小 = 一级间接地址索引数 * (索引块大小 / 地址大小) * 数据块大小

  • 二级间接地址索引表示的文件大小 = 二级间接地址索引数 * (索引块大小 / 地址大小)^2 * 数据块大小

  • 就是要先把一个索引块能索引多少个地址算出来，再看情况。

性能

对于任何类型的访问，连续分配都只需要访问一次就能获得磁盘块。

对于链接分配，很明显直接访问效能很差。

索引分配更复杂，效能要看索引结构。

空闲空间管理

位向量

无脑bit map image-20240630205439347

链表

将所有空虚的磁盘块用链表链接起来。image-20240630205527563

组

在第一块空闲磁盘块中存储n个空闲块地址，n-1个磁盘块都是空闲的，第n个磁盘块又有n个空闲地址。

计数

通常，多个连续分配的文件要同时释放。

000001111000

可以表示为(0:5), (9,3)

题目

  1. 题目image-20240630213332844

​ 答：4个直接地址索引为1k，2个一级间接地址索引为 2 * (256 / 4) * 256 = 32k，一个二级间接地址索引为 (256 / 4) * (256 / 4) * 256 = 1024k，答案是1057k。

  1. 题目 image-20240630213801015

​ 512M

  1. 扇区和块的区别

    扇区是磁盘中最小的存储单位。块是操作系统中最小的逻辑存储单位。块是抽象(虚拟)出来的。

  2. 比较三种磁盘分配(连续，链接，索引)的优缺点

    1. 连续分配：支持直接访问和顺序访问，但会产生外部碎片。

    2. 链接分配：只支持顺序访问，不产生外部碎片，但指针需要空间存放，且指针如果丢失，会导致访问文件出错。

    3. 索引分配：支持直接访问，顺序访问，不产生外部碎片，但也要耗费空间

  3. 链接分配中FAT的优点是什么？

    可以提升随机访问的时间，并且可以直接访问中间的块了，不需要再去一块一块访问。

  4. 对输入输出设备，输入输出操作的信息传输单位为 ( )。字符

  5. 对存储型设备，输入输出操作的信息是以 ( ) 为单位传输的。块

  6. 索引结构为每个文件建立一张索引表，用来存放 ( )。 A．逻辑记录的地址 B．部分数据信息 C．主关键字内容 D．逻辑记录存放位置的指针 D是答案。

操作系统复习
https://tobytam23.github.io/2024/12/02/操作系统复习/
Author
tanzhuoheng
Posted on
December 2, 2024
Licensed under