UTXO

UTXO模型 什么是UXTO? 在区块链里,账本里记录的是一笔又一笔的交易。每笔交易都有若干交易输入,也就是资金来源;也有若干交易输出,也就是资金去向。一般来说,每一笔交易都要花费一笔输入,产生一笔输出,而当其所产生的输出,并被其他交易所花费时,这笔输出就可以被称为 “未花费过的交易输出”,也就是UTXO。 比特币中交易过程的实现 在比特币的世界里,记录交易记录正是基于UTXO模型。要理解UTXO,最简单的方法就是把一枚比特币从诞生到交易的经历描述一下。 假设,张三通过挖矿得到了12.5枚比特币。过了几天,他把其中2.5枚比特币交给了李四。再过几天,他和李四各出资2.5比特币凑成5比特币给王五,整个交易过程再UTXO模型里的记录是这样的: 从图上可以看出,当张三付给李四2.5个比特币时这笔交易时,收款人有两个,分别是李四和张三他自己,张三收到了余额10枚比特币,李四收到了2.5枚比特币,此时,张三原有的挖矿所得的12.5的记录因为以及消费,已经不能算是UTXO的记录了,因此,张三此时的余额就是10枚比特币。 可以看出,从消费这一点来看,UTXO类似日常生活中的纸币消费,当你拿10块钱买了3块钱的肥宅快乐水时,你需要付给老板3块,同时老板会找零给你7块。此时你原来的10块钱就不存在了。 当李四给了王五2.5枚比特币之后,李四的已经没有比特币了,因此没有李四的交易输出了;同时,王五同时收到了两个人的比特币,收款数额直接计算总数,并合并成一条数额为5的记录。这里似乎是可以不合并分开成两条输出记录的,待确定 !!! 由上面的例子说明,其实并没有什么比特币,只有 UTXO。当我们说张三拥有10枚比特币的时候,我实际上是说,当前区块链账本中,有若干笔交易的UTXO 项收款人写的是张三的地址,而这些UTXO项的数额总和是 10。 注意点 Coinbase交易是指矿工挖矿所得比特币的交易,这种交易比较特殊,交易输入并不是来自前面某一个或者某几个交易的UTXO。 每一笔交易的交易输入必须等于交易输出 计算某个人的账户余额时,只计算 未花费的 交易输出 怎么确定交易输入是有效的? 当节点接收到一笔交易的时候,它需要去 UTXO 数据库里查,看看这笔交易所引用的 UTXO 是否存在,它的收款人(拥有者)是不是当前新交易的付款者。 怎么保证一笔交易所引用的UTXO没有被重复消费? 当某一笔比特币交易被创建—签名—广播到区块链网络之中后,每一个节点(比特币交易参与者)会对这笔交易进行验证,看交易的输出是否存在于UTXO。 如果A拥有1枚比特币被证实确实是“未花费过的交易输出”,他要是将这1枚比特币同事转账给B1、B2两个人,挖矿节点会选择性的记录一笔交易,或许是最先收到的,或许是手续费更高的。 情况1: 如果这两笔交易是先后被挖矿节点接收到的,那依据时间戳(时间戳是矿工打包区块时的时间),先被接收到的交易会被验证成功,而后被接收到的交易则会因交易输入已经不存在于UTXO而验证失败。 情况2: 如果两个挖矿节点分别 同时 记录了这两笔交易,并且这两笔交易被分别证明是合法的,此时这两个挖矿节点会将各自挖到的新区块广播到全网。这时链就会 分叉。当其中一笔交易(是交易被确认还是新区块被确认???)被6个节点确认后,它将获得最终的确认,成为最长链,记录在最长链上的交易最终会被认证是成功的,而记录在另一条链上的交易则不会被认证。 UTXO模型是怎么计算余额的? 我们知道,要计算A的余额,在UTXO模型里,其实就是计算有多少笔交易的收款人的地址写的A,且这条交易输出没有被花费,那么这个余额怎么才能快速计算出来呢? 比特币客户端的实现维护一个UTXO数据库,也称UTXO池,是区块链中所有未支付交易输出的集合。“UTXO池”的名字听上去与交易池相似,但它代表了不同的数据集。UTXO池不同于交易池和孤立交易池的地方在于,它在初始化时不为空,而是包含了数以百万计的未支付交易输出条目,有些条目的历史甚至可以追溯至2009年。UTXO池可能会被安置在本地内存,或者作为一个包含索引的数据库表安置在永久性存储设备中。

October 4, 2018 · 1 min · Theme PaperMod

Kadamlia

简介 Kademlia算法是区块链底层实现点对点通信时所用的算法,它通过对节点之间的数学操作,获得逻辑上的节点距离,并用这个距离构建一个不同层次的路由表。通过对该路由表的查询,更新等操作,使节点与节点之间能够相互发现。 主要概念 NodeID Kadamlia算法使用160bit(20字节)的哈希值作为节点的唯一标识,当一个节点新加入网络时,会被分配这个NodeID 距离 节点与节点之间的距离,是将两个节点的NodeID进行XOR操作后得到值,一般将得到的二进制数转化为十进制数后的值作为距离,例如对于NodeID分别为 0011 和 1011 的节点,异或之后得到的值为1000(二进制),即距离为4(十进制) 公共前缀长度 Common Prefix Length(CPL) 举个列子,假设NodeID为3位,那么对于节点 110,它与周围节点的CPL分别为 CPL 所含节点 0 000 001 010 011 1 100 101 2 111 3 110(自身) 可以看出,节点间CPL越大,则节点XOR之后的值越小,即两节点的逻辑距离越小 二叉前缀树 一个完整的网络空间可以被表示成为一颗二叉树,树的叶子节点代表网络节点 K-Bucket K-Bucket又称为K桶,Bucket里存的是一组CLP的长度一样的节点 路由表 一个由K-Bucket构成的链表 分裂 某些Kadamlia算法的实现是一开始仅有一个Bucket,当Bucket的容量超过限制时,将最小的cpl的节点和其他节点分裂开的操作 仍以上面的例子为例,如果一开始仅有一个Bucket,那么 000 ~ 111 的 8 个节点都存在一个Bucket中,假设此时Bucket的容量K为1,即现有的8个节点超过了容量,需要将之分裂 第一次分裂 Old Bucket = (000 001 010 011) New Bucket = (100 101 111)...

October 3, 2018 · 1 min · Theme PaperMod

Pow算法

什么是Pow算法? Pow的全称是Proof of Work,即工作量证明,是区块链中用来判断由哪个矿工获得区块打包权的算法。 区块链的块的结构 在聊Pow之前,首先,必须先认识区块的结构,基本的区块结构如下 区块结构 当前块的hash值 前一个区块的哈希值 Merkle根哈希值 时间戳 难度值 随机数Nonce 区块包含的交易列表 Merkle根 交易列表里记录的每一笔交易都有一个唯一的哈希值,将交易的hash值两两组合,最后生成Merkle根 Merkle保证了区块的交易信息不会被串改 Nonce值 矿工挖矿的过程其实就是对交易数据进行打包后,算出一个符合如下公式的Nonce值的过程 CryptoJS.SHA256(index + previousHash + timestamp + data + nonce) 该公式的结果是一个hash值,而挖矿的难度就是这个hash值的前面有几个0,难度越大,即要求的0的个数越多,就越难算出来,这个算的过程就是矿工工作的过程,所以这个算法才叫工作量证明算法。

October 3, 2018 · 1 min · Theme PaperMod

Grunt

Grunt是一个基于NodeJS,可用于自动化构建、测试、生成文档的项目管理工具。

September 4, 2018 · 2 min · Lambert Xiao

Gulp

Gulp 是一个构建工具,可以通过它自动执行网站开发过程中的公共任务,比如编译 SASS/Less,编译压缩混淆 JavaScript,,合并编译模板和版本控制等。因为 gulp 是基于 Node.js 构建的,所以 gulp 源文件和开发者自己定义的 gulpfile 都被写进 JavaScript 里,前端开发者可以用自己熟悉的语言来编写 gulp 任务。

September 4, 2018 · 2 min · Lambert Xiao

TCP协议

TCP协议 TCP(Transmission Control Protocol 传输控制协议)是一种面向连接的、可靠的、基于字节流的传输层通信协议,由IETF的RFC 793定义。在简化的计算机网络OSI模型中,它完成第四层传输层所指定的功能,用户数据报协议(UDP)是同一层内另一个重要的传输协议。 主要特点 面向连接 一对一 可靠交付 全双工 面向字节流 套接字Socket的含义 Socket := IP + Port TCP连接 := {Socket1, Socket2} 解释为两个Socket之间的连接 TCP可靠传输的工作原理 停止等待协议 超时重传 超时计时器 保留已发送分组的副本 对数据分组和确认分组的编号 重传时间的设置 确认丢失和确认迟到 信道利用率 连续ARQ协议 发送方维持的滑动窗口 累计确认 容易实现,即使确认丢失也不必重传 不能向发送方反映出接收方以及正确接收到的所有分组的信息 TCP报文段的首部格式 源端口和目的端口 序号 确认号ack...

September 4, 2018 · 2 min · Theme PaperMod

UDP协议

UDP协议 UDP协议全称是用户数据报协议,在网络中它与TCP协议一样用于处理数据包,是一种无连接的协议。在OSI模型中,在第四层——传输层,处于IP协议的上一层。UDP有不提供数据包分组、组装和不能对数据包进行排序的缺点,也就是说,当报文发送之后,是无法得知其是否安全完整到达的。 基本特点 无连接的 不保证可靠交付 面向报文的,在添加了UDP协议的首部后就直接塞给UP层了 没有拥塞控制 支持一对一,一对多和多对多的交互通信 UDP首部开销小 UDP首部格式 源端口 目的端口 长度 校验和(检测UDP数据包在传输中是否有错,有错就丢弃)

September 4, 2018 · 1 min · Theme PaperMod

Webpack

webpack 是一个模块打包器(module bundler)。打包器(bundler)帮助您取得准备用于部署的 JavaScript 和样式表,将它们转换为适合浏览器的可用格式。

September 4, 2018 · 2 min · Lambert Xiao

产生死锁的原因和必要条件

产生死锁的原因和必要条件 在多道程序系统中,虽可借助于多个进程的并发执行来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——死锁。所谓死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。 产生死锁的必要条件 互斥条件 指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由 一个进程占用。如果此时还有其它进程请求该资源,则请求者只能等待,直至占有该资源的进程用毕释放。 请求和保持条件 指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。 不剥夺条件 指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完 时由自己释放。 环路等待条件 指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,…,Pn}中的 P0正在等待一个 P1占用的资源; P1正在等待 P2占用的资源,……,Pn正在等待已被 P0占用的资源。 处理死锁的基本方法 预防死锁 该方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但由于所施加的限制条件往往太严格,因而可能会导致系统资源利用率和系统吞吐量降低。 避免死锁 是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁 检测死锁 这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进 入不安全区,而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源; 然后,采取适当措施,从系统中将已发生的死锁清除掉 解除死锁 这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须 将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行

September 2, 2018 · 1 min · Theme PaperMod

基本分段存储管理方式

基本分段存储管理方式 如果说推动存储管理方式从固定分区到动态分区分配,进而又发展到分页存储管理方式的主要动力,是提高内存利用率,那么,引入分段存储管理方式的目的,则主要是为了满足用户(程序员)在编程和使用上多方面的要求。 分段存储管理方式的引入 方便编程 通常,用户把自己的作业按照逻辑关系划分为若干个段,每个段都是从 0 开始编址,并有自己的名字和长度。因此,希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。 信息共享 在实现对程序和数据的共享时,是以信息的逻辑单位为基础的。比如,共享某个例程 和函数。分页系统中的“页”只是存放信息的物理单位(块),并无完整的意义,不便于实现共享;然而段却是信息的逻辑单位。 信息保护 动态增长 在实际应用中,往往有些段,特别是数据段,在使用过程中会不断地增长,而事先又无法确切地知道数据段会增长到多大。(是哪种情况?) 动态链接 动态链接是指在作业运行之前,并不把几个目标程序段链接起来。要运行时,先将主程序所对应的目标程序装入内存并启动运行,当运行过程中又需要调用某段时,才将该段(目标程序)调入内存并进行链接。可见,动态链接也要求以段作为管理的单位。 分段系统的基本原理 分段 在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组逻辑信息。例如,有主程序段MAIN、子程序段X、数据段D及栈段S等。每个段都有自己的名字。为了实现简单起见,通常可用一个段号来代替段名,每个段都从 0开始编址,并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定,因而各段长度不等。 分段方式已得到许多编译程序的支持,编译程序 能自动地根据源程序的情况而产生若干个段。编译程序可以为全局变量、用于存储相应参数及返回地址的过程调用栈、每个过程或函数的代码部分、每个过程或函数的局部变量等等,分别建立各自的段。 段表 在前面所介绍的动态分区分配方式中,系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中,则是为每个分段分配一个连续的分区,而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行,亦即,能从物理内存中找出每个逻辑段所对应的位置,应像分页系统那样,在系统中为每个进程建立一张段映射表,简称“段表”。每个段在表中占有一个表项,其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。段表可以存放在一组寄存器中,这样有利于提高地址转换速度,但更常见的是将段表放在内存中 地址变换机构 为了实现从进程的逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用于存放段表始址和段表长度TL。在进行地址变换时,系统将逻辑地址中的段号与段表长度TL 进行比较。若S>TL,表示段号太大,是访问越界,于是产生越界中断信号;若未越界,则根据段表的始址和该段的段号,计算出该段对应段表项的位置,从中读出该段在内存的起始地址,然后,再检查段内地址d是否超过该段的段长SL。若超过,即 d>SL,同样发出越界中断信号;若未越界,则将该段的基址d与段内地址相加即可得到要访问的内存物理地址。 像分页系统一样,当段表放在内存中时,每要访问一个数据,都须访问两次内存,从而极大地降低了计算机的速率。解决的方法也和分页系统类似,再增设一个联想存储器,用于保存最近常用的段表项。 分页和分段的主要区别 两者都采用离散分配方式,且都要通过地址映射机构来实现地址变换。 分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位,它含有一组其意义相对完整的信息 页的大小固定且由系统决定,由系统把逻辑地址划分为页号和页内地址两部分,是 由机器硬件实现的,因而在系统中只能有一种大小的页面;而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分。 分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需利用一个记忆 符,即可表示一个地址;而分段的作业地址空间则是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址 信息共享 分段系统的一个突出优点,是易于实现段的共享,即允许若干个进程共享一个或多个分段,且对段的保护也十分简单易行。在分页系统中,虽然也能实现程序和数据的共享,但远不如分段系统来得方便。 举个例子 有一个多用户系统,可同时接纳 40 个用户,他们都执行一个文本编辑程序(Text Editor)。如果文本编辑程序有 160 KB 的代码和另外 40 KB 的数据区,则总共需有 8 MB 的内存空间来支持 40个用户。如果160KB的代码是可重入的(Reentrant),则无论是在分页系统还是在分段系统中,该代码都能被共享,在内存中只需保留一份文本编辑程序的副本,此时所需的内存空间仅为1760KB(40×40+160),而不是8000KB。假定每个页面的大小为 4 KB,那么,160KB的代码将占用40个页面,数据区占10个页面。为实现代码的共享,应在每个进程的页表中都建立40个页表项,它们的物理块号都是21#~60#。在每个进程的页表中,还须为自己的数据区建立页表项,它们的物理块号分别是61#~70#、71#~80#、81#~90#,…,等等。...

September 2, 2018 · 1 min · Theme PaperMod

基本分页存储管理方式

基本分页存储管理方式 连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间,但须为之付出很大开销。$\color{maroon}{如果允许将一个进程直接分散地装入到许多不相邻接的分区中}$,则无须再进行“紧凑”。 基于这一思想而产生了离散分配方式。 如果离散分配的基本单位是页,则称为分页存储管理方式; 如果离散分配的基本单位是段,则称为分段存储管理方式 页面与页表 页面 页面和物理块 分页存储管理是将一个 进程的逻辑地址空间 分成若干个大小相等的片,称为页面或页,并为各页加以编号,从 0 开始,如第 0 页、第 1 页等。 也把 内存空间 分成与页面相同大小的若干个存储块,称为(物理)块或页框(frame),也同样为它们加以编号,如0#块、1#块等等。 在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为“页内碎片”。 页面大小 在分页系统中的页面其大小应适中。页面若太小,一方面虽然可使内存碎片减小,从而减少了内存碎片的总空间,有利于提高内存利用率,但另一方面也会使每个进程占用较多的页面,从而导致进程的页表过长,占用大量内存;此外,还会降低页面换进换出的效率。然而,如果选择的页面较大,虽然可以减少页表的长度,提高页面换进换出的速度,但却又会使页内碎片增大。因此,页面的大小应选择适中,且页面大小应是 2 的幂,通常为 512 B~8 KB。 地址结构 前一部分为页号P,后一部分为位移量W(或称为页内地址)。图中的地址长度为32位,其中 0~11 位为页内地址,即每页的大小为4KB;12~31 位为页号,地址空间最多允许有 1 M 页。 对于某特定机器,其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A,页面的大小为 L,则页号 P 和页内地址 d可按下式求得: P = INT(A/L) d = MOD(A/L) 页面 在分页系统中,允许将进程的各个页离散地存储在内存不同的物理块中,但系统应能保证进程的正确运行,即能在内存中找到每个页面所对应的物理块。为此,系统又为每个进程建立了一张页面映像表,简称页表。在进程地址空间内的所有页(0~n),依次在页表中有一页表项,其中记录了相应页在内存中对应的物理块号。在配置了页表后,进程执行时,通过查找该表,即可找到每页在内存中的物理块号。可见,页表的作用是实现从页号到物理块号的地址映射。 即使在简单的分页系统中,也常在页表的表项中设置一存取控制字段,用于对该存储块中的内容加以保护。当存取控制字段仅有一位时,可用来规定该存储块中的内容是允许读/写,还是只读;若存取控制字段为二位,则可规定为读/写、只读和只执行等存取方式。如果有一进程试图去写一个只允许读的存储块时,将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器,则还须增设一数据项。 地址变换机构...

September 2, 2018 · 1 min · Theme PaperMod

对换

对换 对换(Swapping)的引入 在多道程序环境下,一方面,在内存中的某些进程由于某事件尚未发生而被阻塞运行,但它却占用了大量的内存空间,甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况;另一方面,却又有着许多作业在外存上等待,因无内存而不能入内存运行的情况。显然这对系统资源是一种严重的浪费,且使系统吞吐量下降。为了解决这一问题,在系统中又增设了对换(也称交换)设施。所谓“对换”,是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上,以便腾出足够的内存空间,再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。 如果对换是以整个进程为单位的,便称之为“整体对换”或“进程对换”。而如果对换是以“页”或“段”为单位进行的,则分别称之为“页面对换”或“分段对换”,又统称为“部分对换”。 实现进程对换,系统必须能实现三方面的功能 对换空间的管理 在具有对换功能的OS中,通常把外存分为文件区和对换区。前者用于存放文件,后者用于存放从内存换出的进程。 进程的换出 每当一进程由于创建子进程而需要更多的内存空间,但又无足够的内存空间等情况发生时,系统应将某进程换出。其过程是:系统首先选择处于阻塞状态且优先级最低的进程作为换出进程,然后启动磁盘,将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误,便可回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改。 进程的换入 系统应定时地查看所有进程的状态,从中找出“就绪”状态但已换出的进程,将其中换出时间最久(换出到磁盘上)的进程作为换入进程,将之换入,直至已无可换入的进程或无可换出的进程为止。

September 2, 2018 · 1 min · Theme PaperMod

操作系统引论

第一章 操作系统引论 操作系统的目标和作用 OS 作为用户与计算机硬件系统之间的接口 OS 作为计算机系统资源(处理器、存储器、I/O 设备以及信息(数据和程序))的管理者 OS 实现了对计算机资源的抽象 操作系统的基本特性 并发性 并行性是指两个或多个事件在同一时刻发生;而并发性是指两个或多个事件在同一时间间隔内发生。 共享性 指系统中的资源可供内存中多个并发执行的进程(线程)共同使用 虚拟技术 时分复用技术 空分复用技术 异步性 由于资源等因素的限制,使进程的执行通常都不是“一气呵成”,而是以“停停走走”的方式运行 操作系统的主要功能 处理机管理功能 在传统的多道程序系统中,处理机的分配和运行都是以进程为基本单位,因而对处理机的管理可归结为对进程的管理;在引入了线程的 OS 中,也包含对线程的管理。处理机管理的主要功能是创建和撤消进程(线程),对诸进程(线程)的运行进行协调,实现进程(线程)之间的信息交换,以及按照一定的算法把处理机分配给进程(线程)。 存储器的功能 存储器管理应具有内存分配、内存保护、地址映射和内存扩充 设备管理功能 设备管理用于管理计算机系统中所有的外围设备,而设备管理的主要任务是:完成用户进程提出的 I/O 请求;为用户进程分配其所需的 I/O 设备;提高 CPU 和 I/O 设备的利用率;提高 I/O 速度;方便用户使用 I/O 设备。为实现上述任务,设备管理应具有缓冲管理、设备分配和设备处理以及虚拟设备等功能。 文件管理功能...

September 2, 2018 · 1 min · Theme PaperMod

线程的基本概念

线程的基本概念 线程的引入 如果说,在操作系统中引入进程的目的,是为了使多个程序能并发执行,以提高资源利用率和系统吞吐量,那么,在操作系统中再引入线程,则是为了减少程序在并发执行时所付出的时空开销,使 OS 具有更好的并发性。 由于进程是一个资源的拥有者,因而在创建、撤消和切换中,系统必须为之付出较大的时空开销。线程作为调度和分派的基本单位。 线程与进程的比较 线程具有许多传统进程所具有的特征,所以又称为轻型进程(Light-Weight Process)或进程元,相应地把传统进程称为重型进程(Heavy-WeightProcess) 调度 在传统的操作系统中,作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中,则把线程作为调度和分派的基本单位,而进程作为资源拥有的基本单位,使线程基本上不拥有资源,这样线程便能轻装前进,从而可显著地提高系统的并发程度。在同一进程中,线程的切换不会引起进程的切换,但从一个进程中的线程切换到另一个进程中的线程时,将会引起进程的切换。 并发性 在引入线程的操作系统中,不仅进程之间可以并发执行,而且在一个进程中的多个线程之间亦可并发执行,使得操作系统具有更好的并发性,从而能更加有效地提高系统资源的利用率和系统的吞吐量 拥有资源 进程是系统中拥有资源的一个基本单位。一般而言,线程自己不拥有系统资源(也有一点必不可少的资源),但它可以访问其隶属进程的资源,即一个进程的代码段、数据段及所拥有的系统资源,如已打开的文件、I/O设备等,可以供该进程中的所有线程所共享。 系统开销 在创建或撤消进程时,系统都要为之创建和回收进程控制块,分配或回收资源,如内存空间和I/O设备等,操作系统所付出的开销明显大于线程创建或撤消时的开销。类似地,在进程切换时,涉及到当前进程CPU环境的保存及新被调度运行进程的CPU环境的设置,而线程的切换则仅需保存和设置少量寄存器内容,不涉及存储器管理方面的操作,所以就切换代价而言,进程也是远高于线程的。此外,由于一个进程中的多个线程具有相同的地址空间,在同步和通信的实现方面线程也比进程容易。在一些操作系统中,线程的切换、同步和通信都无须操作系统内核的干预。 线程的属性 轻型实体 线程中的实体基本上不拥有系统资源,只是有一点必不可少的、能保证其独立运行的资源,比如,在每个线程中都应具有一个用于控制线程运行的线程控制块 TCB,用于指示被执行指令序列的程序计数器,保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。 独立调度和分派的基本单位 可并发执行 共享进程资源 线程的状态 状态参数 在 OS 中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项: 寄存器状态,它包括程序计数器 PC(存放下一条指令所在单元) 和堆栈指针中的内容; 堆栈,在堆栈中通常保存有局部变量和返回地址; 线程运行状态,用于描述线程正处于何种运行状态; 优先级,描述线程执行的优先程度; 线程专有存储器,用于保存线程自己的局部变量拷贝; 信号屏蔽,即对某些信号加以屏蔽。...

September 2, 2018 · 1 min · Theme PaperMod

经典进程的同步问题

经典进程的同步问题 生产者—消费者问题 利用记录型信号量解决 假定在生产者和消费者之间的公用缓冲池中,具有n个缓冲区,这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量emptyCount和fullCount分别表示缓冲池中 空缓冲区 和 满缓冲区 的数量 mutex, emptyCount, fullCount := 1, n, 0 func proceducer() { wait(emptyCount) wait(mutex) // 生产一个产品,放入一个空的缓冲区中 signal(mutex) signal(fullCount) } func consumer() { wait(fullCount) wait(mutex); // 消费一个产品,取走一个满缓冲区的内容 signal(mutex); signal(emptyCount); } 利用 AND 信号量解决 对于生产者—消费者问题,也可利用AND信号量来解决,即用 Swait(empty,mutex) 来代替 wait(empty) 和 wait(mutex);用 Ssignal(mutex,full) 来代替 signal(mutex) 和 signal(full) ;用 Swait(full,mutex) 来代替 wait(full) 和 wait(mutex),以及用 Ssignal(mutex,empty) 代替 Signal(mutex) 和 Signal(empty)。 mutex, emptyCount, fullCount := 1, n, 0 func proceducer() { Swait(emptyCount, mutex) // 生产一个产品,放入一个空的缓冲区中 Ssignal(mutex,fullCount) } func consumer() { Swait(fullCount,mutex) // 消费一个产品,取走一个满缓冲区的内容 Ssignal(mutex,emptyCount) } 利用管程解决...

September 2, 2018 · 1 min · Theme PaperMod

虚拟存储器的基本概念

虚拟存储器的基本概念 虚拟存储器的引入 常规存储器管理方式的特征 一次性。在前面所介绍的几种存储管理方式中,都要求将作业全部装入内存后方能运行,即作业在运行前需一次性地全部装入内存,而正是这一特征导致了上述两种情况的发生。此外,还有许多作业在每次运行时,并非其全部程序和数据都要用到。如果一次性地装入其全部程序,也是一种对内存空间的浪费。 驻留性。作业装入内存后,便一直驻留在内存中,直至作业运行结束。尽管运行中的进程会因 I/O 而长期等待,或有的程序模块在运行过一次后就不再需要(运行)了,但它们都仍将继续占用宝贵的内存资源。 局部性原理 程序执行时,除了少部分的转移和过程调用指令外,在大多数情况下仍是顺序执行的。该论点也在后来的许多学者对高级程序设计语言(如 FORTRAN 语言、PASCAL 语言)及 C 语言规律的研究中被证实。 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域,但经研究看出,过程调用的深度在大多数情况下都不超过 这就是说,程序将会在一段时间内都局限在这些过程的范围内运行。 程序中存在许多循环结构,这些虽然只由少数指令构成,但是它们将多次执行。 程序中还包括许多对数据结构的处理,如对数组进行操作,它们往往都局限于很小的范围内。 时间局限性。如果程序中的某条指令一旦执行,则不久以后该指令可能再次执行;如果某数据被访问过,则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。 空间局限性。一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,其典型情况便是程序的顺序执行。 虚拟存储器的定义 基于局部性原理,应用程序在运行之前,没有必要全部装入内存,仅须将那些当前要运行的少数页面或段先装入内存便可运行,其余部分暂留在盘上。程序在运行时,如果它所要访问的页(段)已调入内存,便可继续执行下去;但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段),此时程序应利用OS所提供的请求调页(段)功能,将它们调入内存,以使进程能继续执行下去。如果此时内存已满,无法再装入新的页(段),则还须再利用页(段)的置换功能,将内存中暂时不用的页(段)调至盘上,腾出足够的内存空间后,再将要访问的页(段)调入内存,使程序继续执行下去。这样,便可使一个大的用户程序能在较小的内存空间中运行;也可在内存中同时装入更多的进程使它们并发执行。从用户角度看,该系统所具有的内存容量,将比实际内存容量大得多。但须说明,用户所看到的大容量只是一种感觉,是虚的,故人们把这样的存储器称为虚拟存储器。

September 2, 2018 · 1 min · Theme PaperMod

调度算法

调度算法 先来先服务和短作业(进程)优先调度算法 先来先服务调度算法 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用 FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 短作业(进程)优先调度算法 短作业(进程)优先调度算法SJ(P)F,是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。 高优先权优先调度算法 非抢占式优先权算法 在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。 抢占式优先权调度算法 在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程 基于时间片的轮转调度算法 时间片轮转法 基本原理 在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。 时间片大小的确定 在时间片轮转算法中,时间片的大小对系统性能有很大的影响,如选择很小的时间片将有利于短作业,因为它能较快地完成,但会频繁地发生中断、进程上下文的切换,从而增加系统的开销;反之,如选择太长的时间片,使得每个进程都能在一个时间片内完成,时间片轮转算法便退化为 FCFS 算法,无法满足交互式用户的需求。一个较为可取的大小是,时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。 多级反馈队列调度算法 前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法,仅照顾了短进程而忽略了长进程,而且如果并未指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要,因而它是目前被公认的一种较好的进程调度算法。 应设置多个就绪队列,并为各个队列赋予不同的优先级 当一个新进程进入内存后,首先将它放入第一队列的末尾,按 FCFS 原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中便采取按时间片轮转的方式运行。 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行

September 2, 2018 · 1 min · Theme PaperMod

进程同步

进程同步 进程同步的基本概念 两种形式的制约关系 间接相互制约关系 同处于一个系统中的进程,通常都共享着某种系统资源,如共享CPU、共享 I/O 设备等。所谓间接相互制约即源于这种资源共享,例如,有两个进程 A和 B,如果在A进程提出打印请求时,系统已将惟一的一台打印机分配给了进程 B,则此时进程A只能阻塞;一旦进程B将打印机释放,则A进程才能由阻塞改为就绪状态。 直接相互制约关系。 这种制约主要源于进程间的合作。例如,有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时,计算进程因不能获得所需数据而阻塞,而当进程A把数据输入缓冲区后,便将进程B唤醒;反之,当缓冲区已满时,进程 A 因不能再向缓冲区投放数据而阻塞,当进程B将缓冲区数据取走后便可唤醒 A。 临界资源 临界区 人们把在每个进程中访问临界资源的那段代码称为临界区(critical section) 同步机制应遵循的规则 空闲让进。当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效地利用临界资源。 忙则等待。当已有进程进入临界区时,表明临界资源正在被访问,因而其它试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。 有限等待。对要求访问临界资源的进程,应保证在有限时间内能进入自己的临界区,以免陷入“死等”状态。 让权等待。当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”状态 信号量机制 整型信号量 把整型信号量定义为一个用于表示资源数目的整型量S,它与一般整型量不同,除初始化外,仅能通过两个标准的原子操作(AtomicOperation)wait(S)和 signal(S)来访问 func wait(s int) { for s <= 0 { } s = s -1 } func signal(s int) { s = s + 1 } 记录型信号量...

September 2, 2018 · 1 min · Theme PaperMod

进程控制

进程控制 进程图 子进程可以继承父进程所拥有的资源,例如,继承父进程打开的文件,继承父进程所分配到的缓冲区等。当子进程被撤消时,应将其从父进程那里获得的资源归还给父进程。此外,在撤消父进程时,也必须同时撤消其所有的子进程。为了标识进程之间的家族关系,在PCB中都设置了家族关系表项,以标明自己的父进程及所有的子进程。 进程的创建 一旦操作系统发现了要求创建新进程的事件后,便调用进程创建原语 Creat( )按下述步骤创建一个新进程。 申请空白 PCB 为新进程申请获得惟一的数字标识符,并从 PCB 集合中索取一个 空白 PCB。 为新进程分配资源 为新进程的程序和数据以及用户栈分配必要的内存空间。 初始化进程控制块 初始化标识信息 将系统分配的标识符和父进程标识符填入新 PCB 中 初始化处理机状态信息 使程序计数器指向程序的入口地址,使栈指针指向栈顶; 初始化处理机控制信息 将进程的状态设置为就绪状态或静止就绪状态,对于优先级,通常是将它设置为最低优先级,除非用户以显式方式提出高优先级要求。 将新进程插入就绪队列 如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列 进程的终止 如果系统中发生了上述要求终止进程的某事件,OS便调用进程终止原语,按下述过程去终止指定的进程。 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态。 若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度。 若该进程还有子孙进程,还应将其所有子孙进程予以终止,以防它们成为不可控的进程。 将被终止进程所拥有的全部资源,或者归还给其父进程,或者归还给系统。 将被终止进程(PCB)从所在队列(或链表)中移出,等待其他程序来搜集信息。 进程的阻塞 正在执行的进程,当发现上述某事件时,由于无法继续执行,于是进程便通过调用阻塞原语 block 把自己阻塞。可见,进程的阻塞是进程自身的一种主动行为。进入 block过程后,由于此时该进程还处于执行状态,所以应先立即停止执行,把进控制块中的现行状态由“执行”改为“阻塞”,并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列,则应将本进程插入到具有相同事件的阻塞(等待)队列。最后,转调度程序进行重新调度,将处理机分配给另一就绪进程并进行切换,亦即,保留被阻塞进程的处理机状态(在 PCB 中),再按新进程的 PCB 中的处理机状态设置 CPU 的环境。...

September 2, 2018 · 1 min · Theme PaperMod

进程的描述操作系统引论

进程的描述 在多道程序环境下,程序的执行属于并发执行,此时它们将失去其封闭性,并具有间断性及不可再现性的特征。这决定了通常的程序是不能参与并发执行的,因为程序执行的结果是不可再现的。这样,程序的运行也就失去了意义。为使程序能并发执行,且为了对并发执行的程序加以描述和控制,人们引入了“进程”的概念。 结构特征 通常的程序是不能并发执行的。为使程序(含数据)能独立运行,应为之配置一进程控制块,即PCB(ProcessControlBlock);而由 程序段 、相关的 数据段 和 PCB 三部分便构了进程实体。所谓创建进程,实质上是创建进程实体 中的 PCB;而撤消进程,实质上是撤消进程的 PCB,本 动态性 进程的实质是进程实体的一次执行过程,“它由创建而产生,由调度而执行,由撤消而消亡 并发性 这是指多个进程实体同存于内存中,且能在一段时间内同时运行 独立性 指进程实体是一个能独立运行、独立分配资源和独立接受调 度的基本单位 异步性 指进程按各自独立的、不可预知的速度向前推进,或说进程实体按异步方式运行 进程的三种基本状态 就绪(Ready)状态 当进程已分配到除 CPU以外的所有必要资源后,只要再获得CPU,便可立即执行,进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个,通常将它们排成一个队列,称为就绪队列。 执行状态 进程已获得 CPU,其程序正在执行。在单处理机系统中,只有一个进程处于执行状态;在多处理机系统中,则有多个进程处于执行状态。 阻塞状态 正在执行的进程由于发生某事件而暂时无法继续执行时,便放弃处理机而处于暂停状态,亦即进程的执行受到阻塞,把这种暂停状态称为阻塞状态。 进程状态转化图 挂起状态的引入 引入原因 终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时,希望暂时使自己的程序静止下来。亦即,使正在执行的进程暂停执行;若此时用户进程正处于就绪状态而未执行,则该进程暂不接受调度,以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。 父进程请求。有时父进程希望挂起自己的某个子进程,以便考查和修改该子进程,或者协调各子进程间的活动。 负荷调节的需要。当实时系统中的工作负荷较重,已可能影响到对实时任务的控制时,可由系统把一些不重要的进程挂起,以保证系统能正常运行。 操作系统的需要。操作系统有时希望挂起某些进程,以便检查运行中的资源使用情况或进行记账。...

September 2, 2018 · 1 min · Theme PaperMod