【操作系统】第一章 第二章

发布于 2023-07-24  358 次阅读


第一章 计算机系统概述

1.1 操作系统的基本概念

1.1 操作系统 的基本概念

image-20230719155406857

image-20230719162249561

狭义的用户接口不包括GUI

image-20230719162437513

image-20230719162629540

并发和共享互为存在条件

image-20230719163119575

image-20230719163316529

CLI,全称为命令行接口(Command Line Interface),是用户和计算机系统交互的一种方式。与图形用户接口(Graphical User Interface,GUI)相比,CLI主要通过键入文本命令来与计算机进行交互。

以下是关于CLI的一些更详细的介绍:

  1. 命令解释器:CLI的核心部分是命令解释器,也被称为shell(在Unix或Linux系统中)或命令处理器(在Windows系统中)。命令解释器是一个特殊的程序,它接收用户键入的命令,解析命令,然后调用相应的程序或函数来执行命令。例如,bash和zsh是Unix和Linux系统中的常见命令解释器,cmd.exe和PowerShell是Windows系统中的命令解释器。

  2. 命令:在CLI中,用户通过键入特定格式的文本命令来执行操作。这些命令可以是内置的shell命令,也可以是外部的程序或脚本。例如,在Unix或Linux系统中,ls、cd、cp等是常见的命令,它们分别用于列出文件、改变当前目录和复制文件。

  3. 参数和选项:大多数命令可以接受参数和选项来修改其行为。参数通常是命令需要操作的对象,例如文件名或目录名。选项通常以一个或两个短划线开头,用于开启或关闭命令的某些特性。例如,在Unix或Linux系统中,命令ls -l /home中,-l是一个选项,表示以长格式列出文件,/home是一个参数,表示要列出的目录。

  4. 脚本:CLI还支持编写脚本来自动化任务。脚本是一系列的命令,它们被保存在一个文件中,然后可以作为一个整体来执行。脚本可以接受参数,可以进行条件判断和循环等控制结构,因此它们是非常强大的工具。例如,bash脚本、Python脚本、Perl脚本等都是常见的CLI脚本。

  5. 管道和重定向:CLI支持使用管道(pipe)和重定向(redirection)来控制命令的输入和输出。管道是一种将一个命令的输出作为另一个命令的输入的机制。重定向则是一种将命令的输出发送到文件,或者从文件获取命令的输入的机制。通过管道和重定向,用户可以组合命令来完成复杂的任务。

总的来说,CLI是一个强大而灵活的工具,尤其对于程序员和系统管理员来说,它提供了大量的功能和灵活性来管理和控制计算机系统。虽然CLI可能需要一定的学习曲线,但是一旦掌握,用户就可以通过CLI来提高工作效率。

操作系统中的不确定性和异步性是一个意思吗?

不确定性和异步性虽然有一些相关性,但它们并不是同一个概念。

不确定性:在操作系统中,不确定性主要是指由于并发执行和资源共享等因素导致的系统状态不可预测性。例如,当有多个进程或线程并发执行时,由于它们之间的执行顺序不确定,因此系统的最终状态也就不可预测。同样,当多个进程或线程共享某个资源时,谁能够首先获取到这个资源也是不确定的。这种不确定性是并发系统的一个基本特性,需要通过同步和调度等机制来管理。

异步性

在计算机科学中,"异步"的含义可能因上下文而异。在讨论操作系统的并发性和多任务处理时,"异步"通常指的是进程或任务不是同时启动或同时完成的,而是各自独立的运行和结束。这样,一个任务无需等待另一个任务完成就能继续运行,进程的执行时间和顺序是不确定的。

然而,在讨论I/O,特别是网络编程时,"异步"通常指的是一种程序设计模式,其中I/O操作(或其他可能阻塞执行的长时间操作)在后台运行,允许程序在等待操作完成时继续执行其他任务。这通常通过回调、Promise/Future、异步/等待语法等机制来实现。

这两种异步性都涉及到任务的非同步执行,但侧重点和应用场景不同。在操作系统层面,异步性关注的是进程的独立执行和调度。在I/O和网络编程中,异步性关注的是阻塞操作的后台执行和程序的非阻塞运行。

我希望这个解释能够帮助你理解异步的不同含义和应用,如果你还有其他问题,欢迎继续提问。

1.2 操作系统的发展历程

![1.2 操作系统的发展历程](1.2 操作系统的发展历程.svg)

image-20230719205530113

image-20230719205643883

image-20230719205954975

image-20230719211656018

image-20230719211759817

image-20230719212148000

在实时操作系统中,计算机系统能及时处理由过程控制反馈的数据。这句话是什么意思?

这句话的含义是在实时操作系统(Real-Time Operating System,RTOS)中,系统能够以满足实时约束条件的方式来处理和响应过程控制(process control)的反馈数据。在这里,"实时" 指的是对计算机响应的时间性能有特定的严格要求。

过程控制通常涉及到某些物理过程或系统的自动化操作,比如工厂的生产线、航空交通控制系统、医疗设备等等。这些系统通常会产生反馈数据,如传感器的读数,需要计算机系统进行处理,以决定下一步的行动。比如,一个温度控制系统可能需要根据传感器的读数来决定是否开启加热器或冷却器。

实时操作系统的一个关键特性就是它能保证在特定的时间内完成对这些反馈数据的处理,即使系统正在处理其他任务。例如,对于一个航空交通控制系统,如果接收到一条新的飞行信息,系统必须在一定的时间内对其进行处理,否则可能会导致严重的后果。在这些情况下,即使有其他任务在执行,实时操作系统也会优先处理这些反馈数据。

因此,当说到"实时操作系统中,计算机系统能及时处理由过程控制反馈的数据",意思就是计算机系统能够在满足实时约束条件的前提下,对过程控制产生的反馈数据进行处理,从而保证系统的正确运行。

1.3 操作系统运行方式

1.3.1 处理器的运行模式

1.3 操作系统运行模式

image-20230719215838254

image-20230719220017578

image-20230719224025563

image-20230719224253531

送程序状态字到程序状态寄存器是什么意思

"送程序状态字到程序状态寄存器"这句话描述的是一种在计算机系统中常见的操作,即将程序状态字(Program Status Word,PSW)的内容更新到程序状态寄存器(也被称为程序状态字寄存器)中。

程序状态字是一个包含程序或进程状态信息的数据结构。它通常包括如下信息:

  1. 程序计数器(Program Counter):包含了下一条要执行的指令的地址。
  2. 条件码(Condition Code):保存了最后一次算术或逻辑操作的结果信息,例如是否发生了溢出、结果是否为零等。
  3. 中断使能位(Interrupt Enable):指示是否允许(或禁止)中断。
  4. 用户/系统模式位(User/System Mode):指示当前是在用户模式还是系统模式下执行。
  5. 其他的状态和控制信息。

程序状态寄存器是一个在CPU中的物理寄存器,用于存储程序状态字。当操作系统进行进程切换时,它会保存当前运行进程的状态信息到其程序状态字中,然后将新的进程的程序状态字加载到程序状态寄存器中。这样,新的进程就可以接着运行。

因此,"送程序状态字到程序状态寄存器"就是指将特定进程的程序状态字的内容加载到CPU的程序状态寄存器中,以便CPU能够继续执行该进程的指令。这是操作系统进行进程调度和切换的关键步骤。

置中断指令是什么

"置中断"指令是一种操作系统指令,用于设置或更改系统的中断状态。中断是一种机制,它允许硬件或软件打断CPU的当前任务,使其转而去处理更高优先级的事件。中断是现代操作系统进行任务管理和设备通信的关键机制。

"置中断"指令通常在两种场景中使用:

  1. 启用(Enable)中断:操作系统或应用程序可能需要打开或启用中断,以便能够响应来自硬件设备(如键盘、鼠标、打印机等)或其他软件的中断请求。例如,在一个IO操作完成后,设备可能会发送一个中断,以通知CPU数据已经准备好。如果没有启用中断,这个通知就会被忽略。

  2. 禁用(Disable)中断:在某些情况下,操作系统或应用程序可能需要关闭或禁用中断。例如,在处理一个关键的系统任务或进行某些类型的硬件操作时,可能需要确保不会被其他事件打断。在这种情况下,"置中断"指令可以用于暂时禁用中断。

需要注意的是,"置中断"指令通常是由操作系统负责执行的,因为它涉及到系统级别的硬件控制和任务管理。普通的应用程序通常没有权限直接执行这种类型的指令,除非它们通过操作系统提供的API或系统调用请求操作系统来执行。

用于内存保护的寄存器是什么

用于内存保护的寄存器通常指的是内存管理单元(Memory Management Unit, MMU)中的一些特定寄存器,这些寄存器在操作系统中起着非常重要的角色。下面是两个重要的用于内存保护的寄存器:

  1. 基址寄存器(Base Register):也被称为下界寄存器,用于存储进程在物理内存或虚拟内存中的起始地址。当一个进程试图访问某个内存地址时,操作系统会检查这个地址是否大于或等于基址寄存器的值,如果不是,则表示进程试图访问不属于它的内存,此时操作系统会阻止这个访问操作并产生一个错误。

  2. 界限寄存器(Limit Register):也被称为长度寄存器或上界寄存器,用于存储进程可以访问的内存区域的长度或者上界。当进程试图访问某个内存地址时,操作系统会检查这个地址是否小于基址寄存器的值加上界限寄存器的值,如果不是,则表示进程试图访问超出其分配内存区域的位置,操作系统会阻止这个访问操作并产生一个错误。

基址寄存器和界限寄存器的值通常在进程切换时由操作系统更新。通过这两个寄存器,操作系统能够实现内存保护,防止进程访问不属于它的内存区域,从而保证了系统的安全性和稳定性。

此外,有些现代操作系统(如Linux、Windows)使用更复杂的内存管理技术,例如分页(paging)和分段(segmentation)。在这些系统中,用于内存保护的寄存器可能包括页表寄存器(Page Table Register)和段表寄存器(Segment Table Register)。

访管指令是什么

访管指令(也叫陷入指令或者系统调用指令)是一种特殊的计算机指令,当运行在用户模式的程序需要请求操作系统提供的服务时,如进行I/O操作,文件操作,创建或结束进程等,会使用这个指令。

这个指令的工作原理如下:当执行访管指令时,计算机会从用户模式切换到内核模式,并跳转到预定的内存地址开始执行操作系统的代码。这个地址通常是一个由操作系统提供的处理程序(称为陷入处理程序或系统调用处理程序),用来处理用户程序的请求。

执行访管指令会产生一种特殊的中断(称为软中断或陷入),用来通知操作系统用户程序需要其服务。这与由硬件设备产生的中断(硬中断)有所不同,硬中断通常用来通知操作系统有新的I/O操作完成或者其他的硬件事件发生。

使用访管指令,用户程序可以在保持操作系统的控制和保护机制的同时,利用操作系统提供的各种服务。这是现代操作系统实现用户程序和内核隔离,同时提供丰富服务的关键机制。

1.3.2 中断和异常

1.3.2 中断和异常

image-20230720101955577

image-20230720094227044

时钟信号是外中断

image-20230720101114415

image-20230720101458669

中断处理程序是内核程序,运行在内核态

image-20230720101640092

1.3.3 系统调用

image-20230720102609815

image-20230720102744091

image-20230720103107743

image-20230720103303888

image-20230720103445029

1.4 操作系统体系结构

对应书1.3.1中的分层

image-20230720152211376

image-20230720152434773

(笔者注:我觉得不止6次)

image-20230720152646796

新考点总结

image-20230720155254491

image-20230720153556653

image-20230720154303962

进程可以申请虚拟空间也可以申请物理空间

image-20230720155207359

1.5 操作系统引导

image-20230720160147100

image-20230720160424692

完整过程

image-20230720160642864

image-20230720160757496

boot程序是bios中的程序吗

实际上,boot程序(或者称之为启动加载程序)并不是存储在BIOS中的,但是它的加载和执行是由BIOS启动的。

当你打开计算机电源,BIOS(基本输入输出系统)会首先被执行。BIOS会进行一些基础的硬件检查和初始化工作,这个过程通常被称为POST(Power-On Self-Test)。完成这些初始化工作后,BIOS会从设定的启动设备(如硬盘、USB驱动器、网络等)中读取boot程序。

这个boot程序通常被存储在启动设备的一个特殊区域,例如在硬盘上,这个区域通常被称为MBR(Master Boot Record)或者EFI系统分区(在更现代的UEFI启动模式下)。BIOS会加载这个boot程序到内存中,并开始执行它。

Boot程序的任务是加载操作系统的内核到内存中,并转交控制权给内核。为了完成这个任务,boot程序需要能够理解操作系统内核的文件格式以及文件系统的结构。因此,尽管boot程序通常很小,但它的任务却十分重要。

请讲解一下UEFI启动模式下操作系统引导的全部过程

UEFI启动模式下操作系统的引导过程相比传统的BIOS启动更为现代化和灵活,以下是一个典型的UEFI启动过程:

  1. 电源打开:用户按下电源按钮,计算机开始接通电源。

  2. UEFI固件启动:统一可扩展固件接口(UEFI)固件被加载并执行。这个阶段包括硬件的自我检测(POST)和UEFI设置的加载。

  3. UEFI Boot Manager启动:UEFI Boot Manager 是UEFI规范的一部分,它会按照预先配置的顺序尝试从不同的启动项(如硬盘、光盘驱动器、USB驱动器)中的EFI系统分区(ESP)启动EFI应用程序。

  4. 引导加载程序(Boot Loader)执行:UEFI Boot Manager从EFI系统分区(ESP)中加载并执行一个EFI应用程序,这通常是一个引导加载程序,如GRUB(对于Linux系统)或Windows Boot Manager(对于Windows系统)。

  5. 操作系统内核加载和初始化:引导加载程序将操作系统的内核加载到内存中,并将控制权交给它。在这个阶段,操作系统内核会初始化设备驱动,挂载必要的文件系统,启动用户空间的服务和程序等。

  6. 用户空间程序启动:操作系统开始运行用户空间的程序,如系统服务和应用程序。在一些系统中,这可能包括启动一个图形用户界面(GUI)。

  7. 用户登录:最后,用户会被提示登录。在成功登录后,用户可以开始使用计算机。

UEFI启动流程提供了许多现代特性,如启动时的网络支持、大硬盘的支持(使用GPT分区表)、安全启动(Secure Boot)等。

请讲解一下BIOS启动模式下操作系统引导的全部过程

在 BIOS(基本输入/输出系统)启动模式下,操作系统的引导过程大致如下:

  1. 电源打开:用户按下电源按钮,计算机开始接通电源。

  2. BIOS启动:计算机的BIOS固件被加载并执行。这个阶段包括硬件的自我检测(POST)和BIOS设置的加载。

  3. 启动设备选择:根据 BIOS 设置,选择一个启动设备(例如硬盘、光盘、U盘、网络等)。

  4. MBR加载和执行:BIOS会读取启动设备的第一个扇区,也就是主引导记录(MBR)。MBR包含了一个小的引导代码和硬盘的分区表。BIOS将这段引导代码加载到内存中,并开始执行它。

  5. 活动分区选择和PBR加载:MBR的引导代码会查找活动分区(也就是装有操作系统的分区),并加载这个分区的第一个扇区,也就是分区引导记录(PBR)。然后开始执行PBR的代码。

  6. 引导加载程序(Boot Loader)执行:PBR通常会加载一个更复杂的引导加载程序,例如 GRUB(用于 Linux 系统)或 NTLDR(用于早期的 Windows 系统)。这个引导加载程序负责加载操作系统的内核。

  7. 操作系统内核加载和初始化:引导加载程序将操作系统的内核加载到内存中,并将控制权交给它。操作系统内核在此阶段会完成设备的初始化,挂载必要的文件系统,启动用户空间的服务和程序等。

  8. 用户空间程序启动:操作系统开始运行用户空间的程序,例如系统服务和应用程序。在一些系统中,这可能包括启动一个图形用户界面(GUI)。

  9. 用户登录:最后,用户被提示登录。在成功登录后,用户可以开始使用计算机。

这就是在 BIOS 启动模式下操作系统的一般引导过程。值得注意的是,现代计算机已经普遍采用 UEFI 替代了传统的 BIOS,因为 UEFI 提供了更多的功能和更好的扩展性。不过,很多 UEFI 仍然提供了 BIOS 兼容模式(也称为 Legacy 模式或 CSM 模式),以支持那些只能在 BIOS 模式下启动的操作系统。

1.6 虚拟机

image-20230720181237900

image-20230720181854314

image-20230720181909474

image-20230720182319498

第二章 进程与线程

2.1 进程与线程

2.1.1 进程的概念和特征

image-20230720192558336

image-20230720192700848

image-20230720192911289

image-20230720192927717

image-20230720192942910

image-20230720193028571

image-20230720193208549

image-20230720193339028

image-20230720193431241

引入线程之后就不是独立调度的基本单位了

image-20230720193610452

2.1.2 进程的状态和切换

image-20230720193737660

进程五状态模型

image-20230720200558089

image-20230720200654653

image-20230720200809098

image-20230721090126572

image-20230721090159802

image-20230721090319310

2.1.4 进程控制

image-20230721093149060

image-20230721091252742

image-20230721091903319

image-20230721092143791

image-20230721092305646

image-20230721093044907

2.1.5 进程间通信

image-20230721094230274

image-20230721094839851

image-20230721094924297

image-20230721100538475

image-20230721101243090

image-20230721101417960

image-20230721102012861

image-20230721102649670

2.1.6 线程和多线程模型

image-20230721143248437

image-20230721143756545

image-20230721143906968

多线程模型

image-20230721144358983

image-20230721144530952

image-20230721144611430

image-20230721144719757

image-20230721144959325

image-20230721145011094

线程的状态与转换

image-20230721145115313

image-20230721145305002

image-20230721145752637

“同一进程中的所有线程都可以访问进程地址空间的每个单元,所以一个线程可以读写甚至清除另一个线程的堆栈”这句话正确吗?

在理论上,这句话是正确的。在同一进程中,所有线程共享同一地址空间,包括代码段、数据段和堆内存。每个线程都可以访问这些内存区域,包括其他线程的堆栈。

然而,在实践中,一个线程试图访问(读取、写入或清除)另一个线程的栈内存通常是一个非常糟糕的编程实践,会导致难以调试的问题,如数据竞争、内存破坏等。这种行为往往会破坏线程之间的数据隔离,导致程序的行为变得不可预测。

因此,尽管理论上可能,我们通常会强烈建议避免让一个线程直接访问另一个线程的栈。线程间应该通过预定义的、明确的方式(如通过共享内存中的数据结构、条件变量、信号量、消息队列等方式)进行通信,而不是直接访问彼此的栈。

“线程被终止之后不立刻释放它所占有的资源,只有当进程中的其他线程执行了分离函数,被终止线程才与资源分离,此时的资源才能被其他线程利用”,这句话怎么理解?

这句话是关于在 POSIX 线程(也称为 pthreads)模型中,线程终止和资源释放的过程。当一个线程终止时(可能是因为它已经完成了它的任务,或者是因为其它线程对其调用了 pthread_cancel 函数),它的退出状态需要被保留下来,这样其他线程如果需要的话,就可以查询到这个状态。这个被终止的线程在退出状态被其他线程查询之前是不能被完全销毁的,我们称这种状态的线程为 "僵尸线程"。

这就引出了两个重要的 pthreads 函数:pthread_join 和 pthread_detach。pthread_join 函数允许一个线程等待另一个线程结束,并获取那个线程的退出状态。当 pthread_join 返回时,被结束线程的资源就会被释放。另一方面,pthread_detach 函数允许一个线程告诉操作系统,当它结束时自动清理它的状态,而不需要另一个线程来 join。

因此,这句话的意思就是:当一个线程结束时,它并不立即释放所有的资源。只有当另一个线程调用 pthread_join(并等待该线程结束)或者该线程被 pthread_detach,它才会释放其资源。否则,它会继续占用部分系统资源,例如用于保存其退出状态的内存,直到其他线程调用 pthread_join 或者该线程被分离(detach)。

请举例给出一个pthread_detach的具体使用场景

在某些场景下,你可能想要创建一个线程,让它在后台执行一些任务,并且在任务完成后自动清理自己。这种时候,你就可以使用 pthread_detach 函数。以下是一个简单的示例:

#include 
#include 

// 这个函数在一个新的线程中运行
void* run(void* arg) {
    // 执行一些工作...
    printf("Background thread is running...\n");

    // 结束线程
    pthread_exit(NULL);
}

int main(void) {
    pthread_t thread_id;

    // 创建一个新的线程
    if (pthread_create(&thread_id, NULL, &run, NULL) != 0) {
        fprintf(stderr, "Failed to create thread\n");
        return 1;
    }

    // 分离线程。这样,当新的线程结束时,它的资源将自动被回收
    if (pthread_detach(thread_id) != 0) {
        fprintf(stderr, "Failed to detach thread\n");
        return 1;
    }

    // 继续执行主线程的工作...
    printf("Main thread is continuing its work...\n");

    // 等待一段时间,确保后台线程有时间完成其工作
    sleep(1);

    return 0;
}

在这个示例中,主线程创建了一个新的线程,并使用 pthread_detach 函数将其分离。这样,新线程在结束时将自动清理自己。主线程不需要调用 pthread_join 来回收新线程的资源,也不用担心新线程结束后变成僵尸线程。

进程在内存中拥有的地址空间包括哪些部分?

一个进程在内存中的地址空间主要包括以下几个部分:

  1. 文本段(Text Segment)或代码段(Code Segment):这部分内存存放的是进程要执行的代码,通常是只读的,防止进程在运行时修改自己的指令。

  2. 数据段(Data Segment):这部分内存存放的是初始化的全局变量和静态变量。

  3. BSS段(Block Started by Symbol):这部分内存存放的是未初始化的全局变量和静态变量,以及程序运行中动态申请的内存。在程序开始运行前,这部分内存中的值通常都被初始化为0。

  4. 堆(Heap):这部分内存用于存放进程运行期间动态分配的数据。进程可以在运行期间根据需要增加(通过mallocnew等函数)或减少(通过freedelete等函数)堆的大小。

  5. 栈(Stack):这部分内存用于存放函数调用的信息,如局部变量,返回地址等。每次函数调用会在栈上创建一个新的栈帧,函数调用结束后,这个栈帧就会被销毁。

  6. 内存映射段(Memory-mapped Segment):这部分内存用于实现文件映射和共享内存。例如,当进程调用mmap函数将一个文件映射到内存时,这个文件的内容就会出现在内存映射段中。

注意,这些内存区域的布局和特性可能依赖于操作系统和硬件架构的具体实现。

这些内存区域之间是什么关系?有没有包含关系?

这些内存区域(文本段、数据段、BSS段、堆、栈、内存映射段)是在同一个进程的地址空间中并列存在的,它们各自有不同的起始地址和结束地址。在物理内存中,它们被映射到不同的内存位置,互相之间没有直接的包含关系。

一般来说,文本段、数据段、BSS段在内存中的位置是静态的,也就是说在程序加载到内存时就已经确定,而堆、栈、内存映射段在内存中的位置和大小是动态变化的。

下面是一个简化的进程内存布局图:

高地址 +------------------+ 

你可以使用Unix/Linux系统中的size命令来查看一个可执行文件的文本段、数据段和BSS段的大小,也可以使用pmap命令来查看一个运行中的进程的内存映射。

2.2 处理机调度

2.2.1 调度的概念

image-20230721200332076

image-20230721195127325

image-20230721195356531

image-20230721195428234

image-20230721195545389

image-20230721200056694

image-20230721200231706

2.2.2 进程调度的时机、切换过程、方式

image-20230721202021600

image-20230721200602043

image-20230721200813800

不能调度和切换的情况——内核程序临界区的理解

image-20230721201323891

进程调度的方式:抢占式和非抢占式

image-20230721201505308

image-20230721201450585

image-20230721201845858

2.2.3 调度器和闲逛进程

抢占式只要就绪队列改变,就要检查需不需要抢占。由时钟周期到时触发检查就绪队列。

image-20230721211116212

image-20230721211844553

image-20230721212006074

2.2.4 调度算法的评价指标

image-20230721212831851

image-20230721212106249

image-20230721212220095

image-20230721212257434

image-20230721212600919

image-20230721212730922

image-20230721212755438

2.2.5 调度算法

适合批处理的调度

image-20230721212948013

先来先服务FCFS

image-20230721213252579

image-20230721213426345

短作业优先SJF

image-20230721214243210

image-20230721214445330

抢占式短作业优先/最短剩余时间优先SRTN

image-20230721214531716

一点注意

image-20230721214724910

image-20230721214815065

image-20230721214911512

高响应比优先HRRN

image-20230721215204412

image-20230721215301823

image-20230721215411122

适合交互式系统的调度

image-20230721215501731

时间片轮转RR

image-20230721220055426

image-20230721220347618

image-20230721220438036

优先级调度

image-20230722085325147

image-20230722085414067

image-20230722085525412

多级反馈队列

image-20230722085942949

image-20230722090143948

image-20230722090333579

多级队列调度算法

分多个队列,每次调度先选中一个队列,再按调度算法选中队列中的一个进程

image-20230722090753092

(笔者注:课本内容的错误)“用硬件的方法来减少上下文切换时间,通常采用两组寄存器,其中一组供内核使用,一组供用户使用”,这句话正确吗

这个描述不准确。通常情况下,不会因为减少上下文切换时间而在硬件上设置两组寄存器专门供内核和用户使用。

上下文切换涉及到将当前运行的进程(或线程)的寄存器状态保存到内存中,然后将即将运行的进程(或线程)的寄存器状态从内存中恢复到寄存器中。这个过程确实会带来一定的开销,但是采用两组寄存器供内核和用户使用并不能解决这个问题。因为无论怎样,当操作系统需要切换不同的用户级线程或进程时,都需要保存和恢复上下文状态。

实际上,硬件采用的策略是在多核或多线程的CPU上,预留多个硬件上下文(也就是多组寄存器)。在这种情况下,不同的线程或进程可以在不同的硬件上下文中并行运行,从而减少了上下文切换的开销。

至于内核和用户,他们不是使用不同的寄存器,而是操作系统将每个进程的地址空间分为用户空间和内核空间。用户空间用于运行用户程序,内核空间用于运行操作系统内核。当用户程序需要请求操作系统服务时,会发生从用户模式到内核模式的切换,但这个过程并不涉及到寄存器的保存和恢复,所以开销较小。

“从用户模式到内核模式的切换这个过程并不涉及到寄存器的保存和恢复”怎么理解?

当进程从用户模式切换到内核模式时,即执行了一次系统调用,该过程涉及改变程序的运行级别和部分处理器的状态。在这个过程中,部分寄存器的值可能会被保存和恢复,但是并不会像完全的上下文切换那样需要保存和恢复全部寄存器的值。这是因为系统调用是同一个进程内的行为,所以其它部分的上下文(例如虚拟内存环境,打开的文件等)都不需要改变,只有少数与执行状态和运行级别相关的寄存器值需要保存和恢复。

例如,当一个用户程序进行系统调用时,它可能首先将系统调用的编号和参数放到特定的寄存器中,然后执行一个特殊的指令(例如在x86架构下的int 0x80syscall)以通知操作系统,这个指令会触发一次保护性的中断,处理器就会自动的将程序计数器(PC)、程序状态字(PSW)以及可能会被改变的其他寄存器的值保存到内核栈中,然后跳转到内核的中断处理程序开始执行。

当系统调用完成后,内核将返回值放入特定的寄存器,然后执行一条特殊的指令(例如在x86架构下的iret)来结束中断,处理器就会从内核栈中恢复PC、PSW以及其他寄存器的值,然后跳回到用户程序接着执行。

因此,虽然从用户模式切换到内核模式涉及到部分寄存器的保存和恢复,但是这个开销要比完全的上下文切换(即从一个进程切换到另一个进程)小得多。

请讲解一下内核空间

在计算机科学中,内核空间是指在操作系统内核运行所使用的内存空间。它通常与用户空间形成对比,后者是用户级应用程序运行所使用的内存空间。

内核空间的主要特性如下:

  1. 保护级别:内核空间在保护级别上具有最高权限,能够访问所有的硬件设备,也能执行所有的指令。这使得操作系统内核可以对整个系统进行管理。

  2. 地址空间在具有虚拟内存支持的系统中,内核空间的地址通常是固定的,不受用户空间地址的影响。内核空间中的地址通常直接映射到物理内存,使得内核可以方便地操作硬件。

  3. 功能:内核空间用于运行操作系统内核代码,包括调度程序、设备驱动、内核服务等。此外,当用户程序执行系统调用时,也会在内核空间中运行

  4. 资源管理:内核空间包含了用于系统运行所需的各种资源,如内核堆栈、页表、I/O 缓冲区等

内核空间和用户空间的划分是一种保护机制,防止用户程序意外或恶意地破坏系统资源。当用户程序需要使用内核提供的服务(如文件操作、网络通信等)时,需要通过系统调用切换到内核空间。这种切换是由操作系统进行控制和管理的,可以确保系统的稳定性和安全性。

内核栈怎么在内核空间中划分?

在 Linux 系统中,每一个进程(包括线程)都会有一个对应的内核栈,这是在内核空间中为每个进程分配的一小块内存区域。这个内核栈的主要目的是为进程在内核模式下运行时提供栈空间。

内核栈的划分和管理大致如下:

  1. 创建:当一个新的进程或线程创建时,操作系统会在内核空间中分配一块连续的内存作为这个进程或线程的内核栈。

  2. 大小:在许多操作系统中,内核栈的大小是固定的。比如在某些版本的 Linux 中,每个进程的内核栈大小是固定的8KB。

  3. 位置:内核栈位于内核空间,但是不同进程的内核栈在内核空间中的位置可以是不连续的。也就是说,每个进程的内核栈都在内核空间中,但是这些内核栈之间可能会被其他的内核数据结构隔开。

  4. 使用:当进程从用户模式切换到内核模式时(例如通过系统调用、异常或中断),它会切换到使用其对应的内核栈。此时,进程在内核模式下执行的所有函数调用、局部变量的分配、返回地址的保存等操作,都会在这个内核栈上进行。

  5. 清理:当进程结束时,其对应的内核栈也会被操作系统回收。

总的来说,内核栈是内核空间中为每个进程或线程分配的一个独立的、私有的栈空间,用于支持这个进程或线程在内核模式下的运行。

(笔者注:书上这里有问题)“现场切换时,操作系统将原进程的现场信息推入当前进程的内核堆栈来保存它们,并更新堆栈指针”,这句话是什么意思?

"现场切换",也就是上下文切换,是指操作系统在切换执行不同进程时需要做的工作。"现场信息"或者"上下文"通常指的是一个进程在被暂停时的状态,包括程序计数器的值(表示下一条要执行的指令),处理器寄存器的值,虚拟内存信息等。

每个进程都有自己的内核堆栈,它主要用来保存进程在执行系统调用或处理中断时的状态。当发生上下文切换时,操作系统需要保存当前正在执行的进程的上下文,以便之后可以继续执行这个进程。这通常是通过将上下文信息“推入”(也就是保存到)当前进程的内核堆栈来实现的。

比如,当一个进程被中断,操作系统需要将当前的程序计数器,处理器寄存器的值,以及其他必要的信息保存到该进程的内核堆栈中。然后,操作系统可能会根据调度策略选择另一个进程来执行,这就涉及到加载该进程之前保存的现场信息。

"更新堆栈指针"是因为每次向堆栈“推入”或者从堆栈“弹出”数据时,都需要移动堆栈指针来指向堆栈的顶部。当保存上下文信息时,堆栈指针需要向下移动;当恢复上下文信息时,堆栈指针需要向上移动。

关于内核堆栈,其实它是属于内存管理信息的一部分,但通常它的具体内容(即堆栈中存储的数据)不直接保存在PCB中。相反,PCB通常会保存一个指向内核堆栈的指针或者其他用于定位内核堆栈的信息。当进程从用户态切换到内核态时,操作系统会使用这些信息来找到对应的内核堆栈,然后把CPU寄存器的内容保存到堆栈中,以便在以后需要时恢复现场。

发生进程调度和切换时,原进程现场信息被保存在哪里?

上下文切换过程中,现场信息确实会涉及到内核栈,但是最终的信息保存位置应该是进程控制块(PCB)或线程控制块(TCB)。

在上下文切换过程中,操作系统会将当前正在运行的进程或线程的现场信息(包括寄存器值、程序计数器等)保存到其对应的PCB或TCB中。然而,在实际操作中,这些信息可能会暂时存放在内核栈中,然后再被移动到PCB或TCB。

具体来说,当发生上下文切换时,操作系统会先将当前进程的现场信息保存到内核栈中,然后再将这些信息从内核栈复制到对应的PCB。这是因为操作系统在处理中断或系统调用时,会先将CPU的现场信息(即所有寄存器的内容)推入内核栈,然后再从内核栈中取出这些信息并保存到PCB或TCB中。

但最终的保存位置应该是PCB或TCB,因为这是用来保存进程或线程的长期状态信息的地方。所以,如果说上下文切换将现场信息保存在内核栈中,这是指的一个临时的保存位置,最终的保存位置应该是PCB或TCB。

切换时,怎么恢复新进程的现场?是从PCB中获取现场信息还是从内核栈中?

在上下文切换时,新进程的现场信息主要是从进程控制块(PCB)中恢复的。

具体来说,当操作系统调度器选择了一个新的进程运行后,操作系统会根据这个进程的PCB中的信息来恢复其执行上下文。这个过程包括设置CPU的程序计数器(PC)为该进程PCB中保存的值,恢复其他CPU寄存器的值,以及可能的其他操作,例如设置虚拟内存映射等。

另一方面,内核栈主要是用来在发生系统调用、中断或异常等情况时保存当前进程的现场信息,以便在这些事件处理完后可以恢复到处理事件之前的状态。也就是说,内核栈主要用于在一个进程的执行过程中临时保存现场信息,而不是在进程间的上下文切换中保存和恢复现场信息。

因此,在上下文切换时,新进程的现场信息主要是从PCB中恢复的。

多级反馈队列调度算法会导致饥饿吗

多级反馈队列调度算法(Multi-Level Feedback Queue Scheduling)是一种动态优先级调度算法,它根据进程的行为和需求调整优先级。具体来说,它包含多个队列,每个队列有不同的优先级,并且有自己的调度算法(例如,队列的顶部可能使用Round Robin,队列的底部可能使用FCFS)。根据其行为,进程可以在这些队列之间移动。

然而,由于该算法倾向于短作业和I/O密集型作业(它们会被提升到更高优先级的队列),因此,如果没有适当的防饥饿机制,长作业和CPU密集型作业可能会被降低到低优先级的队列,并可能遭受饥饿。

饥饿是指在一个调度系统中,一些低优先级的任务可能永远不会得到执行,因为总是有一些高优先级的任务需要执行。这是一个严重的问题,因为它可能导致某些任务永远无法完成。

多级反馈队列调度算法通常通过“老化”来解决这个问题。老化是一种机制,通过它,长时间等待在低优先级队列中的进程会逐渐提升到更高的优先级队列。这确保了所有的进程,最终都能得到执行。所以,虽然多级反馈队列调度算法可能会导致饥饿问题,但是通过适当的机制,可以避免这个问题。

2.3 同步与互斥

2.3.1 概念

image-20230722182344099

image-20230722181549444

image-20230722181648973

image-20230722182200659

image-20230722182307392

2.3.2 实现临界区互斥的基本方法

软件实现

单标志为“谦让”,双标志为“表达意愿”

image-20230722184212108

image-20230722182452394

image-20230722182801247

image-20230722182914940

image-20230722183217300

image-20230722183357642

image-20230722183652545

image-20230722183956384

image-20230722184030595

硬件实现

image-20230722185633309

image-20230722184336031

image-20230722184524907

image-20230722184838800

TS 指令是在一些处理器架构中用于实现原子性操作的指令,全称为 Test-and-Set。Test-and-Set指令是一种常见的用于实现锁的机制,常常用于实现各种形式的互斥(mutexes)和信号量(semaphores),这是并发编程中非常重要的概念。

简单来说,TS指令会将一个内存位置设置为一个特定的值,并返回这个位置之前的值。这两个操作(设置和返回)作为一个原子操作一起完成,即没有其他进程或线程可以在这两个操作之间运行。

这种指令在实现互斥时非常有用。例如,如果一个线程想要获取一个互斥锁,它可以使用TS指令将表示锁状态的内存位置设置为“已锁定”。如果TS返回的旧值表明该锁之前已经被锁定(即已经被其他线程获取),那么该线程知道它没有成功获取锁,并可以选择重试或执行其他操作。如果返回的旧值表明锁之前是可用的,那么该线程就知道它已经成功获取了锁。

请注意,不是所有的计算机架构都有TS指令,具体取决于硬件的设计和指令集。在没有TS指令的系统中,可以使用其他原子操作,如 Compare-and-Swap(CAS)等来实现类似的功能。

image-20230722185503102

SWAP 指令用于原子地交换两个位置的值。这个指令经常用于实现各种形式的互斥(mutexes)和信号量(semaphores),这是并发编程中非常重要的概念。

简单来说,SWAP 指令通常接收两个参数,一个是内存位置(通常用于表示锁的状态),另一个是一个寄存器。指令会将这两个位置的值交换。由于这个交换操作是原子的,因此它能够安全地在并发环境中使用,没有其他线程或进程会在交换操作的中间阶段看到这两个位置的值。

在互斥(mutex)的上下文中,SWAP 可能这样用:如果一个线程想要获取一个锁,它会尝试将锁的内存位置与一个包含预期锁定值的寄存器交换。如果锁已经被获取,那么交换后寄存器中的值将是锁定值,线程知道它没有成功获取锁。如果锁是可用的,那么交换后寄存器中的值将是解锁值,线程知道它已经成功获取了锁。

注意,不是所有的计算机架构都直接提供 SWAP 指令,它可能会有各种实现方式,具体取决于底层硬件的特性和指令集。

TSL 和 swap 都适用于多处理机,但不满足让权等待

2.3.3 互斥锁

自旋锁适用于多处理机

image-20230722190047445

互斥锁(Mutex,全称 Mutual Exclusion,意为互斥)是一种在并发编程中用于防止两个线程同时对同一公共资源(例如全局变量)进行读写的机制。这可以防止数据在多线程环境下的竞态条件。互斥锁基本上说就是不能同时由两个线程拥有。如果一个线程已经获取了锁,其他尝试获取锁的线程就会被阻塞,直到拥有锁的线程释放了锁。

互斥锁的基本使用步骤大致如下:

  1. 在访问公共资源之前,线程会尝试获取互斥锁。如果互斥锁已被其他线程持有,则此线程会被阻塞(即被放入等待状态),直到拥有锁的线程释放锁为止。

  2. 当线程成功获取了互斥锁后,它就可以安全地访问公共资源。

  3. 访问完成后,线程必须释放互斥锁,以便其他线程可以获取锁。

使用互斥锁时需要特别注意的一个问题是死锁。例如,如果一个线程无限期地持有一个锁,而其他线程都在等待获取这个锁,那么就会发生死锁。为了避免死锁,一种常用的策略是为等待获取锁的时间设置一个上限,或者设定一个获取锁的尝试次数。

请注意,互斥锁是一种较重的同步机制,其使用需要涉及到内核态和用户态的切换,因此在有些情况下,为了提高效率,开发者可能会选择使用更轻量级的同步机制,如自旋锁(Spinlock)或原子操作。

2.3.4 信号量

image-20230722202253996

image-20230722200045105

image-20230722200251104

咸鱼存疑:忙等的时候会不会就不能发生切换了?

image-20230722201044947

image-20230722201607464

image-20230722202154210

同步与互斥

image-20230722203451160

image-20230722202544613

image-20230722202806165

image-20230722203117170

image-20230722203336157

2.3.6 经典同步问题

生产者消费者

image-20230722203957315

image-20230722212115800

v操作不影响,p操作同步必须在互斥之前

image-20230722212457050

image-20230722212605702

多种产品

image-20230722213550324

image-20230722214139720

如果所有被P的操作都最多只有一个,就不需要对缓冲区设置mutex

image-20230722214234705

image-20230722214341501

image-20230722214353837

(笔者注:怎么才能把对”进程“的分析看做对”事件“的分析?)

image-20230722214759861

读写者问题

image-20230722215229396

image-20230722221730175

读写公平法

image-20230722222136412

image-20230722222406593

哲学家就餐

image-20230723090724013

image-20230723091012022

image-20230723091441954

image-20230723091414897

image-20230723091703273

2.3.5 管程

image-20230724135931912

image-20230723091743792

image-20230723091902483

image-20230724135343239

image-20230724135729158

image-20230724135841829

补充:可重入代码

可重入代码可以通过同步互斥的方式访问共享数据以确保安全,即可以安全的访问和改变共享数据;或者不访问任何共享数据,即每一次调用都是相互独立的。我这么理解正确吗

是的,你的理解是正确的。一段可重入的代码可以安全地并发执行,它能实现这一点的主要方式有两种:

  1. 不访问共享数据:如果一段代码不访问共享数据,那么它就可以被认为是可重入的。这是因为它在执行过程中不会被其他代码的执行状态影响,也不会影响其他代码的执行。因此,无论何时、何地、如何被调用,它都能产生一致的结果。这种类型的可重入代码通常也被称为"纯函数"或"无副作用函数"。

  2. 通过同步机制访问共享数据:即使一段代码需要访问共享数据,只要它使用了适当的同步机制(例如互斥锁、信号量等)来保护这些数据,那么它仍然可以被认为是可重入的。在这种情况下,尽管多个进程或线程可能同时调用这段代码,但由于同步机制的存在,任何时候都只有一个进程或线程能够实际访问共享数据。因此,即使在并发环境下,这段代码也能正确地执行,并产生一致的结果。

所以,你的理解是完全正确的。不论是通过避免访问共享数据,还是通过使用同步机制来保护共享数据,可重入的代码都能在并发环境中安全、正确地执行。

2.4 死锁

2.4.1 死锁的概念

image-20230724155617053

image-20230724153948405

image-20230724154428207

image-20230724154704729

image-20230724154757447

image-20230724155541229

2.4.2 预防死锁

image-20230724160551078

image-20230724155714832

image-20230724155905654

image-20230724160044259

image-20230724160216608

image-20230724160511272

2.4.3 避免死锁和银行家算法

image-20230724160948832

image-20230724161352749

image-20230724162345151

image-20230724162515988

image-20230724162535756

image-20230724162615973

试探性的更改,如果不安全就退回

image-20230724162853531

image-20230724163011428

2.4.4 死锁的检测和解除

image-20230724163344387

image-20230724163648914

image-20230724164013005

image-20230724164140909

image-20230724164353659

image-20230724165839057