操作系统：
是一组控制和管理计算机软硬件资源、合理调度各类作业以及方便用户使用的程序集合。
操作系统的五大功能：
操作系统相关概念：
（1）多道：
允许多个相对对立的程序同时存在于内存中，按照某种原则分派处理机逐个执行这些程序。
（2）多道程序设计：
为提高系统系统的吞吐量和资源利用率，允许多个程序同时驻留内存，让处理机在这些程序之间切换，一段时间内执行完多个程序的处理技术。现代操作系统大多采用多道程序设计技术。
（3）多道批处理系统：
多道性、无序性、调度性（作业调度、进程调度）。
（4）分时系统：
由于多道批处理系统交互性差，因此在多道程序技术的基础上为用户配置联机终端从而产生分时系统。
进程：
（1）进程的三种基本状态：
就绪状态：进程已获得除处理机以外的所有必要资源，只要再获得处理机就能够执行的状态。
执行状态：已经获得CPU正在运行的状态。
阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时放弃处理机而进入的状态。
（2）进程的两大关系：
互斥：并发执行的多个进程由于竞争同一种资源而产生的相互排斥的关系。互斥没有传递性。
同步：进程间共同完成一项任务时直接发生相互作用的关系。
处理机调度：
一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度：
（1）高级调度：从外存后备队列中挑选一个作业调入内存，并为它们创建进程、分配资源、排在就绪队列上，准备执行。
（2）低级调度：从就绪队列中挑选一个进程，并为它分配CPU，使之运行。
（3）中级调度。
（4）作业调度/进程调度算法：
1）先来先服务（FCFS）优先调度算法。
谁先来先为谁服务，不利于短作业。
2）短作业（SJF）/短进程（SPF）优先调度算法。
总是先为需要CPU时间最短的作业或进程服务。
周转时间 = 完成时刻-提交时刻
带权周转时间 = 周转时间/运行时间
3）优先级调度算法。
根据作业或进程的紧迫程度，来确定给谁先服务。
4）高响应比（HRN）优先调度算法。
R = 1+W/T，
W：进程在就绪队列中或作业在后备队列中已经等待的时间，
T：进程或作业估计需要CPU的时间。
存储器管理：
（1）存储器的层次结构：
（2）存储器管理的任务：
跟踪哪些存储器正在被使用、哪些存储器空闲、在进程需要时为它分配存储器、使用完毕后
释放存储器、并且在主存无法容纳所有的进程时管理主存和磁盘间的交换。
（3）存储器分配方式：
1）连续分配方式
整个程序存放在一段连续的内存空间。
a、单一连续分配：
内存分两个区域：系统区和用户区，应用程序装入到用户区，一次只装入一个作业。
优点：易于管理。
缺点：内存利用率低。
b、固定分区分配：
在系统启动时把内存划分为若干个固定大小的连续分区。当需要为作业分配空间时，
依次查找分区将大小满足作业请求容量并且使用状态为空闲的分区分配给该作业。作
业运行完毕后，将分区收回，分区使用状态置为空闲。
优点：易于实现。
缺点：容易产生碎片；分区总数固定，限制并发执行的程序数目。
碎片：不可以利用的空间。
内部碎片：分区内未被利用的空间。
外部碎片：分区间未被利用的空间。
c、动态分区分配：
在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。常用的数据
结构为空闲分区表和空闲区链表，
空闲分区表：
空闲区链表：将所有空闲分区用指针链接成一个双向链表。
优点：解决了内部碎片问题，提高了内存利用率。
缺点：数据结构也需要空间。
d、动态可重定位分区分配：
引入紧凑，将总量大于作业大小的多个小分区拼接成一个大分区后分配给作业。
优点：解决了外部碎片，提高了内存利用率。
缺点：紧凑需要花费时间。
分区分配算法：
a、基于顺序搜索的动态分区分配算法
i、首次适应法。
先将空闲分区按地址递增的次序排列。当需要分配内存时，从空闲区链首开始顺
序查找，直到找到第一个能满足大小要求的空闲区为止。
ii、循环首次适应法。
不是每次都从链首开始查找，而是从上次找到的空闲分区的下一个开始查找，直到
一个能满足大小要求的空闲分区。
iii、最佳适应法。
扫描整个空闲区链表，找到能满足需求且最小的空闲区。
iiii、最坏适应法。
扫描整个空闲区链表，找到能满足需求且最大的空闲区，一部分分给进程，另一
部分仍留在链中期待能继续分给其他进程。
b、基于索引搜索的动态分区分配算法
i、快速适应算法。
将空闲分区按照大小进行分类，对每一类空闲分区建立一个空闲分区链表。同时
在内存中建立一张管理索引表，该表的每一项对应一个空闲分区链表，并记录
该类空闲分区链表的表头指针。当需要分配内存时，根据所需要的内存大小，寻
找能容纳它的最小空闲区链表，并取第一个分区进行分配。
2）非连续分配方式：
整个程序存放在分散的各个内存空间。
a、分页式存储管理
把程序逻辑空间分成若干大小相等的片，成为页面或页。
把内存空间分成与页相同大小的若干个存储块，称为物理块或页框。
分配内存时，将程序的若干页分别转入多个可不相邻的块中。
（只有最后一页才有页内碎片）
程序的逻辑地址结构：
页表：
页表记录页号和块的对应关系。
地址转换：
CPU指令所给出地址分为两部分：逻辑页号和页内偏移地址
逻辑页号，页内偏移地址——>查进程页表得物理号（CPU第一次访问内存）
——>物理地址（CPU第二次访问内存）
计算时注意：
逻辑空间：空间的大小根据程序而定。假设4KB。
编址过程：以字节B为存储单位，每个字节都有一个编号，4KB=4096B，
i、如果以十进制数表示编号：从0开始编到4095结束。
ii、如果以二进制数表示编号： 共有4096个号，需要12位二进制表示，
从0000 0000 0000编到1111 1111 1111结束。
内存空间：空间的大小根据系统而定。编址过程相同。
i、若给出的地址为16进制，则将其转换为二进制，然后根据页长以及程序地址的长度
，分别取出程序地址的高几位和低几位就得到页号及页内地址。如页长为2K，程序
地址为16位。分析：
2K = 2KB = 2048B，2048 = 2^11，需要11位来表示
则高5位为页号，低11位为页内地址。
ii、若给出的地址为10进制，则用公式：
程序地址/页长，商为页号，余数为页内地址。如，程序地址为8457，页长为4KB，
则8457/4096得商为2，余数为256。
注意：快表（具有并行查询能力的高速缓冲存储器）
例、有一个页式系统，其页表存放在主存中：
i、如果对主存的一次存取需要1.5us，实现一次页面访问的存取时间是1.5*2 = 3（us）
ii、如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为
0，则此时存取时间为0.85*1.5 + （1-0.85）*2*1.5 = 1.725（us）。
b、分段式存储管理
和分页式存储管理的基本相同，只是将程序按逻辑上进行有完整意义的段划分，每段
有自己的名字。
程序的逻辑地址结构：
段表：
段表的每一项：段号，段长和该段在主存的始址。
地址变换机构：
CPU指令所给出地址分为两部分：逻辑段号和段内偏移地址
逻辑段号，段内偏移地址——>查进程段表得始址和段长（CPU第一次访问内存）
——>物理地址（CPU第二次访问内存）
c、段页式存储管理
结合页式管理和段式管理。
用分段方法来分配和管理虚存，用分页方法来分配和管理实存。
逻辑地址：
段表、页表：
每个程序有一个段表，每个段有一个页表。
地址变换：
虚拟存储器管理：
常规存储器管理要求一个作业全部装入内存才能运行，且作业装入内存后便一直驻留在内存中，直至作业运行结束。但是，
程序在执行时总是呈现出局部性规律，即在一较短时间内程序的执行仅限于某个部分且访问
的存储空间也局限于某个区域。因此，
在分页（分段）的基础上，增加请求分页（请求分段）功能和页面（段）置换功能，将一个完整的程序分好几次调入内存运行，从逻辑上对内存容量加以扩充。——虚拟存储器管理
页面置换算法：（发生缺页中断后到低将哪个页面置换出去）
假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
（1）最佳置换算法（OPT）
将那些永不使用的或者最长时间内不再被访问的页面置换出去。
（2）先进先出置换算法（FIFO）
将最先进入内存的页面置换出去。（队列）
（3）最近最久未使用置换算法（LRU）
将离当前时间最久未使用的页面置换出去。
编辑于 2019-09-12 22:46:54
回复(1)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
