第一章 操作系统引论
★计算机操作系统是方便用户、管理和控制计算机软硬件资源的系统软件（或程序集合）。
1.OS的目标：有效性、方便性、可扩充性、开放性
2.OS的作用：1) OS作为用户与计算机硬件系统之间的接口；
★（用户使用计算机的三种方式：命令、系统调用、图标窗口）
2）OS作为计算机系统资源的管理者；
3）OS实现了对计算机资源的抽象。
3. OS发展过程：1）无操作系统的计算机系统
★2）单道批处理系统（单道、顺序、自动性）
★3）多道批处理系统（多道、无序、调度性）
动力：提高资源利用率和系统吞吐量
优缺：资源利用率高、 系统吞吐量大、平均周转时间长、无交互能力
4）分时系统（多路、独立、及时、交互性）
动力：用户的需求
5）实时系统（多路、独立、及时、交互、可靠性）
6）微机操作系统
4. ★★★OS基本特性：
1）并发：并行性（多处理器）并发性（双端口存储器、流水线技术）
进程：拥有资源独立运行的基本单位
2）共享：互斥共享（打印机、磁带机） 同时访问（磁盘）
并发导致的共享
3）虚拟：时分复用（虚拟处理机、虚拟设备）空分复用（虚拟存储器技术）
4）异步：（速度不可知）
5. ★★★OS主要功能：
1）处理机管理（进程控制、同步、通信、调度）
2）存储器管理（内存分配、内存保护、地址映射、内存扩充）
3）设备管理（缓冲管理 、设备分配、设备处理）
4）文件管理（存储空间的管理、文件目录管理、文件共享与安全）
5）用户接口（用户接口、程序接口）
6）现代OS新功能（系统安全、网络的功能和服务、支持多媒体）
第二章 进程的描述与控制
1.前趋图：有向无循环图
2.程序的顺序执行（单）特征：顺序、封闭、可再现性
3.程序的并发执行（多）特征：执行的间断、失去封闭、不可再现性
4.进程描述：是程序的一次执行，使程序能够正确地并发执行。
1）特征：动态性、并发性、独立性、异步性
2）★★三状态（画图）： 就绪（只差CPU）、执行（获得CPU）、阻塞
就绪（进程调度/时间片完）执行（I/O请求）阻塞（I/O完成）就绪
3）挂起：（交换技术）暂时不能运行的进程换出到外存，以腾出足够的内存空间，已具备运行条件的进程换入内存。进程被交换到外存，状态变为挂起状态。
4）★★五状态（画图）：执行（时间片完/调度）活动就绪（挂起/激活）静止就绪（无/释放）静止阻塞（激活/挂起）活动阻塞（无/请求I/O）
6）进程管理中的数据结构（进程控制块PCB）
程序段+相关数据段+PCB=进程实体
PCB 的作用就是将程序变成可并发执行的进程。PCB常驻内存
5.进程控制：通过原语来实现
1）原语：由若干条指令组成、用来实现某个特定操作的一个过程。常驻内存
2）★★原子操作：原语的执行具有原子性，不可分割的基本单位。
3）进程控制原语：创建create与终止、阻塞block与唤醒wakeup、挂起suspend与激活active
6. ★进程同步：多个相关进程在执行次序上进行协调，使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行上具有可再现性。
1）同步机制：用来实现同步的机制
2）两种形式的制约关系：互斥→间接制约关系（资源共享）同步→直接制约关系（合作）
3）临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。
临界区（互斥区）：在进程中涉及到临界资源的程序段叫临界区
4）★★★同步准则（使用互斥区原则）：空闲让进、忙则等待、有限等待、让权等待
7.信号量机制
1）整型信号量s:资源的数量 P操作（wait阻塞原语） V操作（signal唤醒原语）
2）★★★记录型信号量：
Value：用于代表资源数目的整型变量
进程链表List：用于链接所有等待进程
如果value初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。
3）AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。
8.信号量的应用
1）类型：互斥信号量、资源信号量
2）★★★利用信号量实现前趋关系：（根据图写出并发代码）
P1(){S1; signal(a); }
P2(){ wait(a); S2; signal(c); }
P3(){wait(b); S3; }
main(){
semaphore a,b,c,d,e,f,g;
a.value=b.value=c.value =0
cobegin(表示并发执行)
p1();p2();p3();
coend}
3）P.V操作必须成对出现，有一个P操作就一定有一个V操作。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。
9. 经典进程的同步问题
1）★★★生产者—消费者问题
int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n;
semaphore full=0;
void proceducer(){
do{
producer an item nextp;
wait(empty);
wait(mutex);
buffer(in)=nextp;
in=(in+1) % n;
signal(mutex);
signal(full);
}while(true); }
void consumer (){
do{
wait(full);
wait(mutex);
nextc=buffer(out);
out=(out+1) % n;
signal(mutex);
signal(empty);
consumer the item in nextc;
…
}while(true);
}
2）哲学家进餐问题
3）读者—写者问题
10.进程通信：
1）高级通信机制：共享存储器系统、消息传递系统、管道(Pipe)通信
2）进程通信：直接、间接
直接消息传递系统：对称寻址方式（提供对方标志）、非对称寻址方式（id）
间接通信方式（信箱通信）
3）★★★直接和间接通信两种方式的主要区别？
①发送和接收原语。
直原语：send(receiver,message),receive(sender,message)；
间原语：send(mailbox,message),receive(mailbox,message)；
它还需要提供有关信箱创建和撤消的原语。
②提供对方的标识符。
直要求发送双方显式地提供对方的标识符，如允许接受多个进程发来的消息，则可以是id；
间只需提供信箱标识；
③通信链路
直进程只需提供对方的标识符建立通信链路由系统自动完成，有且仅有一条通信链路；
间仅当进程共享某个信箱时，它们才有通信链路，且一条链路可对应多个进程，每对进程间也可以有多条链路。
④实时性。
直接通信通常只能提供实时通信；
间接通信则既可实现实时通信也可实现非实时通信。
11.线程：线程是进程中的一个实体，是独立调度和分派的基本单位。
1）线程是调度和分派的基本单位，而进程是拥有资源的基本单位。
2）线程控制块TCB ：控制和管理线程的信息
第三章 处理机调度与死锁
1. 处理机调度：对处理机资源进行分配。
2. ★★（判断）层次：高级（多道批）、低级（都必须）、中级（挂起）
3.共同目标：资源利用率、公平性、平衡性、策略强制执行
★ CPU利用率=CPU有效工作时间/ CPU有效工作时间+CPU空闲等待时间
批处理目标：平均周转时间短、系统吞吐量高、处理机利用率高
★平均带权周转时间W=1/n∑Ti/Ts
分时系统目标：响应时间快（首次产生）、均衡性
实时系统目标：截止时间的保证、可预测性
4.多道批处理系统：
1） 作业：用户提交给系统的一项相对独立的工作。
2）★★★（选择填空）先来先服务（FCFS）和短作业优先（SJF）调度算法
优先级调度算法（PSA）和高响应比优先调度算法
★响应比Rp=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间
5.进程调度方式：非抢占式、抢占式
★抢占式：优先权原则、短作业(进程)优先原则、时间片原则。
7.分时系统★轮转调度算法：基于时间片的轮转、FCFS
8.实时调度：最早截止时间优先EDF、最低松弛度优先即LLF
★松弛度=必须完成时间-其本身的运行时间-当前时间
9. ★★死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
（1）★★产生必要条件：互斥条件、请求和保持条件、不抢占条件、循环等待条件
（2）★★处理死锁方法：预防死锁、★避免死锁、检测死锁、解除死锁
10. ★★★银行家算法
Need［i,j］=Max［i,j］-Allocation［i,j］
1） T0时刻的安全性
2） 检查：① Request1()≤Need1()② Request1()≤Available1() 不满足则等待
满足则暂修改Available, Allocation1和Need1向量
3） 检查此时系统是否安全，安全则分配资源，不安全则不分配
第四章 存储器管理
★存储器管理任务：内存的分配回收、存储的保护、存储容量的扩充、地址映射
1. ★ 程序的装入：绝对装入、重定位装入、动态运行时装入
绝对：按程序逻辑地址，将程序和数装入内存指定的地方。用于单道操作系统
★重定位（静）：必须进行地址映射（程序装入时），将逻辑地址转换为物理地址。
动态：将逻辑地址转为物理地址（程序执行时）重定位寄存器：保存程序在内存中起始地址。
2. 连续分配存储管理方式：单一连续、固定分区、动态分区、动态可重定位分区分配
动态分区：1）基于顺序：FF、NF、BF、WF
2）基于索引：快速适应（248）、伙伴系统（2^m）
动可重定：1）紧凑
2）动态重定位（紧凑后都需重定位，为提高效率）
3. 离散分配存储管理方式：分页、分段、段页存储管理方式（全部装入内存的）
分页：1）★★逻辑→物理 页号P=逻辑地址/页面大小 位移量W=逻辑地址mod页面大小
2）★★处理机每次存取指令或数据须访问 2 次物理内存
3）高速缓冲寄存器（快表）：保存当前进程最近使用的一组页表项
4）★内存的有效访问时间（EAT）EAT=t+t=2t EAT=a*λ+（1-a）*（t+λ）+t
5）两级和多级页表
分段：1）为什么引入：可分为若干段、相对独立的逻辑单位、动态链接成大程序
2）由若干逻辑段组成，程序逻辑地址由段号和段内偏移量决定。
分页VS分段：
1）页是信息的物理单位，段是信息的逻辑单位
2）页的大小固定由系统决定，段的长度不固定
3）页的用户程序地址空间是一维的，只需一个记忆符；
段的用户程序地址空间是二维的，需要段名和段内地址
段页：用分段方法来分配和管理逻辑地址空间，用分页方法来管理物理存储空间（物页）
1）采用分段的方法组织用户程序，采用分页方法分配和管理内存。三次访问内存
2）段号+段内页号+页内地址
对用户而言，仍然是二维编址。对系统而言，则是三维编址
第五章 虚拟存储器（进程部分装入）
1.基本概念：具有请求调入和置换功能，从逻辑上实现对内存容量加以扩充的存储器系统。
2.特征：多次性、对换性、虚拟性
3. 实现虚拟存储的关键技术（基于离散分配存储器）：分页、分段请求系统
4. ★请求分页系统（分页技术+请求调页、页面置换）
1）页表机制：页号、物理块号、状态位P、访问字段A、修改位M、外存地址
2）★★地址变换过程：要访问存在位为0 → 向CPU发缺页中断 → 保留CPU环境 → 分析中断原因转入中断程序 → 内存未满启动磁盘I/O → 将所缺之页调入内存 → 修改页表
缺页率f=F（访问失败从外调入次数）/A（访问成功+失败）
3）★★★页面置换算法：最佳置换（换最远访问） 先进先出（换最前进入）最近最少使用、clock置换算法、页面缓冲算法PBA
5. 请求分段系统（分段技术+请求调段、分段置换）
1）特有项：增补位
2）地址变换过程：访问[S][W] →w<=字段长（否则分段越界中断处理）→符合存取方式（否则分段保护中断处理）→段S在主存（否则缺段中断处理）→修改访问字段为1 →形成访问主存地址（A）=（主存始址）+（位移量w）→访问[S][W]