【不周山之算法与数据结构】拾贰 其他知识

这一章包括剩余一些比较基本的常识性知识,具体可能是以聊天的形式来进行交流,关键就在于理解,不要死记硬背。其实计算机学科的各种概念联系都比较紧密,梳理清晰自然就记住了。


系列文章

基本上编程中重要的内容,都在这里了。

网络

计算机之间的交互模型通常是指Open Systems Interconnection model (OSI),该模型将网络通信系统抽象成了七层

路由

从用户角度来看,路由(Routing)是指将数据从一个用户终端,通过网络节点(例如路由器,交换机等),发送到另一个用户节点的过程。理论上说,对于一个拥有多个节点的拓扑网络而言,路由是指在Network Layer(OSI model的第三层),将数据包(data packet)从一个节点以最优路径发送到目标节点的实现方法。其核心包括:如何获得邻近节点的信息,如何估计链路质量,如何寻址,如何构建网络拓扑结构“等等。 通过路由器之间的路由协议(routing protocol),可以实现两个网络节点之间信息(包括网络域名,邻近节点,链路质量等)的交换和散布,通过不断重复该过程,每个节点都会获得足够多关于所在网络的拓扑信息。当有数据包需要传送时,路由器再通过路由算法(routing algorithm)计算传递当前数据包的最优路径,并把数据包发送给下一个邻近节点。许多路由算法基于图理论,实现了最小生成树,最短路径等等经典的拓扑算法。关于路由算法的进一步讨论,请参考“工具箱”中提到的参考教材。

网络中,所谓的地址是指IP地址,IPv4规定利用32bits作为IP地址。但随着网络设备的增多,IPv4已经不能满足人们的需求,故互联网逐渐向IPv6进行演进,IPv6利用128bits作为IP地址。

事实上,直观而言,network routing的过程就相当于传统意义上的邮包寄送,IP地址可以类比于邮政编码,路由器就相当于邮局,通过目的地邮政编码与邮局系统中的递送路径进行比较,由此确定下一步应该把当前包裹传递到哪里。

常用网络统计指标

衡量网络质量通常有下面两个指标:

1) 带宽/速率(Bandwidth/Rate)

所谓的带宽是指一个网络节点能以多快的速度将数据接收/发送出去,单位是bits per second(bps)。对于对实时性要求不高的数据,例如下载等,带宽是影响用户体验的主要因素。两个终端节点之间的带宽由路径中所有节点的最小带宽决定。同时,终端的数据发送速度不应该超过当前的上载带宽,否则会对网络造成压力导致拥堵(congestion)。

2) One-way Delay / Round Trip Time (RTT)

One-way Delay用以衡量网络的延迟。假设在时间点A从一个节点发送数据到另一个节点,目的地节点在时间点B收到数据,则两个时间点之差即为One-way Delay。类似地,RTT则是数据完成一个Round Trip回到始发节点的时间差,一般RTT可以近似估计为One-way Delay的两倍。对于网络会议,IP电话等等,延迟是影响用户体验的主要因素。延迟可能是由网络中某个节点处理数据速度慢,突然有大规模数据需要传输,或者某条链路不断重传数据造成的。延迟与带宽有一定的相关性,但没有必然联系:可以类比某个路口,假设每秒可以有一辆车通过该路口,但现在突然来了100辆车,路口的通过效率并没有变化(即带宽不变),但每辆车通过路口的等待时间却变长了(延迟增加)。

Transmission Control Protocol,TCP

Reliable Protocol

TCP是一种可靠的传输协议,即在网络条件正常的情况下,TCP协议能够保证接收端收到所有数据,并且接收到的数据顺序与发送端一致。TCP通过在发送端给每个数据包分配单调递增的sequence number,以及在接受端发送ACK(acknowledgement)实现可靠传输。每个发送的数据包都包含序列号,当接收端收到数据包时,会发送ACK告诉发送端当前自己期待的下一个序列号是多少。例如,发送端分别发送了序列号为99,100,101,102的四个数据包,接收端收到数据包99后,会发送ACK100,意味着接收端期待下一个数据包编号100。如果由于某些原因,数据包100没有到达接收端,但数据包101,102到达了,那么接收端会继续发送ACK100。当发送端发现当前发送的数据包编号超过了100,但接收端仍然期望收到100,那么发送端就会重新发送数据包100。“如果接收端收到了重新发送的数据包100,那么接收端会回复ACK103,继续进行剩下的数据传输,并且把数据包99,100,101,102按顺序传递给上一层。

Flow Control

TCP使用了end-to-end flow control以避免发送端发送数据过快导致接收端无法处理。TCP采用了滑动窗口(sliding window)实现流量控制。接收端通过ACK告诉发送端自己还能够接收多少数据,发送端不能发送超过该值的数据量。当接收端返回的窗口大小为0时,发送端停止发送数据,直到窗口大小被更新。由于ACK是由发送端发送的数据触发,可能接收端窗口已经打开,但是由于发送端已经停止发送,故接收端没有机会通过ACK告知发送端新的窗口大小,在这种情况下会造成死锁。在实际实现中,发送端会设置一个timer,如果timer到期,发送端会尝试发送小数据包,以触发接收端的ACK。

Congestion Control

为了控制传输速度防止堵塞网络,并且在网络容量允许的范围内尽可能多地传输数据,TCP引入congestion control,用以判断当前的网络负荷,并且调整传输速率。TCP通常采用additive increase,multiplicative decrease的算法,即如果按时收到对应的ACK,则下一次传输速率线性增加,否则则视为发生了网络堵塞,下一次传输的比特数折半。所谓的“按时”基于RTT:发送端会估计RTT,并且期望当数据包发送以后,在RTT时间内收到对应的ACK。“现代TCP需要分别实现Slow-start,congestion avoidance,fast retransmit和fast recovery,以达到最高的效率。具体请参考“工具箱”给出的资料。

User Datagram Protocol,UDP

相比于TCP,UDP简单许多:连接建立时不需要经过类似于TCP的三次握手,只需要知道接收端的IP和端口,发送端就可以直接发送数据。同时,UDP也没有ACK,flow control和congestion control,故UDP本身不能保证传输是可靠的。由于UDP本身只负责把数据传输到目的地,故可扩展性比较强。有些应用可以实现基于UDP 的特定算法,使得传输效率高于TCP。例如,当发生丢包时,TCP会重传该数据包,但该操作增加了传输延时。对于某些实时性要求较高的应用,可能继续传输新的数据更为重要,故基于UDP的传输方式可以更好地满足该要求。

通常而言,如果需要满足可靠性,有序接收,自适应带宽等要求,应该优先考虑TCP,因为其协议本身确保了这点。如果对实时性要求较高,或者应用需要特定的网络传输特性,则可以实现基于UDP的传输协议。往往,这样的协议需要实现congestion control,flow control,retransmission等机制,故通常情况下都可以直接采用TCP以减小开发成本。

数据库

事务的概念来自于两个独立的需求:并发数据库访问,系统错误恢复。

一个事务是可以被看作一个单元的一系列SQL语句的集合。

事务的特性(ACID)

  • A, atomacity 原子性 事务必须是原子工作单元;对于其数据修改,要么全都执行,要么全都不执行。通常,与某个事务关联的操作具有共同的目标,并且是相互依赖的。如果系统只执行这些操作的一个子集,则可能会破坏事务的总体目标。原子性消除了系统处理操作子集的可能性。
  • C, consistency 一致性。事务将数据库从一种一致状态转变为下一种一致状态。也就是说,事务在完成时,必须使所有的数据都保持一致状态(各种 constraint 不被破坏)。
  • I, isolation 隔离性 由并发事务所作的修改必须与任何其它并发事务所作的修改隔离。事务查看数据时数据所处的状态,要么是另一并发事务修改它之前的状态,要么是另一事务修改它之后的状态,事务不会查看中间状态的数据。换句话说,一个事务的影响在该事务提交前对其他事务都不可见。
  • D, durability 持久性。事务完成之后,它对于系统的影响是永久性的。该修改即使出现致命的系统故障也将一直保持。

事务的隔离级别

如果不对数据库进行并发控制,可能会产生异常情况:

  1. 脏读(Dirty Read)
    • 当一个事务读取另一个事务尚未提交的修改时,产生脏读。
    • 同一事务内不是脏读。 一个事务开始读取了某行数据,但是另外一个事务已经更新了此数据但没有能够及时提交。这是相当危险的,因为很可能所有的操作都被回滚,也就是说读取出的数据其实是错误的。
  2. 非重复读(Nonrepeatable Read) 一个事务对同一行数据重复读取两次,但是却得到了不同的结果。同一查询在同一事务中多次进行,由于其他提交事务所做的修改或删除,每次返回不同的结果集,此时发生非重复读。
  3. 幻像读(Phantom Reads) 事务在操作过程中进行两次查询,第二次查询的结果包含了第一次查询中未出现的数据(这里并不要求两次查询的SQL语句相同)。这是因为在两次查询过程中有另外一个事务插入数据造成的。
    • 当对某行执行插入或删除操作,而该行属于某个事务正在读取的行的范围时,会发生幻像读问题。
  4. 丢失修改(Lost Update)
    • 第一类:当两个事务更新相同的数据源,如果第一个事务被提交,第二个却被撤销,那么连同第一个事务做的更新也被撤销。
    • 第二类:有两个并发事务同时读取同一行数据,然后其中一个对它进行修改提交,而另一个也进行了修改提交。这就会造成第一次写操作失效。

为了兼顾并发效率和异常控制,在标准SQL规范中,定义了4个事务隔离级别,( Oracle 和 SQL Server 对标准隔离级别有不同的实现 )

  1. 未提交读(Read Uncommitted)
    • 直译就是”读未提交”,意思就是即使一个更新语句没有提交,但是别的事务可以读到这个改变。
    • Read Uncommitted允许脏读。
  2. 已提交读(Read Committed)
    • 直译就是”读提交”,意思就是语句提交以后,即执行了 Commit 以后别的事务就能读到这个改变,只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别。
    • Read Commited 不允许脏读,但会出现非重复读。
  3. 可重复读(Repeatable Read):
    • 直译就是”可以重复读”,这是说在同一个事务里面先后执行同一个查询语句的时候,得到的结果是一样的。
    • Repeatable Read 不允许脏读,不允许非重复读,但是会出现幻象读。
  4. 串行读(Serializable)
    • 直译就是”序列化”,意思是说这个事务执行的时候不允许别的事务并发执行。完全串行化的读,每次读都需要获得表级共享锁,读写相互都会阻塞。
    • Serializable 不允许不一致现象的出现。

事务隔离的实现——锁

  1. 共享锁(S锁)
    • 用于只读操作(SELECT),锁定共享的资源。共享锁不会阻止其他用户读,但是阻止其他的用户写和修改。
  2. 更新锁(U锁)
    • 用于可更新的资源中。防止当多个会话在读取、锁定以及随后可能进行的资源更新时发生常见形式的死锁。
  3. 独占锁(X锁,也叫排他锁)
    • 一次只能有一个独占锁用在一个资源上,并且阻止其他所有的锁包括共享缩。写是独占锁,可以有效的防止“脏读”。

Read Uncommited 如果一个事务已经开始写数据,则另外一个数据则不允许同时进行写操作,但允许其他事务读此行数据。该隔离级别可以通过“排他写锁”实现。

Read Committed 读取数据的事务允许其他事务继续访问该行数据,但是未提交的写事务将会禁止其他事务访问该行。可以通过“瞬间共享读锁”和“排他写锁”实现。

Repeatable Read 读取数据的事务将会禁止写事务(但允许读事务),写事务则禁止任何其他事务。可以通过“共享读锁”和“排他写锁”实现。

Serializable 读加共享锁,写加排他锁,读写互斥。

索引

数据库创建索引能够大大提高系统的性能。

  1. 通过创建唯一性的索引,可以保证数据库表中每一行数据的唯一性。
  2. 可以大大加快数据的检索速度,这也使创建索引的最主要的原因。
  3. 可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。
  4. 在使用分组和排序子句进行数据检索时,同样可以显著的减少查询中查询中分组和排序的时间。
  5. 通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。

增加索引也有许多不利的方面。

  1. 创建索引和维护索引需要消耗时间,这种时间随着数量的增加而增加。
  2. 索引需要占物理空间,除了数据表占据数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要额空间就会更大。
  3. 当对表中的数据进行增加,删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

应该对如下的列建立索引

  1. 在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构。
  2. 在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度。
  3. 在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的。
  4. 在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间。
  5. 在经常使用在where子句中的列上面创建索引,加快条件的判断速度。

有些列不应该创建索引

  1. 在查询中很少使用或者作为参考的列不应该创建索引。
  2. 对于那些只有很少数据值的列也不应该增加索引(比如性别,结果集的数据行占了表中数据行的很大比例,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度)。
  3. 对于那些定义为text,image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。
  4. 当修改性能远远大于检索性能时,不应该创建索引,因为修改性能和检索性能是矛盾的。

创建索引的方法:直接创建和间接创建(在表中定义主键约束或者唯一性约束时,同时也创建了索引)。

索引的特征:

唯一性索引和复合索引。唯一性索引保证在索引列中的全部数据是唯一的,不会包含冗余数据。复合索引就是一个索引创建在两个列或者多个列上。可以减少一在一个表中所创建的索引数量。

测试

在面试软件开发的过程中,面试官可能也会询问关于软件开发流程以及测试方法相关的问题。在大多数互联网公司,许多部门不一定配有专门的QA(Quality Assurance),在这种情况下,程序员本身需要对自己开发的模块和系统进行测试。另一方面,程序员在开发过程中测试自己的程序也是非常好的习惯,这样可以确保开发效率。基于上述原因,面试软件开发职位但遇到测试相关的问题并不少见。

测试现实世界的物体、软件或函数

三者并无本质的差别,问题的核心均在于:测试对象在不同的输入下,能否实现预计的功能,提供恰当的输出。 一般情况下,总是需要考虑以下几个方面,以全面测试对象对于不同类型输入的效果:

(1) 常规情况(Normal cases)

输入不同类型的合法数据,主要用以判断对象的功能性:在给定输入的情况下能否给出期望的输出,由此判断功能的实现是否正确。比如,测试银行账户的转账功能:假设账户中有1000元,可以输入100,2000等并判断余额及转出钱数是否符合期望。

(2) 极端情况(Extreme cases)

测试一些边界条件或极端情况。所谓的极端情况包括多用户或多线程情况下频繁地访问/更新数据。比如,继续测试银行账户的转账功能:假设账户中有1000元,可以测试边界条件,取出1000元等。或者测试极端情况,假设用户开了多个页面,并在每个页面上几乎同时都尝试转出1000元,或者用户通过ATM机和手机APP同时进行转账操作等。

(3) 非法情况(Invalid case)

主要测试用户输入非法数据时系统不会崩溃,并且能够给出恰当的反馈。比如,测试银行账户的转账功能:当用户输入大于账户余额的数字时,或者当接收人账户错误时,系统能否给出错误提示等。

故障排除(Troubleshooting)

另一大类的常见问题是给出一个有问题的测试现象,让面试者判断问题出现在哪里。对于这类问题,首先考虑测试对象由生成,到运行,到产生最终结果的完整流程,其次判断每一步执行了什么,需要依赖哪些参数,该步骤的异常是否会导致最终的测试现象,并且考虑如何验证自己的判断。 例如,测试用户无法访问你开发的网站。首先考虑主要流程,简述如下:用户连接到网络,发送HTTP请求到网站,网站发送数据包给用户,用户浏览器显示页面。在此例中,每一步都有可能导致无法访问网站的情况,具体描述如下:

(1) 用户连接到网络:这一步用户需要获得有效的IP,获取访问互联网的权限。需要依赖用户的网卡是否工作正常,是否能够被分配到有效的IP,是否能够从路由器或者服务器获得互联网访问权限等等。检验方式可以是:可以打开终端用ping命令,尝试建立与大型网站的连接。或者直接用浏览器尝试访问其他大型网站。如果不能建立与其他网站的连接,则网络接入有问题。

(2) 发送HTTP请求到网站:用户首先会通过DNS获取服务器地址,然后发送HTTP请求到对应的IP。需要依赖用户能否正确获取网站IP地址。检验方式可以是:在用户端利用抓包软件,例如WireShark,tcpdump等,观察是否有HTTP请求发送到网站服务器。如果没有发送HTTP请求或目的地IP有问题,则DNS可能有错。

(3) 网站发送数据包给用户:这一步需要网站接收到HTTP请求,并且将对应数据传回给用户。需要依赖网站能否收到HTTP请求以及对于HTTP请求的处理是否正确。检验方式可以是:在服务器端通过log判断是否有新用户接入,接入请求的处理是否正确,以及发送给用户的数据是什么。如果网站没有收到请求,则服务器端的网络可能有问题。如果服务器无法处理HTTP请求或抛出异常,则服务器的实现可能有问题。

(4) 用户浏览器显示页面: 这一步需要用户接收到网站发回的数据,浏览器解析数据并显示页面。需要依赖于用户能否收到数据,以及收到的数据是否能够被浏览器正确解析及显示。检验方式可以是:在用户端利用抓包软件,观察是否有来自服务器的数据。一般来说,如果用户用的是商用浏览器,即能够正确解析数据。故如果能收到服务器数据但是不能正常显示,我们可以认为服务器的数据有问题。

测试的方法

AB Testing

AB测试是一种对比测试方案。测试人员对于不同用户随机生成两种方案,例如,某些用户看到的网页按钮是圆形的,其他用户看到的网页按钮是方形的。通过用户对于不同测试方案的反应,来决定最终部署哪种方案。具体请参考:
http://en.wikipedia.org/wiki/A/B_testing

Black Box Testing

黑箱测试主要用于测试程序的功能,而不是内部结构或运作。测试者秩序知道输入以及对应的输出,就可以生成测试数据。黑箱测试的目的在于快速检测程序的功能性。特别地,黑箱测试还应该包括非法的输入数据,以确保程序不会崩溃。

White Box Testing

与黑箱测试相对,白箱测试主要用于测试程序的内部结构或运作。测试人员需要从程序设计的角度生成测试案例:输入测试数据并验证程序按照既定的流程执行。

工业界测试流程

Unit Test

优良的软件设计强调模块化,即模块之间通过API进行交互,每个模块负责实现相对独立的功能。单元测试的目的在于对于每个模块设计相应的测试数据,用以检验模块的功能。通常,单元测试采用黑箱测试,通过运行脚本完成。测试人员将测试数据输入脚本,将输出结果与期望的输出数据进行比较。单元测试不仅仅可以用于新模块的开发,还可以用于对于已有模块的更新,维护。对于模块的每次更改都应该运行相应的单元测试以确保功能的完整性。

Alpha Test

Alpha测试通常是阶段性开发完成后开始进行。主要是面向内部开发人员,在模拟环境中输入模拟的数据进行测试,以验证系统符合使用者以及设计者的需求。

Beta Test

当Alpha阶段完成后,可以进入由公众参与的beta测试阶段。Beta测试通常使用真实的运行环境,并且使用实际数据进行测试,以确认系统效率。测试的主要目的在于进一步测试及完善功能。

操作系统

大部分互联网公司的软件开发职位面试可能不会直接涉及这一层面的知识,但并不意味着这部分知识不重要。对于计算机底层实现的深入理解,能帮助你了解计算机的运行原理,能够更好地设计高效的架构,并且有助于调试、判断错误。特别地,对于多线程的理解尤为重要:现今的程序架构都需要并发处理,如何协调不同线程之间的分工协作,避免死锁、同步出错等等问题,是程序员应当具备的技能。对于后端工程师而言,良好的操作系统知识基础更是深刻理解并实现复杂分布式系统的前提条件。

进程

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源,是一个动态的概念,是一个活动的实体。它不只是程序的代码,还包括当前的活动,通过程序计数器的值和处理寄存器的内容来表示。

进程的概念主要有两点:第一,进程是一个实体。每一个进程都有它自己的地址空间,一般情况下,包括文本区域(text region)、数据区域(data region)和堆栈(stack region)。文本区域存储处理器执行的代码;数据区域存储变量和进程执行期间使用的动态分配的内存;堆栈区域存储着活动过程调用的指令和本地变量。第二,进程是一个“执行中的程序”。程序是一个没有生命的实体,只有处理器赋予程序生命时,它才能成为一个活动的实体,我们称其为进程。

进程的基本状态

  1. 等待态:等待某个事件的完成;
  2. 就绪态:等待系统分配处理器以便运行;
  3. 运行态:占有处理器正在运行。
  4. 运行态→等待态 往往是由于等待外设,等待主存等资源分配或等待人工干预而引起的。

等待态→就绪态 则是等待的条件已满足,只需分配到处理器后就能运行。

运行态→就绪态 不是由于自身原因,而是由外界原因使运行状态的进程让出处理器,这时候就变成就绪态。例如时间片用完,或有更高优先级的进程来抢占处理器等。

就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器,此时就变成了运行态

进程调度

调度种类

高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:

  • 高级调度:(High-Level Scheduling)又称为作业调度,它决定把后备作业调入内存运行;
  • 低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU;
  • 中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换。

非抢占式调度与抢占式调度

  • 非抢占式
    • 分派程序一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成或发生进程调度进程调度某事件而阻塞时,才把处理机分配给另一个进程。
  • 抢占式
    • 操作系统将正在运行的进程强行暂停,由调度程序将CPU分配给其他就绪进程的调度方式。

调度策略的设计

响应时间: 从用户输入到产生反应的时间

周转时间: 从任务开始到任务结束的时间

CPU任务可以分为交互式任务和批处理任务,调度最终的目标是合理的使用CPU,使得交互式任务的响应时间尽可能短,用户不至于感到延迟,同时使得批处理任务的周转时间尽可能短,减少用户等待的时间。

调度算法

  1. FIFO或First Come, First Served (FCFS)
    • 调度的顺序就是任务到达就绪队列的顺序。
    • 公平、简单(FIFO队列)、非抢占、不适合交互式。未考虑任务特性,平均等待时间可以缩短
  2. Shortest Job First (SJF)
    • 最短的作业(CPU区间长度最小)最先调度。
    • 可以证明,SJF可以保证最小的平均等待时间。
    • Shortest Remaining Job First (SRJF)
    • SJF的可抢占版本,比SJF更有优势。
    • SJF(SRJF): 如何知道下一CPU区间大小?根据历史进行预测: 指数平均法。
  3. 优先权调度
    • 每个任务关联一个优先权,调度优先权最高的任务。
    • 注意:优先权太低的任务一直就绪,得不到运行,出现“饥饿”现象。
    • FCFS是RR的特例,SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。
  4. Round-Robin(RR)
    • 设置一个时间片,按时间片来轮转调度(“轮叫”算法)
    • 优点: 定时有响应,等待时间较短;缺点: 上下文切换次数较多;
    • 如何确定时间片?
    • 时间片太大,响应时间太长;吞吐量变小,周转时间变长;当时间片过长时,退化为FCFS。
  5. 多级队列调度
    • 按照一定的规则建立多个进程队列
    • 不同的队列有固定的优先级(高优先级有抢占权)
    • 不同的队列可以给不同的时间片和采用不同的调度方法
    • 存在问题1:没法区分I/O bound和CPU bound;
    • 存在问题2:也存在一定程度的“饥饿”现象;
  6. 多级反馈队列
    • 在多级队列的基础上,任务可以在队列之间移动,更细致的区分任务。
    • 可以根据“享用”CPU时间多少来移动队列,阻止“饥饿”。
    • 最通用的调度算法,多数OS都使用该方法或其变形,如UNIX、Windows等。

进程同步

临界资源与临界区

在操作系统中,进程是占有资源的最小单位(线程可以访问其所在进程内的所有资源,但线程本身并不占有资源或仅仅占有一点必须资源)。但对于某些资源来说,其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机,或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护,那么很有可能造成丢数据的问题)。

对于临界资源的访问,必须是互斥进行。也就是当临界资源被占用时,另一个申请临界资源的进程会被阻塞,直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。

对于临界区的访问过程分为四个部分:

  1. 进入区:查看临界区是否可访问,如果可以访问,则转到步骤二,否则进程会被阻塞
  2. 临界区:在临界区做操作
  3. 退出区:清除临界区被占用的标志
  4. 剩余区:进程与临界区不相关部分的代码

解决临界区问题可能的方法:

  1. 一般软件方法
  2. 关中断方法
  3. 硬件原子指令方法
  4. 信号量方法

线程

线程,有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元。一个标准的线程由线程ID,当前指令指针(PC),寄存器集合和堆栈组成。

线程具有以下属性:

  1. 轻型实体 线程中的实体基本上不拥有系统资源,只是有一点必不可少的、能保证独立运行的资源。线程的实体包括程序、数据和TCB。线程是动态概念,它的动态特性由线程控制块TCB(Thread Control Block)描述。TCB包括以下信息:
    • 线程状态。
    • 当线程不运行时,被保存的现场资源。
    • 一组执行堆栈。
    • 存放每个线程的局部变量主存区。
    • 访问同一个进程中的主存和其它资源。
    • 用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。
  2. 独立调度和分派的基本单位。
    • 在多线程OS中,线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位。由于线程很“轻”,故线程的切换非常迅速且开销小(在同一进程中的)。
  3. 可并发执行。 在一个进程中的多个线程之间,可以并发执行,甚至允许在一个进程中所有线程都能并发执行;同样,不同进程中的线程也能并发执行,充分利用和发挥了处理机与外围设备并行工作的能力。
  4. 共享进程资源。 在同一进程中的各个线程,都可以共享该进程所拥有的资源,这首先表现在:所有线程都具有相同的地址空间(进程的地址空间),这意味着,线程可以访问该地址空间的每一个虚地址;此外,还可以访问进程所拥有的已打开文件、定时器、信号量机构等。由于同一个进程内的线程共享内存和文件,所以线程之间互相通信不必调用内核。 线程共享的环境包括:进程代码段、进程的公有数据(利用这些共享的数据,线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

协程

协程,又称微线程,纤程。英文名Coroutine。

协程可以理解为用户级线程,协程和线程的区别是:线程是抢占式的调度,而协程是协同式的调度,协程避免了无意义的调度,由此可以提高性能,但也因此,程序员必须自己承担调度的责任,同时,协程也失去了标准线程使用多CPU的能力。

使用协程改写生产者-消费者问题:

import time
def consumer():
r = ''
while True:
n = yield r
if not n:
return
print('[CONSUMER] Consuming %s...' % n)
time.sleep(1)
r = '200 OK'
def produce(c):
c.next()
n = 0
while n < 5:
n = n + 1
print('[PRODUCER] Producing %s...' % n)
r = c.send(n)
print('[PRODUCER] Consumer return: %s' % r)
c.close()
if __name__=='__main__':
c = consumer()
produce(c)

可以看到,使用协程不再需要显式地对锁进行操作

进程 vs. 线程

进程(process)与线程(thread)最大的区别是进程拥有自己的地址空间,某进程内的线程对于其他进程不可见,即进程A不能通过传地址的方式直接读写进程B的存储区域。进程之间的通信需要通过进程间通信(Inter-process communication,IPC)。与之相对的,同一进程的各线程间之间可以直接通过传递地址或全局变量的方式传递信息。

此外,进程作为操作系统中拥有资源和独立调度的基本单位,可以拥有多个线程。通常操作系统中运行的一个程序就对应一个进程。在同一进程中,线程的切换不会引起进程切换。在不同进程中进行线程切换,如从一个进程内的线程切换到另一个进程中的线程时,会引起进程切换。相比进程切换,线程切换的开销要小很多。线程于进程相互结合能够提高系统的运行效率。

线程可以分为两类:

一类是用户级线程(user level thread)。对于这类线程,有关线程管理的所有工作都由应用程序完成,内核意识不到线程的存在。在应用程序启动后,操作系统分配给该程序一个进程号,以及其对应的内存空间等资源。应用程序通常先在一个线程中运行,该线程被成为主线“程。在其运行的某个时刻,可以通过调用线程库中的函数创建一个在相同进程中运行的新线程。 用户级线程的好处是非常高效,不需要进入内核空间,但并发效率不高。

另一类是内核级线程(kernel level thread)。对于这类线程,有关线程管理的所有工作由内核完成,应用程序没有进行线程管理的代码,只能调用内核线程的接口。内核维护进程及其内部的每个线程,调度也由内核基于线程架构完成。内核级线程的好处是,内核可以将不同线程更好地分配到不同的CPU,以实现真正的并行计算。

事实上,在现代操作系统中,往往使用组合方式实现多线程,即线程创建完全在用户空间中完成,并且一个应用程序中的多个用户级线程被映射到一些内核级线程上,相当于是一种折中方案。

上下文切换

对于单核单线程CPU而言,在某一时刻只能执行一条CPU指令。上下文切换(Context Switch)是一种将CPU资源从一个进程分配给另一个进程的机制。从用户角度看,计算机能够并行运行多个进程,这恰恰是操作系统通过快速上下文切换造成的结果。在切换的过程中,操作系统需要先存储当前进程的状态(包括内存空间的指针,当前执行完的指令等等),再读入下一个进程的状态,然后执行此进程。

系统调用

系统调用(System call)是程序向系统内核请求服务的方式。可以包括硬件相关的服务(例如,访问硬盘等),或者创建新进程,调度其他进程等。系统调用是程序和操作系统之间的重要接口。

在讲系统调用之前,先说下进程的执行在系统上的两个级别:用户级和核心级,也称为用户态和系统态(user mode and kernel mode)。

程序的执行一般是在用户态下执行的,但当程序需要使用操作系统提供的服务时,比如说打开某一设备、创建文件、读写文件等,就需要向操作系统发出调用服务的请求,这就是系统调用。

Linux系统有专门的函数库来提供这些请求操作系统服务的入口,这个函数库中包含了操作系统所提供的对外服务的接口。当进程发出系统调用之后,它所处的运行状态就会由用户态变成核心态。但这个时候,进程本身其实并没有做什么事情,这个时候是由内核在做相应的操作,去完成进程所提出的这些请求。

系统调用和中断的关系就在于,当进程发出系统调用申请的时候,会产生一个软件中断。产生这个软件中断以后,系统会去对这个软中断进行处理,这个时候进程就处于核心态了。

那么用户态和核心态之间的区别是什么呢?(以下区别摘至《UNIX操作系统设计》)

  1. 用户态的进程能存取它们自己的指令和数据,但不能存取内核指令和数据(或其他进程的指令和数据)。然而,核心态下的进程能够存取内核和用户地址
  2. 某些机器指令是特权指令,在用户态下执行特权指令会引起错误

对此要理解的一个是,在系统中内核并不是作为一个与用户进程平行的估计的进程的集合,内核是为用户进程运行的。

Semaphore/Mutex

当用户创立多个线程/进程时,如果不同线程/进程同时读写相同的内容,则可能造成读写错误,或者数据不一致。此时,需要通过加锁的方式,控制核心区域(critical section)的访问权限。对于semaphore而言,在初始化变量的时候可以控制允许多少个线程/进程同时访问一个critical section,其他的线程/进程会被堵塞,直到有人解锁。

Mutex相当于只允许一个线程/进程访问的semaphore。此外,根据实际需要,人们还实现了一种读写锁(read-write lock),它允许同时存在多个阅读者(reader),但任何时候至多只有一个写者(writer),且不能于读者共存。

信号量是一个确定的二元组(s,q),其中s是一个具有非负初值的整形变量,q是一个初始状态为空的队列,整形变量s表示系统中某类资源的数目:

  • 当其值 ≥ 0 时,表示系统中当前可用资源的数目
  • 当其值 < 0 时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目

除信号量的初值外,信号量的值仅能由P操作和V操作更改,操作系统利用它的状态对进程和资源进行管理

P操作

P 操作记为P(s),其中s为一信号量,它执行时主要完成以下动作:

s.value = s.value - 1;  /*可理解为占用1个资源,若原来就没有则记帐“欠”1个*/

若s.value ≥ 0,则进程继续执行,否则(即s.value < 0),则进程被阻塞,并将该进程插入到信号量s的等待队列s.queue中

说明:实际上,P操作可以理解为分配资源的计数器,或是使进程处于等待状态的控制指令

V操作

V 操作记为V(s),其中s为一信号量,它执行时,主要完成以下动作:

s.value = s.value + 1;/*可理解为归还1个资源,若原来就没有则意义是用此资源还1个欠帐*/

若s.value > 0,则进程继续执行,否则(即s.value ≤ 0),则从信号量s的等待队s.queue中移出第一个进程,使其变为就绪状态,然后返回原进程继续执行

说明:实际上,V操作可以理解为归还资源的计数器,或是唤醒进程使其处于就绪状态的控制指令

信号量方法实现:生产者 − 消费者互斥与同步控制

semaphore fullBuffers = 0; /*仓库中已填满的货架个数*/
semaphore emptyBuffers = BUFFER_SIZE;/*仓库货架空闲个数*/
semaphore mutex = 1; /*生产-消费互斥信号*/
Producer()
{
while(True)
{
/*生产产品item*/
emptyBuffers.P();
mutex.P();
/*item存入仓库buffer*/
mutex.V();
fullBuffers.V();
}
}
Consumer()
{
while(True)
{
fullBuffers.P();
mutex.P();
/*从仓库buffer中取产品item*/
mutex.V();
emptyBuffers.V();
/*消费产品item*/
}
}

使用pthread实现的生产者-消费者模型:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define BUFFER_SIZE 10
static int buffer[BUFFER_SIZE] = { 0 };
static int count = 0;
pthread_t consumer, producer;
pthread_cond_t cond_producer, cond_consumer;
pthread_mutex_t mutex;
void* consume(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == 0){
printf("empty buffer, wait producer\n");
pthread_cond_wait(&cond_consumer, &mutex);
}
count--;
printf("consume a item\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_producer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
void* produce(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == BUFFER_SIZE){
printf("full buffer, wait consumer\n");
pthread_cond_wait(&cond_producer, &mutex);
}
count++;
printf("produce a item.\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_consumer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_consumer, NULL);
pthread_cond_init(&cond_producer, NULL);
int err = pthread_create(&consumer, NULL, consume, (void*)NULL);
if(err != 0){
printf("consumer thread created failed\n");
exit(1);
}
err = pthread_create(&producer, NULL, produce, (void*)NULL);
if(err != 0){
printf("producer thread created failed\n");
exit(1);
}
pthread_join(producer, NULL);
pthread_join(consumer, NULL);
//sleep(1000);
pthread_cond_destroy(&cond_consumer);
pthread_cond_destroy(&cond_producer);
pthread_mutex_destroy(&mutex);
return 0;
}

死锁

在引入锁的同时,我们遇到了一个新的问题:死锁(Deadlock)。死锁是指两个或多个线程/进程之间相互阻塞,以至于任何一个都不能继续运行,因此也不能解锁其他线程/进程。例如,线程A占有lock A,并且尝试获取lock B;而线程2占有lock B,尝试获取lock A。此时,两者相互阻塞,都无法继续运行。

总结产生死锁的四个条件(只有当四个条件同时满足时才会产生死锁):

  1. Mutual Exclusion – Only one process may use a resource at a time
  2. Hold-and-Wait – Process holds resource while waiting for another
  3. No Preemption – Can’t take a resource away from a process
  4. Circular Wait – The waiting processes form a cycle

生产者消费者

生产者消费者模型是一种常见的通信模型:生产者和消费者共享一个数据管道,生产者将数据写入buffer,消费者从另一头读取数据。对于数据管道,需要考虑为空和溢出的情况。同时,通常还需要将这部分共享内存用mutex加锁。在只有一个生产者一个消费者的情况下,可以设计无锁队列(lockless queue),线程安全地直接读写数据。

进程间通信

本地进程间通信的方式有很多,可以总结为下面四类:

  • 消息传递(管道、FIFO、消息队列)
  • 同步(互斥量、条件变量、读写锁、文件和写记录锁、信号量)
  • 共享内存(匿名的和具名的)
  • 远程过程调用(Solaris门和Sun RPC)

在介绍进程的时候,我们提起过一个进程不能直接读写另一个进程的数据,两者之间的通信需要通过进程间通信(inter-process communication, IPC)进行。进程通信的方式通常遵从生产者消费者模型,需要实现数据交换和同步两大功能。

1) Shared-memory + semaphore

不同进程通过读写操作系统中特殊的共享内存进行数据交换,进程之间用semaphore实现同步。

2) Message passing

进程在操作系统内部注册一个port,并且监测有没有数据,其他进程直接写数据到该port。该通信方式更加接近于网络通信方式。事实上,网络通信也是一种IPC,只是进程分布在不同机器上而已。

逻辑地址/物理地址/虚拟内存

所谓的逻辑地址,是指计算机用户(例如程序开发者),看到的地址。例如,当创建一个长度为100的整型数组时,操作系统返回一个逻辑上的连续空间:指针指向数组第一个元素的内存地址。由于整型元素的大小为4个字节,故第二个元素的地址时起始地址加4,以此类推。事实上,逻辑地址并不一定是元素存储的真实地址,即数组元素的物理地址(在内存条中所处的位置),并非是连续的,只是操作系统通过地址映射,将逻辑地址映射成连续的,这样更符合人们的直观思维。

另一个重要概念是虚拟内存。操作系统读写内存的速度可以比读写磁盘的速度快几个量级。但是,内存价格也相对较高,不能大规模扩展。于是,操作系统可以通过将部分不太常用的数据移出内存,“存放到价格相对较低的磁盘缓存,以实现内存扩展。操作系统还可以通过算法预测哪部分存储到磁盘缓存的数据需要进行读写,提前把这部分数据读回内存。虚拟内存空间相对磁盘而言要小很多,因此,即使搜索虚拟内存空间也比直接搜索磁盘要快。唯一慢于磁盘的可能是,内存、虚拟内存中都没有所需要的数据,最终还需要从硬盘中直接读取。这就是为什么内存和虚拟内存中需要存储会被重复读写的数据,否则就失去了缓存的意义。

现代计算机中有一个专门的转译缓冲区(Translation Lookaside Buffer,TLB),用来实现虚拟地址到物理地址的快速转换。

与内存/虚拟内存相关的还有如下两个概念:

1) Resident Set

当一个进程在运行的时候,操作系统不会一次性加载进程的所有数据到内存,只会加载一部分正在用,以及预期要用的数据。其他数据可能存储在虚拟内存,交换区和硬盘文件系统上。被加载到内存的部分就是resident set。

2) Thrashing

由于resident set包含预期要用的数据,理想情况下,进程运行过程中用到的数据都会逐步加载进resident set。但事实往往并非如此:每当需要的内存页面(page)不在resident set中时,操作系统必须从虚拟内存或硬盘中读数据,这个过程被称为内存页面错误(page faults)。当操作系统需要花费大量时间去处理页面错误的情况就是thrashing。

文件系统

Unix风格的文件系统利用树形结构管理文件。每个节点有多个指针,指向下一层节点或者文件的磁盘存储位置。文件节点还附有文件的操作信息(metadata),包括修改时间,访问权限等等。

用户的访问权限通过访问控制表(Access Control List)和能力表(Capability List)实现。前者从文件角度出发,标注了每个用户可以对该文件进行何种操作。后者从用户角度出发,标注了某用户可以以什么权限操作哪些文件。

Unix的文件权限分为读、写和执行,用户组分为文件拥有者,组和所有用户。可以通过命令对三组用户分别设置权限。

实时 vs.分时操作系统

操作系统可以分为实时操作系统(Real-time system),和分时操作系统(Sharing time system)。通常计算机采用的是sharing time,即多个进程/用户之间共享CPU,从形势上实现多任务。各个用户/进程之间的调度并非精准度特别高,如果一个进程被锁住,可以给它分配更多的时间。而实时操作系统则不同,软件和硬件必须遵从严格的deadline,超过时限的进程可能直接被终止。在这样的操作系统中,每次加锁都需要仔细考虑。

编译器

对于高级语言来说,代码需要通过编译才能够运行。编译通过编译器(compiler)实现,是一个将程序源代码转换成二进制机器码的过程。计算机可以直接执行二进制代码。在编译的过程中,编译器需要进行词法分析(lexical analysis),解析(parsing)和过渡代码生成(intermediate code generation)。编译器的好坏可以直接影响最终代码的执行效率。

中断

所谓的中断就是在计算机执行程序的过程中,由于出现了某些特殊事情,使得CPU暂停对程序的执行,转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类:

  1. 由计算机硬件异常或故障引起的中断,称为内部异常中断;
  2. 由程序中执行了引起中断的指令而造成的中断,称为软中断(这也是和我们将要说明的系统调用相关的中断);
  3. 由外部设备请求引起的中断,称为外部中断。简单来说,对中断的理解就是对一些特殊事情的处理。

与中断紧密相连的一个概念就是中断处理程序了。当中断发生的时候,系统需要去对中断进行处理,对这些中断的处理是由操作系统内核中的特定函数进行的,这些处理中断的特定的函数就是我们所说的中断处理程序了。

另一个与中断紧密相连的概念就是中断的优先级。中断的优先级说明的是当一个中断正在被处理的时候,处理器能接受的中断的级别。中断的优先级也表明了中断需要被处理的紧急程度。每个中断都有一个对应的优先级,当处理器在处理某一中断的时候,只有比这个中断优先级高的中断可以被处理器接受并且被处理。优先级比这个当前正在被处理的中断优先级要低的中断将会被忽略。

典型的中断优先级如下所示:

机器错误 > 时钟 > 磁盘 > 网络设备 > 终端 > 软件中断

当发生软件中断时,其他所有的中断都可能发生并被处理;但当发生磁盘中断时,就只有时钟中断和机器错误中断能被处理了。

系统调用

在讲系统调用之前,先说下进程的执行在系统上的两个级别:用户级和核心级,也称为用户态和系统态(user mode and kernel mode)。

程序的执行一般是在用户态下执行的,但当程序需要使用操作系统提供的服务时,比如说打开某一设备、创建文件、读写文件等,就需要向操作系统发出调用服务的请求,这就是系统调用。

Linux系统有专门的函数库来提供这些请求操作系统服务的入口,这个函数库中包含了操作系统所提供的对外服务的接口。当进程发出系统调用之后,它所处的运行状态就会由用户态变成核心态。但这个时候,进程本身其实并没有做什么事情,这个时候是由内核在做相应的操作,去完成进程所提出的这些请求。

系统调用和中断的关系就在于,当进程发出系统调用申请的时候,会产生一个软件中断。产生这个软件中断以后,系统会去对这个软中断进行处理,这个时候进程就处于核心态了。

那么用户态和核心态之间的区别是什么呢?(以下区别摘至《UNIX操作系统设计》)

  1. 用户态的进程能存取它们自己的指令和数据,但不能存取内核指令和数据(或其他进程的指令和数据)。然而,核心态下的进程能够存取内核和用户地址
  2. 某些机器指令是特权指令,在用户态下执行特权指令会引起错误

对此要理解的一个是,在系统中内核并不是作为一个与用户进程平行的估计的进程的集合,内核是为用户进程运行的。

IO多路复用

基本概念

IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取,它就通知该进程。IO多路复用适用如下场合:

  1. 当客户处理多个描述字时(一般是交互式输入和网络套接口),必须使用I/O复用。
  2. 当一个客户同时处理多个套接口时,而这种情况是可能的,但很少出现。
  3. 如果一个TCP服务器既要处理监听套接口,又要处理已连接套接口,一般也要用到I/O复用。
  4. 如果一个服务器即要处理TCP,又要处理UDP,一般要使用I/O复用。
  5. 如果一个服务器要处理多个服务或多个协议,一般要使用I/O复用。

与多进程和多线程技术相比,I/O多路复用技术的最大优势是系统开销小,系统不必创建进程/线程,也不必维护这些进程/线程,从而大大减小了系统的开销。

常见的IO复用实现

select(Linux/Windows/BSD Unix), epoll(Linux),kqueue(BSD/Mac OS X)

内存分配

  • 虚拟地址:用户编程时将代码(或数据)分成若干个段,每条代码或每个数据的地址由段名称 + 段内相对地址构成,这样的程序地址称为虚拟地址
  • 逻辑地址:虚拟地址中,段内相对地址部分称为逻辑地址
  • 物理地址:实际物理内存中所看到的存储地址称为物理地址
  • 逻辑地址空间:在实际应用中,将虚拟地址和逻辑地址经常不加区分,通称为逻辑地址。逻辑地址的集合称为逻辑地址空间
  • 线性地址空间:CPU地址总线可以访问的所有地址集合称为线性地址空间
  • 物理地址空间:实际存在的可访问的物理内存地址集合称为物理地址空间
  • MMU(Memery Management Unit内存管理单元):实现将用户程序的虚拟地址(逻辑地址) → 物理地址映射的CPU中的硬件电路
  • 基地址:在进行地址映射时,经常以段或页为单位并以其最小地址(即起始地址)为基值来进行计算
  • 偏移量:在以段或页为单位进行地址映射时,相对于基地址的地址值

虚拟地址先经过分段机制映射到线性地址,然后线性地址通过分页机制映射到物理地址。

虚拟内存

请求调页,也称按需调页,即对不在内存中的“页”,当进程执行时要用时才调入,否则有可能到程序结束时也不会调入

页面置换算法

  • FIFO算法
    • 先入先出,即淘汰最早调入的页面。
  • OPT(MIN)算法
    • 选未来最远将使用的页淘汰,是一种最优的方案,可以证明缺页数最小。
    • 可惜,MIN需要知道将来发生的事,只能在理论中存在,实际不可应用。
  • LRU(Least-Recently-Used)算法
    • 用过去的历史预测将来,选最近最长时间没有使用的页淘汰(也称最近最少使用)。
    • LRU准确实现:计数器法,页码栈法。
    • 由于代价较高,通常不使用准确实现,而是采用近似实现,例如Clock算法。

内存抖动现象:页面的频繁更换,导致整个系统效率急剧下降,这个现象称为内存抖动(或颠簸)。抖动一般是内存分配算法不好,内存太小引或者程序的算法不佳引起的。

Belady现象:对有的页面置换算法,页错误率可能会随着分配帧数增加而增加。

FIFO会产生Belady异常。

栈式算法无Belady异常,LRU,LFU(最不经常使用),OPT都属于栈式算法。

磁盘调度

磁盘访问延迟 = 队列时间 + 控制器时间 + 寻道时间 + 旋转时间 + 传输时间

磁盘调度的目的是减小延迟,其中前两项可以忽略,寻道时间是主要矛盾。

磁盘调度算法

  • FCFS
    • 先进先出的调度策略,这个策略具有公平的优点,因为每个请求都会得到处理,并且是按照接收到的顺序进行处理。
  • SSTF(Shortest-seek-time First 最短寻道时间优先)
    • 选择使磁头从当前位置开始移动最少的磁盘I/O请求,所以 SSTF 总是选择导致最小寻道时间的请求。
    • 总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比 FCFS 算法更好的性能,会存在饥饿现象。
  • SCAN
    • SSTF+中途不回折,每个请求都有处理机会。
    • SCAN 要求磁头仅仅沿一个方向移动,并在途中满足所有未完成的请求,直到它到达这个方向上的最后一个磁道,或者在这个方向上没有其他请求为止。
    • 由于磁头移动规律与电梯运行相似,SCAN 也被称为电梯算法。
    • SCAN 算法对最近扫描过的区域不公平,因此,它在访问局部性方面不如 FCFS 算法和 SSTF 算法好。
  • C-SCAN
    • SCAN+直接移到另一端,两端请求都能很快处理。
    • 把扫描限定在一个方向,当访问到某个方向的最后一个磁道时,磁道返回磁盘相反方向磁道的末端,并再次开始扫描。
    • 其中“C”是Circular(环)的意思。
  • LOOK 和 C-LOOK
    • 釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端,显然,在实际使用时还可以改进,即磁头移动只需要到达最远端的一个请求即可返回,不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求。

分区表

  • MBR:支持最大卷为2 TB(Terabytes)并且每个磁盘最多有4个主分区(或3个主分区,1个扩展分区和无限制的逻辑驱动器)
  • GPT:支持最大卷为18EB(Exabytes)并且每磁盘的分区数没有上限,只受到操作系统限制(由于分区表本身需要占用一定空间,最初规划硬盘分区时,留给分区表的空间决定了最多可以有多少个分区,IA-64版Windows限制最多有128个分区,这也是EFI标准规定的分区表的最小尺寸。另外,GPT分区磁盘有备份分区表来提高分区数据结构的完整性。

RAID 技术

磁盘阵列(Redundant Arrays of Independent Disks,RAID),独立冗余磁盘阵列之。原理是利用数组方式来作磁盘组,配合数据分散排列的设计,提升数据的安全性。

  • RAID 0
    • RAID 0是最早出现的RAID模式,需要2块以上的硬盘,可以提高整个磁盘的性能和吞吐量。
    • RAID 0没有提供冗余或错误修复能力,其中一块硬盘损坏,所有数据将遗失。
  • RAID 1
    • RAID 1就是镜像,其原理为在主硬盘上存放数据的同时也在镜像硬盘上写一样的数据。
    • 当主硬盘(物理)损坏时,镜像硬盘则代替主硬盘的工作。因为有镜像硬盘做数据备份,所以RAID 1的数据安全性在所有的RAID级别上来说是最好的。
    • 但无论用多少磁盘做RAID 1,仅算一个磁盘的容量,是所有RAID中磁盘利用率最低的。
  • RAID 2
    • 这是RAID 0的改良版,以汉明码(Hamming Code)的方式将数据进行编码后分区为独立的比特,并将数据分别写入硬盘中。因为在数据中加入了错误修正码(ECC,Error Correction Code),所以数据整体的容量会比原始数据大一些,RAID2最少要三台磁盘驱动器方能运作。
  • RAID 3
    • 采用Bit-interleaving(数据交错存储)技术,它需要通过编码再将数据比特分割后分别存在硬盘中,而将同比特检查后单独存在一个硬盘中,但由于数据内的比特分散在不同的硬盘上,因此就算要读取一小段数据资料都可能需要所有的硬盘进行工作,所以这种规格比较适于读取大量数据时使用。
  • RAID 4
    • 它与RAID 3不同的是它在分区时是以区块为单位分别存在硬盘中,但每次的数据访问都必须从同比特检查的那个硬盘中取出对应的同比特数据进行核对,由于过于频繁的使用,所以对硬盘的损耗可能会提高。(块交织技术,Block interleaving)

RAID 2/3/4 在实际应用中很少使用

  • RAID 5
    • RAID Level 5是一种储存性能、数据安全和存储成本兼顾的存储解决方案。它使用的是Disk Striping(硬盘分区)技术。
    • RAID 5至少需要三块硬盘,RAID 5不是对存储的数据进行备份,而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上,并且奇偶校验信息和相对应的数据分别存储于不同的磁盘上。
    • RAID 5 允许一块硬盘损坏。
    • 实际容量 Size = (N-1) * min(S1, S2, S3 … SN)
  • RAID 6
    • 与RAID 5相比,RAID 6增加第二个独立的奇偶校验信息块。两个独立的奇偶系统使用不同的算法,数据的可靠性非常高,即使两块磁盘同时失效也不会影响数据的使用。
    • RAID 6 至少需要4块硬盘。
    • 实际容量 Size = (N-2) * min(S1, S2, S3 … SN)
  • RAID 10/01(RAID 1+0,RAID 0+1)
    • RAID 10是先镜射再分区数据,再将所有硬盘分为两组,视为是RAID 0的最低组合,然后将这两组各自视为RAID 1运作。
    • RAID 01则是跟RAID 10的程序相反,是先分区再将数据镜射到两组硬盘。它将所有的硬盘分为两组,变成RAID 1的最低组合,而将两组硬盘各自视为RAID 0运作。
    • 当RAID 10有一个硬盘受损,其余硬盘会继续运作。RAID 01只要有一个硬盘受损,同组RAID 0的所有硬盘都会停止运作,只剩下其他组的硬盘运作,可靠性较低。如果以六个硬盘建RAID 01,镜射再用三个建RAID 0,那么坏一个硬盘便会有三个硬盘脱机。因此,RAID 10远较RAID 01常用,零售主板绝大部份支持RAID 0/1/5/10,但不支持RAID 01。
    • RAID 10 至少需要4块硬盘,且硬盘数量必须为偶数。

常见文件系统

  • Windows: FAT, FAT16, FAT32, NTFS
  • Linux: ext2/3/4, btrfs, ZFS
  • Mac OS X: HFS+

Linux文件权限

Linux文件采用10个标志位来表示文件权限,如下所示:

-rw-r--r--  1 skyline  staff    20B  1 27 10:34 1.txt
drwxr-xr-x   5 skyline  staff   170B 12 23 19:01 ABTableViewCell

第一个字符一般用来区分文件和目录,其中:

  • d:表示是一个目录,事实上在ext2fs中,目录是一个特殊的文件。
  • -:表示这是一个普通的文件。
  • l: 表示这是一个符号链接文件,实际上它指向另一个文件。
  • b、c:分别表示区块设备和其他的外围设备,是特殊类型的文件。
  • s、p:这些文件关系到系统的数据结构和管道,通常很少见到。

第2~10个字符当中的每3个为一组,左边三个字符表示所有者权限,中间3个字符表示与所有者同一组的用户的权限,右边3个字符是其他用户的权限。

这三个一组共9个字符,代表的意义如下:

  • r(Read,读取):对文件而言,具有读取文件内容的权限;对目录来说,具有浏览目录的权限
  • w(Write,写入):对文件而言,具有新增、修改文件内容的权限;对目录来说,具有删除、移动目录内文件的权限。
  • x(eXecute,执行):对文件而言,具有执行文件的权限;对目录来说该用户具有进入目录的权限。

权限的掩码可以使用十进制数字表示:

  • 如果可读,权限是二进制的100,十进制是4;
  • 如果可写,权限是二进制的010,十进制是2;
  • 如果可运行,权限是二进制的001,十进制是1;

具备多个权限,就把相应的 4、2、1 相加就可以了:

若要 rwx 则 4+2+1=7 若要 rw- 则 4+2=6 若要 r-x 则 4+1=5 若要 r-- 则 =4 若要 -wx 则 2+1=3 若要 -w- 则 =2 若要 --x 则 =1 若要 --- 则 =0

默认的权限可用umask命令修改,用法非常简单,只需执行umask 777命令,便代表屏蔽所有的权限,因而之后建立的文件或目录,其权限都变成000,

依次类推。通常root帐号搭配umask命令的数值为022、027和 077,普通用户则是采用002,这样所产生的权限依次为755、750、700、775。

chmod命令

chmod命令非常重要,用于改变文件或目录的访问权限。用户用它控制文件或目录的访问权限。

该命令有两种用法。一种是包含字母和操作符表达式的文字设定法;另一种是包含数字的数字设定法。

  1. 文字设定法
    • chmod [who] [+ | - | =] [mode] 文件名
    • 命令中各选项的含义为:
    • 操作对象who可是下述字母中的任一个或者它们的组合:
      • u 表示“用户(user)”,即文件或目录的所有者。
      • g 表示“同组(group)用户”,即与文件属主有相同组ID的所有用户。
      • o 表示“其他(others)用户”。
      • a 表示“所有(all)用户”。它是系统默认值。
    • 操作符号可以是:
      • 添加某个权限。
      • 取消某个权限。
      • = 赋予给定权限并取消其他所有权限(如果有的话)。
    • 设置mode所表示的权限可用下述字母的任意组合:
      • r 可读。
      • w 可写。
      • x 可执行。
      • X 只有目标文件对某些用户是可执行的或该目标文件是目录时才追加x 属性。
      • s 在文件执行时把进程的属主或组ID置为该文件的文件属主。方式“u+s”设置文件的用户ID位,“g+s”设置组ID位。
      • t 保存程序的文本到交换设备上。
      • u 与文件属主拥有一样的权限。
      • g 与和文件属主同组的用户拥有一样的权限。
      • o 与其他用户拥有一样的权限。
    • 文件名:以空格分开的要改变权限的文件列表,支持通配符。
    • 在一个命令行中可给出多个权限方式,其间用逗号隔开。例如:chmod g+r,o+r example 使同组和其他用户对文件example 有读权限。
  2. 数字设定法
    • 直接使用数字表示的权限来更改:
    • 例: $ chmod 644 mm.txt

chgrp命令

  • 功能:改变文件或目录所属的组。
  • 语法:chgrp [选项] group filename
  • 例:$ chgrp - R book /opt/local /book
  • 改变/opt/local /book/及其子目录下的所有文件的属组为book。

chown命令

  • 功能:更改某个文件或目录的属主和属组。这个命令也很常用。例如root用户把自己的一个文件拷贝给用户xu,为了让用户xu能够存取这个文件,root用户应该把这个文件的属主设为xu,否则,用户xu无法存取这个文件。
  • 语法:chown [选项] 用户或组 文件
  • 说明:chown将指定文件的拥有者改为指定的用户或组。用户可以是用户名或用户ID。组可以是组名或组ID。文件是以空格分开的要改变权限的文件列表,支持通配符。
  • 例:把文件shiyan.c的所有者改为wang。
  • chown wang shiyan.c

附录

捧个钱场?