面试

整理一些经典问题

包括数据结构和算法、网络、iOS等

Posted by renchao on July 18, 2017

整理一些经典问题

[TOC]

数据结构与算法

栈和队列的应用

函数调用 递归调用 断点实现 符号匹配 计算代数式 CPU的资源分配等

海量数据查找top

对于100w个数据求几个数，其实总量也就是4*1000000 = 4M，直接堆排序就可以。如下面的例题：

    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录， 这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。 
（1）请描述你解决这个问题的思路； 
（2）请给出主要的处理流程，算法，以及算法的复杂度。
    我们知道，数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢?比如这第2题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。So:
    1.hash统计：先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable，即Hashmap(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；
    2.堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。

更高数量级：

一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。
     1）hash映射：hash(单词) % 1000, 这样这些单词就分布在1000个小文件中
     2）hash统计：用hashmap或者trie树进行统计，找出每个小文件中的最常出现的10个词
     3）堆排序：用第一个文件的10个最常出现词构建小根堆，然后依次读入剩下999个文件的最常出现单词，调整对，最后将得到总体的最常出现词
动态规划和贪心算法的区别

这两种算法都是递推算法，都是通过局部最优解来推导出全局最优解。

贪心算法的思路是，从问题的某个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当到达某个算法的某一步不能再继续前进时，算法停止。该算法存在的问题在于，不能保证最后的解是最佳的，不能用来求得最大最小问题解问题，只能求满足某些约束条件的可行解的范围。最经典的例子就是给钱问题。每次都拿最大的，这就是贪心，但是贪心得到的不一定是最优解，不一定是张数最少的，只是一个比较好的，效率比较高的解。

不同之处在于，贪心算法做的每一步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不做保留。所以每一步的最优解一定包含上一步的最优解。贪心特殊在每个子树的根值不取决于下面叶子值，而只取决于当前问题的状态。也就是说，不需要知道每个节点的子树情况就可以求出这个节点的值，这个值通常都是当前情况下显而易见最优的。自根开始，选择最优的路一路走到底就可以。

但是动态规划中，全局最优解一定包含了局部最优解，但是不一定是上一步的局部最优解，所以需要记录之前所有最优解。关键在于如何由已求得的局部最优解来推导出全局最优解。与动态规划相比，贪心的代价只取决于子问题的数目，而选择数目总为1。动态规划的经典例子是最长公共子序列问题。

实现进程的互斥
  1. 临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
  2. 互斥量:为协调共同对一个共享资源的单独访问而设计的。
  3. 信号量:为控制一个具有有限数量用户资源而设计。
  4. 事 件:用来通知线程有一些事件已发生，从而启动后继任务的开始。

四大原则：忙则等待 空闲让进 有限等待 让权等待

计算机网络

TCP最大连接数

首先我们要知道如何表示一个连接，系统识别一个连接，用的是一个五元组（协议名、源IP、源端口、目的IP号、目的端口号）。

客户端最大TCP连接数：每次连接请求都要选取一个空闲的本地端口，该端口是独占的，不能和其他TCP连接共享，TCP端口号类型是unsigned short，因此本地端口个数最大是2^16=65535。

服务器最大TCP连接数：服务器是监听本地端口，等待客户端的连接请求。对端口也是独占的。因此最大连接数应该是客户端的IP数*客户端的端口数，即2^32*2^16=2^48。

实际的TCP连接数：上面给出的是理论上的单机最大连接数，在实际环境中，受到机器资源、操作系统等的限制，特别是sever端，其最大并发tcp连接数远不能达到理论上限。在unix/linux下限制连接数的主要因素是内存和允许的文件描述符个数（每个tcp连接都要占用一定内存，每个socket就是一个文件描述符），另外1024以下的端口通常为保留端口。对server端，通过增加内存、修改最大文件描述符个数等参数，单机最大并发TCP连接数超过10万,甚至上百万是没问题的。

TCP四个计时器

重传计时器

  • 目的：为了控制丢失的报文段或者丢弃的报文段。这段时间为对报文段的等待确认时间。
  • 创建时间：在TCP发送报文段时，会创建对次特定报文段的重传计时器。
  • 可能发生的两种情况：在截止时间（通常为60秒）到之前，已经收到了对此特定报文段的确认，则撤销计时器；在截止时间到了，但为收到对此特定报文段的确认，则重传报文段，并且将计时器复位。
  • 重传时间：2*RTT（Round Trip Time，为往返时间）这段时间为对报文段的等待确认时间。

坚持计时器

  • 目的：主要解决零窗口大小通知可能导致的死锁问题
  • 死锁问题的产生：当接收端的窗口大小为0时，接收端向发送端发送一个零窗口报文段，发送端即停止向对端发送数据。此后，如果接收端缓存区有空间则会重新给发送端发送一个窗口大小，即窗口更新。但接收端发送的这个确认报文段有可能会丢失，而此时接收端不知道已经丢失并认为自己已经发送成功，则一直处于等待数据的状态；而发送端由于没有收到该确认报文段，就会一直等待对方发来新的窗口大小，这样一来，双方都处在等待对方的状态，这样就形成了一种死锁问题。如果没有应对措施，这种局面是不会被打破的。为了解决这种问题，TCP为每一个连接设置了坚持计时器。
  • 工作原理：当发送端TCP收到接收端发来的零窗口通知时，就会启动坚持计时器。当计时器的期限到达时，发送端就会主动发送一个特殊的报文段告诉对方确认已经丢失，必须重新发送。【这个特殊的报文段就称为探测报文段，探测报文段只有1个字节的大小，里边只有一个序号，该序号不需要被确认，甚至在计算其他部分数据的确认时该序号会被忽略。】
  • 截止期的设置：设置为重传时间的值。但如果没有收到接收端的响应，则会发送另一个探测报文段，并将计时器的值加倍并复位，直到大于门限值（一般为60秒）。在此之后，发送端会每隔60秒发送一个探测报文段，直到窗口重新打开。

保活计时器

  • 目的：主要是为了防止两个TCP连接出现长时间的空闲。当客户端与服务器端建立TCP连接后，很长时间内客户端都没有向服务器端发送数据，此时很有可能是客户端出现故障，而服务器端会一直处于等待状态。保活计时器就是解决这种问题而生的。
  • 工作原理：每当服务器端收到客户端的数据时，都将保活计时器重新设置（通常设置为2小时）。过了2小时后，服务器端如果没有收到客户端的数据，会发送探测报文段给客户端，并且每隔75秒发送一个，当连续发送10次以后，仍没有收到对端的来信，则服务器端认为客户端出现故障，并会终止连接。

时间等待计时器(time-wait)

  • 时间等待计时器是在连接终止期间使用的。（MSL(Maximum Segment Lifetime)即报文段最大生存时间 ）
  • 当TCP关闭连接时并不是立即关闭的，在等待期间，连接还处于过渡状态。这样就可以使重复的FIN报文段在到达终点之后被丢弃。
  • 时间设置：一般为报文段寿命期望值的2倍。
HTTP几个常用的状态码
  • 200：成功接收请求，返回请求应答文档
  • 301：客户请求的文档在其他地方，新的URL在Location头中给出，浏览器应该自动地访问新的URL，对于搜索引擎来说，表示永久重定向，即告诉搜索引擎所访问的地址已经永久转移到指定的新URL
  • 302：此状态码类似于301，但新的URL应该被视为临时性的替代，而不是永久性的。所有网站运营中对于短暂性的URL转移可以使用302跳转这样会更好，起码可以保证搜索引擎不会立刻旧的URL地址过渡到新地址上
  • 304：表示客户端有缓冲的文档并发出了一个条件性的请求(一般是提供If-Modified-Since头表示客户只想比指定日期更新的文档)。服务器告诉客户，原来缓冲的文档还可以继续使用。例如SDWebImage中检验图片是否过期，检验If-Modified-Since和Last-Modified是否一致，或者E-Tag值和If-None-Match比较
  • 403：服务器已经识别了请求信息，但是或因为服务器的权限设置导致无法返回应答。
  • 404：即Not Found，无法找到指定位置的资源。对于网站中已经失效的页面请返回404状态码以使更友好于搜索引擎
  • 410：此表示所请求的文档已经不再可用，而且服务器不知道应该重定向到哪一个地址。它和404的不同在于，返回404表示文档永久地离开了指定的位置，而410表示由于未知的原因文档不可用
  • 500：服务器内部错误

iOS相关

category的意义和实现

意义就是可以在本类中直接添加方法而不用新建一个子类。团队协作的时候可以明确分工，不同的任务有不同的划分，便于合作、阅读和维护。AFN，SDW等就用到了分类。声明私有方法等。

但是缺点是无法添加成员变量，但可以通过runtime的关联方法实现。分类的方法具有更高响应优先级，所以可能导致原始类以及父类的方法得不到调用，可以通过runtime遍历同名方法，取最后的方法。

实现：其实实现主要在runtime源码的objc-runtime-new.mm文件下，有一个叫做read_images的方法，将category和主类或元类注册到哈希表中，如果主类或元类已经实现了，就重建方法列表。分两种情况：Category 中的实例方法和属性被整合到主类中；而类方法则被整合到元类中。另外，对协议的处理比较特殊，Category 中的协议被同时整合到了主类和元类中。在remethodizeClass方法里，将 Category 中的方法、属性和协议整合到类（主类或元类）中，更新类的数据字段 data() 中 method_lists（或 method_list）、properties 和 protocols 的值。进一步，我们通过 attachCategoryMethods 函数的源码可以找到真正处理 Category 方法的 attachMethodLists 函数：attachMethodLists。

它的主要作用就是将类中的旧有方法和 Category 中新添加的方法整合成一个新的方法列表，并赋值给 method_lists 或 method_list 。通过探究这个处理过程，我们也印证了一个结论，那就是主类中的方法和 Category 中的方法在 runtime 看来并没有区别，它们是被同等对待的，都保存在主类的方法列表中。

不过，类的方法列表字段有一点特殊，它的结构是联合体，method_lists 和 method_list 共用同一块内存地址。当 newCount 的个数大于 1 时，使用 method_lists 来保存 newLists ，并将方法列表的标志位置为 RW_METHOD_ARRAY ，此时类的方法列表字段是 method_list_t 类型的指针数组；否则，使用 method_list 来保存 newLists ，并将方法列表的标志位置空，此时类的方法列表字段是 method_list_t 类型的指针。

Tagged Pointer

2013年9月推出了首次搭载64架构A7双核处理器的5s。为了节省内存和提高效率，苹果提出了Tagged Pointer的概念。对于64位程序，引入Tagged Pointer后，相关逻辑能减少一半的内存占用，以及3倍的访问速度提升，100倍的创建、销毁速度提升。

我们先看看原有的对象为什么会浪费内存。假设我们要存储一个NSNumber对象，其值是一个整数。正常情况下，如果这个整数只是一个NSInteger的普通变量，那么它所占用的内存是与CPU的位数有关，在32位CPU下占4个字节，在64位CPU下是占8个字节的。而指针类型的大小通常也是与CPU位数相关，一个指针所占用的内存在32位CPU下为4个字节，在64位CPU下也是8个字节。所以一个普通的iOS程序，如果没有Tagged Pointer对象，从32位机器迁移到64位机器中后，虽然逻辑没有任何变化，但这种NSNumber、NSDate一类的对象所占用的内存会翻倍。

我们再来看看效率上的问题，为了存储和访问一个NSNumber对象，我们需要在堆上为其分配内存，另外还要维护它的引用计数，管理它的生命期。这些都给程序增加了额外的逻辑，造成运行效率上的损失。

为了改进上面提到的内存占用和效率问题，苹果提出了Tagged Pointer对象。由于NSNumber、NSDate一类的变量本身的值需要占用的内存大小常常不需要8个字节，拿整数来说，4个字节所能表示的有符号整数就可以达到20多亿（注：2^31=2147483648，另外1位作为符号位)，对于绝大多数情况都是可以处理的。所以我们可以将一个对象的指针拆成两部分，一部分直接保存数据，另一部分作为特殊标记，表示这是一个特别的指针，不指向任何一个地址。所以，引入了Tagged Pointer对象之后，64位CPU下NSNumber的内存图变成了以下这样：

img

WWDC2013的《Session 404 Advanced in Objective-C》视频中，看到苹果对于Tagged Pointer特点的介绍：

  1. Tagged Pointer专门用来存储小的对象，例如NSNumber和NSDate
  2. Tagged Pointer指针的值不再是地址了，而是真正的值。所以，实际上它不再是一个对象了，它只是一个披着对象皮的普通变量而已。所以，它的内存并不存储在堆中，也不需要malloc和free。
  3. 在内存读取上有着3倍的效率，创建时比以前快106倍。

苹果将Tagged Pointer引入，给64位系统带来了内存的节省和运行效率的提高。Tagged Pointer通过在其最后一个bit位设置一个特殊标记，用于将数据直接保存在指针本身中。因为Tagged Pointer并不是真正的对象，我们在使用时需要注意不要直接访问其isa变量。

iOS常见加密方式

  1. base64加密

    base64 编码是现代密码学的基础。基本原理：原本是8个bit一组表示数据，改为6个bit一组表示数据，不足的部分补零,每两个0用一个=表示，用base64编码之后，数据长度会变大，增加了大约 1/3 左右。(8-6)/6可进行反向解密。Xcode7.0 之后出现的编码有个非常显著的特点，末尾有个=号。

    // 获取需要加密文件的二进制数据
NSData *data = [NSData dataWithContentsOfFile:@"/Users/wangpengfei/Desktop/photo/IMG_5551.jpg"];

// 或 base64EncodedStringWithOptions
NSData *base64Data = [data base64EncodedDataWithOptions:0];

// 将加密后的文件存储到桌面
[base64Data writeToFile:@"/Users/wangpengfei/Desktop/123" atomically:YES];

    // 获得加密后的二进制数据
NSData *base64Data = [NSData dataWithContentsOfFile:@"/Users/wangpengfei/Desktop/123"];

// 解密 base64 数据
NSData *baseData = [[NSData alloc] initWithBase64EncodedData:base64Data options:0];

// 写入桌面
[baseData writeToFile:@"/Users/wangpengfei/Desktop/IMG_5551.jpg" atomically:YES];

    // 将文件 meinv.jpg 进行 base64运算之后存储为 meinv.txt
base64 meinv.jpg -o meinv.txt

// 讲meinv.txt 解码生成 meinv.png
base64 -D meinv.txt -o meinv.png

// 将字符串 "hello" 进行 base 64 编码 结果:aGVsbG8=cho "hello" | base64

// 将 base64编码之后的结果 aGVsbG8= 反编码为字符串
echo aGVsbG8= | base64 -D

  2. NSUserDefaults

    NSUserDefaults *userDefaults = [NSUserDefaults standardUserDefaults];

[userDefaults setObject:self.userName.text forKey:kUserNameKey];

[[NSUserDefaults standardUserDefaults] removeObjectForKey:kUserNameKey];

  3. token值

    登录令牌，利用token值来判断用户的登录状态，类似于MD5加密之后的长文字串。用户登录成功之后，在服务器会根据用户的登录状态生成唯一的值，这个值就是token值。服务器会保存这个值，以后利用这个token值来检索对应的用户信息，并且判断用户的登录状态。用户登录成功之后，服务器会将生成的token值返回给客户端，在客户端也保存这个token值（一般保存在cookie中）。

    以后客户端再发送新的网络请求的时候，会默认自动附带这个token值。服务器会拿这个token值和保存在服务器本地的token值进行对比，以此来判断用户身份和登录状态。如果客户端没有这个token值，意味着没有登录成功过，提示用户登录。若客户端有这个token，一般会认为登录成功，不需要用户再次登录。

    token值会有失效时间，一般app失效时间为一年以上，特殊的app如银行类、支付类，token失效时间为15分钟左右。一旦用户信息改变，会在服务器生成新的token值，原来的token值就会失效，需要再次输入账号密码以生成新的token值。

    唯一性判断：每次登录，都会生成新的token值，原来的token值就会失效，利用时间来判断登陆的差异性。

  4. MD5加密

    把任意长度的字节串变换成一定长度的十六进制大整数。注意，转换的过程是不可逆的，不能通过加密后的结果得到原始内容。应用场合如一致性验证：数字签名、安全访问认证。

    特点：

    • 压缩性：任意长度的数据转换后都是固定的
    • 容易计算：从原始数据算出MD5值很容易
    • 抗修改性：对原数据有一字节的修改，值都不同
    • 弱抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪数据）是非常困难的
    • 强抗碰撞：想找到两个不同数据，是他们具有相同的MD5值，是非常困难的
    //利用 MD5 对字符串进行加密

  NSString *password = @"WangPengfei";

  password = [password md5String];

  NSLog(@"password1:%@", password);

//加盐:可以保证 MD5加密之后更加安全

  NSString *salt = @"234567890-!@#$%^&*()_+QWERTYUIOP{ASDFGHJKL:XCVBNM<>";

  [password stringByAppendingString:salt];

  password = [password md5String];

  NSLog(@"password2:%@", password);

  5. 时间戳密码

    动态密码：相同的密码明文+相同的加密算法–>因为每次登陆时间都不同,所以每次计算出的结果也都不相同.可以充分保证密码的安全性.服务器会计算两个时间值,当期时间和前一分钟的时间(比如:第59S发送的网络请求,一秒钟后服务器收到并作出响应,这时服务器当前时间比客户端发送时间晚一分钟，仍然能够判断准确的值)。

    //获取MD5 首次加密的密码

  // 1. 当前密码
  NSString *password = @"zhang";

  // 2. hmacKey值，是对“WangPengfei” 进行 MD5加密之后的值（动态生成的）
  NSString *hmacKey = @"d3bba33b51acaa0a272de7a2f6dfa233";

//加密过程

  // 1. 第一次加密：第一次 HMAC 运算
  password = [password hmacMD5StringWithKey:hmacKey];

  // 2.1 获得当前的时间
  NSDate *date = [NSDate date];

  // 2.2 获得当前时间的字符串
  // 实例化时间格式器
  NSDateFormatter *formatter = [[NSDateFormatter alloc] init];

  // 设置时间格式
  formatter.dateFormat = @"yyyy-MM-dd HH:mm";

  // 获取当前时间（要和服务器保持一致）
  NSString *dateStr = [formatter stringFromDate:date];

  // 3. 将第一次加密后的密码与当前时间的字符串拼接在一起
  password = [password stringByAppendingString:dateStr];

  // 4. 进行第二次 HMAC 加密
  password = [password hmacMD5StringWithKey:hmacKey];

  6. 钥匙串keychain

    苹果在 iOS 7.0.3版本以后公布钥匙串访问的SDK.钥匙串访问接口是纯C语言的.

    钥匙串使用 AES 256加密算法,能够保证用户密码的安全.

    钥匙串访问的第三方框架SSKeychain,是对C语言框架的封装.注意:不需要看源码.

    钥匙串访问的密码保存在哪里?只有苹果才知道.这样进一步保障了用户的密码安全.

操作系统

CPU取值步骤

CPU在执行进程指令时要取一个实际的物理地址的值主要有几步：

  1. 把进程指令使用的虚拟地址通过MMU（存储器管理单元）转换成物理地址
  2. 把物理地址映射到高速缓存的缓存行
  3. 如果高速缓存命中就返回
  4. 如果不命中，就产生一个缓存缺失中断，从主存相应的物理地址取值，并加载到高速缓存中。CPU从中断中恢复，继续执行中断前的指令
死锁

死锁：一个进程在执行过程中需要其他资源而陷入等待，但是其他资源的获取需要其他进程的执行，但是进程不能执行而导致都陷入了等待状态。

四个条件：互斥、请求和保持、不可抢占、循环等待。

处理方法：

  1. 预防死锁

    1. 破坏请求保持条件：在开始运行之前就申请到所有所需的资源，优点是简单易行安全，但是缺点是资源严重被浪费，进程容易出现饥饿现象。改进一下就是，允许一个进程只获得初期所需的资源就开始运行，逐步再释放资源请求资源。
    2. 破坏不可抢占条件：当一个已经保持了某些不可被强占资源的进程，提出新的资源请求而不得到满足时，必须释放保持的资源，需要时再重新申请。实现起来比较复杂而且需要付出很大代价。可能因为反复申请和释放资源而导致进程的执行被无限推迟。不仅延长了进程的周转时间，也增加了系统开销，降低系统的吞吐量。
    3. 破坏循环等待条件：将资源线性排序，按序号请求资源。如果某进程已经请求到高序号的资源，后来又想请求序号低的资源，那么就需要先释放所有具有相同序号或更高的资源才能申请低序号的资源。这样就不会出现环路。事实上总有一个进程占据较高序号的资源，此后它继续申请的资源必定是空闲的，所以进程可以一直推进。问题是：序号相对稳定，限制了新类型设备的增加；使用资源的顺序和系统规定的顺序不同，导致资源的浪费；限制用户自主编程。

  2. 避免死锁

    也是属于事先预防的策略，是在资源动态分配的过程中，防止系统进入不安全状态。

    使用银行家算法避免死锁。

  3. 检测死锁

    保持相关资源的请求和分配信息，提供某种算法检测是否死锁状态。

  4. 解除死锁：

    1. 从其他进程中抢占足够多的资源，分配给死锁进程。
    2. 终止或撤销死锁进程，直到打破环路。

    ​

页面置换算法

  1. 最佳置换算法：被淘汰页将是以后永不使用或最长时间内不再被访问的页面。

  2. 先进先出算法：总是淘汰最先进入的页面。

  3. 最近最久未使用算法（LRU）：选择最近最久未使用的页面淘汰。（时间）

  4. 最少使用算法（LFU）：选择最近时期使用最少的页面淘汰。（频率）

  5. Clock算法：为每页设置一位访问位，再将内存中所有页面都通过链接指针连接成一个循环队列，某页被访问时，置1，淘汰时，检查访问位，0则换出，1则置0。

  6. Clock改进：修改过的页面换出时代价较大，所以改进版不仅考虑使用情况，还要考虑是否被修改。

    未被访问+未被修改 = 最佳淘汰页

    未被访问+被修改 = 不是很好的淘汰页

    最近被访问+未被修改 = 可能再次被访问

    最基本访问+被修改 = 可能再被访问，几率更大

  7. 页面缓冲算法（PBA）：特点是降低页面换进换出的频率，内存分配策略上采用了可变分配和局部置换的方式，系统为每个进程分配一定数目的物理块，系统自己保留一部分空闲物理块。为了降低换进换出的频率，在内存中设置两个链表：

    1. 空闲页面链表：是一个空闲物理块链表，是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程，降低该进程的缺页率。当这样的进程需要读入一个页面时，可利用空闲物理块链表的第一个物理块来装入该页。当有一个为被修改过的页要换出时，实际上并不是换出到外存，而是把它们所在的物理块挂在空闲链表的末尾。注意：这些挂在空闲链表上的未被修改的页面中是有数据的，如果以后某进程需要这些页面数据，便可以从空闲链表中取下，免除从磁盘读取的操作，减少页面换出的开销。
    2. 修改页面链表：由已修改页面形成的链表，设置该链表的目的是减少已修改页面换出的次数。当今程序需要将一个页面换出时，并不直接换出到磁盘，而是将它所在物理块挂在修改页面链表的末尾，降低了已修改页面换出的频率。
磁盘调度算法
  1. FIFO：先来先服务算法；假设当前磁道在某一位置，依次处理服务队列里的每一个磁道，这样做的优点是处理起来比较简单，但缺点是磁头移动的距离和平均移动距离会很大。
  2. SSTF： 最短寻道时间算法；这种算法的本质是利用贪心算法来实现，假设当前磁道在某一位置，接下来处理的是距离当前磁道最近的磁道号，处理完成之后再处理离这个磁道号最近的磁道号，直到所有的磁道号都服务完了程序结束。这样做的优点是性能会优于FIFO算法，但是会产生距离当前磁道较远的磁道号长期得不到服务，也就是“饥饿”现象，因为要求访问的服务的序列号是动态产生的，即各个应用程序可能不断地提出访问不同的磁道号的请求。
  3. SCAN：电梯调度算法；先按照一个方向(比如从外向内扫描)，扫描的过程中依次访问要求服务的序列。当扫描到最里层的一个服务序列时反向扫描，这里要注意，假设最里层为0号磁道，最里面的一个要求服务的序列是5号，访问完5号之后，就反向了，不需要再往里扫。结合电梯过程更好理解，在电梯往下接人的时候，明知道最下面一层是没有人的，它是不会再往下走的。
  4. CSCAN： 循环扫描算法；来看一下上一种算法，有什么问题。仔细一看，我们会发现，在扫描到最里面的要求服务的序列时，接着会反向，在接下来的很大一部分时间里，应该是没有要求服务的磁道号的，因为之前已经访问过了。什么意思，就是说从初始磁道号到最里层的一个磁道号之间的所有序列都已经访问过了，所以SCAN会增加等待的时间。为了解决这样的情况，CSCAN算法的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。也就是始终保持一个方向。就像梳头发，从上往下梳，到了最下面之后，再一次的从上往下梳，这个顺序是不会变的。没有人会从下往上梳头发吧。
  5. FSCAN：分步电梯调度算法(分两个队列)，算法思想是，在扫描的过程中所有新产生的序列放在另外的一个队列中，当访问完当前队列之后，再访问新产生的一个队列。这种算法可以有效防止磁壁粘着现象。

数据库

范式

第一范式：如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF。第一范式就是每一个属性都不可再分，不符合第一范式则不能称为关系数据库。

第二范式：若关系模式R∈1NF，并且每一个非主属性都完全函数依赖于R的码，则R∈2NF。简单的说，是表中的属性必须完全依赖于全部主键，而不是部分主键.所以只有一个主键的表如果符合第一范式，那一定是第二范式。这样做的目的是进一步减少插入异常和更新异常。

第三范式：是为了消除数据库中关键字之间的依赖关系。

bc范式：是在第三范式的基础上的一种特殊情况，既每个表中只有一个候选键（在一个数据库中每行的值都不相同，则可称为候选键）。

第四范式：是消除表中的多值依赖，也就是说可以减少维护数据一致性的工作。

总结：

​ 上面对于数据库范式进行分解的过程中不难看出，应用的范式登记越高，则表越多。表多会带来很多问题：

  1. 查询时要连接多个表，增加了查询的复杂度

  2. 查询时需要连接多个表，降低了数据库查询性能

    而现在的情况，磁盘空间成本基本可以忽略不计，所以数据冗余所造成的问题也并不是应用数据库范式的理由。

因此，并不是应用的范式越高越好，要看实际情况而定。第三范式已经很大程度上减少了数据冗余，并且减少了造成插入异常，更新异常，和删除异常了。我个人观点认为，大多数情况应用到第三范式已经足够，在一定情况下第二范式也是可以的。

分享：数据库那些事

脏读 不可重复读 幻读

脏读：当一个事务正在访问数据，并对数据进行了修改，而这种修改还没有提交到数据库，这时，另外一个事务也访问了这个数据，然后使用了这个数据。

例如：1.小明原工资1000，财务人员或因操作失误将小明工资改成了8000，但是并未结束事务。

2.小明读取自己的工资，发现是8000，很开心。

3.财务发现操作有误，回滚了事务，又把工资改为1000。

此时小明读取的8000就是脏数据。

不可重复读：指在一个事务中，多次读取同一数据。在这个事务还没结束时，另一个事务也访问了该数据，那么在第一个事务的两次读数据之间，由于第二个事务的修改，第一个事务两次读到的数据可能不一样，这样就叫做不可重复读。

例如：1.小明在事务一中读取自己的工资，并没有结束事务。

2.事务二中，财务人员修改了小明的工资，并提交了事务。

3.在事务一中，小明再次读到了自己的工资，发现变为了2000。

解决办法：如果只有在修改事务完全提交之后才可以读取数据，则可以避免该问题。

幻读：指当事务不是独立执行时发生的一种现象。例如第一个事务对表中数据进行了修改，涉及了表中所有数据行。同时，第二个事务也修改了这个表中的数据，这种修改是插入了一行新数据，那么以后就会发生，操作第一个事务的用户发现表中还有没有修改的数据，好像幻觉一样。

例如：目前工资为1000的员工有10人。

1.事务一，读取所有工资为1000的员工

2.事务二向表中插入一条员工记录，工资也为1000

3.事务一再次读取所有工资为1000的员工，共读取到11条记录。

解决方法是如果在操作事务完成数据处理之前，任何其他事务都不可以添加新数据，则可避免该问题。

不可重复读的重点是修改 :同样的条件, 你读取过的数据,再次读取出来发现值不一样了 幻读的重点在于新增或者删除：同样的条件, 第 1 次和第 2 次读出来的记录数不一样

FEATURED TAGS
iOS 计算机 操作系统 计算机网络
FRIENDS