一、导论

概念

操作系统极小化定义：内核才是操作系统
中断：当出现需要时，CPU暂时停止当前进程的执行，转而执行处理新情况的中断处理程序。当执行完该中断处理程序后，则重新从刚才停下的位置继续当前进程的运行。

设备控制器：
每个设备控制器有一个本地缓冲
CPU在内存和本地缓冲之间传输数据
I/O控制器从设备到本地缓冲之间传输数据
协作：控制器通过调用中断通知CPU完成操作

操作系统目标
核心	运行程序
面向用户	更方便使用计算机
面向系统	更高效使用计算机

并行：同一时刻运行
并发：同短时间内依次运行

双重模式：用户模式和内核模式
由硬件提供模式位，特权指令即可能引起系统崩溃的指令，只能运行在内核模式

用户程序需要用特权指令则执行系统调用

1. CPU和设备控制器可以并行工作
2. 一次系统调用的完成需要进行2次模式转换
3. 批处理系统的主要缺点是缺乏交互性
4. 特权指令：获取事件指令、内存访问指令、I/O指令
5. 操作系统的最基本的设计目标是 使应用程序能够顺利运行 ，在此基础上，还需要考虑 高效 （面向系统）和 易用 （面向用户）

操作系统类型

• 大型机系统（目标系统效率）
  简单批处理系统：作业（单道程序设计）
  多道程序设计系统：相互穿插运行
  分时系统：时间片轮转
• 桌面系统
  Windows、Linux、MacOS
• 嵌入式系统
  IOS、Android
• 手持系统
• 分布式系统
  支持分布式处理的软件系统，又称松耦合系统
• 虚拟系统
• 多处理器系统
  并行系统
  紧耦合系统

---

二、操作系统结构

• 操作系统服务形式
  系统调用
  用户接口
  系统程序

• 操作系统结构

操作系统结构	例子
简单结构	MS-DOS、早期UNIX
层次结构	THE、iOS
微内核结构	Mach、Windows 2000
模块结构	大部分线代操作系统采用模块结构、Solaris模块
混合结构	Mac OS X

CLI(command-line interface)命令行界面
GUI(graphical user interface)用户图形界面

• 微内核
  好处:
  便于扩充微内核
  便于移植操作系统到新架构系统上
  更稳定 (更少的代码运行在核心态)
  更安全
  坏处:
  用户空间和内核空间通信的系统开销增加
  解决方法：提出消息传递机制
• 模块结构

• 虚拟机

虚拟机：一种通过软件模拟实现，具有完整硬件系统功能，并运行在一个完全隔离环境中的完整计算机系统

名称	功能	目的
高级语言虚拟机	模拟代码执行	跨平台
工作站虚拟机	面向工作站、PC	多个操作系统可以同时在一个计算机上使用
服务器虚拟机	多用户、多操作系统并存	把一个物理计算机虚拟化为多个虚拟机

宿主操作系统（Host OS）：安装在硬件上的OS
客户操作系统（Guest OS）安装在操作系统上的操作系统

1. 采用简单结构的操作系统是MS-DOS
2. 微内核操作系统效率更高（X）
3. 大多数线代操作系统采用的是模块结构
4. 用户接口和系统调用是操作系统提供给用户（程序）的服务形式
5. 系统调用之间往往会相互调用，但这不涉及模式转换（√）
6. 服务器虚拟机主要功能是使得代码能够跨平台运行（X）
7. 模块结构更加安全（X）
8. 操作系统的结构有多种，其中采用微内核结构的有 Windows XP Mach QNX 等；采用模块化结构有 Solaris Linux Mac 等

---

三、进程

概念

• 进程包括
  • 代码(Text)
  • 当前活动
    程序计数器(PC)：指向当前要执行的指令
    堆栈(Stack)：存放函数参数、临时变量等临时数据
    数据(Data)：全局变量，处理的文件
    堆(Heap)：动态内存分配
• PCB
  进程状态
  程序计数器
  CPU寄存器
  CPU调度信息
  内存管理信息
  计账信息
  I/O状态信息

CPU在进程间切换 五状态图

1. 如果系统中有N个进程，运行的进程最多1个，最少0个；就绪进程最多N-1个最少0个；等待进程最多N个，最少0个。
2. 一个进程退出等待队列而进入就绪队列是因为进程获得了所等待的资源
3. 等待只能到就绪，就绪只能到运行
4. 进程和程序是一一对应的（X）

进程创建

1. 进程创建原语的任务是为进程创建PCB表
2. 进程操作的原语有创建、撤销、唤醒、阻塞原语

请从资源共享、进程创建和进程结束三个方面谈谈父进程和子进程的关系。
资源共享方面：父进程创建子进程时，子进程可能从操作系统那里直接获得资源，也可以从父进程那里获得。父进程可能必须在子进程之间共享资源。 进程创建方面：子进程被父进程创建时，除了得到各种物理和逻辑资源外，初始化数据（或输入）由父进程传递给子进程。
进程结束方面：子进程使用了超过它所分配的资源，或者分配给子进程的任务已不再需要，父进程将终止子进程。父进程退出，如果父进程终止，那么操作系统（处特殊的操作系统）不允许子进程继续。

进程间通信

• 两种基本形式
  共享内存
  消息传递

采用间接通信的方法有剪贴板、系统消息队列、信箱

---

四、线程

概念

• 线程
  可在CPU上运行的基本执行单位
  进程内的一个代码片段可以被创建称为一个线程
  线程状态：就绪、运行、等待等
  线程操作：创建、撤销、等待、唤醒等
  进程依旧是资源分配的基本单位
  线程自己不拥有系统资源，通过进程申请资源
• 线程结构

• 线程优点

• 线程和进程比较
  

什么是用户态线程和核心态线程？它们之间的映射关系有哪些？

• 用户态线程：用户态线程的管理过程全部由用户程序完成，操作系统内核只对进程进行管理。
• 核心态线程：核心态线程由操作系统内核进行管理。操作系统内核给应用程序提供相应的系统调用和应用程序接口API，以使用户程序可以创建、执行、撤销进程。
• 用户态线程与和核心态线程之间的映射关系有1对1、多对1、多对多。

1. 一对一模型最得益于多处理器架构
2. Win32线程调用会产生系统调用

多线程模型

线程库

image.png

---

五、调度

概念

（可选）长程调度：新建->就绪
（必需）短程调度：选择下一个执行的进程

将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态的任务为上下文切换。

• CPU调度可能发生的时机
  从运行转到等待（非抢占式）
  运行转到就绪（抢占式）
  从等待转到就绪（抢占式）
  终止运行（非抢占式）

调度指标	定义
CPU利用率	固定时间内CPU运行时间的比例
吞吐量	单位时间内运行完的进程数
周转时间	进程从提交到运行结束的全部时间
等待时间	进程等待调度（不运行）的时间片总和
响应时间	从进程提交到首次运行[而不是输出结果]的时间段，也就是第一段的等待时间
周转时间	=等待时间+运行时间

并行：同一时刻运行
并发：同短时间内依次运行

CPU调度可发生在哪些情况下？哪些情况是可抢占式调度？哪些是非抢占式调度？
（1） 正在执行的进程执行完毕。
（2） 执行中进程自己调用阻塞原语。
（3） 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资源的进程队列。
（4） 执行中进程提出I/O请求后被阻塞。
（5） 在分时系统中时间片已经用完。
（6） 在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。
（7） 就绪队列中的某进程的优先级变的高于当前执行进程的优先级，从而也将引发进程调度。
可抢占式调度：（7） 非抢占式调度：（1）、（2）、（3）、（4）、（5）、（6）

算法分类

• 先来先服务调度算法FCFS

• 短作业优先调度算法SJF

通常用于长程调度
优点：最短的平均等待时间
缺点：存在饥饿问题
一般来说，抢占式SJF算法比非抢占式SJF算法的系统开销大。

• 优先级调度算法PR

默认：小优先数具有高优先级
目前主流的操作系统调度算法
存在问题：饥饿（解决方法为老化）

• 时间片轮转调度算法RR

时间片，为每个进程分配不超过一个时间片的CPU响应时间
时间片小=>增加上下文切换时间
时间片大=>FCFS

• 多级队列调度MLQ
  要素：1.队列数2.每个队列的调度算法3.决定新进程进哪个队列
• 多级反馈队列调度MLFQ
  和多级队列调度算法相比，多级反馈队列调度算法还需要考虑升级、降级的方法
• 多队列调度方法MQMP和单队列调度方法SQMP

甘特图以及计算***************
非抢占式调度*******
抢占式调度********待写

1. 存在饥饿问题的调度算法有 优先级调度、最短作业优先调度
2. SJF有利短进程而不利于长进程
   RR系统开销大
   交互进程需要短的响应时间
   批处理进程需要短的等待时间

---

六、进程同步

概念

竞争条件：多个进程并发访问同一共享数据的情况
同步：协调执行次序
互斥：只让一者排他的运行
临界区：涉及临界资源的代码段

• 同步应遵循的基本准则
  互斥：Pi在某临界区执行，其他进程将被排除在临界区外，有相同临界资源的临界区都需要互斥，没有相同临界资源的临界区不需要互斥
  有空让进：临界区内无进程执行，不能无限期地延长下个要进临界区的进程的等待时间
  有限等待：进入前的等待时间必须有限，不能无限等待
  无空等待：不允许两个以上的进程同时进入互斥区。

1. 实现有空让进准则可以在退出区

信号量

• 整型信号量（最初始原型如下，有忙等待的问题，实际应用不这样）

wait(S){
  while(S<=0)
    ;//no-op
  S--;
}

signal(S){
  S++;
}

忙等：如果S<=0 该进程将不断重复执行while语句

• 记录型信号量（增加了一个等待队列list，消除了忙等，先减再判断）

P(S) {
    value--;
    if (value < 0) {
        add this process to list
        block//阻塞
    }
}

V(S) {
    value++;
    if (value <= 0) {
        remove a process P from list
        wakeup(P);//唤醒一个
    }
}

• 操作系统区分计数（同步）信号量和二值（互斥）信号量：
  计数信号量值域不受限制
  二值信号量的值只能为0或1
  S初始值不能为负数且只能必须置一次初始值

• 同步信号量的简单使用

semaphore S=0
P1:
  C1;
  signal(S);
P2:
  wait(S);
  C2;
//这样表示了P1和P2进程运行时让C1段优先于C2段代码运行

S>0: 有资源可用；
S=0:没有资源可用；
S<0:有进程在等待资源；
P(S):当有S资源可用时，S减一；如果没有S资源可用时，阻塞当前进程；
V(S):当资源不再使用时，S加一；如果有进程因为等待当前资源而阻塞，需要唤醒他们。
用V操作可以唤醒一个进程，被唤醒的进程状态是就绪
二值信号量的值区间是0-1（X） 0和1

信号量的应用

• 1.找到临界区（即用到共享资源的代码）加上互斥的机制
  加互斥信号量实际上是最简单的，只要在你觉得这个操作是原子的部分上下加P、V(mutex)
• 2.同步分析（即分析运行次序）
• 3.给信号量写初始值
  互斥信号量初始值一般为1
  同步信号量初始值0~N

• 生产者-消费者问题：共享有限缓冲区

我觉得empty是NumOfEmpty，full是NumOfFull，所以empty初始值为N，full初始值为0，这两个英文的使用让人理解困难
生产者-消费者问题解决的是共享资源的问题，在资源使用over的时候需要一者和另一者按顺序执行所以产生了信号量的应用，其中有三种情况参考ppt
signal（full）其实就是增加一个full的单位，那么消费者就可以去消费了那就是唤醒了消费者
signal（empty）就是增加一个空的单位，那么生产者就可以去往这个空的单位生产东西了

• 读者写者问题：数据读写操作

如果单纯的让读写互斥无法满足多个读者一起读！
此处其实共同的资源已经是个次要问题了，最关键的是能否用一个计数器来表明是否是第一个读者以及最后一个读者，这个计数器必须要用一个互斥的信号量来维护，所以临界区如图所示

• 哲学家就餐问题：资源竞争

现在有5个信号量分别是从ph[0]~ph[4]，初始值都是0
test字如其名就是测试他能不能拿筷子，如果左右哲学家都没吃饭那这个i就是有能力吃饭的
在test函数内部就V(ph[i])就是这个哲学家i的信号量变成1啦
然后开始P(ph[i])，就是看看这个哲学家的信号量有没有1，因为我们的大前提是这5个进程在并发运行
恰巧我们这个哲学家在资源竞争中运气好信号量变成1了，此时左右两个肯定变不成1了
所以他吃完之后要帮助旁边两个人测试下是否能吃，助推一把
整个过程就是这些进程都准备开始运行，实际上物理运行的时候会有人随机先走，这个人先走之后顺序也就定好了。

管程

一个管程定义了一个数据结构和一组操作（操作可以同步进程和改变管程中的数据）
应该如何理解管程
深入理解l操作系统的管程，进程，线程（一）

---