操作系统心得
2.进程管理
顺序程序设计的特点:
1.执行的顺序性。
2.环境的封闭性。
3.计算过程的可再现性。
顺序程序设计的顺序性、封闭性和再现性给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。
并发性：程序之间
顺序性：程序之内
采用并发程序设计的目的是：
充分发挥硬件的并行性，消除处理器和I/O 设备的互等现象，提高系统效率。
机器部件能并行工作仅仅有了提高效率的可能性，而机器部件并行工作的实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。
程序的并发执行的特征
间断性：程序在并发执行时，由于共享资源，或者需要相互合作，致使相互间产生了制约关系，呈“走走停停”的间断执行特征。
失去封闭性：程序并发执行时的系统环境（主要指各程序所共享的系统资源的状态）是由多个程序来改变的，因而失去了封闭性。
不可再现性：程序在并发执行时的结果与其执行速度等有关，从而不可再现。
进程的特征
动态性：进程的实质是程序的一次执行过程，进程是动态产生，动态消亡的。
并发性：任何进程都可以同其他进程一起并发执行
独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；
异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进
结构特征：进程由程序、数据和进程控制块三部分组成。
信号量机制解决读者写着问题:
Var RN integer;
L, mx: semaphore:=RN,1;
读者Readers:
begin
repeat
Swait(L,1,1);
Swait(mx,1,0);
…
执行读操作;
…
Ssignal(L,1);
until false;
end
*************************************
写者Writers：
begin
repeat
Swait(mx,1,1;L,RN,0);
执行写操作;
Ssingal(mx,1);
until false;
end
进程通信:
1.共享存储设备通信机制
2.管道通信机制
3.消息传递机制
3.1直接通信机制
3.2间接通信机制
3.线程的特点：
是进程的一个实体，可作为系统独立调度和分派的基本单位。
不拥有系统资源（只拥有从属进程的全部资源，资源是分配给进程）
一个进程中的多个线程可并发执行。（进程可创建线程执行同一程序的不同部分）
系统开销小、切换快。（进程的多个线程都在进程的地址空间活动）
3.处理机调度与死锁
1.什么是作业：是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合。
2.1高级调度:又称为作业调度或长程调度，主要功能是根据某种算法，把外存上处于后备对列中的那些作业调入内存，调度的对象是作业。
2.2中级调度:又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量
2.3低级调度:称为进程调度或短程调度，它所调度的对象是进程。
3. 优先权调度算法的类型
非抢占式优先权算法: 用于某些对实时性要求不严的实时系统中。
抢占式优先权调度算法:用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。
4. 先来先服务和短作业(进程)优先调度算法
1. 先来先服务调度算法(FCFS)
2. 短作业(进程)优先调度算法(SJF)
SJ(P)F调度算法也存在不容忽视的缺点：
(1) 该算法对长作业不利
(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
5. 高优先权优先调度算法
1.高响应比优先调度算法(HRRN)
该算法，就是每调度一个作业投入运行时，计算后备作业表中每个作业的响应比，将响应比作为优先权，然后挑选响应比最高的作业投入运行，该方法属于动态优先权。
2 .抢占式段作业优先调度算法
比较新进入就绪队列的进程的运行时间和正在运行进程的剩余时间，如果小则终止当前进程的执行，调度新作业执行，也称为最短剩余时间优先级调度(SRTF)。
6. 基于时间片的轮转调度算法(RR)
1. 时间片轮转法
7. 关于死锁的一些重要结论
（1）参与死锁的进程数至少为2
（2）参与死锁的所有进程均等待资源
（3）参与死锁的进程至少有两个占有资源
（4）参与死锁的进程是系统中当前正在运行进程的一部分
8. 死锁的解除
通过抢占资源实现恢复和通过杀掉进程解除死锁。
8.1．通过抢占资源实现恢复
即临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。
8.2．通过杀掉进程实现恢复
终止所有的死锁进程。一次终止一个进程，直至消除死锁环路。
************************************************************
例3. （2001，国防科大）假设系统有n个进程共享m个相同的资源，每个进程至少请求一个资源。证明：当n个进程最多需要的资源数之和小于m+n时，该系统不会死锁。
证明： 设每个进程的最大需求量为Max[i]、需要资源数为Need[i]、已分配资源数为Allocation[i]，根据题意，则有以下式子成立：
Max[1]+Max[2]+…+Max[n] < m+n (1)
假设系统会发生死锁，即系统的资源已分配完毕，因而下式成立：
Allocation[1]+Allocation[2]+...+Allocation[n]=m (2)
又因为
Max[i]=Allocation[i]+Need[i] (3)
由（1）、（2）、（3）式可得：
Max[1]+...+Max[n] <Allocation[1]+...+Allocation[n]
+Need[1]+…+Need[n]
=m+Need[1]+....+Need[n] <m+n
所以，Need[1]+...+Need[n] <n , 这说明此刻至少存在一个进程i，Need[i]=0，即它已获得了所需要的全部资源。既然该进程已获得了他所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明了在这个系统中不会发生死锁。
4. 存储器管理
1. 存储管理的功能
1.1 内存由很大的一组字或字节所组成，每个字或字节都有它们自己的编号，称为内存地址。
1.2 对内存的访问是通过一系列对指定地址单元进行读写来实现的。
1.3 内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。
1.4 我们把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址映射，或称为地址重定位。
1.4.1地址映射的方式：
1、 静态地址重定位
1.1程序被装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换。
1.2假定程序装入内存的首地址为BR，程序地址为VR，内存地址为MR，则地址映射按下式进行：MR=BR+VR 。
2、 动态重定位
2.1动态地址重定位是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。
2. 分区管理的基本原理
1.1 固定分区法：通常采用*****静态地址重定位*******
1.1.1把内存区固定地划分为若干个大小不等的区域。划分的原则由系统操作员或操作系统决定
1.1.2分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变
1.1.3固定分区的分配和回收
当用户程序要装入执行时，存储管理程序根据用户程序的大小查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。
1.2 动态分区法:
1.2.1动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变,这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率
1.2.1动态分区的分配
1.2.2动态分区的内存回收
当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。
3. 连续内存分配
3.1 分配算法：
（1）首次适应算法：
n 要求空闲区按首址递增的次序组织空闲区表（队列）。
n 申请：取最小可满足区域；
n 优点：尽量使用小空闲区， 保持大空闲区。缺点：可能形成碎片
（2）最佳适应算法：
n 要求按空闲区大小从小到大的次序组成空闲区表（队列）。
n 申请：取最小可满足区域；
n 优点：尽量使用小空闲区， 保持大空闲区。缺点：可能形成碎片
（3）最坏适应算法
n 要求空闲区按大小递减的顺序组织空闲区表（或队列）。
n 申请：取最大可满足区域；
n 优点：防止形成碎片。缺点：分割大空闲区域。
例题:（华中科技大学2002）某系统采用动态分区存储管理技术。某时刻在内存中有三个空闲区，它们的首地址和大小分别是：空闲区1（100KB，10KB）、空闲区2 （200KB，30KB）、空闲区3 （300KB，15KB）。现有如下作业序列：作业1要求15KB、作业2要求16KB、作业3要求10KB。要求：
（1）画出该时刻内存分布图；
（2）用首次适应算法和最佳适应算法画出此时的自由主存队列结构；
（3）哪种算法能将该作业装入内存（给出简要的分配过程）。
例题:（华中科技大学2002）某系统采用动态分区存储管理技术。某时刻在内存中有三个空闲区，它们的首地址和大小分别是：空闲区1（100KB，10KB）、空闲区2 （200KB，30KB）、空闲区3 （300KB，15KB）。现有如下作业序列：作业1要求15KB、作业2要求16KB、作业3要求10KB。要求：
（1）画出该时刻内存分布图；
（2）用首次适应算法和最佳适应算法画出此时的自由主存队列结构；
（3）哪种算法能将该作业装入内存（给出简要的分配过程）。
例题: (华中科技大学2001)某操作系统采用可变分区分配存储管理方法,用户区大小为512K且初始值为0,用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对于下列申请序列： 申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K
回答下列问题：
（1）请分别画出采用首次适应算法、最佳适应算法进行内存分配和回收后的内存使用状态。
（2）如果再申请100K，针对上述两种算法会有什么结果？
4. 碎片问题
内部碎片：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。
外部碎片：指系统中无法利用的小的空闲分区。如动态分区中存在的碎片
交换技术:是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术 。(解决内存不足的问题)
5. 分页管理
5.1 页 :把用户程序的地址空间划分成若干大小相等的区域，每个区域称作页面或页。每个页都有一个编号，叫做页号。页号一般从0开始编号
(以页为单位进行内存分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻)
5.2 帧: 把内存空间划分成若干和页大小相同的物理块，这些物理块叫“帧”(frame)或内存块
5.3 页表的作用:
在分页系统中，页面的大小是由硬件的地址结构所决定的。机器确定、页面大小便确定了
n 如果给定的逻辑地址是A，页面的大小为L，则页号p和页内地址(页内偏移量)w可按下式求得： p=INT[A/L]，w=[A] MOD L
页号P=逻辑地址 % 页大小 页内位移W=逻辑地址 mod 页大小
n 页表的作用就是实现页号到物理块号的地址映射。
5.4 例题
5.4.1 例1设有8页的逻辑地址空间，每页有1024个字节，它们被映射到32块的的物理存储区，那么逻辑地址的有效位是多少，物理地址至少多少位？
5.4.2 例2：在一分页系统中，逻辑地址的长度为16位，页面大小为4096字节，现有一逻辑地址2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址是多少？
5.4.3 例3：在某分页系统，主存的容量为64K，页面的大小为1K，对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中，试将十进制的逻辑地址1023、2500、3500和4500转化成物理地址。
5.4.4 页表分析:
由于页表是驻留在内存的某个固定区域中，而取数据或指令又必须经过页表变换才能得到实际物理地址。因此，取一个数据或指令至少要访问内存两次以上。一次访问页表以确定所取数据或指令的物理地址，另一次是根据地址取数据或指令，这比通常执行指令的速度慢了一倍。
解决这个问题的一种方法是把页表放在一组快速存储器中（Cache），从而加快访问内存的速度。我们把这种快速存储器组成的页表称为快表，把存放在内存中的页表称为慢表。快表又叫相联(联想)存储器
5.4.5 例题:
假定访问主存时间为100毫微秒，访问相联存储器时间为20毫微秒，相联存储器为32个单元时快表命中率可达90%，按逻辑地址存取的平均时间为：
（100＋20）×90%＋(100+100+20)×(1-90%)＝130毫微秒,比两次访问主存的时间100毫微秒×2＝200毫微秒下降了四成多。
5.5 分段存储管理的基本原理
5.5.1 段的共享是通过不同进程段表中的项指向同一基址来实现的
5.5.2 分段和分页的比较：
（1）页是信息的物理单位，而段是信息的逻辑单位。分页时为了实现离散分配方式，以减少内存碎片，提高内存利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
（2）页的大小是由系统确定的，由系统把逻辑地址划分成页号和页内地址两部分，整个系统只能有一种大小的页面；而段的长度却不固定，决定于用户的程序。通常由编译程序在对源码进行编译时，根据信息的性质来划分。
（3）分页的进程地址空间是一维的，即单一的线性空间；而分段的进程地址空间是二维的，有段号和段内地址两部分组成。
5.5.3 作业的逻辑地址包括3个部分：段号、页号和页内位移。
5.5.4
5.6 请求分页技术
5.6.1 页表的扩充
（1）状态位P：指示该页是否已调入内存。
（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。
（3）修改位M：表示该页在调入内存后是否被修改过。若修改过，则换出时需重写至外存。
（4）外存地址：指出该页在外存上的地址。
5.6.2 缺页中断
5.6.2.1 程序在执行时，首先检查页表，当状态位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。
5.6.2.2 缺页中断的处理过程是由硬件和软件共同实现的。
5.6.2.3 缺页中断同一般中断都是中断，相同点是：保护现场 中断处理 恢复现场
不同点：一般中断是一条指令完成后中断，缺页中断是一条指令执行时中断
一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。
5.6.3 页面置换算法
5.6.3.1 页面置换的过程
（1）找出所需页面在磁盘上的位置；
（2）找出可用空闲内存块。如果有，就立即使用，否则，就进行页面置换，选择一个老的页面置换到外存磁盘。
（3）将所需页面装入内存，修改相应的数据结构。
（4）继续执行用户进程。
5.6.4 选择置换算法的原则是保证系统的缺页次数最少。
5.6.5 置换算法
5.6.5.1 最佳置换算法 {局部置换,适用于固定分配}
其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。(不可行,不能确定序列,这只是理想状态)
也就是说每次都要看看不远的将来那个页面最晚再次被加入
5.6.5.2 先进先出(FIFO)页面置换算法 {局部置换,适用于固定分配}
FIFO算法是最早出现的页面置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中停留时间最长（年龄最老）的一页予以淘汰
出现Belady异常现象，即缺页次数随内存块增加而增加。
不管你是不是最新又加入的,只要你存在的时间最长,那么就把你置换出来(可以画图,然后看那个数字持续显示的次数最多就将那个置换出来)不可行.置换太频繁,效率低
5.6.5.3 最近最久未使用(LRU)置换算法 {局部置换,适用于固定分配}
最近最久未使用置换算以“最近的过去”作为“不久将来”的近似，选择最近一段时间内最久没有使用的页面淘汰掉。它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰 。
需要有硬件支持:寄存器或者栈
5.6.5.4 例题
1. 某页式虚拟存储管理系统的物理空间为3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3635、3632、1140、3584、2892、3640、40、2148、1700、2145、3209、0、1102、1100。如果上述数字均为十进制，而内存尚未装入任何页，试计算采用OPT、LRU和FIFO页面置换算法的缺页次数
2. 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。
3. 假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,开始时3个物理块均为空，给出采用最佳置换算法时页面置换情况，并计算出该算法的缺页率？
（1）最佳置换淘汰算法
（2）先进先出淘汰算法
（3）最近最久未使用淘汰算法