一、操作系统引论

操作系统基本特征：虚拟技术，时分复用(虚拟处理器，如CPU、设备，如物理I/O设备)和空分复用(虚拟磁盘，如一个硬盘分4个卷并对应C、D、E、F四个逻辑驱动，虚拟存储器，利用存储器的空闲空间来存放其他程序，以提高内存利用率)。调度有高级（作业）、中级及低级（进程）调度。一个应用程序（源程序）经过编译后，通常会形成若干个目标程序；这些目标程序再经过链接便形成了可装入的程序，这些程序的地址都是从“0”开始的，程序中的其他地址都是相对于起始地址计算的。

二、进程管理

程序段、相关数据段和PCB三部分构成了进程实体。因为PCB经常被系统访问，故应常驻内存，存放在操作系统中专门开辟的PCB区内，如Linux用task_struct数据结构来描述PCB，Windows用一个执行体进程块(EPROCESS)来表示进程对象的基本属性。PCB的组织方式，可是链接方式与索引方式。 信号量有：整型（忙等）、记录型（让权等待）、AND型（不分配或同时分配）、信号量集（一次可多个P、V操作）。管程（Monitors）：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程与进程都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据，如消息队列，进程用于系统并发性，管程用于解决共享资源的互斥使用，管程是被动工作方式（被进程调用），进程是主动。条件变量，因不能原因被阻塞，管程对每个条件变量都予以说明，如x.wait表正在调用管理的进程因x条件需要被阻塞或挂起。 由于进程间通信所交换的信息量少而被归结为低级通信。进程间通信方式：共享存储器，消息传递（直接通信、间接通信，用信箱），管道（连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件），以字符流形式写入、读取文件。进程通信时同步方式两者都阻塞，发不、接阻塞，也可两者都不阻塞（只有发满了发才阻塞，只有空接才阻塞）。 进程是资源拥有者，在创建、撤消和切换中系统必须为之付出较大的时空开销，分开即作为调度和分派的基本单位，不同时作为拥有资源的单位。同一进程中线程切换不会引起进程切换，而从一个进程的线程切换到另一个进程的线程则会引起进程的切换。为减少线程被阻塞的机会，有的系统可用Trylock，当mutex处于开锁状态会返回成功状态码，当失败，不会阻塞该线程而只是返回一个指示失败的状态码。 条件变量：只用mutex可能导致死锁，条件变量与互斥乐一起使用即在创建一个互斥锁时便联系着一个条件变量，线程首先对mutex执行关锁操作，若成功便进入临界区，若在临界区里申请的资源处理忙碌状态则开锁并阻塞自身，以避免死锁。对于设置了用户级线程的系统，其调度仍是以进程为单位进行的，如A进程包含一个用户级线程，而B中有100个，则A中线程运行时间将是B中各线程的100倍，如系统中设置的是内核支持线程，则调度是以线程为单位的。TCB线程控制块。

三、处理机调度与死锁

对批量型作业而言，通常要经历作业调度（高级调度）和进程调度（低级调度）两个 过程后才能获取处理机，为提高内存利用率，往往还有中级调度。作业是一个比程序更广泛的概念，它不仅包含通常的程序和数据，而且还应配有一份说明书，系统根据该说明书来对程序的运行控制，在批处理系统中，是以作为为基本单位从外在调入内存的，同样有JCB。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量，使暂不能运行的进程不再占用内存，而将它们调至外存上等待（挂起状态），中级调度实际上就是存储器管理中的对象功能（调入、调出内存、外存），高级调度也称长程调度，因为它发生的周期较长。带权周转时间为作业的周转时间除以系统为它提供服务的时间。调度算法：1.先来先服务FCFS（有利于长作业不利于短作业，适合CPU繁忙型作业，不适合I/O繁忙型作业）、2.短作业（进程）优先SJ(P)F（对长作业不利）、3.1.高优先权优先调度算法FPF（可静态、动态优先权，随着等待时间增长，优先级提高，而对当前正在执行的如长作业，随着执行时间的增加，优先级降低），3.2.高响应比优先调度算法，等待时间与服务时间之和就是系统对该作业的响应时间，响应比为响应时间除以要求服务时间，如等待时间同，服务时间越短其优先权越高有利于短作业，当服务时间相同，作业优先权决定于等待时间，因此它是FCFS，对长作业，其优先级随等待时间的增加而提高。4.基于时间片的轮转调度算法RR(Round Robin)。多级反馈队列调度算法不必事先知道各进程所需的执行时间，目前公认的一种较好的进程调度算法，设置多个就绪队列，第一队列优先级最高时间片最小，后面依次优先级降低时间片增大，当新进程进入内存后先放在第一队列尾按FCFS调度，如执行时能在一个时间片完成即可撤离系统，如果完不成就到第二队列，依次下次，直接到最后一个队列按时间片轮转运行，采用抢占式。系统在安全状态下一定不会发生死锁，而不安全状态不一定会发生死锁。银行家算法避免死锁，如果检测到有就不分配，用资源分配图检测死锁，是已经分配好再检测是否会形成死锁。死锁解除方法：剥夺资源、撤销进程。

四、存储器管理

寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质6层，前四层属于操作系统存储管理，掉电后消失，后两层属设备管理，可设多级缓存。调整缓存是一种物理设备，而磁盘缓存并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存的存储空间，来暂存从磁盘中读出或写入的信息。目标模块装入内存方式：绝对装入、可重位装入、动态运行时装入。绝对装入只能将目标模块装入到内存中事先指定的位置，在多道程序环境下，编译程序不可能预知编译的目标模块应放在内存的何处，因此只适用于单道程序环境。在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序的其他地址也是相对于起始地址计算的。可重定位的地址变换在是装入时一次完成的，以后不再改变故称为静态重定位。在运行过程中程序在内在中的位置可能经常改变，此时应用动态运行时装入方式。动态运行时的装入程序在把装入模块装入到内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是推迟到程序真正要执行时才进行，需要重定位器的支持。程序的链接有：静态、装入时动态、运行时动态。静态链接的每个调用都要有一个拷贝，而动态只需要一个。分区分配算法：首次适应算法FF(first fit)，循环首次适应算法(next fit)，最佳适应算法(best fit)，最坏适应算法(worst fit)，快速适应算法(quick fit)。伙伴系统。在分页存储管理中，如果不具有页面对换功能，则称为基本分布存储管理方式或纯分布存储管理方式，它不具有支持实现虚拟存储器的功能，要求把每个作业全部装入内存后方能运行。分页存储是将一个进程的逻辑地址空间分成若干大小相等的片，而内存分成物理块或页框。页内碎片。页面大小应为2的幂，通常512B~8KB。20位页号，12位页内地址。计算页号与页内地址时除以及取模页大小页表实现页号到物理块号的转换。页表大多驻留在内存，在系统中只设置一个页表寄存器PTR(Page-Table Register)，其中存储页表在内存的起始地址和页表长度，平时进程未执行时，页表的始址和长度存放在本进程的PCB中，调度时才装入页表寄存器（只有一个）。为提高地址变换速度，在地址变换机构中增设一具有并行查寻能力的特殊高速缓冲寄存器，又称联想寄存器或快表，TLB(Translation Lookaside Buffer)，用以存放当前访问的那些页表项。对于要求连续内存空间来存放页表的问题，可利用将页表分页，并离散地将各页面分别存放在不同的物理块中的办法来解决，加外层页表。 分页为了提高内存利用率，分段是为了满足程序员在编程和使用，每段从0开始，并有自己的名字和长度，逻辑地址是由段名和段内偏移量决定的。分段管理中，整个作业的地址空间由于分成多个段，因而是二维的，段号与段内地址各16位。段表中有段在内存的起始地址和段的长度。同样需要两次访问内存，也可增加联想存储器，由于一般段比页大，需要的联想存储器也相对少。页是信息的物理单位，为提高内存利用率，段是信息的逻辑单位，为满足用户。段页式需要三次访问内存，第一次访问段表，找到页表的始址，第二次访问页表，加其中的页内地址找到指令或数据的物理地址，第三次访问所得内存取指令或数据，也可增加高速缓冲寄存器。虚拟存储器是指具有请求调入功能和转换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。请求分页系统每次调入和换出的基本单位是长度固定的页面，而段的长度可变，因此页是常用的实现虚拟存储器的方式。页表中要增加状态位、访问字段、修改位、外存地址等信息。对换区采用连续分配方式。 最佳转换算法，先进先出页面置换算法，最近最久未使用(LRU,Least Recently Used)置换算法（需要的硬件支持：使用移位寄存器或栈（当再次访问时弹出并放到栈顶，移出时移出栈底的），LRU需要较多的硬件支持，可用其近似算法Clock。简单Clock置换算法，又称最近未用算法NRU(Not Recently Used)，增加访问位，改进型Clock置换算法，再增加转换代价即修改位。其它置换算法：最少使用转换算法(LFU:Least Frequently Used，也可用移位寄存器实现)。请求分段存储管理方式。分段为了共享及佑护，段可以共享，在系统中配置共享段表，对于保护，有越界检查及存取控制检查（只读、只执行及读/写）。

五、设备管理

计算机系统中的各部件如CPU，存储器及各种I/O设备都是通过总线来连接的，总线有ISA、EISA、VESA、PCI等，局部总线：指将多媒体卡、高速LAN网卡等从ISA总线上卸下来，通过局部总线直接连接到CPU上，使之与高速总线相匹配，而打印机、CDROM等仍挂在ISA总线上，有VESA、PCI。直接存储器访问(DMA)I/O控制方式，可比中断驱动I/O、程序I/O更高效，是以块为方式。逻辑设备表(LUT,Logical Unit Table)实现逻辑设备名映射到物理设备名。多道程序技术将一台物理CPU虚拟为多台逻辑CPU，从而允许多个用户共享一台主机，SPOOLing技术是将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。当系统引入多道程序技术后，可利用其中一道程序模拟脱机输入时的外围控制机功能，把低速I/O设备上的数据传送到调整磁盘上，再用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上，这样便可在主机的直接控制下实现脱机输入、输出功能，此时的外围操作与CPU对数据的处理同时进行，把这种在联机情况下实现的同时外围操作称为SPOOLing(Simultaneaus Periphernal Operating On Line)或称假接机操作，如可用此技术共享打印机。磁盘有多个磁面，每个磁盘有多个同心圆磁道，每个磁道又有多个扇区，一个扇区又叫一个盘块。访问磁盘很慢，包括寻道时间如5-30ms，旋转延迟时间，即指定扇区移动到磁头下时间如50-100ms，传输时间，把数据从磁盘读出或向磁盘写入数据所经历的时间，这块占相对较小的时间，因此数据要集中放。磁盘调度的目标是使平均寻道时间最短，先来先服务(FCFS)，最短寻道时间优先(SSTF,Shortest Seek Time First)（可能导致饥饿），扫描(SCAN)算法（不仅考虑距离，还考虑磁头当前移动方向），即电梯调度算法，循环扫描算法(CSCAN)，NStepSCAN避免磁臂粘着，FSCAN是N步SCAN的简化，只分成2个队列。 磁盘的调整缓存并非实际存在的在内存和CPU之间所增设的一个小容量高速存储器，而是利用内存中的存储空间来暂存从磁盘中读出的一系统盘块中的信息，因此是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块；置换算法，当高速缓存区满时，也要换出也可采用LRU，NRU，LFU等；通常每执行一条指令便可能访问一次联想存储器，其访问频率与指令相当，而高速缓存的访问频率仅与磁盘I/O相当。其他提高磁盘I/O速度的方法：提前读，延迟写，优化物理块分布即尽量分配在同或相近磁道。 廉价磁盘冗余阵列(RAID,Redundant Array of Inexpensive Disk)，交叉存取，把大文件分多个块并存储到多个盘，需要读取时同时读取多个盘。

六、文件管理

文件逻辑结构又称为文件组织，有有结构文件（记录式文件）和无结构文件（字符流文件，流式文件），物理结构又称存储结构。外存分配方式可用连续分配（占连续空间）、链接分配（对隐式找中间某个效率低，对显示可能占用更多空间）和索引分配。一个物理硬盘可以划分为多个卷，一个卷也可由多个物理磁盘组成，如RAID磁盘阵列。对FAT12，其表项为12位，最多有4096个表项，若以盘块为基本分配单位，每个盘块（扇区）大小为512字节，每个磁盘分区容量为4096512B=2MB，同时一个物理磁盘支持4个逻辑磁盘分区，磁盘最大容量为8M，如改成以簇为分配单位（一个或多个扇区成一个簇），可增大磁盘容量，但会产生大的簇内零头，且文件名受8+3（文件名+扩展名）限制。表长度为16位为FAT16，后来对FAT16进行了扩展，通过一个长文件名占用多个目录项的方法，使得文件名长度可以长达255个字符，这种扩展的FAT16称为VFAT。FAT32每一簇在FAT表中表项占据4字节(2^32)，每个簇固定4KB（较小值产生较小碎片），可管理的磁盘容量：4KB2^32=2TB。FAT32缺点：文件分配表过大，运行速度慢，且其卷至少有65537个簇，因此不支持容量小于512M的分区，且单个文件长度不能大于4G（应该和表项为32位有关），且不能向下兼容。 NTFS使用64位磁盘地址，理论上可支持2^64次方字节的磁盘分区，且单个文件名达255个字符，有容错、加密、压缩等功能，也是以簇为基本单位，一个文件占用若干簇，一个簇只属于一个文件，其簇的大小称为卷因子 ，对簇的定位采用逻辑簇号LCN和虚拟簇号VCN进行的，NTFS可识别FAT，反之不行。链接分配不能高效直接存取，使用FAT时由于事先不知道使用的是哪个盘块，因此把将整个FAT调入内存，占用更多的空间，索引需要花更多的外存空间去存储索引块，对大文件，可采用多级索引。文件控制块FCB，用于描述和控制文件的数据结构。多级目录，先找到对应索引再找索引对应盘块，一层层向下寻找。文件存储和内存分配类似，也可连续或链表，也可采用位示图法，用一位来对应磁盘中某个盘块的使用情况，所有盘块都有对应位。 空闲表法和空间链表法都不适用于大型文件系统，因为其表太长，在Unix中用成组链接法，这是将上述两种方法相结合而形成的一种空间盘块管理方法；其中空闲盘块号栈用来存放可用的一组空闲盘块的盘块号（最多100个）以及栈中尚有的空间盘块号数N，N还兼作栈顶指针用，栈是临界资源，要加锁 https://blog.csdn.net/ajay666/article/details/73569654。 文件共享可用基于索引结点的共享方式（各用户、进程目录项中不存储具体文件内容，同时指向公用索引）和利用符号链实现文件共享（只有文件主才拥有指向其索引结点的指针，共享该文件的其他用户只有该文件的路径名，缺点是当其他用户去读共享文件时系统是根据给定的文件名，逐个名去查找目录直到找到该文件的索引结点，因此可能会多次地读盘）。

七、操作系统接口

操作系统的接口有用户接口和程序接口。UNIX为用户提供了实时和非实时两种通信方式，分别是write和mail。 CPU指令可分为特权指令和非特权指令。 中断可分为外中断和内中断，外中断指由于外部设备事件所引起的中断，如磁盘、打印机中断等，内中断则由于CPU内部事件所引起的中断，如程序出错（非法指令、地址越界）、电源故障等，内中断(trap)也被译为“捕获”或“陷入”，由于系统调用引起的中断属于内中断，因此把由于系统调用引起中断的指令称为陷入指令。

八、网络操作系统

NOS：Network Operating System。为传输更快，及WAN中使用了光缆作为传输信道，大大降低了传输的误码率，可采用简单的差错检测机制来提高信息的传输速率，于是出现了帧中继。网桥工作在数据链路层，将两个LAN连起来，根据MAC来转发帧，可看作一个“低层的路由器”，能互连两个采用不同数据链路层协议、不同传输介质与不同传输速率的网络，功能有：帧发送和接收、接收与发送缓冲、协议转换。网关用于互连异构型网络，一般在网关中至少要进行网络层、数据链路层及物理层的协议转换，如连接LAN与WAN。对于LAN其数据链路层分为：逻辑链路控制子层LLC（Logical Link Control）和介质访问控制子层MAC，使得LAN获取了LLC规程与具体LAN所采用的介质访问方法与网络形式无关这一理想特性，LLC子层提供了无连接和面向连接两种类型的服务。

九、系统安全性

对称加密加密和解密往往使用相同的密钥，或者知道加密密钥Ke很容易推导出解密密钥Kd，非对称加密则相反，可以将其中一个密钥公开而成为公开密钥。基本加密算法有易位法和置换法。对称加密算法如DES(Data Encryption Standar)。在其余行业许多业务都要求在单据上加以签名或加盖印章，以证实其真实性，备日后查验，在计算机网络传送报文时，可将公开密钥法用于电子（数字）签名来代替传统的签名，如发送者A用私用密钥对明文P加密后发送给B，B可利用A的公开密钥对P解密。认证机构CA(Certification Authority)为公开密钥发放一份公开密钥证明书（数字证明书），用于证明通信请求者的身份，如同司机的驾照，学生的学生证等。可在物理层和数据链路层中采用链路加密方式。

十、UNIX系统内核结构

信号与中断都采用异步通信方式，而中断有优先级，信号没有，信号是在用户态下运行的，且对信号的响应通常有较长的时间延迟，而中断则在核心态下运行，响应及时。
图书（已加目录）：链接：https://pan.baidu.com/s/12V2gHzsGmUll_ep-R3S3yw 密码：an00