Ajax 技术简介 AJAX即“Asynchronous JavaScript and XML”（异步的JavaScript与XML技术），指的是一套综合了多项技术的浏览器端网页开发技术。Ajax的概念由杰西·詹姆士·贾瑞特所提出。传统的Web应用允许用户端填写表单（form），当提交表单时就向网页服务器发送一个请求。服务器接收并处理传来的表单，然后送回一个新的网页，但这个做法浪费了许多带宽，因为在前后两个页面中的大部分HTML码往往是相同的。由于每次应用的沟通都需要向服务器发送请求，应用的回应时间依赖于服务器的回应时间。这导致了用户界面的回应比本机应用慢得多。与此不同，AJAX应用可以仅向服务器发送并取回必须的数据，并在客户端采用JavaScript处理来自服务器的回应。因为在服务器和浏览器之间交换的数据大量减少，服务器回应更快了。同时，很多的处理工作可以在发出请求的客户端机器上完成，因此Web服务器的负荷也减少了。 JSON技术 JavaScript 对象表示法JSON 用jQuery实现Ajax jQuery.ajax([settings]) type：类型，“POST”或“GET”，默认为“GET” url：发送请求的地址 data：是一个对象，联通请求的发送到服务器中的数据； dataType：预期服务器返回的数据类型。如果不确定，jQuery将自动根据HTTP包MIME信息来只能判断，一般采用json格式，将其设置为“JSON”； success：是一个方法请求成功后的回调函数，传入返回后的数据，以及包含成功代码的字符串； error：是一个方法，请求失败时调用此函数，传入XMLHttpRequest对象。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

JSON基本概念 JSON：JavaScript对象表示法（JavaScript Object Notation） JSON是存储和交换文本信息的语法，类似XML。采用键值对的方式来组织，易于人们阅读和编写，同时也有益于机器解析与生成。 JSON是独立于语言的，不管是什么语言，都可以及逆行解析json，按照json规则来就行。 JSON和XML对比 JSON的长度相对于XML来说比较短小 JSON读写速度比较快 JSON可以使用JavaScript内建的方法直接进行解析，转换成JavaScript对象，十分的方便 语法规则 书写格式是：名称/值对 名称/值对组合中的名称写在前面（在双引号中），值对写在后面（同样在双引号中），中间用冒号隔开，比如“name”:”张三” 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

今天我师傅给我做了一个很牛很牛的内网优盘！！

上次重装系统是上一年了，自己在读研的时候，买了一个组装笔记本，很便宜，2000多块钱，15年到现在也有3年时间了，竟然没有一点问题。这个本子当时因为读研期间项目编程要用到VS，MAC系统不方便，而且不喜欢用虚拟机，于是有了这个本子的来历。 趁着office软件崩溃，想着干脆系统重做一下好了，于是就下载了最新的win10，然后安装了上。win10的版本与版本之间的差距还是挺明显的。刚好office订阅还有一台电脑可以用，刚好用在这个本上。硬件在win10下运行了一天也没什么问题~因为又怕遇到什么软件崩溃了什么的，所以也搜了下如何备份系统，最终采用了dism++工具备份系统。软件安装到现在，基本也就装齐了。

不知不觉中，网站已经运行了小半年了，其中有60天左右是在GitHub上部署的，当初是用本地的Node.JS进行网站渲染静态网页进行上传的，但是随着时间的流逝，自己的文章逐渐多了起来，渲染时间越来越长，看到现在网站加载的越来越慢，自己真是于心不忍，看到网上有这个WordPress好的平台，二话不说，就是干，哈哈，于是在大年29完成搭建，到现在一看我的时间戳，时间过的真快，希望网站越来越好，继续发展下去吧！ 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

作为工作之后第一个春节假期，果然不出意料短的要命。 赶在放假前我由白班转为运行班，所谓白班即周一到周五，双休，正常节假日。所谓运行班，不论周末或节假日，均上一休二。所以，春节的七天长假对于我来说，已经泡汤了。

文件的逻辑结构 设计文件逻辑结构的原则 易于操作 查找快捷 修改方便 空间紧凑 文件的逻辑结构 文件的逻辑结构就是用户所看到的文件的组织形式。 文件划分为三类逻辑结构：无结构的字符流式文件、定长记录文件和不定长记录文件构成的记录树。 定长记录文件和不定长文件可以统称为记录式文件。 流式文件 流式文件是有序字符的集合，其长度为该文件所包含的字符个数，所以又称为字符流文件。 源程序、目标代码等文件属于流式文件。UNIX内系统采用流式文件结构。 记录式文件 定长记录文件：各个记录长度相等。在检索时，可以根据记录号i及记录长度L就可以确定该记录的逻辑地址。 不定长记录文件：各个记录的长度不等，在查找时，逐条查找，直到找到所需要的记录。 文件的物理结构 顺序结构 顺序结构原理 顺序结构又称为连续结构，这是一种最简单的文件物理结构，他把逻辑上连续的文件信息依次存放在连续编号的物理快中。 在顺序结构中，一个文件的目录项中只要指出该文件占据的总块数和起始块号即可。 顺序结构的优缺点 优点：只要是知道了文件在文件存储设备上的起始块号和文件长度，就能很快地进行存取。 缺点：文件不能动态增长。 链接结构 链接结构原理 为每个文件构造所使用的磁盘块的链表。使用这种链接结构的文件，将逻辑上连续的文件分散存放在若干个不连续的物理块中。 间接索引是在索引表所指的物理快中不存放在文件信息，而是装有存在这些信息的物理快地址。 在索引结构文件中要存取文件时，需要至少访问存储设备两次以上，其中，一次是访问索引表，另一次是根据索引表访问在存储设备上的文件信息。 索引表的链接模式：一个索引表通常就是一个物理盘快。对大文件就用多个索引连接在一起。 多级索引：将一个大文件的所有索引表（二级索引）的地址存放在另一个索引表（一级索引）中。 索引结构的示例–I节点 基本思想：给每个文件赋予一张称为I节点的小表，在这张小表中列出了文件属性及文件中个块在磁盘上的地址。 文件数据盘快，称为直接盘快。 该索引指向文件数据盘快，称为一重间接盘快。 二级索引表，称为二重间接盘快。 三级索引表，称为三重间接盘快。 文件的存储介质 存储介质的特点 外存储设备同内存相比较，一般有容量大、断电后仍可保存信息、速度快慢、成本较低等特点。 外存储设备通常由驱动部分和存储介质两部分组成。存储介质又常称为卷。 驱动器的作用是是计算机能够实现读写（及保存、控制、测试）存储介质上的内容。 存储设备有很多种类。如磁盘、磁带、磁鼓、纸带、光盘和内存等。一个计算机系统中可同时连接说中存储设备。 磁盘空间由盘面、柱面、磁道和扇区组成。 外存设备存取的过程大致由：读状态-》置数据-》置地址-》置控制-》读状态。 用户对外存储设备的要求 用户对外存设备的要求是：方便、效率、安全。 在读写外存储设备时不涉及硬件细节，用户直接使用逻辑地址和逻辑操作。 外存储设备存取速度尽可能快，容量大切空间利用率高。 外存储设备上存放的信息安全可靠，防止来自硬件的故障和他人的侵权。 可以方便的共享，存储空间可以动态扩大、缩小，携带，拆卸便捷，可随时了解存储设备及使用情况。 以尽可能小的代价完成上述要求。 文件在存储设备中的存取 顺序存储设备 磁带就是典型的顺序存储介质。 优点：存储容量大； 缺点：存取速度比较慢。 随机存取设备 磁盘是典型的随机存储设备。 磁盘一般由若干个磁盘片组成，每个磁盘片对应两个读写磁头，分别对磁盘片的上下两面进行读写。各个磁头与磁头臂之间相连。系统在对磁盘初始化时，将盘片上划分出一些同心圆，作为存储信息的介质，称为磁道。对每个磁道又分为若干段，称为扇区。每个扇区就构成了一个物理快，整个磁盘上所有扇区（物理块）统一编号，从零开始，所有磁盘片的相同磁道称为柱面。 磁盘上每个物理快的位置可用柱面号、磁头号、扇区号。 已知物理号，则磁盘地址： 柱面号 = [ 物理块号/(磁头数 X 扇区数) ] 磁头号 = [(物理块号 mod (磁头数 X 扇区数)) / 扇区数] 扇区号 = (物理块号 mod (磁头数 X 扇区数)) mod 扇区数 已知磁盘地址： 物理块号 = 柱面号 X（磁头数 X 扇区数）+ 磁头号 X 扇区数 + 扇区号。 磁头臂只能沿半径方向移动。在访问磁盘时，首先要把磁头臂移动到相应柱面的磁道上，称为寻道。然后等待盘片旋转，使指定的扇区转到磁头之下，实现了对磁道和扇区的定位。最后控制磁头对扇区中的数据进行读写。 一次访问磁盘的时间由寻道时间、旋转定位时间和数据传输时间所组成，寻道时间是机械动作的时间，因而需要花费的时间最长。 文件的存储方式 在用户面前，文件的呈现方式是文件的物理结构，在存储介质面前，文件呈现的是文件的物理结构，这与文件所使用的存储介质的特性有关。 哪一种文件的存取方式，取决于用户使用文件的方式，也与文件所使用的存储介质有关。数据库文件，就适合采用随机存储的方法。而如果存储介质采用的是磁带，就只能采用顺序存储。 顺序存储 顺序存储就是从前往后的依次访问文件的各个信息项。 若当前读取的记录为R，则下一次读取的记录被自动的确定为Ri+1. 随机存储 随机存取又称为直接存取，即允许用户按任意的次序直接存取文件中的任意一个记录，或者根据存储命令把读写指针移到文件的指定记录处读写。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

计算机的主要功能之一就是对数据进行数值或非数值计算。系统软件必须提供数据存储、数据处理、数据管理的基本功能。数据管理是通过文件管理的方式来完成的，而目录又是建立在分区或卷的基础之上的。操作系统中文件和目录相关的子系统称之为文件系统。 计算机程序都要存储信息、检索信息。 能够存储大量的信息。 长期保存信息。 可以共享信息。 管理的内容：文件的结构、命名、存取、使用、保护和实现方法。 透明存取：指的是不必要了解文件存放的物理机制和查找方法，只需要给定一个代表某段程序或数据的文件名称，文件系统就会自动的完成对与给定文件名称相对应的文件的有关操作。 文件和文件系统 文件的定义 文件：一组带标识的、逻辑上有完整意义的信息项的序列。 标识：文件名。 信息项：文件内容的基本单位。一组有序序列。 读写指针：用来记录文件当前的读取位置，它向下一个将要读取的信息项。 写指针：用来记录文件当前的写入位置，下一个将要写入的信息项被写到该处。 文件的长度：是单字节或多字节，这些字节可以是字符，也可以组成记录。 UFS：可达255个字符。 FAT12（MS-DOS所使用的文件系统）命名规则规定文件名为8个字符。 NTFS：达到255个字符。 EXT2：chap5, htm, Chap5等文件名称。 文件系统 文件系统：操作系统中统一管理信息资源的一种软件。 从用户的角度来看，文件系统负责为用户建立文件、读写文件、修改文件、复制文件和撤销文件。文件系统还负责完成对文件的按名存取和对文件进行存取控制。 文件分类 按文件的用途分类 系统文件 操作系统和各种系统应用程序和数据所组成的文件。 不允许对该类文件进行读写或修改。 库函数文件 标准子程序及常用应用程序组成的文件。允许用户对其进行读取、执行，但不允许对其进行修改。C语言子程序库。 用户文件 用户文件是用户委托文件系统保护的文件。可以由源程序、目标程序、用户数据文件、用户数据库等组成。 按文件的组织形式分类 普通文件 指文件的组织格式为文件系统中所规定的最一般格式的文件。普通文件即包括用户文件、库函数文件和用户实用程序文件等。 目录文件 有文件的目录构成的特殊文件。含有文件目录信息的一种特定文件。主要用来检索文件的目录信息。 特殊文件 把特殊文件的操作转成为对应设备的操作。 一些常见的文件分类方式 按文件的保护方式可划分为：只读文件、读写文件、可执行文件、无保护文件等 按信息的流向分类可划分为：输入文件、输出文件和输入输出文件 按文件的存放时限可划分为：临时文件、永久文件和档案文件 按文件所使用的介质类型可划分为：磁盘文件、磁带文件、卡片文件和打印文件 按文件的组织结构分类：顺序文件、链接文件和索引文件。 UNIX类操作系统中文件的分类 普通文件 目录文件 特殊文件 文件系统的功能 统一管理文件的存储空间，实施存储空间的分配和回收。 实现文件从名字空间到外存地址空间的映射。 实现文件信息的共享，并提出文件的保护和保密措施。 向用户提供一个方便使用的接口。 系统维护及向用户提供有关信息。 保持文件系统的执行效率。 提供与I/O的统一接口。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

虚拟存储技术 基本思想：利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存。 操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存与磁盘之间动态交换。支持多道程序设计技术。 实现虚拟存储器需要以下的硬件支持： 系统有容量足够大的内存。 系统有一定容量的内存。 最主要的是：硬件提供实现虚-实地址映射的机制。 工作原理：当进程开始运行时，现将一部分程序转入内存，另一部分暂时留在外存但要执行的指令不在内存时，系统自动选择部分内存空间将其中原有的内容交换到磁盘扇区，并释放这些内存空间供其他进程使用。 交换技术是以进程为单位进行的，进程所需内存大于当前西戎内存，那么该进程就不能在系统中运行。 虚拟内存一般是以页或段为单位，所以如果一个进程所需内存大于当前系统内存，那么该进程仍然可以在系统中正常运行，因为该进程的一部分可以被还出到外存上。 虚拟页式存储管理 基本思想 在进程开始运行之前，不是装如全部页面。而是转入一个或零个页面，之后根据进程运行的需要，动态转入其他页面，当内存空间已满，而又需要装入新的页面时，则根据某种算法置换出某个页面，易变装入新的页面。 在使用虚拟页式存储管理时需要在页表中增加以下表项： 页号—页面的编号。 有效位—又称驻留位、存在位或中断位，表示该页是在内存还是在外存。 页框号—页面在内存中时所对应的内存块号。 访问位—又称引用位或参考位，表示该页在内存期间是否被访问过。 修改位—表示该页在内存中是否被修改过。 保护位—是否能读写执行。 禁止缓存位—采用内存映射I/O的机器中需要的位。 缺页中断 页面调度策略 虚拟存储器系统通常定义三种策略来规定如如何（或何时）进行页面调度：调入策略、置页策略和置换策略。 调入策略 什么时候将一个页由外存调入内存中。 请求调页：只调入发生缺页时所需的页面。这种调入策略实现简单，但容易产生较多的缺页中断，造成对外存I/O次数过多，时间开销过大，容易产生抖动现象。 预调页：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。提高了调页I/O效率，减少I/O次数。 置页策略 当线程产生缺页中断，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则。 置换策略 如果缺页中断发生时物理内存已经满，“置换策略”被用于确定那个虚拟页面必须从内存中移出，为新的页面腾出空位。 固定分配局部置换：可基于进程的类型，为每一进程分配固定的页数的空间，在整个运行期间都不会再改变。采用该策略时，如果进程在运行中出现缺页，则只能从该进程的N个页面中选出一个换出，然后再调入一页，以保证分配给该进程的内存空间不变。 可变分配全局置换：先为系统中的每一进程分配一定数量的物理快，操作协同本身也保持一个空闲物理快队列，当某进程发生缺页是，由系统的空闲物理快队列中取出一物理快分配给该进程。但当空闲物理快队列中的物理快用完时，操作系统才从内存中选这一块调出。该块可能是系统中任意一个进程的页。 可变分配局部变量：基于进程的类型，为每个进程分配一定的数目的内存空间。但当某进程发生缺页时，只允许从该进程的页面中选出一页换出，这样就不影响其他进程的运行。 页面置换算法 如果刚被调出的页面又要立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁，这种现象称之为“抖动”或称“颠簸”。 先进先出页面置换算法FIFO 选择最先装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。 把转入内存的哪些页面的页号按进入的先后次序排好队，每次总是调用队首的页，当装入一个新页面后，把新页面的页号排入队尾。 把操作系统维护一个所有当前在内存中的页面的链表，最老的页面在表头，最新的页面在表尾。当发生缺页时，置换表头的页面并把新调入的页面加到表尾。 最近最少使用页面置换算法LRU 在缺页发生时，首先置换掉最长时间未被使用过的页面。 总是选择距离现在最长时间内没有被访问过的页面先调出。实现这种算法的一种方法是在页表中为每个页增加一个“计时”标志，记录该页面自上次被访问以来的所经历的时间，每个访问一次都应从“0”开始计时。 计时值最大的那一页调出（即最近一段时间里最长时间没有被使用过的页），此开销比较大。 最近最不常用页面置换算法LFU 根据在一段时间里页面被使用的次数选择可以调出的页，如果一个页面被访问的次数比较多，则是最常使用的页面，就不应该把它调出。 每一页设置一个计数器，每当访问一页时就把该页对应的计数器加1，另外，操作系统还要确定一个周期T，在周期T的一段时间内，若没有发生缺页中断，则把所有的计数器清“0”，开始一个新的周期从新计数。若在周期T的时间内发生了缺页中断，则选择计数值最小的那页调出。 实现要花很大的开销，并且要确定一个合适的周期T也有一定的难度。 理想页面置换算法OPT 该算法置换以后不再需要的或者在最长时间以后才会用到的页面。 作为衡量其他页面置换算法优势的一个标准。 最近未使用页面置换算法NRU 当访问页面（读或写）时设置R位，当写入页面（即修改页面）时设置M位。 用R位和M位可以构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都是由操作系统设置为0，定期将R位（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。 NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰。在最近一个时钟滴答中（典型的时间为20ms）置换一个没有被访问的已经修改的页面比要置换一个被频繁使用的“干净”页面好。 优点：易于理解和能够有效地被实现。但性能并不是最好的。 第二次机会页面置换的算法 FIFO算法可能会把经常使用的页面置换出去。检查进入内存时间最久的页面的R位，如果是0，那么这个页面即老有没有被使用过，可以立刻置换掉；如果是1，就将R位清0，并把该页放到链表的尾部，修改其进入时间，然后继续搜索。 基本思想：寻找一个从来没有访问过的页面，如果所有的页面都被访问过了，该页面就退化为FIFO算法。 时钟页面置换算法Clock 把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面，如果他的R位为0，就置换这个页面，并把新的页面插入到这个位置，然后把表针前移一个位置，如果是R位是1，就清楚R位并把表指针前移一个位置，重复这个过程直到找到一个R位为0的页面为止。 缺页中断率 假设一个程序共有n页，系统分配给它的内存块是m块（m、n均为正整数，且1<=m<=n）。该程序最多有m页可以同时装入内存。如果程序执行中访问页面的总次数为A，其中有F次访问的页面尚未装入内存，故产生了F次缺页中断。 f = F / A 把f称为“缺页中断率”。 缺页中断率与缺页中断的次数有关。 分配给程序的内存块数 分配给程序的内存块数多，这同时装入内存的页面数就越多，故减少了缺页中断的次数，也就降低了缺页中断率，反之，缺页中断率就高。 页面的大小 页面的大小取决于内存分块的大小，快大页面也大，每个页面大了则程序的页面数就少。装入程序时是按页面存放在内存中的，因此，装入一页的信息量就越大，就减少了缺页中断的次数，降低了缺页中断率。反之，若页面小则缺页中断率就越高。 程序编制方法 缺页中断率与程序的局部化程度密切相关。 页面置换算法 页面置换算法对缺页中断率的影响很大，调度不好就会出现“抖动”，理想的调度算法（OPT）能使缺页中断率最低。 虚拟存储管理的性能问题 在虚拟内存中，页面可能在内存与外存之间频繁调度，有可能出现抖动或颠簸。 颠簸是由于缺页率高引起的。 一般进程在一段时间内集中访问一些页面，称为“活动页面”，如果分配给一个进程的内存物理页面数太少，使得该进程所需要的“活动页面”不能全部装入内存，则进程在运行过程中会频繁的发生缺页中断，从而产生颠簸。 段式与段页式存储管理方案 段式与段页式存储管理方案 设计思想 系统将内存空间动态划分为为若干个长度不同的区域，每个区域乘坐一个物理段。每个物理段在内存中有一个起始地址，乘坐段首址。将物理段中的所有单元从0开始依次编址，称为段内地址。 用户程序则按逻辑上有完整意义的段来划分，称为逻辑段（简称段），将用户程序的所有逻辑段从0开始编号，称为段号。将一个逻辑段中的所有单元从0开始编址，称为段内地址。用户程序的逻辑地址由段号和段内两部分组成。 内存分配时，系统以段为单位进行内存分配，为每个逻辑段分配一个连续的内存区（物理段）。逻辑上连续的段在内存中不一定连续存放。 段表包括逻辑段号、物理段起始地址（段首址）和物理长度三项内容。 按逻辑段的顺序排列，放在内存中。 地址转换 与页式存储管理相同，为了实现段式管理，系统提供一对寄存器：段表起始地址和段表长度寄存器。 段表起始地址寄存器用于保存正在运行程序的段表在内存的首地址。当进程被调度程序选中并投入使用时，系统将其段表首地址从进程控制块中取出送入该寄存器。 段表长度寄存器用于保护正在运行进程的段表的长度。当进程被选中时，系统将他从进程控制块中取出送入该寄存器。 与可变分区管理方案的比较 相同：有相同结构的内存分配表，包括已分配区表和空闲区表。 不同：段式存储管理是为程序的每一个分段分配一个连续的内存空间。 段页式存储管理方案 为用户提供了一个二维地址空间，满足程序和信息的逻辑分段的要求。段式管理反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护，大大方便了用户。 特征：等分内存，有效的克服了碎片，提高了存储器的利用率。 基本思想：用页式存储方法来分配和管理内存空间，即把内存划分为若干大小的相等的页面；用段式方法对用户程序按照其内在的逻辑关系划分成若干个大小相等的页面。内存是以页为基本单位的分配给每个用户程序的，逻辑上相邻的页面在物理内存中不一定相邻。 需要增加段式管理和页式管理的成分：必须为每个程序建立一张段表；由于一个段又被分为了若干也，系统有为每个段建立一张表页。段表中记录了该段对应页表的起始地址和长度，而页表则给出该段逻辑页面与内存块号之间的对应关系。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

把一个逻辑地址连续的程序分散存放到几个不连续的内存区域中，并且保证程序的正确执行，即可充分利用内存空间，又可减少移动所花费的开销。 基本思想 该技术已广泛用于微机系统中，支持页式存储管理的硬件部件通常称为“存储管理部件”。 存储管理部件首先把内存分为大小相等的许多区把每个区称为“块”，块是进行主存空间分配的物理单位。要求程序中的逻辑地址也进行分页，页的大小与块的大小一致。 假定地址用m个二进制表示，其中页内地址部分占用n个二进制位，那么，每一块的长度就是2的n次方，也就是每一页有2的n次方个字节。页号部分占用了m-n位，所以，最大的程序可允许有2的（m-n）次方个页面。逻辑地址从“0”，页内地址也为“0”，当编制到2的n次方-1时，第0页的页内地址的各位均为“1”，即占满了一个页面。下一个地址是2的n次方，这时页号部分就为“1”，而页内地址部分又恢复到了“0”，表示进入了第1页。再继续顺序编址，此时页内地址0~(2のn次方-1)是属于第1页。一组顺序的逻辑地址结构将其自然地分页。 存储空间的分配与回收 那些块已经分配。 那些块尚未进行分配。 当前剩余的空闲块数。 假设内存的可分配区域被分为256块，则可用字长为32位的8个字作为“位示图”，位于图中的每一位与一个内存块对应，每一一个的值可以是0或1，0表示对应的内存块为空闲，1表示已经占用。 找出一些为0位，把这些位置成1，并从空闲块数中减去本次分配的块数，然后按照找的的位计算出相对应的块号。 块号 = 字号 X 字长 +位号 根据归还的块号计算出该块在位示图中对应的位置，将占用标志修改成0，再把回收的块数相加到空闲块数中。 地址转换与块表 为每一个被装入内存的进程提供一张页表，该页表所在内存的起始地址和长度作为现场信息存放在该进程的PCB中。 页式存储管理的地址转换 当进程被调度程序选中投入运行时，系统将其页表手地址从进程控制块中取出送入该寄存器，页表长度寄存器用于保存正在运行进程的页表的长度。 页表指出该程序逻辑地址中的页号与所占用的内存块号之间的对立关系。页表长度由程序拥有的页面数而定，故每个程序的页表长度可能是不同的。 若页表中有次页号，则可得到对应的内存块号， 物理地址 = 内存块号 x 块长 + 页内地址 页表 多级页表 假设用户地址空间为2GB，页面大小为4KB，则一个进程最多有2的19次方页。 存放页表的页面为页表页。 在大多数操作系统中采用二级页表，有页表页和页目录一起构成进程页表。 第一级表示页目录，保存页表页的地址，第二级表示页表页，保存物理页面号（即内存块号）。 散列页表 当地址空间大于32位时，一种常见的方法是使用以页号为散列值的散列页表。 虚拟页号 所映射的页框号。 指向链表中下一个元素的指针。 反置页表 每个进程都有与之相关的页表。 每个物理页框对应一个表现，每个表项包含与该页框相对应的虚拟页面地址以及拥有该页面进程的信息。 块表 页面存储管理中的页表是存放在内存中的。当要按给定的逻辑地址进行读写时，必须访问内存两次。 第一次按页号读出页表中对应的块号。 第二次按计算出来的绝对地址进行读写。 两次访问内存显然延长了指令的执行周期，降低了执行速度。 在地址映射机制中增加一组高速寄存器保存页表，这需要大量的硬件开销，在经济上不可行。 在地址映射机制中增加一个小容量的联想寄存器（相联寄存器），他又Cache组成。 利用高速缓冲存储器存放当前访问次数最少活动页面的页号，这个高速缓冲器被称为“快表”，也称为转换检测缓冲器。TLB 快表中登记了页表中的一部分页号与内存块号的对应关系。 快表只存放当前进程中最活跃的少数几页，随着进程的推进，快表的内容动态更新。 更新原理：查找快表和查找内存页表，而直接利用快表中的逻辑页号。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

平衡二叉树介绍 平衡二叉树，又称AVL树，实际上就是遵循一下两个特点的二叉树： 每一子树中的左子树和右子树的深度都不超过1； 二叉树的每一个子树都要求是平衡二叉树。 只要是每个子树都满足左子树还有右子树的深度都不超过1即可。 平衡因子 每一个结点都有各自的平衡因子，表示的就是左子树深度同右子树深度的差。 平衡二叉树中的各结点平衡因子取值只可能是：0、1、-1. 其中 （a） 的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过 1，所以 （a） 中两棵二叉树都是平衡二叉树；而 （b） 的两棵二叉树中有结点的平衡因子数的绝对值超过 1，所以都不是平衡二叉树。 二叉排序树转化为平衡二叉树 为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。 例如，使用上一节的算法在对查找表{13，24，37，90，53}构建二叉排序树时，当插入 13 和 24 时，二叉排序树此时还是平衡二叉树： 当继续插入 37 时，生成的二叉排序树如图 （a），平衡二叉树的结构被破坏，此时只需要对二叉排序树做“旋转”操作（如图（b）），即整棵树以结点 24 为根结点，二叉排序树的结构没有破坏，同时将该树转化为了平衡二叉树： 当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，如图（a）所示，此时只需要改变扁担的支撑点（树的树根），就能使其重新归为平衡。实际上（b） 是对（a） 的二叉树做了一个向左逆时针旋转的操作。 继续插入 90 和 53 后，二叉排序树如图 （a）所示，导致二叉树中结点 24 和 37 的平衡因子的绝对值大于 1 ，整棵树的平衡被打破。此时，需要做两步操作： 如图 （b） 所示，将结点 53 和 90 整体向右顺时针旋转，使本该以 90 为根结点的子树改为以结点 53 为根结点； 如图 （c） 所示，将以结点 37 为根结点的子树向左逆时针旋转，使本该以 37 为根结点的子树，改为以结点 53 为根结点； 做完以上操作，即完成了由不平衡的二叉排序树转变为平衡二叉树。 特殊的树转为平衡树的情况 当平衡二叉树由于新增数据元素导致整棵树的平衡遭到破坏时，就需要根据实际情况做出适当的调整，假设距离插入结点最近的“不平衡因子”为 a。则调整的规律可归纳为以下 4 种情况： 单向右旋平衡处理：若由于结点 a 的左子树为根结点的左子树上插入结点，导致结点 a 的平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则只需进行一次向右的顺时针旋转，如下图这种情况： 单向左旋平衡处理 ：如果由于结点 a 的右子树为根结点的右子树上插入结点，导致结点 a 的平衡因子由 -1变为 -2，则以 a 为根结点的子树需要进行一次向左的逆时针旋转，如下图这种情况： 双向旋转（先左后右）平衡处理 ：如果由于结点 a 的左子树为根结点的右子树上插入结点，导致结点 a 平衡因子由 1 增至 2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转操作，如下图这种情况： 注意：图中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置还是结点 C 右孩子，（c）中插入结点的位置为结点 A 的左孩子。 双向旋转（先右后左）平衡处理：如果由于结点 a 的右子树为根结点的左子树上插入结点，导致结点 a 平衡因子由 -1 变为 -2，致使以 a 为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作，如下图这种情况： 注意：图中插入结点也可以为结点 C 的右孩子，则（b）中插入结点的位置改为结点 B 的左孩子，（c）中插入结点的位置为结点 B 的左孩子。 注 ：在对查找表{13，24，37，90，53}构建平衡二叉树时，由于符合第 4 条的规律，所以进行先右旋后左旋的处理，最终由不平衡的二叉排序树转变为平衡二叉树。 时间复杂度 使用平衡二叉树进行查找操作的时间复杂度为O(logn)。 构建平衡二叉树代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 #include <stdio.h> #include <stdlib.h> //分别定义平衡因子数 #define LH +1 #define EH 0 #define RH -1 typedef int ElemType; typedef enum {false,true} bool; //定义二叉排序树 typedef struct BSTNode{ ElemType data; int bf;//balance flag struct BSTNode *lchild,*rchild; }*BSTree,BSTNode; //对以 p 为根结点的二叉树做右旋处理，令 p 指针指向新的树根结点 void R_Rotate(BSTree* p) { //借助文章中的图所示加以理解，其中结点 A 为 p 指针指向的根结点 BSTree lc = (*p)->lchild; (*p)->lchild = lc->rchild; lc->rchild = *p; *p = lc; } ////对以 p 为根结点的二叉树做左旋处理，令 p 指针指向新的树根结点 void L_Rotate(BSTree* p) { //借助文章中的图 6 所示加以理解，其中结点 A 为 p 指针指向的根结点 BSTree rc = (*p)->rchild; (*p)->rchild = rc->lchild; rc->lchild = *p; *p = rc; } //对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理，令指针 T 指向新的根结点 void LeftBalance(BSTree* T) { BSTree lc,rd; lc = (*T)->lchild; //查看以 T 的左子树为根结点的子树，失去平衡的原因，如果 bf 值为 1 ，则说明添加在左子树为根结点的左子树中，需要对其进行右旋处理；反之，如果 bf 值为 -1，说明添加在以左子树为根结点的右子树中，需要进行双向先左旋后右旋的处理 switch (lc->bf) { case LH: (*T)->bf = lc->bf = EH; R_Rotate(T); break; case RH: rd = lc->rchild; switch(rd->bf) { case LH: (*T)->bf = RH; lc->bf = EH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; L_Rotate(&(*T)->lchild); R_Rotate(T); break; } } //右子树的平衡处理同左子树的平衡处理完全类似 void RightBalance(BSTree* T) { BSTree lc,rd; lc= (*T)->rchild; switch (lc->bf) { case RH: (*T)->bf = lc->bf = EH; L_Rotate(T); break; case LH: rd = lc->lchild; switch(rd->bf) { case LH: (*T)->bf = EH; lc->bf = RH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; R_Rotate(&(*T)->rchild); L_Rotate(T); break; } } int InsertAVL(BSTree* T,ElemType e,bool* taller) { //如果本身为空树，则直接添加 e 为根结点 if ((*T)==NULL) { (*T)=(BSTree)malloc(sizeof(BSTNode)); (*T)->bf = EH; (*T)->data = e; (*T)->lchild = NULL; (*T)->rchild = NULL; *taller=true; } //如果二叉排序树中已经存在 e ，则不做任何处理 else if (e == (*T)->data) { *taller = false; return 0; } //如果 e 小于结点 T 的数据域，则插入到 T 的左子树中 else if (e < (*T)->data) { //如果插入过程，不会影响树本身的平衡，则直接结束 if(!InsertAVL(&(*T)->lchild,e,taller)) return 0; //判断插入过程是否会导致整棵树的深度 +1 if(*taller) { //判断根结点 T 的平衡因子是多少，由于是在其左子树添加新结点的过程中导致失去平衡，所以当 T 结点的平衡因子本身为 1 时，需要进行左子树的平衡处理，否则更新树中各结点的平衡因子数 switch ((*T)->bf) { case LH: LeftBalance(T); *taller = false; break; case EH: (*T)->bf = LH; *taller = true; break; case RH: (*T)->bf = EH; *taller = false; break; } } } //同样，当 e>T->data 时，需要插入到以 T 为根结点的树的右子树中，同样需要做和以上同样的操作 else { if(!InsertAVL(&(*T)->rchild,e,taller)) return 0; if (*taller) { switch ((*T)->bf) { case LH: (*T)->bf = EH; *taller = false; break; case EH: (*T)->bf = RH; *taller = true; break; case RH: RightBalance(T); *taller = false; break; } } } return 1; } //判断现有平衡二叉树中是否已经具有数据域为 e 的结点 bool FindNode(BSTree root,ElemType e,BSTree* pos) { BSTree pt = root; (*pos) = NULL; while(pt) { if (pt->data == e) { //找到节点，pos指向该节点并返回true (*pos) = pt; return true; } else if (pt->data>e) { pt = pt->lchild; } else pt = pt->rchild; } return false; } //中序遍历平衡二叉树 void InorderTra(BSTree root) { if(root->lchild) InorderTra(root->lchild); printf("%d ",root->data); if(root->rchild) InorderTra(root->rchild); } int main() { int i,nArr[] = {1,23,45,34,98,9,4,35,23}; BSTree root=NULL,pos; bool taller; //用 nArr查找表构建平衡二叉树（不断插入数据的过程） for (i=0;i<9;i++) { InsertAVL(&root,nArr[i],&taller); } //中序遍历输出 InorderTra(root); //判断平衡二叉树中是否含有数据域为 103 的数据 if(FindNode(root,103,&pos)) printf("\n%d\n",pos->data); else printf("\nNot find this Node\n"); return 0; } 本博文从 平衡二叉树（AVL树）及C语言实现 严长生 转载而来，表示感谢。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

覆盖技术 覆盖技术是指一个程序的若干程序段和几个程序的某些部分共享一个存储空间。覆盖技术的实现是把程序分为若干个功能上相对独立的程序，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。 覆盖技术是用户程序自己附加的控制。要把一个程序划分成不同的程序段，并规定好他们的执行和覆盖顺序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。 该程序正文段所需要的内存空间是A（20KB）+B（50KB）+F（30KB）+C（30KB）+D（20KB）+E（40KB）=190KB，但是在采用了覆盖技术后只需要A（20KB）+B（50KB）+E（40KB）=110KB占用空间。 覆盖技术主要用于系统程序的内存管理上，MS-DOS系统分为两个部分。 操作系统中经常要用到的基本部分，它们常驻在内存且占用固定区域。 不太经常使用的部分，它们存放在磁盘上，当调用它们时才被调入内存覆盖区。 交换技术 交换技术：在分时系统中，用户的进程比内存能容纳的数量要多，这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时，再将它们装入内存。 进程从内存移到磁盘并再移动回内存称为交换。交换技术是进程在内存与外存之间的动态调度，是由操作系统控制的。 后备存储区（又称盘交换区）。 目的：尽可能达到”足够快的交换进程，以使当CPU调度程序想重新调度CPU时，总有进程在内存中处于就绪（准备执行）状态“的理想状态，从而提高内存利用率。 交换技术的原理： （1）换出进程的选择：系统需要将内存中的进程换出时，应该选择那个进程？ 根据时间片轮转法或基于优先数的调度算法来选择要换出的进程。 （2）交换时间的确定 在内存空间不够或有不够的危险时，还出内存中的部分进程到外存，以释放所需要的内存。 （3）交换空间的分配 在一些系统中，当进程在内存中时，不再外塔分配磁盘空间。当它被换出时，必须为它分配磁盘交换空间。 在另一些系统中，进程一但创建，就分配给它磁盘上的交换空间。无论何时程序被换出，他都被换到已经为它分配的空间，而不是每次换到不同的空间。 （4）换入进程换回内存时位置的确定 绝对地址：在原来的位置上； 相对地址：可再进行地址重定位。 交换技术的缺点： 由于交换时需要花费大量的CPU时间，这将影响对用户的响应时间，因此，减少交换的信息量是交换技术的关键问题。 合理的做法： 在外存中保留每个程序的交换副本，换出时仅将执行时修改过的部分复制到外存。 覆盖技术和交换技术的发展导致了虚拟存储技术的出现。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

基本思想：是把内存划分成若干个连续的区域，称为分区，每个分区装入一个运行程序。 固定分区 基本思想 固定分区是指系统先把内存划分为若干个大小固定的分区，一旦分配好，在系统运行期间便不再重新划分。程序运行时必须提供对内存资源的最大申请量。 内存分配表与分区的分配、回收 用于固定分区管理的内存分配表是一张分区说明表，按顺序每个分区说明表中对应一个表目。表目内容包括分区序号、分区大小、分区起始地址以及使用状态（空闲或占用）。一个程序在运行时，想要根据其对内存的需求量，按一定的分配策略在分区说明表中查找空闲分区。若找到合乎需要的分区，就将该分区分配给程序，并将该分区置为占用状态。当程序完成时释放这块分区内存，由系统回收，并在分区说明表中间回收的分区重新置为空闲状态。 固定分区方案灵活性差，可接纳程序的大小受到了分区大小的严格限制。 可变分区 基本思想 可变分区是指系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。可变分区有较大的灵活性，较之固定分区能更好的内存利用率。 系统初次启动后，在内存中出操作系统区之外，其余空间为一个完整的大空闲区，当有程序要求装入内存运行时，系统从该空闲区中划分出一块与程序大小相同的区域进行分配。当系统运行一段时间后，随一系列的内存分配与回收，原来的一整块大空闲区形成了若干占用区和空闲区相间的布局，若有上下相邻的两块空闲区，系统应将他们合并成为一块连续的大空闲区。 移动技术 内存经过一段时间的分配回收之后们会存在很多晓得空闲块。它们每一块都不足以满足程序进一步分配内存的要求，但其总和却可以满足程序的分配要求，这些空闲块称之为碎片。 解决碎片的办法：在适当时刻进行碎片整理，通过移动内存中的程序，把所有空闲碎片合成一个连续的大空闲区且放在内存的一端，而把所有程序占用区放在内存的另一端，称为“移动技术”或“紧凑技术”或“紧缩技术”。 提高内存的利用率，便于作业动态扩充内存。采用移动技术需要注意以下问题： 移动技术会增加系统的开销。增大了系统运行时间。 移动是由条件的，不是任何在内存中的作业都能随时移动。 采用移动技术是应该尽可能减少需要移动的作业数和信息量。 可变分区的实现 采用可变分区方式管理时，要有硬件的地址转换机构作为支持。硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器。 基址寄存器用来存放程序所占用分区的起始地址。 限长寄存器用来存放程序所占分区的长度。 但程序被装到所分配的分区后，把分区的起始地址和长度作为现场信息存入该作业进程的进程控制块中。 为了实现可变分区的管理，必须设置某种数据结构用以记录内存分配的情况，确定某种分配策略并且实施内存的分配与回收。 内存分配表由两张表格组成： 已分配区表：记录已装入的程序在内存中占用分区的起始地址和长度，用标志位指出占用分区的程序名。 空闲区表：记录内存中可供分配的空闲区的起始地址和长度，用标志位指出该分区是未分配的空闲区。 空闲分区的分配策略 最先适应算法 最先适应算法，又称顺序分配算法，当接到内存申请是，顺序查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配，可以快速做出分配决定。 最优适应算法 当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其分割并分配。 优点：最节约空间，因为它尽量不分割大的空闲区。 缺点：可能会形成很多很小的空闲区域，称为碎片。 最坏适应算法 当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。 基本思想：在大空闲区中装入信息后，分割剩下的空闲区相对也很大，还能用于装入其他程序。 优点：是可以避免形成碎片。 缺点：分割了大的空闲区后，如果在遇到较大的程序申请内存时，无法满足要求的可能性越大。 下次适应算法 当接到内存申请时，查找分区说明表，从上一次分配的位置开始扫描内存，选择下一个大小足够的可用块。 分区的回收 当用户程序执行接受后，系统要回收已经使用完毕的分区，将其记录在空闲区表中。在回收空间时，应首先检查是否有与回收区相邻的空闲区，即检查相邻的空闲区表中标志为“未分配”的栏目，以确定是否有相邻空闲区，若有，则应合并成一个空闲区登记。 假定作业归还的分区起始地址为S，长度为L。 （1）回收区的上邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。 如果空闲区表中第i个登记栏中的“起始地址+长度”正好等于S，则说明回收区有一个上邻空闲区。 长度 = 原长度 + L 2）回收分区的下邻分区是空闲的，需要将两个空闲区合并成一个更大的空闲区，然后修改空闲区表。 如果S+L正好等于空闲区表中某个登记的栏目（假定为第i栏）所示分区的起始地址表明回收区有一个下邻空闲区。 起始地址 = S 长度 = 原长度 + L 第i栏指示的空闲区是回收区与下邻空闲区合并之后的一个大空闲区。 （3）回收区的上邻分区和下邻分区都是空闲的，需要将三个空闲区合并成一个更大的空闲区，然后修改空闲区表。 S = 第i栏起始地址 + 长度 S + L = 第k栏起始地址 表明回收区既有上邻空闲区，又有下邻空闲区。必须把这三个区合并为一个空闲区。 第i栏起始地址不变。 第i蓝长度为“i栏中原长度+k栏中长度+L”。 第k栏目的标志应修改为“空”状态。 （4）回收分区的上邻分区和下邻分区都不是空闲的，则直接将空闲分区记录在空闲区表中。 应找一个标志为“空”的登记栏，把回收区的起始地址和长度登记入表，且把该栏目中的标志位修改成“未分配”，表示该登记栏中指示了一个空闲区。 分区的保护 （1）系统设置界限寄存器，界限寄存器是可以上下界寄存器或基址、限长寄存器。 （2）保护键发：即为每个分区分配一个保护键，相当于一把锁。同时为每个进程分配一个相应的保护键，相当于一把钥匙，存放在程序状态字中。美方访问内存时，都要检查钥匙和锁是否匹配，若不匹配，将发出保护性中断。 分区管理方案的优缺点 优点：分区管理是实现多道程序设计中一种简单易行的存储管理技术。通过分区管理，内存真正成了共享资源，有效地利用了处理机和I/O设备，从而提高了系统的吞吐量和缩短了周转时间。在内存利用率方面，可变分区的内存利用率比固定分区高。 缺点：内存使用不充分，并且存在较为严重的碎片问题，虽然可以解决碎片问题，但需要移动大量信息，浪费了处理机时间。收到物理存储器实际存储容量的限制。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

进程（线程）间相互作用 相关进程与无关进程 相关进程：在逻辑上具有某种联系的进程。 无关进程：在逻辑上没有任何联系的进程。 如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。无关的并发进程一定没有共享的变量。 如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。 与时间有关的错误 京城执行的速度是不能由进程自身控制的。对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一个进程也开始使用，形成交替使用共享资源。 进程同步：值多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。 进程互斥：指由于共享资源所要求的排他性，进程间要相互竞争以使用这些互斥资源。 进程互斥 解决进程互斥的两种方法： 由竞争各方平等协商。 引入进程管理者，有管理者来协调竞争各方对互斥资源的使用。 临界资源：计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码块、共享数据结构等。对各进程在对临界资源进程进行访问时，特别是进行写入或修改操作时，必须互斥的运行。 计算机系统中资源共享的程度分为三个层次：互斥、死锁和饥饿。 互斥：保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求。 死锁：避免死锁是指多个进程互不相让，避免出现都得不到足够资源的情况，从而保证系统功能的正常运行。 饥饿：避免饥饿是指避免某些进程一直得不到资源或者得到资源的概率很小，从而保障系统内资源使用的公平性。 为了保证临界资源的正确使用，可把临界资源的访问过程分为四个部分： 进入区：为了进入临界区使用临界值资源，在进入区要检查可否进入临界区；如果可以进入临界区，通常设置相应的”正在访问临界区“标志，以阻止其他进程同时进入临界区。 临界区：进程中访问临界资源的一段代码。 退出区：将”正在访问临界区“标识清除。 剩余区：代码中的其他部分。 为了合理使用计算机系系统中的资源，在操作系统中采用的进程同步机制应遵循以下几条： 空闲则入：任何同步机制都必须保证任何时间嗯最多只有一个进程位于临界区。当有程序位于临界区时，任何其他进程均不能进入临界区。 忙着等待：当以有进程处于其他临界区时，后到达的进程只能在进入区等待。 有限等待：为了避免死锁等现象的出现，等待进入临界区的进程不能无期限的”死等“。 让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态以使得其他进程有机会得到处理机的使用权。 进程互斥的软件方法 算法1：单标志算法 假设有两个进程Pi和Pj，设立一个公用整理变量turn，描述允许进入临界区的进程标识。每个进程都在进入区循环检查变量turn是否允许本进程进入。即turn为i时，进程Pi可进入，否则循环检查该变量，直到turn为本进程标识，在退出区修改允许进入进程标识，即进程Pi退出时，Pj的标识为j。 可以保证任何时刻最多只有一个进程在临界区。 缺点：强制轮流进入临界区，没有考虑进程的实际需要，容易造成资源利用不充分。 算法2：双标志、先检查算法 修改临界区标志的设置，设立一个标志数组flag[]，描述各进程是否在临界区，初始值均为FALSE. 在进入区的操作为：先检查，后修改。即在进入区像检查另一个进程是否在临界区，不在时修改本进程在临界区的标志，表示本进程在临界区，在退出区修改本进程在临界区的标志，表示本进程不在临界区。 算法2的优点是克服了算法1的缺点，两个进程不用交替进入，可连续使用。但由于使用多个标志，算法有产生新的问题，即进程Pi和Pj可能同时进入临界区，从而违反了最左只有多个进程在临界区的要求。 算法3：双标志、后检查算法 一是保证检查和修改操作间不会出现间隔。 一是修改标志含义。 算法3可防止两个进程同时进入临界区，但它的缺点是Pi和Pj可能都进入不了临界区。在修改本进程标志flag之后和检查对方flag之间有一段时间间隔，这个间隔导致两个进程都想进入临界区，从而在检查对方标志时不通过。 算法4：先修改、后检查、后修改者等待算法 结合了算法3和1，标志flag[i]表示进程i想进入临界区，标志turn表示同时修改标志时要在进入区等待的进程标识。 在进入区先修改后检查，通过修改统一标志turn来描述标志修改的先后；检查对方标志flag，如果对方不想进入临界区则自己进入；否则在检查标志turn，由于标志turn中保存的是较晚的一次赋值，则交往修改标志的进程等待，较早的修改标志的进程进入临界区。 实现了同步机制要求的四条准则中的前两条：空闲则入、忙着等待。 进程互斥的硬件方法 主要思路：使用一种指令完成读和写的两个操作，因而保证读操作与写操作不被打断，依据采用的指令的不同，硬件方法分成TS指令和Swap指令。 TS（Test-and-Set）指令 TS指令的功能是读出指定标识后把该标志设置为TRUE。 每个临界资源设置一个公共布尔变量lock，表示资源两种状态：TURE表示正被占用，FALSE表示空闲，初始值为FALSE。 有进程在临界区时，重复检查，直到其他进程退出时检查通过，所有要访问临界资源的进程的进入区和退出区代码是相同的。 Swap指令 利用Swap指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，初值为FALSE，每个进程设置一个私有布尔变量key，用于与lock间的信息交换。在进入区利用Swap指令交换lock和key的内容，然后检查key的状态，有进程在临界区时，重复交换和检查过程到其他进程推出啊是检查通过。 优点： 适用范围广：适用于任意数目的进程，在单处理器和多处理器黄健中完全相同。 简单：硬件方法的标志设置简单，含义明确，容易验证其正确性。 支持多个临界区：在一个进程内有多个临界区是，只需为每个临界区设立一个变量。 缺点： 进程在等待进入临界区时，要耗费处理机时间，不能实现”让权等待“。 由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致”饥饿“。 信号量 信号量机制所使用的P、V原语就来自荷兰语test和increment。每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中存放的是阻塞在该信号量的各个进程的标识。 信号量只能通过初始化和标准的原语来访问。 P、V原语的执行，不受进程调度和执行的打断，从而很好地解决了原语操作的整体性。信号量的初始化可指定一个非负整数数值，表示空闲资源总数；若为负值，其绝对值表示当前等待临界区的进程数。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P原语所执行的操作可用下面函数wait（s）来描述。 wait(s){ --s.count; //表示申请一个资源 if(s.count<0){ //表示没有空闲资源 调用进程进入等待队列s.queue; 阻塞调用进程; } } V原语所执行的操作可用下面函数signal(s)描述。 signal(s){ ++s.count; //表示释放一个资源 if(s.count <= 0){ //表示有进程处于阻塞状态 从等待队列s.queue中取出头一个进程P； 进程P进入就绪队列; } } 在使用信号量进行共享资源访问控制时，必须成对使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏。 利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前驱关系。 前趋关系是指并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成执行。可为每个前趋关系设置一个互斥信号量S12，其初值为0.这样，只有在P1执行到V（S12）后，P2才会结束P（S12）的执行。 经典的进程同步问题 Dijkstra将同步问题抽象成一种“生产者-消费者关系”。 简单生产者-消费者问题 设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来。缓冲区只能容纳一个产品，生产者不断的生产产品；而消费者则不断从缓冲区中取出产品，并消费掉。 生产者-消费者同步问题的解决方案如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 生产者进程P: while(true){ P(empty); 生产一个产品; 送产品到缓冲区; V(full); }; 消费者进程Q： while(true){ P(full); 从缓冲区去产品; V(empty); 消费产品; }; 产品生产出来之后立即往缓冲区中存放产品，因为刚开始时缓冲区是空的，一定可以存放一个产品。 多个生产者-消费者问题 设有多个生产者进程P1，P2，……, Pn，若干个消费者进程Q1，Q2，Q3，……，Qm，他们通过一个唤醒缓冲池联系起来，该环形缓冲池由K个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次往空缓冲区送一个产品；消费者每次从缓冲区取出一个产品。生产者进程不断地生产产品并把他们放给缓冲池内，消费者进程不断的从缓冲池内取出产品并消费之。 当整个缓冲池全满时，出现供大于求的现象。当整个缓冲池全空时，出现供不应求的现象。 环形缓冲池是临界资源，因为生产者和消费者都需要使用它。 同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量empty，初值为k，用于指示缓冲池中空缓冲区数目。Q进程不能从“空”的缓冲区中取产品，设置信号量full，初值为0，用于指示缓冲池中满缓冲区数目。 互斥问题：设置信号量mutex，初值为1，用于实现临界区（环形缓冲区）的互斥。 算法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 P1，P2，......,Pn; i:=0; while(true){ 生产产品; P(empty); P(mutex); 往Buffer[i]中放产品; i:=(i+1) mod k; V(mutex); V(full); }; Q1,Q2,......,Qm; j:=0; while(true){ P(full); P(mutex); 从Buffer[i]中存放产品; j:=(j+1) mod k; V(mutex); V(empty); 消费产品; } 读者-写者问题 假定有某个共享文件F，系统允许若干个进程对文件F进行读或写，这里要把读文件的进程称为读者，要把写文件的进程称为写者. 多个进程可以同时读文件F； 任一个进程在对文件F进行写时，按规定每次只允许一个进程执行写操作； 当有进程正在读文件时不允许任何进程去写文件。 当有多个读者与写者都需要读写文件时，按规定每次只允许一个进程执行写操作，且在有进程执行写的时候不允许进程读文件。 同步与互斥的综合应用 例1 路口单双号交通管制 Check：指示可否在车辆号码识别区中进入一辆汽车，由于只能进入一辆，其初值为1. Ddd：指示汽车号码是否为奇数，其初值为0，表是不是奇数。 Lven：指示汽车号码是否为偶数，其初值为0，表示不是偶数。 例2 物流系统中的物品分拣问题 问题 从沿长江一线进入枢纽的集装箱，要从这里直接吊装到上海至旧金山的定期集装箱班轮上。 而从沪杭高速公路上进入枢纽的集装箱，要从这里还转到专门在京沪高速公路上行驶的集装箱运输箱上。 该中转枢纽的场地每次只能接受一个方向来的同一批次的集装箱。 分析 长江一线进入的集装箱卸货是一个生产者，从沪杭高速公路上进入的集装箱卸货是第二个生产者。 这两个生产者都要使用中转枢纽的场地，由于该场地每次只能接受一个方向来的同一批次的集装箱，所以长江一线生产者和沪杭高速公路生产者必须互斥。 Site：指示能否在中转的枢纽的场地上卸下集装箱。 Arrive_Y:指示场地上的集装箱是否来自长江。 Arrive_H:指示场地上的集装箱是否来自沪杭。 说明 由于Site初值为1，P(Site)起到互斥作用，无论谁先卸下了集装箱，另一个物流方向上不能在卸货，只能等待. 进程“旧金山班轮装货”和“北京运输车装货”在装完集装箱之后，都调用V(Site),发出可以接受新集装箱的消息。 Site信号量既作为互斥的信号量，又起着同步信号量的作用。 管程 管程的提出 采用P、V同步机制来编写并发程序，对于共享变量及信号量的操作将被分散于各个进程中。 缺点： 对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序。 程序不利于修改和维护，局部性很差，所以任意一组变量或一段代码的修改都可能影响全局。 正确性难以保证，保证一个复杂系统没有逻辑错误是很难的。 管程的概念及组成 一个管程是一个由过程、变量及数据结构等组成的集合，他们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但他们不能在管程之外声明的过程中直接访问管程内的数据结构。 一个管程由四个部分组成：管程名称、共享数据的说明，对数据进行操作的一组过程和对共享数据赋初值的语句。 管程能保障共享资源的互斥执行，即一次只能有一个进程可以在管程内活动。 三个特性： 模块化： 一个基本程序单位，可以单独编译。 抽象数据类型： 管程是一种特殊的数据类型，其中不仅有数据，而且还有对数据进行操作的代码。 信息隐蔽： 管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能怎么样实现的，其外部则是不可见的。 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接的访问管程中的共享变量，为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作。 任意时刻管程中只能有一个活跃进程，这个特性使管程能有效地完成互斥。当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程，如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒，如果没有活跃进程在使用管程，则该调用进程可以进入。 管程中的条件变量 解决方法是引入条件变量以及相关的两个操作：wait和signal，当一个管程过程发现它无法继续运行时（例如：生产者发现缓冲区满），他会在某个条件变量（如full）上执行wait操作，该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程，另一个进程，比如消费者，可以唤醒正在睡眠的伙伴进程，这可以通过对其伙伴正在等待的一个条件变量执行signal完成。 wait操作必须在signal之前，这条规则使得实现简单了许多，实际上这不是一个问题，因为需要时，用变量很容易跟踪每个进程的状态。 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权每当一个进入管程的进程执行唤醒操作（如P唤醒Q）时，管程中便存在两个同时处于活动状态的进程。 处理方法： P等待Q继续，直到Q退出或等待（Hoare提出）。 Q等待P继续，直到P等待或退出。 规定唤醒为管程中最后一个可执行的操作。 当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当由一个进程等待队列。在管程内部，由于执行唤醒操作，可能会出现多个进程等待队列，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列，它的优先级应当高于入口等待队列的优先级signal(c)；如果c链为空，则相当于空操作，执行此操作的进程继续；否者幻想第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部。 用管程解决生产者-消费则问题 Pthread中的互斥与同步 Pthread提供了可用于线程同步与互斥的机制，他们是互斥量和条件变量，两者结合起来使用已达到管程的效果。 互斥量及相关函数 解决线程互斥问题的基本思想是使用一个可以加锁和解锁的互斥量来保护临界区。一个进程如果想要进入临界区，他首先尝试锁住相关的互斥量。如果互斥量没有加锁，那么这个线程可以立即进入，并且该互斥量被自动锁定以防止其他进程进入。如果互斥量已经被加锁，则调用线程被阻塞，直到该互斥量被解锁。如果多个线程在等待同一个互斥量，当它被解锁时，这些等待的线程中只有一个得到互斥量并将其锁定。 条件变量及相关函数 除互斥量之外，Pthread提供了一种同步机制：条件变量，它允许线程由于一些为满足的条件而被阻塞。 让一个线程锁住一个互斥量，如果该线程不能获得它期望的结果时，则等待一个条件变量；最后另一个线程会向它发出信号，使它可以继续执行。 通信进程 P、V操作是一类低级通信原语，不能承担进程间大量信息的交换任务。 解决进程之间的大量信息通信问题有三个方案：共享内存、消息机制以及通过共享文件进行通信，即管道通信。他们不仅要保证相互制约的进程之间的正确关系，还要同时实现进程之间的信息交换。 共享内存 在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程中的读写互斥问题。操作系统一般只提供要共享的内存空间，而处理进程间在公共内存中的互斥关系则是程序开发人员的责任。 消息机制 消息机制是用于进程间同行的高级通信原语之一。进程在运行过程中可能需要与其他的进程进行信息交流，于是进程通过某种手段发出自己的信息或接收其他进程发来的消息。这种方式类似于人们通过邮政局收发邮件来实现交换信息的目的。 信息缓冲通信 基本思想：根据“生产者-消费者”原理，利用内存中共用消息缓冲区实现进程之间的信息交换。 内存中开辟了若干信息缓冲区，用于存放消息。 一个进程可以给若干个进程发送消息，反之，一个进程可以接受不同进程发来的消息，显然，进程中关于消息队列的操作是临界区，当发送进程正往接收进程的消息队列中添加一条消息时，接收进程不能同时从该消息队列中取出信息；反之也一样。 消息缓冲区通信机制包括以下几个内容： 消息缓冲区：这是一个由消息长度、消息正文、发送者、消息队列指针组成的数据结构。 消息队列首指针：m_q,一般存在PCB中。 互斥信号量m_mutex,初始值为1. 同步信号量m_syn,初始值为0. 发送消息原语send(receiver, a)。 接收信息原语receive(a). 信箱通信 以发送信件以及接收回答新建为进程间通信的基本方式。 当一个进程希望与另一个进程通信时，就创建一个链接两个进程的信箱，发送进程把信件投入信箱，而接收进程可以在任何时刻取走信件。 一个新鲜的结构可有“信箱说明”和“信箱体”两部分组成。 有如下的数据结构： 可存信件数 是在设立信箱时预先确定的，表明信箱的容量大小。 已有信件数 指出信箱中已有信件的数量。 可存信件的指针 指示当前可存入一封信的位置。该指针的初始值为指向可存第一封信的位置。 为了实现信箱通信，必须提供相应的原语，如创建信箱原语、撤销信箱原语、发送信箱原语和接收信箱原语等。 表示的是一个发送者和一个接收者单向通信的例子，在进程A发送信件之间，信箱中至少应该有空位置，可以存放信件，同样，在进程B接收信件之前，信箱中应该有信件，否则进程应该等待。 好处：发送方和接收方不必直接建立联系，没有处理时间上的限制。发送方可以在任何时间发信，接收方可以在任何时间收信。 由于发送方和接收方都是独立工作的，如果发的快而接受的慢，则信箱会溢出。相反，如果发的慢而收的快，则信箱会变空。 规则： 若发送信件时信箱已经满了，则发送进程应被置为“等信箱”状态，直到信箱有空时才被释放。 若取信件时信箱中无信，则接收进程应被置成“等信件”状态，直到有信件时才被释放。 管道通信 管道通信首先出现在UNIX操作系统中。 管道：就是连接在两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。发送进程可以源源不断的从管道一端写入数据流，每次写入的信息长度是可变的，接受进程在需要时可以从管道的另一端读出数据，读出单位长度也是可变的。管道通信的基础是文件系统。 在对管道文件进行读写操作的过程中，发送进程和接收进程都要实施正确的同步和互斥，以确保通信的正确性，管道通信机制中的同步与互斥都由操作系统自动进行，对用户是透明的。 具有传送数据量大的优点，但是通信速度比较慢。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

计算机系统中的存储器可以分为两类：内存储器（简称内存）和外存储器（简称外存）。处理器可以直接访问内存，但不能直接访问内存。CPU要通过启动相应的输入/输出设备后才能使内存和外存交换信息。 内存管理是操作系统中重要功能之一。 基本概念 存储体系 存储设备的速度仍然明显慢于同一级别的中央处理器的速度。任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。 少量的、非常快速、昂贵、内存易变的高速缓冲器Cache，通常是有KB的数量级。 若干兆字节、中等速度、中等价格、内容易变的内存RAM，通常是千MB的数量级。 低速、廉价、内容不一边的外存（磁盘），通常是百至千GB的数量级。 存储管理的任务 任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储空间直接影响系统性能。 内存空间：由存储单元（子节或字）组成的一维连续的地址空间，内存空间用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的亦即程序计数器所指的存储空间。 系统区：用以存放操作系统常驻内存的部分，用户不能占用这部分空间。 用户区：分配给用户使用，用于装入并存放用户程序和数据，信息随时都会发生变化， 存储管理的实质就是管理供用户使用的那部分空间。 内存管理问题的主要包括：内存管理方法、内存的分配和释放算法、虚拟存储器的管理、控制内存和外存之间的数据流动方法、地址交换技术和内存数据保护与共享技术等。 单道、单用户：在一个区域内存放系统软件，如操作系统本身，而另外一个区域放置用户程序。 多道、多用户系统：为了提高系统的的利用率，需要将内存划分更多的区域，以便支持多道程序。 充分利用内存，为多道程序并发执行提供内存基础。 尽可能方便用户使用： 操作西戎自动装入用户程序。 用户程序中不必考虑硬件细节。 系统能够解决程序空间比内存实际内存空间大的问题。 程序的长度在执行时可以动态伸缩。 内存存取速度快。 存储保护与安全。 共享与通讯。 及时了解有关资源的使用状况。 实现的性能和代价合理。 在操作系统中存储管理的主要任务。 内存的回收与分配 一个有效的存储分配机制，应对用户提出的需求予以快速响应，为之分配相应的存储空间。在用户程序不再需要它的同时及时回收，以供其他用户使用。 功能： 记住每个存储区的状态。 实施分配。 回收。 为了实现上述功能，必须引入分配表格，统称为内存分配表，其组织方式包括： 位示图表示法：用一位（Bit）表示一个空闲页面（0表示空闲，1表示占用）。 空闲页面表：包括首页面号和空闲页面的个数，连续若干个页面作为一组登记在表中。 空闲块表： 空闲块首址和空闲块长度，没有记录的区域即为进程所占用。 内存分配的两种方式： 静态分配：程序要求的内存空间是在目标模块连续装入内存时确定并分配的，并且在程序运行过程中不允许再申请或者在内存中“搬家“，即分配工作是在程序运行前一次性完成。 动态分配：程序要求的基本内存空间是在目标模块转入时确定并分配的，但是在程序运行过程中，允许申请附加的内存空间或在内存中”搬家“，即分配工作是在程序运行前即运行过程中逐步完成的。 动态存储分配具有较大的灵活性： 它不需要一个程序的全部信息进入内存后才可以运行，而是在程序运行中需要时系统自动将其调入内存。 程序当前暂不使用的信息可以不进入内存，这对提高内存的利用率有好处。 存储共享 存储共享是指两个或多个进程共用内存中的相同区域，这样不仅能使多道程序动态的共享内存，提高内存利用率，而且还能共享内存中某个区域的信息。 内容包括：代码共享和数据共享，特别是代码共享要求代码必须是纯代码。 一是通过代码共享节省内存空间，提高内存利用率。 一是通过数据共享实现进程通信。 存储保护 为多个程序共享内存提供保障，是在内存中的各个程序只能访问其自己的区域，避免各程序间相互干扰。 存储保护通常是需要有硬件的支持，并由软件配合实现。 保护系统程序区不被用户有意或者无意的侵犯。 不允许用户程序读写不属于自己地址空间的数据，如系统区地址空间、其他用户程序的地址空间。 （1）地址越界保护 每个进程都具有其相对独立的进程空间，如果进程在运行是所产生的地址超出其地址空间，则发生地址越界。地址越界可能侵犯其他进程的空间，影响其他进程的正常运行；也可能侵犯操作系统空间，导致系统混乱。对程序产生的地址必须加以检查，发生越界时产生中断，由操作系统进行相应处理。 （2）权限保护 对于多个进程贡献的公共区域，每个进程都有自己的访问权限。 对属于自己的区域的信息，可读可写。 对公共区域中允许共享的信息或获得授权可使用的信息，可读而不可修改。 对未获授权使用的信息。不可读、不可写。 当发生地址越界或者非法操作的时候，由硬件产生中断，进入操作系统处理。 ”扩充“内存容量 在硬件支持下，软件、硬件相互协作，将内存和外存结合起来统一使用。 借助虚拟存储技术或其他交换技术在逻辑上扩充内存容量，亦即为用户提供比内存物理空间大的多的地址空间，使得用户感受它的程序是在一个大的存储器中运行。 地址转换 存储器以字节（1B=8个二进制位）为编址单位，每个字节都有一个地址与其对应。假定存储器的容量为n个字节，其地址编号为0，1，2，3，…，n-1 。这些地址称为内存的“绝对地址”，与绝对地址对应的内存空间称为“物理地址空间”。 用户程序中使用的地址称为“逻辑地址”，与逻辑地址对应的存储空间称之为“逻辑地址空间”。 地址重定位 当用户程序进入计算机系统请求执行时，存储管理要为他分配合适的内存空间，这个分配到的内存空间可能是从某个单元开始的一组连续的地址空间。该地址空间的起始地址是不固定的，而且逻辑地址与分到的内存地址空间的绝对地址经常不一致。每个逻辑地址在内存中也没有一个固定的绝对地址与之对应。 为了保证程序的正常执行，必须根据分配给程序的内存区域对程序中指令和数据的存放地址进行重定位，即要把逻辑地址转换成为绝对地址。 把逻辑地址转换成绝对地址的工作称为“地址重定位”或“地址转换”，又称“地址映射”。重定位的方式有“静态重定位”和“动态重定位”两种。 静态重定位 由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无须再进行地址转换工作。称为“静态重定位”。 动态重定位 在装入程序时，不进行地址转换，而是直接把程序装到分配的内存区域中，在程序执行过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。称为“动态重定位”。 动态重定位由软件和硬件互相配合来实现。硬件要有一个地址转换机构，该机构可由一个基址寄存器和一个地址转换线路组成。 存储管理为程序分配内存区域后，装入程序把程序直接装到所分配的区域中，并把内存区域的起始地址存入相应程序进程的进程控制块中。当程序进程被调度占用处理器时，随同现场信息的恢复，程序所占的内存区域的起始地址也被存放到“基址寄存器”中。程序执行时，处理器每执行都会把指令中的逻辑地址与基址寄存器中的值相加得到绝对地址，然后按绝对地址访问内存。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

线程模型 线程：能够独立运行的基本单位，试图用它来提高系统内程序并发执行的程度。 线程的引入 基本属性：进程是一个可拥有资源的独立单位，又是一个可以独立调度和分派的基本单位。 创建进程：必须为其分配所有资源（除CPU外），包括内存空间、I/O设备以及建立相应的数据结构PCB。 撤销进程：必须先对这些资源进行回收操作，然后在撤销PCB。 进程切换：由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需要花费不少的CPU时间。 进程是一个资源拥有者，因而在进程的创建、撤销和切换中，系统必须为之付出较大的时空开销。 创建背景：如果将作为调度和分派的经本单位不同时作为独立分配资源的单位，以使轻快运行；而对拥有资源的基本单位，又不频繁地对之进行切换。 线程的基本概念 线程是进程中的一个实体，是CPU调度和分派的基本单位。 一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。 线程也同样有就绪、等待和运行三种基本状态。 线程的属性 每一个线程有一个唯一的标识符和一张线程描述表，记录了线程执行的寄存器和栈等现场状态。 不同的线程可以执行相同的程序，同一个服务程序被不同用户调用时操作系统为它创建不同的线程。 同一个进程中的各个线程共享进程的内存地址空间。 线程是处理器的独立调度单位，多个线程是可以并发执行的，在单个CPU的计算机系统中，各个线程可交替的占用CPU；在多个CPU计算机系统中，各个线程可同时占用不同的CPU，若各个CPU同时为一个进程内的各种线程服务是可以缩短进程的处理时间。 一个线程被创建后便开始了它的生命周期，直至终止，县城在生命周期内会经历等待、就绪和运行等各种状态变化。 引入线程的好处 创建一个新的进程花费的时间少，不需另行分配资源，创建线程的速度比创建进程的速度快，且系统的开销也少。 两个线程的切换花费时间少。 由于同一个进程内的线程共享内存和文件，线程之间相互通信无须调用内核。 线程能独立运行，能充分利用和发挥处理器与外围设备并行工作能力。 线程与进程的比较 线程具有许多传统进程所具有的特征，故又称为轻量级进程或者是进程元，把床听的进程称为重量级进程。 调度：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入县城的操作系统中，则把线程作为调度和分派的基本单位。同一进程中，线程切换不会引起进程切换；而在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行。很有效的使用系统资源和提高系统的吞吐量。 拥有资源：线程的自己不拥有系统资源，但它可以访问其隶属进程的资源，可供同一进程的其他所有线程共享。 系统开销：由于在创建或撤销进程时，系统都要为之分配或回收资源。因此，操作系统所付出的开销将显著地大于在创建或撤销线程时的开销。 线程实现机制 用户级线程 用户级线程不依赖于内核。用户级线程只存在于用户态中，对它的创建、撤销和切换不会通过系统调用来实现，因而这种线程与内核无关。内核也并不知道有用户级线程的存在，从内核角度考虑，就是按正常的方式管理即单线程进程。 支持用户级进程的典型操作系统就是Linux。 在用户空间管理线程时，每个进程都需要有其专用的线程表。用来跟踪该进程中的线程。该线程表由运行时系统管理。但一个线程转换到就绪状态或阻塞状态时，在该进程表中存放着从新启动该线程所需要的信息，于内核在进程表中存放进程的信息完全一样。 内核级线程 内核级线程依赖于内核，无论是在用户进程中的线程，还是系统进程中的线程，他们的创建、撤销和切换都是有内核实现的。在内核中保留一个线程控制块，系统根据该控制块而感知该线程的存在并对县城进行控制。 支持内核级线程的典型操作系统是Windows。 内核的线程表保存了每个线程的仅存表、状态和其他信息。所以能够阻塞线程的表用都以系统调用的形式实现。当一个线程阻塞时，内核可以选择运行的同一个进程中的另一个线程（若有一个就绪进程）或者运行另一个进程中的线程。而在用户及线程中，运行时系统时钟运行自己进程中的线程，直到内核剥夺它的CPU（或者没有可运行的线程存在了）为止。 用户级线程和内核级线程比较 线程的调度与切换速度：核心级线程的调度与切换与进程的调度和切换十分相似。在线程调度时的调度方式，同样也是采用抢占方式和非抢占方式两种。在线程的调度算法上，也同样可采用时间片轮转法、优先权算法等。用户级线程的切换通常是发生在一个应用进程的诸线程之间，这时，不仅无需同福哦终端进入操作系统的内核，而且切换的规则页远比进程调度和切换的规则简单。用户级线程的切换速度特别快。 系统调用：在传统的用户进程调用一个西戎调用时，要由用户状态转入核心状态，用户进程将被封锁。当那个完成系统调用而返回时，才将该进程唤醒，继续执行，而在用户级线程调用一个系统调用时，由于内核并不知道有该用户级进程的存在，因而把西戎调用看作是整个进程的行为，于是使该进程等待，而调度另一个进程执行。当一个进程调用一个系统调用时，内核把系统调用只看作是该线程的行为，以问封锁该进程中的其他线程执行。 线程执行时间：对于只设置了用户级线程的系统，调度是以进程为单位进行的。 混合实现方式 支持混合方式线程的典型操作系统是Solaris。 Pthread线程包 IEEE标准1003.1c定义了线程标准，Pthread是基于该标准实现的线程包。 多道程序设计模型 作用：提高CPU的利用率。 程序的顺序执行 程序是一个在时间上按严格次序前后相继的操作序列，这些操作是机器指令或高级语言编写的语句。 特点： 顺序性：程序所规定的动作在机器上严格地按顺序执行。 封闭性：资源的状态（除了初始状态外）只有程序本身的动作才能改变。 确定性：程序执行结果与它的执行速度无关，也称为程序执行结果与时间无关性。即CPU在执行程序时，任意两个动作之间的停顿对程序的计算结果都不会产生影响。 可再现性：如果程序执行在不同的时间执行，只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。 多道程序系统中程序执行环境的变化 多道程序设计技术的引用 为了提高计算机系统中各种资源的利用效率，缩短作业的周转时间。多种硬件资源能并行工作。 单CPU：并发程序按给定的时间片交替的在处理机上执行，其执行的时间是重叠的。 多CPU：这些并发程序在各自的处理机上运行。 例： 假设有两个程序A和B都要执行，A程序的执行顺序为在CPU中执行10s、在设备DEV1上执行5s、又在CPU上执行了5s、在设备DEV2上执行了10s、最后在CPU上执行了10s； B程序的执行顺序为：在设备DEV2上执行10s、在CPU上执行10s、在设备DEV1上执行5s、又在CPU上执行了5s、最后在设备DEV2上执行10s。 在顺序环境下，A执行完之后B执行，或则B执行完之后A执行。假设A先执行，程序A、B全部执行完之后需要80s的时间，其中有40s是程序使用CPU，15S使用设备DEV1，25s使用设备DEV2. CPU利用率=40/80=50% DEV1利用率=15/80=18.75% DEV2利用率=25/80=31.25% 在并发环境下，程序A、B可以同时执行，当程序A在CPU上执行时，程序B可以在设备DEV1上执行，程序A、B全部执行完成之后需要45s时间。 CPU利用率=40/45=89% DEV1利用率=15/45=33% DEV2利用率=25/45=56% 多道程序设计环境的特点 多道程序设计就是允许多个程序同时进入内存并运行。 系统吞吐量衡量系统效率的尺度。吞吐量是指单位时间内系统所处理的作业（程序）的道数（数量）。 如果系统的资源利用率高，则单位时间内所完成的有效工作多，吞吐量大。 如果系统的资源利用率低，则单位时间内所完成的有效工作少，吞吐量小。 **作用：**提高了设备资源利用率，提高了内存资源利用率，提高了处理机资源利用率，最终，最终提高了系统吞吐量。 多道程序设计环境的特点 独立性：每道程序都是在逻辑上独立的。 随机性：程序和数据的输入与执行开始时间都是随机的。 资源共享性：资源共享将导致对进程执行速度的制约。 程序的并发执行 程序的并发执行是指两个或两个以上的程序在计算机系统中同处与已开始执行的且尚未结束的状态。能够参与并发执行的程序称为并发程序。 特性 并发程序在执行期间具有相互制约关系：“执行-暂停-执行”。 程序与计算不再一一对应：允许多个用户作业调用一个共享程序段。 并发程序执行结果不再可现：宏观上是同时进行的，在单CPU系统中，他们仍是顺序执行。 进程模型 进程 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配与调度的一个独立单位。 系统进程执行操作系统程序，完成操作系统的某些功能。 用户进程运行用户程序，直接为用户进行服务。 系统进程的优先级通常高于一般的用户进程的优先级。 进程与程序的联系与区别 联系： 程序是构成进程的组成部分之一，一个进程的运行是执行它所对应的程序。 进程是有程序，参数和进程控制块（PCB）部分组成。 区别： 程序是静态的，而进程是动态的。 程序可以是永久的，而进程存在只是暂时的。 一个进程可以执行一个或几个程序、一个程序可以构成多个进程。 进程具有创建其他进程的功能，被创建的进程称为子程序，创建者称为父程序。 进程的特性 并发行：一个进程的第一个动作可以在另一个进程的最后一个动作结束之前开始。 动态性：进程动态产生、动态消亡，在进程生命周期内，其状态动态变化。 独立性：一个进程是一个相对完整的资源分配单位。 交往性：一个进程在运行过程中可能会与其他进程发生直接或间接的相互作用。 异步性：每个进程按照各自独自的、不可预知的速度向前推进。 进程的状态及其状态转换 三状态进程模型 运行中的进程可以处于以下三种状态之一：运行、就绪、等待。 运行状态Running：运行状态是指进程已经获得CPU，并且在CPU上执行的状态。 在一个单CPU系统中，最多只有一个进程处于运行状态。 就绪状态Ready：指一个进程已经具备运行条件，但由于没有获得CPU而不能运行所处的状态。一旦CPU分配给他，该程序就可以运行，处于就绪状态的进程可以是多个。 等待状态Waiting：也称阻塞状态或封锁状态，是指程序因等待某种事件发生而暂时不能运行的状态。 就绪–》运行 未能获取处理机，故仍然不能运行。 运行–》就绪 由于规定的运行时间片用完而使系统发出超时中断请求，超时中断处理程序把该进程的状态修改为就绪状态。 运行–》等待 处于运行状态的进程是否能继续运行，除了受时间限制外，还收其他种种因素的影响。 等待–》就绪 等待的进程在其被柱塞的原因获得解除后，因为处理及满足不了进程的需要，于是将状态有等待变成就绪，仅当进程调度程序把处理机再次分配给他时，才可恢复现场继续运行。 五状态进程模型 运行状态 Running：进程占用处理机资源 出于此状态的进程的数目不小等于处理机的数目，再没有其他进程时可以执行是，通常会自动执行系统的空闲进程。 就绪状态 Ready：进程已获得除处理机外所需的资源，等待分配处理机资源，只要分配处理机就可以执行。 阻塞状态 Blocked：由于进程等待的I/O操作或进程同步等条件而暂停运行时处于阻塞状态。即使把处理机分配给该进程，也是无法继续执行的。 创建状态 New：进程正在创建的过程中，还不能运行。包括分配和创建进程控制块表项、建立资源表格并分配资源，机在程序并建立地址空间。 结束状态 Exit：进程已结束运行，回收除进程控制块之外的其他资源，并让其他进程从进程控制块中收集有关的信息。 操作系统中多个进程的并发执行是通过进程交替进入运行状态来实现的。 创建进程：创建一个新的进程，来运行一个程序。 提交admit：完成一个新进程的创建过程，新进程进入就绪状态。 调度运行dispatch：从就绪进程表中选择一个进程进入运行状态。 释放release：由于进程完成或失败而终止进程运行，进入结束状态。 运行到结束的转换可分为正常退出和异常退出，其中异常退出是指进程执行超时、内存不够。 超时timeout：由于运行的时间片或高优先级进程就绪状态等因素导致进程停止运行。 事件等待event wait：进程要求的事件未出现而进入阻塞。 可能的原因包括申请进程系统服务或资源、通信、I/O等操作。 事件出现event occurs：进程等待的事件出现，如操作完成，申请成功。 七状态进程模型 五状态进程模型没有区分进程地址空间位于内存还是外存，虚拟存储管理技术后，需要进一步区分进程的地址空间状态。 好处： 有空闲内存空间用于提交新进程。 提供足够的内存。 有利于调试：被挂起的调试程序，可方便对其他地址空间进行读写。 下面是列出在挂起的进程模型中的四种意义变化或新的状态。 就绪状态：立即进入运行状态。 阻塞状态：在内存并等待某事件的出现。 阻塞挂起状态：进程在外存并等待某事件的出现。 就绪挂起状态：进程在外存，但只要进入内存。 挂起：把一个进程从内存转到外存。 阻塞到阻塞挂起。 就绪到就绪挂起：有高优先阻塞加入时。 运行到就绪挂起。 激活：把一个进程从内存转到外存。 就绪挂起到就绪：就绪挂起进程优先级高于就绪进程。 阻塞挂起到阻塞：当一个进程释放足够的内存时，系统会把一个高优先级阻塞挂起进程激活。 事件出现：进程等待的事件出现。 阻塞到就绪：内存进程的事件出现。 阻塞挂起到就绪挂起：针对外存进程的事件出现。 提交：完成一个新进程的创建过程，新进程进入就绪状态或就绪挂起状态。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

调度是分层次的，在操作系统中，一般将调度分为高级调度、中级调度和低级调度。 高级调度也称作业调度，其主要任务是按一定的原则，对磁盘中的处于后备状态的作业进行选择并创建为进程。 中级调度的主要任务是按照给定的原则和策略，将处在磁盘对换区中切具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到对换区。 低级调度即进程（线程）调度，是决定就绪队列中哪个进程将获得处理机，并使即将处理及分配给该进程的操作。 进程（线程）调度即处理机调度。任务是控制、协调进程（线程）对CPU的竞争，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。 概述 进程（线程）调度的主要功能 记录系统中所有进程（线程）的执行状况，根据一定的调度算法，从就绪队列中选出一个进程（线程）来，准备把CPU分配给它，把CPU分配给进程（线程），即把选中进程（线程）的进程（线程）控制块内有关的现场信息，让它占用CPU运行。 进程（线程）调度的时机 正在执行的进程（线程）运行完毕。 调用阻塞原语将自己阻塞起来进入等待状态。 调用阻塞原语操作，并且因为资源不足而被阻塞；或调用唤醒原语操作激活了等待资源的进程（线程）。 时间片用完。 就绪队列中的某个就绪队列中一旦有优先级高于当前运行进程（线程）优先级时，引发进程（线程）调度。 抢占方式：就绪队列中一旦由优先级高于当前运行进程（线程）优先级的进程（线程）存在时，便立即进行调度，转让CPU。 不可抢占方式：一旦把CPU分配给一个进程（线程），它就一直占用CPU，直到该进程（线程）自己因调用原语操作或等待I/O而进入阻塞状态或时间片用完时才让出CPU，重新执行进程（线程）调度。 调度算法设计原则 进程行为 几乎所有的进程的（磁盘）I/O请求或计算都是交替完成的。某些I/O活动可以看作是计算，在CPU向视频RAM复制数据以更新屏幕时，因为使用了CPU，所以这是计算，而不是I/O，当一个进程等待外部设备完成工作而被阻塞的行为属于I/O。 计算密集型：进程花费了绝大多数时间在计算上。 I/O密集型：进程在等待I/O上花费了绝大多数时间。 系统分类 通常分为三类环境：批处理、交互式和实时系统。 批处理系统：减少了进程的切换从而改善了性能。 交互式：避免一个进程霸占CPU拒绝为其他进程服务，抢占是必需的。服务器也归于此类，因为通常他们要服务多个突发的（远程）用户。 实时限制：只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意程序。 调度算法的设计目标 运行大量批处理作业的大型计算中心的管理者们为了掌握其系统的工作状态，通常是检查各个指标：吞吐量、周转时间以及CPU利用率。 吞吐量：是系统每小时完成的作业数量。 周转时间：从一个批处理作业提交时间开始直到该作业完成时刻为止的统计平均时间。 CPU利用率：用于对批处理系统的度量，系统每小时可完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。 进程（线程）调度算法 进程（线程）调度算法解决以何中次序对各就绪进程（线程）进程处理机的分配以及按何种时间比例让进程（线程）占用处理机。 先来先服务FCFS算法 进程按照他们请求CPU的顺序使用CPU。 最短作业优先SJF算法 当输入队列中有若干同等重要的作业被启动时，调度程序应使用最短作业优先算法。 有4个作业A、B、C、D，运行时间分别是8、4、4、4分钟。 先到先服务：若按图A，B，C，D 的次序运行，则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均为14分钟。 最短作业优先：运行顺序为BCDA，则周转时间分别为4、8、12、20分钟，平均时间为11分钟。 最短剩余时间优先SRTN算法 调度程序总是选择其剩余运行时间最短的那个进程运行。 最高响应比优先HRRF算法 响应比Rp=（等待时间+预计运行时间）/预计运行时间=周期时间/预计运行时间。 轮转法RR算法 基本思想：将CPU的处理时间划分为一个个的时间片，就绪队列中的诸程序轮流运行一个时间片。当时间片结束时，就强迫运行的进程让出CPU，该进程机内就绪队列，等待下一次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。 影响时间片值设置的几个主要因素： 系统响应时间：当进程数目一定时，时间片Q值的大小占比于系统对响应时间的要求，例如进程数目为N，要求响应时间为T，则Q=T/N，Q值随T值的大或小而大或小。 就绪进程的数目：当系统响应时间T一定时，时间片Q值的大小反比于就绪进程数。 计算机的处理能力：计算机的处理能力直接决定了每道程序的处理时间，显然，处理速度越高，时间片值就可以越小。 结论：时间片设置的太短会导致过多的进程切换，降低了CPU效率；而设的太长有可能引起对短的交互请求的响应时间变长，将时间片设置为20~50ms通常是一个比较合理的折中。 最高优先级HPF算法 最高优先级调度每次将处理及分配给具有最高优先级的就绪进程（线程）。进程（线程）的优先级由进程（线程）优先数决定的。 进程（线程）优先数的设置可以是静态的也可以是动态的。 静态优先数是在进程（线程）创建时根据进程（线程）初始特性或用户要求而确定的，在进程（线程）运行期间不能再改变。 动态优先数是指在进程（线程）创建时先确定一个初始优先数，以后在进程（线程）运行中随着进程（线程）特性的改变（如等待时间增长），不断修改优先数。优先数小的进程（线程）优先级高。 如果不对优先级进行调整，则低优先级进程很有可能产生饥饿现象。 多级反馈队列算法 以最高优先级算法作为主要的调度模式，但对于具有相同优先数的进程（线程）按先进先出调度算法处理。 多级队列反馈法就是综合了先进先出调度算法、时间片轮转法和可抢占式最高优先级算法的一种进程（线程）调度算法。 被调度队列的设置：系统按优先级别设置若干个就绪队列，不同优先级别的队列有不同的时间片，对级别较高的队列分配较小的时间片Si（i=1，2…..，n）。 在同一个队列之间的调度原则：除了第n级队列是按照RR算法调度之外，其他各级队列均按照先进先出调度算法调度。 在不同队列之间的调度原则：西戎总是先调度级别比较高的队列，仅当级别较高的队列为空是才去调度次一级队列中的就绪队列。当等待进程（线程）被唤醒时，它进入与其优先级相同的就绪队列，若该进程（线程）优先级高于正在执行的的进程（线程），便抢占CPU。 最短进程优先 如何从当前可运行进程中找出最短的那一个进程。 根据进程过去的行为进行推测，并执行估计运行时间最短的哪一个。 老化：通过当前测量值和向前估计值进程加权平均而得到下一个估计值的技术。 实时系统中的调度算法 实时系统是一种时间起着主导作用的系统，即系统的正确性不及取决于计算的逻辑结果，而且还依赖于产生结果的时间。 实时系统应用的例子包括实验控制、过程控制设备、机器人、空中交通管制、电信、军事指挥与控制系统。 硬实时任务值必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。 软实时任务也有一个与之关联的最后期限，并希望能满足这个期限的要求，但并不是强制的，即使超过了最后期限，调度和完成这个任务仍是有意义的。 速率单调调度算法：适用于可抢先的周期性进程的经典静态实时调度算法是速率单调调度RMS。 每个周期性进程必须在其周期内完成。 没有进程依赖于任何其他进程。 每一进程在一次有突发中需要相同的CPu时间量。 任何非周期性进程都没有最终时限。 进程抢先即刻发生而没有系统开销。 最早最终时限优先调度：EDF算法是一个动态算法，它不像速率单调算法那样要求进程是周期性的，他也不详RMS那样要求CPU突发有相同的运行时间。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

进程控制块PCB 在操作系统中，为进程定义了一个专门的数据结构，称为进程控制块PCB。 PCB内容 PCB内容可以分为调度信息和现场信息两大部分。 调度信息供进程使用时使用，描述了进程当前所处的状况，他包括进程名、存储信息、进程号、优先级、当前状态、资源清单、“家族”关系、消息队列指针、进程队列指针和当前打开的文件等。 现场信息刻画了进程的运行情况，由于每个进程都有自己专用的工作存储区，其他进程运行时不会改变它的内容。 进程的组成 PCB组织 线性方式：将所有的PCB部分状态组织在一个连续表（称为PCB表）中。 优点：简单，且不需要额外的开销，适用于进程数且不多的系统。 缺点：需要扫描整个PCB表。 索引方式：对于具有相同状态的进程，分别设置各自的PCB索引表，表目为PCB在PCB表（线性表）中的地址。就构成了就绪索引表和等待索引表。 链接方式：对于具有相同状态的进程PCB，通过PCB中的链接字构成一个队列。按“先进先出”的原则出对，若队列指针为0，表示该队列为空。 进程的队列 就绪队列：进程入队和出队的次序与处理机调度算法有关。 等待队列：每一个等待事件一个队列。 运行队列：在单CPU系统中整个系统有一个运行队列。 进程控制 作用：就是对进程在这个生命周期中各种状态之间的转换进行有效的控制。 原语：通常由若干的指令组成，用来实现某个指定的操作。通过一段不可分割的或不可中断的程序实现其功能。原语的执行过程必须是连续的，一旦开始执行就不能间断，直到执行结束。原语是操作系统的可行，在管态下执行，并且常驻内存。 进程控制原语 用于进程控制的原语一般有：创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。 创建原语：一个进程可以使用创建原语创建一个新的进程，前者称为父进程，后者称为子进程，子进程又可以创建新的子进程，构成新的子进程，构成新的父子关系。建立进程控制快PCB：先申请一个空闲的PCB区域，将有关信息填入PCB，置该进程为就绪状态，最后将它插入到就绪状态队列中去。 撤销原语：找到要被撤销的进程PCB，将它从所在队列中消去。 阻塞原语：把进程运行状态转换为阻塞状态。首先应中断CPU执行，把CPU的当前状态保存到PCB的现场信息中，把它插入到该事件的等待队列中去。 唤醒原语：京城因为等待时间的发生而处于等待状态，当等待事件完成后，就用唤醒原语将其转换为就绪状态。具体操作过程：在等待队列中找到该进程，置该进程的当前状态为就绪状态，然后将它从等待队列中撤去并插入到就绪队列中排队，等待调度执行。 UNIX类操作系统的进程控制操作 父进程调用fork()函数。 为子进程分配一个空闲的proc结构（进程描述符）。 赋予子进程唯一标识pid。 以一次一页的方式复制父进程用户地址空间。 获得子进程继承的共享资源的指针。 子进程就绪，加入调度队列。 对子进程返回标识符0；向父进程返回子进程的pid。 父进程和新建子进程的区别在于它们有着不同的pid。 fork()函数的执行的特点就像是只被调用一次，却会返回两次：一次是在调用进程（父进程）中，一次是在新创建的子进程中。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

缓存 浏览器的一次请求需要从服务器获得许多css、img、js等相关的文件，如果每次请求都把相关资源文件加载一次，对带宽、服务器资源、用户等待时间都有严重的损耗，浏览器有做优化处理，就是把css、img、js等文件在第一次请求成功后就在本地保留一个缓存备份，后续的每次请辞u就在本身获得相关的缓存资源文件就可以了，可以明显地加快用户的访问速度。 css、img、js等文件可以缓存，但是动态程序文件例如PHP文件不能进行缓存，即使缓存我们也不要其缓存效果。浏览器对动态程序文件缓存的处理解决： 给请求的地址设置随机数【推荐】； 给动态程序设置header头信息，禁止浏览器对其缓存。 给请求的地址设置随机数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Ajax对缓存的处理</title> <script type="text/javascript"> function f1(){ var xhr = new XMLHttpRequest(); xhr.open('get', './server.php?'+Math.random()); xhr.send(null); } </script> </head> <body> <h2>Ajax对缓存的处理</h2> <input type="button" value="触发" onclick="f1()"> <div id="result"></div> </body> </html> 给动态程序设置header头信息 1 2 3 4 5 6 //设置header头禁止浏览器缓存当前页面 header("Cache-Control:no-cache"); header("Pragma:no-cache"); header("Expires:-1"); $fp = fopen("test.txt","a"); fwrite($fp, "php "); fclose($fp); 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页

计算机网络技术的形成与发展 主要知识点记录 “三网融合” ：计算机网络、电信网与电视网之间的融合。 UNIX操作系统 集中式、分时、多用户的系统架构 制订了基于Unix的易移植操作系统环境（POSIX）标准 Linux操作系统 常见的发行版本：Rad Hat、Mandrake、Slackware、SUSE、TurbpLinux、Debian、Caldera、Ubuntu，国内的有蓝点、红旗等。 计算机网络的基本概念 计算机网络的定义 计算机网络 用相互共享资源的方式互联起来的自治计算机系统的集合。 特征： 主要目的是资源的共享 互联的计算机是分布在不同地理位置的多台独立的“自治计算机” 联网计算机之间的通讯需要遵循共同的网络协议。 常见计算机名词区分： 术语 英文名称 含义 计算机网络 computer network 用相互共享资源的方式互联起来的自治计算机系统的集合 网络互联 internet 将多个计算机网络互联成大型网络系统的技术 互联网 Internet 指目前广泛应用、覆盖了全世界的大型网络系统 内部的专用网络系统 Intranet 将分布在不同地理位置的部门局域网连接起来的企业内部专用网络。 计算机网络的分类 按照覆盖的地理范围划分为：广域网、城域网、局域网、个人区域网。 广域网技术 WAN又称为远程网，覆盖的地理位置从几十千米到几千千米。 城域网技术 IEEE802协会对其的定义与特征表述： 以光纤为传输介质，能够提供45-150Mbps的高传输速率，支持数据、语音和视频综合业务的数据传输，可以覆盖50~100km的城市范围，实现高速的数据传输。 局域网技术 局域网用于将有限范围的各种计算机，终端与外部设备互联成网。 特征如下： 局域网覆盖有限的地理范围 提供高传输速率（10Mbps~100Gbps）、低误码率的高质量数据传输环境 一般为一个单位所有，易于建立、维护与扩展 决定局域网的三个因素： 拓扑 传输介质 介质访问控制方法 从介质访问控制方法的角度，分为以下两方面： 共享介质式局域网 交换式局域网 个人局域网技术 自身附近范围的个人操作空间。 无线个人局域网络 用无线通信技术实现联网设备之间的通信。 计算机网络的拓扑结构 网络拓朴学知识补充： 拓扑学时间实体抽象成于其大小、形状无关的“点”，将连接实体的路线抽象成“线”。 计算机网络拓扑是通过网中节点与通信线路之间的几何关系表示的网络结构。 计算机网络拓扑是指通信子网的网络拓朴。 基本的网络拓朴有五种：星形、环形、总线型、树形与网形。 星形拓扑 通过点-点通信线路与中心节点连接。 任何两个节点之间的通信都要通过中心节点。 结构简单，易于实现，便于管理。 中心节点是全网性能与可靠性的预测，中心节点瘫痪会造成全网瘫痪。 环形拓扑 通过点-点通信线路连接成闭合的环路。 数据沿一个方向传送。 结构简单、传输延时稳定。 每个节点与连接节点之间的通信线路都会成为网络可靠性的瓶颈。 方便接点的加入和撤出、控制节点数据传输顺序。 总线型拓扑 所有的节点连接到一条作为公共传输介质的纵向，以广播的方式发送和接受数据。 但一个节点利用总线发送数据时，其他节点只能接受数据。 两个或两个以上的节点同时发送数据时，就会出现冲突，照成传输失败。 结构简单，但是得解决多节点访问总线的介质访问控制问题。 树形拓扑 按层次进行连接，信息交换主要在上下节点之间进行，相邻及同层节点之间通常不进行数据交换，或则交换量较小。 树形拓扑可以看成是星形拓扑的一种扩展，树形拓扑网络适用于汇集信息。 网状拓扑 节点之间的连接是任意的，没有规律。 系统可靠性高，广域网一般都采用网状拓扑。 必须采用路由算法、流量控制与拥塞控制方法。 描述计算机网络传输性能的参数 数据传输率 数据传输率是每秒钟传输构成数据的二进制比特数。 单位：比特/秒（bit/second）简称：bps 数据传输率公式： S=1/T（bps） T:发送1比特所需的时间。 常见速率换算公式： 奈奎斯特准则与香农定律 奈奎斯特准则 定义：具有理想低通矩形特性的信道在无噪声情况下的最高速率与带宽关系的公式。 奈奎斯特准则指出：如果间隔为π/w（w=2πf），通过理想通信信道传输窄脉冲信号，则前后码元之间不会产生相互串扰。 对于二进制数据信号的最大数据传输速率Rmax与通信信道带宽B（B=f，单位Hz）的关系可以转化为： $$ R_{\max }=2f\left( bps\right) $$ 此准则描述了有限带宽、五噪声信道的最大数据传输速率与信道带宽之间的关系。 香农定律 定义：在有随机热噪声信道上传输数据信号时，数据传输速率Rmax与信道带宽B，信号与噪声功率比S/N关系。 R max = 13 log 2 1 + S / N 此定律描述了有限带宽、有随机热噪声的最大传输速率与信道带宽、信号噪声功率比之间的关系。 关注微信公众号，第一时间获取最新内容，让我们一起变得更强！Debug客栈：订阅本站· 文章归档· 我的项目· 友情链接· 我的使用· 飞湾计划· 摄影展集· 我的主页