进程管理
进程与线程
- 进程概念：就是一个具有独立功能的程序的一次动态执行。
进程的状态与转换：
进程的三个基本状态是就绪、执行、阻塞。就绪态到执行态的转换只需要cpu调度即可，阻塞态只能转为就绪态不能直接转为执行态。执行态如果时间片用完就转成了就绪态如果等待某事件发生就转成阻塞态。如果在这三个基本状态下进程发生挂起行为则从就绪态转为挂起或称静态就绪，从执行态转也转为静止就绪，从阻塞态转为静止阻塞。
进程控制：
进程控制就是对系统中所有进程从产生到消亡实施管理，由OS的内核实现，内核是通过调用各种原语来实现的。有进程创建原语，进程撤销原语，阻塞原语，唤醒原语等。
进程组织：
一个进程是由三部分组成的，程序、数据、进程控制块(PCB)。这三个合起来也称为进程实体。其中进程控制块是进程动态特性的集中反映，创建进程则产生pcb撤销进程就要收回pcb，pcb表项的个数是确定的，所以一个系统中的进程不是无限多的。
进程控制块很重要所以详细写点，它包含的内容很多，有
（1）进程描述信息：进程标示符（每个进程有一个唯一的号）和用户标示符（每个进程属于某个用户）
（2）进程控制信息：进程当前状态，如果是阻塞的要再pcb中说明阻塞原因，进程优先级、代码执行入口地址、程序外存地址、各种计时信息(程序执行时间，页面调度情况)
（3）资源管理信息：用于说明有关虚拟地址空间的现状，打开文件的列表，和使用的输入输出的信息。
（4）CPU现场保护结构：保存各种寄存器的值。
系统中pcb数目众多，他们是怎么组织起来的有链接方式和索引方式两种：链接方式就是形成就绪队列，阻塞队列等，还要对就绪队列按进程优先权排列。索引方式是建立几种状态的索引表，索引表记录pcb的地址。
进程通信
进程的互斥与同步交换的信息量较少，所以称为低级通信方式。进程之间以较高的效率传送大量数据的通信方式叫高级通信方式分为三大类：
(1) 共享存储系统：就是共享内存。。其实编程没编过我对这些都理解不深刻。
(2) 消息传递系统：直接通信(send和receive通信命令直接发给接收进程)间接通信(信箱通信就是把消息放信息里让另一个进程取)。
(3) 管道通信。相当于一个队列形式的一个进程在管道尾写，另一个进程在管道头取，管道分为无名管道和有名管道。无名管道是用pipe函数创建的，只能用于子进程之间的通信，有名管道用mkfifo函数创建用于任意两个进程之间通信，对管道的操作相当于对文件的操作比如open函数打开管道close函数关闭管道等。
线程概念与多线程模型
有了线程之后，处理机调度的单位就成了线程。而资源的分配还是以进程为单位。一个进程的多个线程是公用代码数据和文件资源的，但是不同的线程有不同的寄存器和栈。线程之间的通信比进程通信方便因为有好多资源共用，线程的切换也比进程的切换简化的多。
处理机调度
调度的基本概念
调度分为作业调度，进程调度，和中级调度。作业调度就是将外存上选中的作用分配内存，创建进程等批处理中几分钟调度一次，其他系统基本不需要作业调度，进程调度就是决定就绪队列中哪个进程获得处理机。中级调度主要功能是对换，即将内存中某些就绪或阻塞的进程交换到外存对换区，主要用来进行内存管理和扩充。
调度的基本准则：
CPU使用率要高，周转时间，等待时间等要小等等。周转时间等于等待时间加响应时间，平均周转时间就是各个作业的周转时间取平均值。带权周转时间等于周转时间除以响应时间，平均带权周转时间就是各个作业的带权周转时间的求平均。
调度方式：
非剥夺式和剥夺式两种。剥夺式是有抢占原则的，一般是按优先权原则，短作业优先原则和时间片原则这三种之一进行抢占的。
典型调度算法
先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法(是FCFS和SJF的折中 响应比=等待时间+要求执行时间的和然后除以要求执行的时间)；多级反馈队列调度算法(多个就绪队列赋予不同的优先级优先级越高时间片越短，新进程加入后 先放第一个队列一个时间片完成不了就往下一个优先级的队列末尾放以此类推)。
进程同步
进程同步的基本概念
多个进程中发生的事件存在某种时序关系，必须协同工作，相互配合，以共同完成某一项任务。同一种进程是互斥关系，不同的进程是同步关系。
实现临界区互斥的基本方法
软件实现方法；硬件实现方法。这时候还不是信号量的那种软件实现而是程序员自己定义的，比如设置一个turn让他等于进程编号，从而使进程轮流进入临界区。还有设置一个标志位flag为0表示其他进程未进入临界区等。硬件实现方法不懂。同步机制只要实现四大准则就可以实现互斥，这四大原则就是:空闲让进、忙则等待、有限等待，让权等待。
信号量
信号量是操作系统提供的管理公有资源的手段，即PV操作。对于独享设备有驱动程序做PV操作。
p操作的过程是：s=s-1；if(s<0){进入等待队列，自己阻塞进程}
v操作的过程是：s=s+1；if(s<0){从等待队列取一个进程；取出的进程进入就绪队列，当前进程该干嘛干嘛}
pv原语不能次序错误，而且必须成对出现。信号量的定义是semaphore mutex；经典同步问题有生产者-消费者问题；读者-写者问题；哲学家进餐问题。
死锁
死锁的概念
多个进程并发执行共享资源时，由于独占资源被其他进程占用，且其他进程遇到同样的问题，于是导致出现环形等待资源的情况，所有每个进程都在等待无法执行这就是死锁。
- 死锁处理策略：有四种方法预防死锁、死锁避免、死锁检测、解除死锁。
- 死锁预防：就是破坏产生死锁的任何四个必要条件之一。死锁的四个必要条件是互斥、请求和保持、不剥夺、和环路等待。
死锁避免：
就是系统在给某进程分资源时要保证一个安全顺序，系统安全状态一般用银行家算法。银行家算法即系统试探着把资源分配给进程pi后修改可用资源的数目，还有每个进程已分配的资源数目跟每个进程还需的资源数目，然后执行安全性算法，如果此次资源分配后，系统处于安全状态才正式分配给进程资源。否则试探分配作废，让进程pi等待。注安全性算法即设置两个向量。一个work向量一个finish向量，开始时work=available，然后找到一个need小于work的进程，给该进程分配资源后使work=work+allocation ，finish=true。然后循环直到所有进程的finish状态都为true则系统处于安全状态。
死锁检测和解除：
就是检测到发生死锁之后，再采取手段解除死锁，有剥夺法，回退法和杀死进程这三种解除法。
内存管理
内存管理基础
内存管理概念
程序装入与链接；逻辑地址与物理地址空间；内存保护。内存管理的任务是记录内存的使用和空闲状态，在进程需要时为进程分配内存，用完后释放内存，已被进程使用的内存区域如何保护，如何在内存不足支持进程运行的情况下进行内外存交换。
程序的装入：指从外存装载在内存
在读入内存时需要对地址部分做调整，即重定位装入，该工作有OS专门的装载程序负责。重定位分为静态与动态重定位，静态重定位指在程序装入内存时由OS进行浮动项的定位，以后不再变化，每个可执行程序的头上有浮动项说明表，表示地址的浮动项。动态重定位是指在装入内存时不进行装配，直接将程序装入内存，定位问题由系统提供的硬件解决，需要借助硬件支持。
交换与覆盖
交换是指进程或作业在内存与外存之间的动态调度，当内存紧张时系统按某种策略将某些进程暂时移到外存，把外存某些进程换进内存占据前者的内存区域，外存分为文件区和交换区中其对换区是连续的。
覆盖是把程序划分为若干个功能相对独立的程序段。这些程序段是不会同时执行的因此可以共享同一块内存区域，若干独立的程序段叫覆盖段。当有关程序段的前一部分执行结束，把后面属于同一覆盖段的程序段调入内存，覆盖前面的程序段，相当于内存扩大了。但是增加了程序员的负担。因为程序员要向系统指明覆盖结构而且要求作业各模块之间有明确的调用结构。
连续分配管理方式
单一连续分配；分区分配。单一连续分配是指内存分为两个区域：系统区和用户区，应用程序装入到用户区可使用用户区的全部空间，这种只适合单用户单任务的OS。分区分配时把内存划分为若干个连续分区。分区分配又分为固定分区分配和动态分区分配，固定分区分配就是分区的大小是固定的，可以相等也可以不等。采用分区表记录分区的大小和使用情况。分区表的数据项有分区号，大小，起止，和状态。动态分区分配说白了就是用多少分多少。一般分区都是从地址低端开始的，动态分区按寻找空闲分区的方法的不同又分为1、首次适应法2、下次适应法3、最佳适应法。
首次适应算法是按分区的先后次序(即从低地址开始)，从头查找，找到符合要求的第一个分区，特点：较大的空闲分区被保留在内存高端，每次分配时查找时间的开销会增大。
下次适应算法是从上次分配的分区开始查找，按分区的先后次序找，特点空闲分区分布的更均匀，但较大的空闲分区不易保留。
最佳适应算法是每次找与其容量最接近的空闲分区，为了方便将按空闲区大小链接起来递增排列利用了好多外碎片。
动态分区还有动态重定位分区分配就是在动态分区的情况下，当剩余零头分区的和超过新任务要求的分区但是连续的空闲区容量却达不到新任务要求时进行紧凑的行为。就是将各个占用分区向内存一端移动，在另一端将空闲分区合并成一个空闲分区。
非连续分配管理方式
包括分页管理方式；分段管理方式；段页式管理方式。当然一个操作系统只使用其中一种管理方式。
页式管理中将逻辑地址空间分成页，物理内存划分为固定的同样大小的(硬件设计时也框的大小已经确定)页框(块)，程序可加载在不连续的块中。程序中逻辑页号和内存中物理页号的对应表叫页表，每个进程一张。系统中有一张页框使用表。系统中还有一张请求表里面存的是进程id和该进程页表地址的对应关系。逻辑地址像物理地址转换的过程：逻辑地址由两部分组成：页号和页内地址。以该页号在页表中查找对应的物理页号，然后和页内地址拼起来就是物理地址。
分段存储的段表是由段号，段长，段基址组成。由逻辑地址转换为物理地址的过程：逻辑地址由段号段内位移组成，根据段号在段表中查找段基址然后加上位移量就是在内存中的位置。
段页式存储管理的逻辑地址由段号，段内页号，页内偏移地址组成。每个进程一张段表。段表由段号，页表大小(包含几个页表)，页表首址组成。逻辑地址到物理地址的转换过程：由段号在段表中查找到对应的页表首址再与逻辑地址的页号相加，即是对应页表中该页号的对应项，将块号和页内地址拼接即求的物理地址。
分页中控制寄存器中存的是页表地址和长度，分段中控制寄存器中存的是段表使址和段表长度，段页式中控制寄存器中存的是段表始址和段表长度，根据寄存器里的值才能得到页表，段表。
虚拟内存管理
虚拟内存基本概念
借助于硬盘，一个进程部分调入内存即可运行的情况下，用到哪个程序段将外存的调入内存，对用户来说是透明的任务内存足够大到可以执行自己的程序这个思想便是虚拟内存的思想，在虚拟存储管理下，用户的逻辑地址空间可远远大于物理空间。
请求分页管理方式
即在简单页式存储管理的基础上，增加了请求调页和页面置换功能。在请求分页中的页表比简单页式存储的页表要多一些字段，包括页号、物理块号、状态位，访问字段、修改位、保护位、外存地址。状态位用来区分该页是否在内存，修改位用来表示该页在调入内存后有没有被修改，保护位表示该页是否可以修改，外存地址表示它在磁盘上现在存的位置，还有一个访问字段表示最后一次访问到现在的时间间隔用于页面置换算法的。
页面置换算法
包括最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；时钟置换算法（CLOCK）。
最佳置换算法：选择未来最常时间里不使用的页，不能实现，因为系统不会预估未来。
先进先出：选择建立最早的页面置换，但是如果这个页经常使用，那就会被反复调入和调出，会出现随着页框增多而中断次数反而增加的现场也称为Belady异常。
最近最久未使用LRU算法：最近最久没有使用的页面，相当于访问到一个把他排队尾最后出，慢慢的队头就是最近没使用的页面淘汰队头即可。
CLOCK置换算法：是LRU和FIFO的折中。也叫二次机会算法，
页面分配策略
保证进程能运行的最小页框，固定分配：给每个进程分配固定数目的页框；可变分配是预分配给进程一定数目的页框，OS控制一定数量的空闲页框，在进程执行过程中，发生缺页时os就分配给该进程一个空闲的页框。
抖动
抖动现象和工作集。工作集指进程在执行过程中所访问页面的集合。驻留集指虚拟页式管理中给进程分配的物理块数。引入工作集目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小。抖动是指内存和外存进行频繁的调入调出，产生这种情况一是因为系统进程数越来越多。每个的驻留集越来越少，因此缺页中断越来越多，这样就会使cpu使用率越来越低，二是因为不合适的调页算法。
请求分段管理方式
此时的段表比简单分段式管理的段表多了几项包括：段名，段长，段基址，存取方式，访问字段，修改字段，存在位，增补位，外存地址。存取方式指的是：执行、只读、读/写；存在位跟分页管理中的状态位是一样的，增补位指示运行过程中是否进行过动态增长。
文件管理
文件系统基础
文件概念
文件是具有文件名的一组相关元素的集合.可分为有结构文件和无结构文件,有结构的文件被看成事由一组记录组成(学过数据库都知道记录是有若干相关的数据项 组成),无结构的文件即流式文件,无格式.
文件结构
文件结构分为逻辑结构和物理结构:
文件的逻辑结构有三种: 顺序文件；索引文件；索引顺序文件。
(1)顺序文件，其记录是按某种顺序排列所形成的,比如按存入时间的先后或关键字排列.对定长记录方便直接存取,但对变长的记录,就得从第一条的长度一直加到第 n条才能知道记录的首址.
(2)索引文件，记录在文件中的位置由索引表来指向，其实是按某个记录键来确定位置的,而索引表本身是定长的顺序文件.所以给定关键字后就可以在索引表中折半 查找相应的记录在哪.索引项是由记录的首址和长度构成的.
(3)索引顺序文件, 将顺序文件中的记录先分为组，为顺序文件建立一张索引表，在索引表里为每组中的第一个记录建立索引项，记录在文件中的位置由索引表和顺 序来决定.
文件的物理结构也有三种:连续分配方式,链接分配方式,和索引分配方式.
(1)连续分配:使得访问速度快但它要求存储空间是连续的而且必须事先知道文件的大小才能将文件存储到外存.
(2)链接分配方式:将属于一个文件的多个离散盘块链接成一个链表这样所形成的一个物理文件称为链接文件.而链接分配又分为隐式链接和显示链接.隐式链接就是在该文件的离散物理块中,下一个物理块的地址由前一个物理块给出.而每个文件的第一个物理块和最后一个物理块是存储在文件目录项中的…显示链接是把用于链接文件的各个物理块指针全存放到一张链接表中,每个FAT表项存的是本物理号对应的下一个物理号是什么,一个磁盘只有一张这个表.叫做FAT文件分配表. 凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的FCB的物理地址字段中.
(3)索引分配方式:链接分配方式需要把FAT都调入内存才能保证一个文件完整的被找到,而且一个个像下查找效率不高,索引方式为每个文件分配一个索引块,把分配给该文件的所有盘块号都记录在该索引表中,将指向该索引块的指针存入FCB中.索引分配还分为单级多级和混合索引分配方式.
至于逻辑结构和物理结构的区别. 逻辑结构是指每个记录在文件中的位置,而物理结构为逻辑结构服务,指文件在外存上存储时，分配方式要保证文件在逻辑上一致而且检索效率还有达到最高的结构.
- 目录管理
(1)从文件管理的角度看,文件时由文件控制块FCB和文件体组成的,文件控制块保存文件的属性信息基本包括文件名,文件结构,文件物理位置,控制信息(存取权限),管理信息(建立/修改日期等等).
(2)目录是由文件说明即FCB的集合构成的.还有一种目录的组成由于每次检索文件是按名检索的,索引把整个由文件说明构成的目录调入内存是一种浪费,因此索引结点方式就诞生了,即将文件名和文件描述信息分开,将文件描述信息单独形成一个称为索引结点的数据结构,在文件目录的目录项中仅存放文件名和对应的指向索引结点的指针..
(3)目录结构的形式有单级目录结构,两级目录结构和多级目录结构(也成为树形目录结构)。单级目录结构下文件不能重名查找速度也慢,两级目录是按用户建立的,即 第一级目录中存放用户名和该用户目录的指针,虽然提高了检索速度在不同用户目录中可以重名,但是不同用户文件之间的共享不方便,于是多级目录就出现了..根目录还是按用户分的,但下面有多重目录.当两个或多个用户共享文件时,不再是树形而是有向非循环图.
文件系统实现
文件系统层次结构
文件系统由三部分组成:与文件管理有关的软件,被管理的文件,实施文件管理所需的数据结构.文件系统由四层构成:最低层是基本输入输出层又叫设备驱动层,下来依次是基本文件系统层,又称物理I/O层.基本I/O管理程序层,逻辑文件系统层.
(1)基本I/O层:负责启动设备I/O以及对设备发来的中断信号进行处理.
(2)物理I/O层:负责处理内存和外存之间的数据块交换.
(3)基本I/O管理程序层:选择文件所在设备,进行逻辑块号到物理块号的转换,对文件空闲存储空间的管理,指定I/O缓冲区等作用.
(4)逻辑文件系统层:负责处理文件及记录的相关操作.
这个名字起得不好,一般物理都是最底层,结果这是是第二层不好记..
文件存储空间的管理
(1) 空闲表法和空闲链表法
空闲表法适用于连续分配方式.系统为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项,其中包括表项序号,该空闲区的第一个盘块号,该区的空闲盘块数等信息,再将所有空闲区按其起始盘块号递增的次序排列.(对换区常用).空闲链表法.将空闲空间,以盘块为单位拉成一条链.
(2) 位示图法
二进制的每一位表示磁盘中的一个盘块,当该位为1时表示已经分配,为0表示空闲.注意给出的字号和位号是从0开始还是从1开始.书上是从1开始的.
(3) 成组链接法
成组链接法将一个文件的所有空闲块按每组100块分成若干组,把每组的盘块数目和该组的所有盘块号计入到前一组的第一个盘块中,第一组的盘块数目和第一组的所有盘块号计入到超级块中.这样每组的第一个盘块就连接成了一个链表,而组内的多个盘块形成了堆栈.
成组链接法的分配和回收空闲块都是所谓的头取头插,即分配从第一组开始分配,如果第一组只剩那个保存有下一组地址的块,就把该块存入超级块,下一组变成第一组.回收的时候,如果第一组满100个,那么将第一组的盘块数和盘块号写入该空闲块中,然后将盘块数等于1及栈顶块号=该空闲块号写入超级块中所以原来的第一组就变成了第二组…
磁盘组织与管理
磁盘的结构
磁盘由若干盘片组成,每个盘片有两面.都可以记录信息.每个盘面由若干磁道组成,不同半径的同心圆叫磁道.每条磁道又分为若干个扇区.每个扇区的大小相当于一个盘块.每个盘面的每一面都有一个磁头.柱面指的是不同盘面相同半径的磁道组成的圆柱..
磁盘的类型可分为固定磁头磁盘和移动磁盘磁头.磁盘的访问时间由寻道时间,旋转延迟时间和传输时间构成.(1)寻道时间:指的是把磁头移到指定磁道上所经历的时间.移动一条磁道的时间是常数.为0.2ms…
(1)寻道时间等于启动磁臂的时间(常数2ms)+移动n个磁道的时间..即0.2 * n + 2
(2)旋转延迟时间为转半转所需的时间..一看都是平均数..
(3)传输时间为所读/写的字节数b除以一条磁道上的字节数(除下来即表示b个字节需要转几转)再乘以一转需要的时间..
磁盘调度算法
(1) 先来先服务
没有对寻到进行优化,导致平均寻道时间可能较长.
(2) 最短寻道优先
只要有新的进程要访问的磁道与当前磁头所在磁道距离较近.就会满足此进程而可能导致某些离得远的一直得不到满足.
(3) 扫描算法
又称电梯调度算法,scan算法所考虑的下一个访问对象是按电梯一样的磁头移动方向下,距离正访问磁道最近的对象.容易使距离两端的进程等待将近一来一回的扫描..
(4) 循环扫描算法
CSCAN算法规定了磁头必须单向移动.例如只允许磁头由内向外移动.移动到最外磁道立即返回最里面又重新开始.
磁盘的存储
可以按并行交叉存储.即连续的物理块分在不同的盘面上.一次就可以取多个,也可以在一个盘面上按顺序号存储这种效率低.容易读完1号处理完磁盘刚好旋转的把2号错过去,所以还有一种是将物理号连续的间隔起来排列.
输入输出（I/O）管理
I/O管理概述
I/O设备的分类
(1) 按传输速率分可分为低速设备(键盘鼠标等)，中速设备(激光打印机等)，高速设备(磁盘机等)。
(2) 按信息交换的单位分可分为块设备(有结构例如磁盘)和字符设备(常采用中断驱动方式)
(3) 按设备的共享方式可分为独占设备(一段时间内只允许一个进程访问:例如打印机)，共享设备(一段时间内允许多个进程同时访问:例如磁盘)，虚拟设备(通过虚拟技术将独占设备变为若干台逻辑设备。)
I/O管理目标
合理分配设备、提高设备与CPU，各外部设备之间的并行性，提供使用方便且独立与设备的界面。
I/O管理功能
(1) 动态的纪录各种设备的状态
(2) 设备分配与回收
(3) 实施设备驱动和中段处理的工作
I/O应用接口
(1) 设备和设备控制器的接口：设备和cpu之间不是直接通信的而是夹着一个设备控制器，设备与设备控制器是靠三根线相连的，数据信号线，控制信号线和状态信号线，数据信号线用于在设备和设备控制器之间传送数据信号，控制信号线传送由设备控制器向I/O设备发送控制信号，状态信号线用于传送设备当前状态的信号。
(2) 设备控制器：控制一个或多个I/O设备，其基本功能有接收和识别(cpu发的)命令，数据交换(与cpu或与设备数据交换)，标示和报告设备的状态(给cpu发)地址识别，数据缓冲，差错控制。
(3) 设备控制器由三部分组成：设备控制器与处理器的接口(由数据线连接DMR和控制状态寄存器，控制线，和地址线组成)，设备控制器与设备的接口(多个设备接口，每个设备接口由数据控制和状态三种信号)，I/O逻辑(当cpu启动一个设备时，将启动命令发给I/O逻辑同时通过地址线给I/O逻辑由它进行译码。。译出命令后对所选设备进行控制。所以地址线和控制线是直接跟I/O逻辑相连的。
I/O通道
I/O通道是特殊的处理机。它具有执行I/O指令的能力，并通过执行通道程序来控制I/O操作，它的指令单一主要与I/O操作相关的指令，通道没有自己的内存，它和CPU共享内存。通道又分为字节多路通道，数组选择通道，和数组多路通道。
(1) 数组选择通道:又称告诉通道，在物理上可以连接多个设备，但某一段时间内通道只能选择一个设备进行工作
(2) 数组多路通道:当某设备进行数据传送时，通道只为该设备服务，当设备在执行寻址等控制性动作时，通道挂起该设备的通道程序，去为其他设备服务。
(3) 字节多路通道:用于大量低速设备，与设备之间数据传送的基本单位是字节，为一个设备传送一个字节后，又可以为另个设备传送一个字节。数组多路通道传输的基本单位是块。而且一次只能有一个设备在传输数据。
I/O控制方式
(1) 程序I/O方式：忙等方式。
(2) 中段驱动I/O方式：当某进程要启动某个I/O设备工作时，便由cpu向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务，此时，CPU和 I/O设备并行操作。以字节为单位进行I/O。
(3) DMA I/O方式：直接存储器访问方式数据传输的单位是块，数据之间在设备和内存中进行交换，仅块传输的开始和结束时才需要CPU干预。(替代了设备控制 器)。DMA控制器中有四类寄存器：命令寄存器(存cpu发的控制命令或设备的状态)，内存地址寄存器，数据寄存器(缓冲数据作用)，数据计数器(存本次要读的字节数)。
(4) I/O通道控制方式：通道是通过执行通道程序，并与设备控制器共同实现对I/O设备的控制的。通道指令格式为命令
1）操作码：规定了指令所执行的操作。
2）内存地址：标明读操作和写操作时的内存首址
3）计数：表示本条占领所要读或写数据的字节数
4）通道程序结束位P：用于表示通道程序是否结束
5）记录结束标志R。
I/O核心子系统
高速缓存与缓冲区
引入缓冲区的目的:改善CPU与外围设备之间的速度不匹配矛盾；减少对CPU的中断次数(一个位做缓冲和块做缓冲的差距)，提高CPU和I/O设备的并行性。
缓冲分为：单缓冲、双缓冲、循环缓冲、和缓冲池
单缓冲属于临界资源，而且cpu与设备无法进行并行操作。单缓冲只允许各自进程独占。双缓冲一般就有发送缓冲区和接收缓冲区。循环缓冲链成一个环形，不过 需要四个指针，比如分别指向用于读进程和写进程的已用和正在访问的单元，循环缓冲进程属于专用缓冲区。不是所有的进程都能用的。所以系统会有多个这种缓冲区。开销比较大。其实单缓冲和多缓冲也是得设置多个。因为多道程序要是设一个缓冲区岂不是没有并行性了。
缓冲池是个好想法：里面有多个进程可以共享的缓冲区。不过既然要使多个进程共享肯定结构比较复杂。有空闲缓冲区，装满输入数据的缓冲区，装满输出数据的缓冲区还有用于收容输入输出数据的缓冲区。
设备分配
设备分配中设计到4张表的数据结构，设备控制表DCT，控制器控制表COCT，通道控制表CHCT，系统设备表SDT，DCT主要包括设备标示、设备类型(块设备还是字符设备)、设备状态、等待该设备的进程、指向控制器表的指针。COCT同理，包括控制器标示符，控制器状态，与控制器连接的通道指针，等待控制器的进程队列。CHCT同上，不过它包含与该通道相连的控制器表的首地址。SDT表里包含设备控制表，还包含驱动程序入口地址等。
设备管理软件具有层次结构，细分为四级，设备中断处理程序，设备驱动程序，与设备无关的操作系统软件，用户级软件。
逻辑设备名与物理设备是有个映射表的叫逻辑设备表，基本上一个系统一个。或者一个用户一个， 数据项有逻辑设备名，物理设备名和驱动程序入口地址。
假脱机技术（SPOOLing）
假脱机技术用辅存的输入输出井替代了以前脱机技术的外围设备机的作用，使对I/O设备的操作变成对输入输出井的操作。多个进程可以同时独享设备实现了虚拟设备的功能，其实设备并没有分给某个进程，而是进程将要处理的数据放到输入输出井中，每个进程在输入输出井中分配的是一个存储区和一张I/O请求表。
计算机系统概论
计算机系统由哪两部分组成？计算机系统性能取决于什么？
计算机系统是由“硬件”和“软件”组成。衡量一台计算机性能的优劣是根据多项技术指标综合确定的，既包括硬件的各种性能指标，又包括软件的各种功能。
1）计算机系统由硬件和软件两部分组成。
2）计算机系统性能由硬件和软件共同决定。
计算机系统5层层次结构从下到上由哪五层组成？哪些是物理机，哪些是虚拟机？
1）微程序机器、传统机器、操作系统机器、汇编语言机器、高级语言机器
2）微程序机器和传统机器是物理机，其他是虚拟机。
在计算机系统结构中，什么是翻译？什么是解释？
1）翻译：将一种语言编写的程序全部翻译成另一种语言，然后再执行；
2）解释：将一种语言编写的程序的一条语句翻译成另一种语言的一条或多条语句，然后执行，执行完这条语言后，再解释下一条。
什么是计算机体系结构？什么是计算机组成？以乘法指令为例说明二者区别。
1）计算机体系结构是指那些能够被程序员看到的计算机的属性。如指令集、数据类型等；
2）计算机组成是指如何实现计算机体系结构所体现出来的属性；
3）以乘法指令为例，计算机是否有乘法指令，属于体系结构的问题。乘法指令是采用专用的乘法器，还是使用加法器和移位器构成，属于计算机组成的问题。
冯诺依曼机器的主要特点？
1）计算机由运算器、存储器、控制器、输入设备和输出设备五大部分组成；
2）指令和数据存储在存储器中，并可以按地址访问；
3）指令和数据均以二进制表示；
4）指令由操作码和地址码构成，操作码指明操作的性质，地址码表示操作数在存储器中的位置；
5）指令在存储器内按顺序存放，通常按自动的顺序取出执行；
6）机器以运算器为中心，I/O设备与存储器交换数据也要通过运算器。（因此，后来有了以存储器为中心的计算机结构）
现代计算机的组成框图。
什么是存储单元、存储字、存储字长、存储体？
存储单元：存储一个存储字并具有特定存储地址的存储单位；
存储字：一个存储单元中存放的所有的二进制数据，按照某个地址访问某个存储单元获取的二进制数据。
存储字长：存储字中二进制数据的位数，即按照某个地址访问某个存储单元获取的二进制数据的位数；
存储体：由多个存储单元构成的存储器件。
主存储器中，什么是MAR，什么是MDR，存储器的最大容量由什么决定？
1）MAR：存储地址寄存器，保存需要访问的存储单元地址。反映存储单元的个数。
2）MDR：存储数据寄存器，缓存读出/写入存储单元的数据。反映存储字长。
3）存储器的最大容量由MAR寄存器的位数和MDR寄存器的位数决定。
什么是机器字长，什么是存储字长长？
机器字长：CPU一次能够处理的二进制数据的位数。
存储字长：按照某个地址访问某个存储单元获取的二进制数据的位数。
假设MAR寄存器的位数为16位，MDR寄存器的位数为16位，存储器的最大容量是多少？
1）MAR寄存器的位数为16位，能表示的地址个数为2的16次方，为64K；
2）MDR寄存器的位数为16位，说明存储字长为16位，也即2个字节；
3）存储器的最大容量为64K * 2B = 128K Byte
系统总线
为什么要使用总线？
在冯诺依曼结构中，各个部件之间均有单独连线，不仅线多，而且导致扩展I/O设备很不容易。即扩展一个I/O设备，需要连接很多线。
因此，引入了总线连接方式，将多个设备连接在同一组总线上，构成设备之间的公共传输通道。
总线的两大基本特征是什么？
1）共享：多个部件连接在同一组总线上，各个部件之间都通过该总线进行数据交换。
2）分时：同一时刻，总线上只能传输一个部件发送的信息；
系统总线按照传输信息的不同，分成哪几类？是单向的，还是双向的？
1）分成数据总线、地址总线以及控制总线。
2）数据总线：各个功能部件之间传送数据信息，双向传输；
3）地址总线：用来指明数据总线上，源数据或目的数据所在的主存单元的地址。单向：由CPU发出
4）控制总线：用来发送各种控制信号。对于控制总线中的单根线，是单向的，即只能由一个部件发向另一个部件。而一组控制总线中，有输入也有输出，因此，控制总线也可以看成是双向的。
什么是总线宽度、总线带宽、总线复用、信号线数？
1）总线宽度：数据总线的根数，一般是8的倍数。是衡量计算机系统性能的重要指标；
2）总线带宽：即总线数据传输速率，总线上每秒能够传输的最大字节量。
3）总线复用：一条信号线上分时传送两种信号。例如数据总线和地址总线的分时复用；
4）信号线数：地址总线、数据总线和控制总线三种总线的线数之和。
假设总线的工作频率为33MHz，总线宽度为32位，则它最大的传输速率是多少？
33 * （32/8） = 132 MB/s
简要说明单总线结构的概念及缺点？（现代计算机为什么要采用多总线结构？）
在单总线结构中，所有的部件（CPU、主存、I/O设备）都连接在一组总线上。
但所有的信息传送都要通过这组总线，同时只能有一个部件向总线上发送信息，导致总线成为系统的瓶颈。
因此，发展出来了多总线结构，其基本思想均是将速度相近的设备挂接在同一组总线上，总线之间通过总线控制器相连。
例如CPU和Cache之间、I/O设备之间等。
集中式总线判优控制有哪三种方式，哪种方式的优先级不能改变？
1）链式查询、计数器定时查询、以及独立请求。
2）链式查询的优先级不能改变，离控制器最近的优先级最高。
什么是总线周期，分为哪几个阶段？
1）总线周期：总线上两个部件完成一次完整且可靠的数据传输时间；
2）分为四个阶段：
申请分配阶段：申请总线
寻址阶段：发出地址及有关命令
传数阶段：进行数据交换
结束：从总线上撤除信号，让出总线
什么是总线通信控制，总线通信控制有哪几种？
1）总线通信控制：解决通信双方如何获知传输开始和传输结束，以及如何协调配合；
2）同步通信、异步通信、半同步通信、分离式通信
什么是同步通信？其优点和缺点？
１）同步通信：总线上各个部件由统一的时钟信号控制；在总线周期中，每个时钟周期各个部件如何动作都有明确的规定。
２）优点：速度快，各个模块间配合简单
３）缺点：以总线上最慢的部件来设计公共时钟，影响总线效率。
什么是异步通信？异步通信分为哪几种类型？
1）异步通信：总线上各部件没有统一的时钟标准，采用应答式通信；（主模块发出请求后，一直等到从模块反馈回来应答信号之后才开始通信）
2）不互锁、半互锁、全互锁。（需要了解各种方式的含义）
什么是波特率？什么是比特率？（需要掌握如何计算波特率、比特率）
波特率：单位时间内传送的二进制数据数据的位数，单位bps
比特率：单位时间内传送的有效的二进制位数。
异步通信时，常规需要设置的参数有哪些？
波特率、停止位（1/2/1.5）、校验位（奇校验、偶校验、无校验）
简述半同步通信的基本原理。
半同步通信结合同步通信和异步通信。
同步通信：采用统一的时钟，规定了在一定的时钟周期干什么事情；
异步通信：如果从模块没有准备好，增加一个“等待响应”信号。
简述分离式通信的基本原理。
主模块发出地址和命令之后，放弃总线，在从模块准备数据期间，使得总线可以被其他设备所用。提高总线利用率。
但是，这种方式控制比较复杂。
奇偶校验可以纠错吗？汉明码可以纠错码？
1）奇偶校验只能检错，不能纠错。
2）汉明码可以纠错。
存储器
存储器按存取方式，可以分成哪四类？哪些属于随机访问存储器，哪些属于串行访问存储器？
1）可以分为随机存储器、只读存储器、顺序存储器和直接存储器；
2）随机存储器和只读存储器属于随机存储器，即存取时间与物理地址无关；
3）顺序存储器（典型的如磁带）和直接存储器（典型的如磁盘）属于串行存储器，即存取时间与物理地址有关。
衡量存储器使用哪三个指标？寄存器、缓存、主存中，哪个速度最快？哪个最便宜？
1）速度、容量、位价格。
2）寄存器速度最快，主存最便宜。
常见的存储系统层次结构有哪两种？透明性如何？各自用来解决什么问题的？
1）缓存-主存层次：用来缓解CPU和主存速度不匹配的问题，由硬件来完成，对所有的程序员完全透明。
2）主存-辅存层次：用来解决主存容量不够的问题，由操作系统和硬件共同完成，对应用程序设计者透明，对系统程序设计者不透明。
（现在一般存储器都即能按字访问，也能按照字节访问，因此，存储器编址时，每个字节都有一个独立的地址。）
字在存储单元中有两种存储方式，大端方式和小端方式。各是什么含义？x86采用的是哪种存储方式？
1）大端方式：字的低位存在内存的高地址中，而字的高位存在内存的低地址中；
2）小端方式：字的低位存在内存的低地址中，而字的高位存在内存的高地址中。
3）x86CPU采用的是小端方式。
主存的三个主要技术指标
存储容量、存取速度和存储带宽
什么是存取时间？什么是存取周期？哪个大？
1）存取时间：启动一次存储器完成本次操作（读或写）所需的时间；
2）存取周期：连续两次启动存储器所需要的最小间隔时间；
3）存取周期包含存取时间；
什么是存储器带宽？（要了解如何计算存储器带宽）
单位时间内存储器存取的信息量；
半导体存储芯片译码驱动包含哪两种方式，请简要说明。
1）线选法：所有的地址芯片通过一个译码器译码，选择一个存储单元的各位，适合于存储容量不大的芯片；
2）重合法：将地址分为两组，每组通过一个译码器译码，选择行或列，行、列交叉处就是要访问的存储位。
随机存储器包含哪两大类？哪个需要刷新？请从速度、容量、价格等方面进行简要比较。
1）静态RAM：采用锁存器原理实现；
2）动态RAM：采用电容原理实现，需要刷新。
3）相比于动态RAM，静态RAM的速度快、容量小、价格高，一般用于缓存，而动态RAM一般用于内存。
只读存储器有哪几种？
1）掩模ROM（MROM）：出厂后内容不能被更改。
2）PROM：可编程只读存储器，可以进行一次性编程；
3）EPROM：可擦除只读ROM，用紫外线照射；
4）EEPROM：电可擦除只读ROM。
6）FLash Memory：采用EEPROM的非易失性存储器。
单片存储器芯片的容量有限，很难满足实际需要，因此必须将若干存储芯片连接在一起才能组成足够容量的存储器。
存储器的扩展通常有位扩展和字扩展，什么是字扩展，什么是位扩展？请举例简要说明
1）位扩展：增加存储器的字长，例如两个1K 4位的存储芯片构成1个1K8位的存储器；
2）字扩展：增加存储器的字数，例如两个1K 8位的存储芯片构成1个2K 8位的存储器；
通常字扩展和位扩展两种方式混合使用。
熟虑掌握存储器的扩展，包括地址空间分配、地址线的连接、数据线的连接、片选信号的产生及连接等；
假设欲检测的二进制代码为n位，为了使其具有1位的纠错能力，需添加K位检测位，组成n+k位的代码。问，应添加多少位检测位？
应添加的检测位位数：2的k次方大于等于n+k+1。
因为要使其有1位的检测能力，必须使用k位来说明n+k位到底哪一位出现了错误，k位能表达的数量为2的k次方，而n+k位到底哪一位
出现了错误或者是全部正确，共有n+k+1种状况，因此，k的取值需要满足：2的k次方大于等于n+k+1
- 对于汉明码，应熟练掌握汉明码的编码方式（按照配偶或配奇的原则），以及给出汉明码，得到要传送的原始信息（包括纠错过程）。
提高访存速度的三种方式。
1）采用高速元器件；
2）采用存储层次结构：cache-主存结构；
3）调整主存结构：包括单体多字，多体并行两种方式。
简述单体多字的存储系统的工作原理，及其优点。
1）单体多字存储系统一次访存取出多个CPU字，即存储字为CPU字的n倍（假设一次访存取出n个cpu字）。
2）优点是：显著提高了存储器带宽。
多体并行系统有哪两种编址方式？请简要说明其编址方式及其优点。
1）高位交叉编址方式：存储体的编址方式为顺序存储，即一个存储体存满后，再存入下一个；存储单元地址的高位为存储体的编号。
高位交叉编址并不能提高单次访存速度，但能使多应用并行访存，提高系统的并发性。
2）低位交叉编址方式：存储体的编址方式为交叉存储。即程序连续存放在相邻的存储体之中。存储单元地址的低位为存储体的编号。
低位交叉编址能显著提高单次访存速度。
在四位低位交叉编址中，假设存取周期为T，总线传输周期为τ，为了实现流水线方式存储，应满足什么条件？如果连续读取四个字，所需要的时间是多少？
1）T= 4τ
2）连续读取四个字，所需要的时间为T + （4-1）τ
注意：假设不是低位交叉编址，而是高位交叉编址，连续读取四个字所需要的时间仍然为4T。
需要大家掌握多体并行存储器在高位交叉编址（顺序存储）和低位交叉编址（交叉存储）的情况下，存储器带宽的计算方式。
在CPU和内存之间引入cache的原因。
1）避免cpu空等I/O访存；
2）缓解CPU和主存速度不匹配的问题。
什么是程序的局部性原理。
CPU从主存取指令或数据，在一定时间内，只是对主存局部地址区域访问。
Cache命中率、平均访问时间以及访问效率的计算。
Cache写操作有哪两种方式？
1）写直达法：写操作既写入Cache又写入主存；
2）写回法：只把数据写入Cache而不写入主存，当Cache中数据被替换出去之后才写入主存。
将主存地址映射到Cache地址称为地址映射，常见的Cache映射方式有哪几种？
直接映射、全相联映射、组相联映射。
直接映射的优缺点？
优点：地址变换速度快。缺点：cache利用率不高，块冲突率高；
全相联映射的优缺点？
优点：cache利用率高，块冲突率低。缺点：地址变换复杂，需要较多的硬件。
需要大家掌握各种映射方式之下，写出主存地址格式、cache地址格式，以及主存地址向cache地址的转换。
Cache常用的替换算法有哪些？哪个命中率最高？
1）先进先出、近期最少使用算法和随机替换算法；
2）命中率最高的是近期最少使用算法；
磁盘的三地址结构包括哪些？
柱面、磁头号和扇区号
输入输出系统
I/O系统的发展大致可以分为哪4个阶段？
1）早期（分散连接、串行工作、程序查询）
2）接口模块和DMA阶段（总线连接、并行工作、中断及DMA）
3）通道阶段（通道是具有特殊功能的处理器）
4）I/O处理机阶段
I/O系统的发展实际上是逐步将CPU从繁重的I/O工作中解放出来的过程；
I/O设备编址有哪两种方式？各有什么优缺点？
1）统一编址方式：和存储器统一编址，I/O地址作为存储器地址的一部分；无须用专用的I/O指令，但占用存储器空间。
2）独立编址方式：和存储地址分开编址，需用专用的I/O指令。
I/O设备与主机的联络方式有哪几种？
I/O设备与主机间交互信息时必须了解彼此的状态。根据I/O设备工作速度的不同，可以分为3类：
1）立即响应：不管其状态（认为其时刻准备好），适用于慢速设备。
2）应答信号：通过应答信号来进行交互；
3）同步时标：采用统一的时钟信号。
I/O总线包括哪四类？
数据线、设备选择线、状态线、命令线
I/O设备通常使用D触发器（完成触发器）和B触发器（工作触发器）来标识设备所处的状态。
D=0，B=0：暂停状态；
D=0，B=1：准备状态
D=1，B=0：就绪状态
程序查询的基本工作原理。
cpu不断去查询I/O设备状态，导致CPU和I/O设备串行工作。
什么是中断？
计算机在执行程序过程中，当出现异常清空或特殊请求时，计算机停止现行程序的运行，转去处理这些异常清空或特殊请求，处理结束后，再返回现行程序的间断处，继续执行原程序，即为中断。
中断服务程序的基本流程包括哪四部分？
1）保护现场
2）中断服务
3）恢复现场
4）中断返回
什么是单重中断和多重中断？
1）单重中断：不允许中断现行的中断服务程序；
2）多重中断：允许级别更高的中断源中断现行的中断服务程序，也称为中断嵌套；
CPU响应中断的时机？
当前指令执行完毕后，cpu发出中断查询信号，也就是说，中断响应一定是在每条指令执行结束之后进行的，不可能在指令执行过程中响应中断。
什么是DMA？
DMA：直接内存访问。在主存和I/O设备之间建立独立的总线连接。
在DMA方式中，由于DMA接口与CPU共享主存，可能会出现两者争用主存的冲突，为解决冲突，DMA和主存交换数据时，通常采用哪三种工作方式？
1）停止CPU访问主存：DMA访存优先级高；
2）周期挪用（窃取）：DMA挪用存储或窃取总线使用权一个或几个主存存取周期；
3）DMA和CPU交替访问：将CPU工作周期分成两部分，一部分供DMA访存，一部分供CPU访存。
DMA工作过程包括哪三部分？
1）预处理
2）数据传输
2）后处理
指令系统
什么是机器指令？什么是指令系统？
1）机器指令：每一条机器语言的语句；
2）指令系统：全部机器指令的集合。
一条指令包含哪两个主要部分？请简要说明各部分作用。
1）操作码：指明指令要完成的操作；
2）地址码：指明指令要操作的数据或数据来源；
操作码长度有固定长度和可变长度两种，各自有什么优点？
1）固定长度：便于硬件设计，指令译码时间短；
2）可变长度：压缩了操作码平均长度；
指令中地址码中的地址可以是哪些设备的地址？
可以是主存地址、寄存器地址或I/O设备的地址；
指令中地址的个数可以有几个？
四地址、三地址、二地址、一地址以及零地址。
假设指令中有四个地址、三个地址、两个地址以及一个地址，各自需要访存几次？
1）四地址：访存4次；
2）三地址：访存4次；
3）两地址：访存3次；
4）一地址：访存2次；
当使用寄存器代替指令字中的地址码字段后，有哪些优点？
1）扩大指令字的寻址范围；
2）缩短指令字长；
3）减少访存次数
数据在存储器中存储时，为什么要按照边界对齐？
减少访存次数。
寻址方式包括哪两类？
1）指令寻址：下一条将要执行的指令的指令地址；
2）数据寻址：确定本指令的操作数地址。
什么是形式地址？什么是有效地址？
1）形式地址：指令的地址码字段通常都不代表操作数的真实地址，成为形式地址，记为A；
2）有效地址：操作数的真实地址，记为EA，由寻址特征和形式地址共同决定；
了解各种寻址方式的概念及根据形式地址形成有效地址的方式。
立即寻址、直接寻址、隐含寻址、间接寻址、寄存器寻址、寄存器间接寻址、基址寻址（隐式或显式）、变址寻址、相对寻址、堆栈寻址
什么是RISC？什么是CISC？
RISC：精简指令集；
CISC：复杂指令集；