操作系统

主要是学习掌握：进程管理与内存管理这两部分；关于IO管理只需了解即可

CH1 操作系统概述

操作系统的概念

操作系统向上层提供的简易服务：

图像化用户接口
命令接口
- 联机命令接口：类似于CMD，交互的方式，用户输入一个命令，操作系统执行对应的操作
- 脱机命令接口：批处理命令接口，比如Windows下执行.bat脚本或者Linux下执行.sh脚本
程序接口：在程序中通过系统调用来使用程序接口，执行相关的功能
- 比如执行print函数，将内容输出时，内部就进行了系统调用

操作系统的基本特征

并发

共享

在一定程度上并发和共享是相互存在的前提条件

异步

虚拟

操作系统的运行机制

核心：内核态与用户态之间的切换

CPU如何实现内核态和用户态之间的切换？

中断和异常

中断的作用

中断是让操作系统内核夺回CPU使用权的唯一途径

发生中断，CPU会暂停当前程序的执行，转而执行对应的中断处理程序

中断的类型

内中断的例子

外中断的例子

中断机制的原理

中断总结

系统调用

什么是系统调用

系统调用与库函数的区别

什么功能需要系统调用？

系统调用的过程

操作系统的体系结构

计算机系统的层次结构

一般可以分为大内核和微内核这两种体系结构

操作系统的引导

虚拟机

CH2 进程管理

进程的概述

要理解以下几个问题：

进程的概念：理解进程与程序的区别
进程的组成：一个进程由哪些部分组成
进程的特征：进程有哪些重要的特征

进程的概念

程序：是静态的，是存放在磁盘里的可执行文件，就是一系列的指令集合

进程：是动态的，是程序的一次执行过程

同一个程序多次运行会对应多个进程

Q:操作系统作为这些进程的管理者，他是如何区分各个进程？

进程的组成

PCB：进程控制块

程序段、数据段

                                 <img src="操作系统/image-20240331184952014.png" alt="image-20240331184952014" style="zoom:33%;" />

进程的特征

进程的状态与转换

进程的状态以及状态之间的转换

操作系统如何将各个进程的PCB组织起来？

进程的组织方式一：链接方式

链表的形式存放不同状态的进程

进程的组织方式二：索引方式

进程组织方式总结

进程控制

如何实现进程的控制

原语：

1	原语是操作系统内核中的一直特殊程序，它的执行具有原子性，也就是这段程序的运行必须是一气呵成，不可中断

为什么进程控制需要用原语来实现(或者为什么这个过程需要一气呵成、不可中断？)

操作系统是如何实现原语的原子性？

背景：

1	正常情况下：CPU每执行完一条指令都会例行检查是否有中断信号需要处理，如果有，则暂停运行当前程序，转而去执行相应的中断处理程序

操作系统利用开中断和关中断指令去保证原语的原子性

进程控制相关的原语

进程创建（创建原语）

进程的终止（撤销原语）

阻塞原语和唤醒原语

切换原语

总结

无论是哪种进程原语，在进程状态切换时无非做的三类事情：

更新PCB中的信息
- 修改进程状态state,保存恢复进程的运行环境
将PCB插入合适的队列
分配/回收资源

扩充：程序是如何执行的以及进程之间的切换会发生什么？

进程通信

概念：进程间通信(IPC,Inter-Process Communication)是指两个进程之间产生数据交互

背景：

1	进程是资源分配的基本单位，因此各个进程拥有的内存地址空间是相互独立的，为了保证安全，一个进程是不能直接访问另一个进程的地址空间

进程之间是如何进行通信的？

进程通信方式一：共享存储

进程通信方式二：消息传递

进程通信方式三：管道通信

                                         <img src="操作系统/image-20240331203332343.png" alt="image-20240331203332343" style="zoom:33%;" />

线程概念

为什么引入线程？

线程的属性

线程的实现方式

用户级线程

用户级线程的特点：

线程的管理工作是由线程库来完成的
线程的切换不需要CP变态(由用户态->核心态)
操作系统无法意识到用户级线程的存在

内核级线程

                                     <img src="操作系统/image-20240331210233658.png" alt="image-20240331210233658" style="zoom:33%;" />

多线程模型

一对一模型

多对一模型

多对多模型

线程的状态与转换

线程的状态以及各个状态之间的转换与进程基本一致

线程的组织与控制

进程的组织与控制是通过PCB来实现的，而线程的组织与控制是通过TCB(线程控制块)来实现的

处理器调度

调度的概念

调度层次

高级调度

低级调度

中级调度

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

进程调度的时机

进程调度方式

进程的切换与过程

调度器和闲逛进程

调度器/调度程序

闲逛进程

调度算法的评价指标

CPU利用率

系统吞吐量

周转时间

等待时间

等待时间=周转时间-运行时间

响应时间

调度算法

先来先服务(FCFS)

短作业优先(SJF)

高响应比优先(HRRN)

时间片轮转（Round-Robin)

优先级调度

多级反馈队列

进程的同步和互斥

进程同步

进程互斥

进程互斥的软件实现方法

单标志法
双标志先检查
双标志后检查
Peterson算法

单标志法

缺陷:

双标志先检查法

双标志后检查法

Peterson算法

总结

进程互斥的硬件实现方法

中断屏蔽方法
TestAndSet(TS指令/TSL指令)
Swap指令

中断屏蔽方法

TestAndSet指令

Swap指令

总结

互斥锁

信号量机制

整型信号量
记录型信号量

背景

信号量机制

                                             <img src="操作系统/image-20240401103540739.png" alt="image-20240401103540739" style="zoom:33%;" />

整型信号量

记录型信号量

总结

信号量机制实现进程互斥、同步和前驱关系

信号量机制实现进程互斥

信号量机制实现同步

信号量机制实现进程前驱关系

总结

生产者消费者问题

问题描述

解决方案

不能改变相邻P、V操作的顺序，因为可能会发生死锁

                                             <img src="操作系统/image-20240401144625031.png" alt="image-20240401144625031" style="zoom:33%;" />

多生产者多消费者问题

问题描述

                                 <img src="操作系统/image-20240401150006736.png" alt="image-20240401150006736" style="zoom:33%;" />

问题解决

本题中缓冲区大小为1，所以在任何时刻，apple、orange、plate三个同步信号量做多只有一个是1，因此在任何时刻，做多只有一个进程的p操作不会被阻塞，并顺利进入临界区

吸烟者问题

问题描述

问题解决

读者写者问题

问题描述

解决方案

这个问题比前面几个问题都要复杂，因为写进程与写进程之间是可以同时进行的，读进程与写进程之间是互斥的

上述方案存在的潜在问题：只要有读进程还在读，写进程就要一直阻塞，可能饿死，在这种算法中，读进程是优先的

写进程优先的解决方案

                                 <img src="操作系统/image-20240401155954921.png" alt="image-20240401155954921" style="zoom:33%;" />

哲学家进餐问题

问题描述

存在的问题：如果5个哲学家并发执行，都拿起了自己左手边的筷子，那么就会出现死锁问题

那么如何防止死锁的发生？

方案一：

可以对哲学家进程施加一些限制，比如每次做多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家能够同时拿到左右两只筷子

方案二：

要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家正好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有一个可以拿起第一只筷子，另一个会直接阻塞。

方案三：仅当一个哲学家左右两只筷子都可用时，才允许他抓起筷子

管程

背景：什么要引入管程？

管程的定义和特征

管程例子：解决生产者消费者问题

死锁

死锁的概述

死锁 vs 死循环 vs 饥饿

死锁产生的必要条件

发生死锁的例子

死锁的处理策略

预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

避免死锁

银行家算法

死锁检测和解除

CH3内存管理

内存的基础知识

什么是内存？内存有什么作用？

相对地址的转换

程序经过编译、链接之后生成的指令中指明的是相对地址，是相对进程起始地址而言的地址，那么如何将相对地址转换为物理地址？

常见的装入方式：

绝对装入
可重定位装入
动态运行时装入

绝对装入

灵活性低，如果绝对装入，换了一台电脑运行，可能就不行了

可重定位装入

动态运行时装入

写程序到程序运行流程

链接的方式

内存管理

内存空间的分配与回收

虚拟技术：操作系统需要提供某种技术从逻辑上对内存空间进行扩充

                                     <img src="操作系统/image-20240402101637091.png" alt="image-20240402101637091" style="zoom:33%;" />

操作系统需要提供地址转换功能，负责程序的逻辑地址和物理地址的转换

操作系统需要提供内存保护功能，保证各个进程在各自存储空间运行，互不干扰

总结

内存空间扩充

覆盖技术
交换技术
虚拟存储技术

覆盖技术

                                 <img src="操作系统/image-20240402110123096.png" alt="image-20240402110123096" style="zoom:33%;" />

交换技术

内存空间的分配与回收

连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间

单一连续分配

固定分区分配

动态分区分配

内存分配

内存回收

                                              <img src="操作系统/image-20240402151853579.png" alt="image-20240402151853579" style="zoom:33%;" />

非连续分配管理方式

非连续分配：为用户进程分配的可以是一些分散的内存空间

动态分区分配算法

首次适应算法

最佳适应算法

最坏适应算法

邻近适应算法

连续分配管理方式

基本分页存储管理

问题一：如何存储逻辑页面与物理页面的对应关系—页表

如何实现地址的转换？

总结

基本地址转换结构

具有快表的地址变换机构

                                      <img src="操作系统/image-20240402192314710.png" alt="image-20240402192314710" style="zoom:33%;" />

两级页表

单级页表存在的问题

如何解决单级页表存在的问题

采用多级页表解决页表必须连续存放的问题

采用虚拟技术解决没有必要让整个页表常驻内存的问题

例题：

两级页表与一级页表相比的缺点：

一级页表只需访问两次内存，二级页表需要访问三次内存

总结

基本分段存储管理

分段管理

                                     <img src="操作系统/image-20240402195537504.png" alt="image-20240402195537504" style="zoom:33%;" />

分段 vs 分页管理

段页式存储管理

分页、分段的优缺点

                                         <img src="操作系统/image-20240402203837533.png" alt="image-20240402203837533" style="zoom:33%;" />

分段+分页—-段页式管理方式

段表、页表

如何实现地址转换

虚拟内存

传统存储管理方式的特征、缺点

                                         <img src="操作系统/image-20240402205246881.png" alt="image-20240402205246881" style="zoom:33%;" />

虚拟内存的定义和特征

如何实现虚拟内存技术？

请求分页管理方式

请求页表

缺页中断机制

                                             <img src="操作系统/image-20240402211008408.png" alt="image-20240402211008408" style="zoom:33%;" />