Final Review

一、数据库

No1. 索引

  1. Mysql数据库使用的索引数据结构为B+树(一种多路平衡查找树,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接)
  2. 为什么不使用二叉树:
    数据库索引存储在磁盘上,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少 IO 次数,对于树来说,IO 次数就是树的高度,而 “矮胖” 就是 b 树的特征之一,它的每个节点最多包含 m 个孩子, m 称为 b 树的阶
  3. 为什么不使用B树

    1. b + 树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更 “矮胖”。B 树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多,查询性能变低;
    2. b + 树查询必须查找到叶子节点,b 树只要匹配到即可直接返回。因此 b + 树查找更稳定(并不慢),必须查找到叶子节点;而B树,如果数据在根节点,最快,在叶子节点最慢,查询效率不稳定
    3. 对于范围查找来说,b + 树只需遍历叶子节点链表即可,并且不需要排序操作,因为叶子节点已经对索引进行了排序操作。b 树却需要重复地中序遍历,找到所有的范围内的节点
  4. 为什么不使用哈希表做索引

    1. 不支持模糊查找:哈希表是把索引字段映射成对应的哈希码然后再存放在对应的位置,这样的话,如果我们要进行模糊查找的话,显然哈希表这种结构是不支持的,只能遍历这个表。而 B + 树则可以通过最左前缀原则快速找到对应的数据。
    2. 不支持范围查找:如果我们要进行范围查找,例如查找 ID 为 100 ~ 400 的人,哈希表同样不支持,只能遍历全表。
    3. 哈希冲突问题:索引字段通过哈希映射成哈希码,如果很多字段都刚好映射到相同值的哈希码的话,那么形成的索引结构将会是一条很长的链表,这样的话,查找的时间就会大大增加。
  5. 最左前缀原则:
    在B + 树结构的索引中,索引项是按照索引定义里面出现的字段顺序排序的,索引在查找的时候,可以快速定位到 ID 为 100 的张一,然后直接向右遍历所有张开头的人,直到条件不满足为止。 也就是说,我们找到第一个满足条件的人之后,直接向右遍历就可以了,由于索引是有序的,所有满足 条件的人都会聚集在一起。

而这种定位到最左边,然后向右遍历寻找,就是我们所说的最左前缀原则

No2. 锁

  1. 当多个用户同时对数据库并发操作时,会带来数据不一致的问题,所以,锁主要用于多用户环境下保证数据库完整性和一致性
  2. 从数据库系统角度(悲观锁按使用性质划分):

    1. 排他锁: X锁/写锁,表示对数据进行写操作。如果一个事务对对象加了排他锁,其他事务就不能再给它加任何锁了
    2. 共享锁: S锁,也叫读锁,用于所有的只读数据操作。共享锁是非独占的,允许多个并发事务读取其锁定的资源
    3. 更新锁: U锁,在修改操作的初始化阶段用来锁定可能要被修改的资源,这样可以避免使用共享锁造成的死锁现象
      因为当使用共享锁时,修改数据的操作分为两步:

      1. 首先获得一个共享锁,读取数据,
      2. 然后将共享锁升级为排他锁,再执行修改操作。
        这样如果有两个或多个事务同时对一个事务申请了共享锁,在修改数据时,这些事务都要将共享锁升级为排他锁。这时,这些事务都不会释放共享锁,而是一直等待对方释放,这样就造成了死锁。

      如果一个数据在修改前直接申请更新锁,在数据修改时再升级为排他锁,就可以避免死锁。

  3. 从程序员角度:

    1. 悲观锁:每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人拿这个数据就会block(阻塞),直到它拿锁
    2. 乐观锁:每次去拿数据的时候都认为别人不会修改,所以,不会上锁,但是在更新的时候会判断一下在此期间别人有没有更新这个数据,可以使用版本号等机制

No3. 事务

  1. 事务是逻辑上的一组操作,要么都执行,要么都不执行(例子:转账)
  2. ACID特性

    1. 原子性(Atomicity):事务是最小的执行单位,不允许分割。事务的原子性确保动作要么全部完成,要么完全不起作用
    2. 一致性(Consistency): 执行事务前后,数据保持一致,例如转账业务中,无论事务是否成功,转账者和收款人的总额应该是不变的;
    3. 隔离性(Isolation): 并发访问数据库时,一个用户的事务不被其他事务所干扰,各并发事务之间数据库是独立的
    4. 持久性(Durability): 一个事务被提交之后。它对数据库中数据的改变是持久的,即使数据库发生故障也不应该对其有任何影响
  3. 数据事务的实现原理
    以 MySQL 的 InnoDB 引擎为例:MySQL InnoDB 引擎使用 redo log(重做日志) 保证事务的持久性,使用 undo log(回滚日志) 来保证事务的原子性。

MySQL InnoDB 引擎通过 锁机制、MVCC 等手段来保证事务的隔离性( 默认支持的隔离级别是 REPEATABLE-READ )。
保证了事务的持久性、原子性、隔离性之后,一致性才能得到保障

  1. 并发事务带来的问题

    1. 脏读(Dirty read): 当一个事务正在访问数据并且对数据进行了修改,而这种修改还没有提交到数据库中,这时另外一个事务也访问了这个数据,然后使用了这个数据。因为这个数据是还没有提交的数据,那么另外一个事务读到的这个数据是“脏数据”,依据“脏数据”所做的操作可能是不正确的。
    2. 丢失修改(Lost to modify): 指在一个事务读取一个数据时,另外一个事务也访问了该数据,那么在第一个事务中修改了这个数据后,第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失,因此称为丢失修改。 例如:事务 1 读取某表中的数据 A=20,事务 2 也读取 A=20,事务 1 修改 A=A-1,事务 2 也修改 A=A-1,最终结果 A=19,事务 1 的修改被丢失。
    3. 不可重复读(Unrepeatable read): 指在一个事务内多次读同一数据。在这个事务还没有结束时,另一个事务也访问该数据。那么,在第一个事务中的两次读数据之间,由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况,因此称为不可重复读。
    4. 幻读(Phantom read): 幻读与不可重复读类似。它发生在一个事务(T1)读取了几行数据,接着另一个并发事务(T2)插入了一些数据时。在随后的查询中,第一个事务(T1)就会发现多了一些原本不存在的记录,就好像发生了幻觉一样,所以称为幻读
    5. 不可重复读和幻读区别:
      不可重复读的重点是修改比如多次读取一条记录发现其中某些列的值被修改,幻读的重点在于新增或者删除比如多次查询同一条查询语句(DQL)时,记录发现记录增多或减少了。

No4. 范式(约束条件)

  1. 第一范式:每一个属性不可再分,具有原子性
  2. 第二范式:在1NF的基础上,消除非主属性对主键的部分依赖
  3. 第三范式:在2NF的基础上,消除非主属性对主键的传递依赖,任何非主属性不依赖于其它非主属性
    比如在设计一个订单数据表的时候,可以将客户编号作为一个外键和订单表建立相应的关系。而不可以在订单表中添加关于客户其它信息(比如姓名、所属公司等)的字段。
  4. BCNF:在3NF基础上,消除主属性对于码的部分与传递函数依赖:
    (仓库名,管理员,物品名,数量)=>仓库(仓库名,管理员)、库存(仓库名,物品名,数量)在3NF基础上,任何非主属性不能对主键子集依赖(在3NF基础上消除对主码子集的依赖)

No5. 基础概念

  • 元组 : 元组(tuple)是关系数据库中的基本概念,关系是一张表,表中的每行(即数据库中的每条记录)就是一个元组,每列就是一个属性。 在二维表里,元组也称为行。
  • 码 :码就是能唯一标识实体的属性,对应表中的列。
  • 候选码 : 若关系中的某一属性或属性组的值能唯一的标识一个元组,而其任何、子集都不能再标识,则称该属性组为候选码。例如:在学生实体中,“学号”是能唯一的区分学生实体的,同时又假设“姓名”、“班级”的属性组合足以区分学生实体,那么{学号}和{姓名,班级}都是候选码。
  • 主码 : 主码也叫主键。主码是从候选码中选出来的。 一个实体集中只能有一个主码,但可以有多个候选码。
  • 外码 : 外码也叫外键。如果一个关系中的一个属性是另外一个关系中的主码则这个属性为外码。
  • 主属性 : 候选码中出现过的属性称为主属性。比如关系 工人(工号,身份证号,姓名,性别,部门). 显然工号和身份证号都能够唯一标示这个关系,所以都是候选码。工号、身份证号这两个属性就是主属性。如果主码是一个属性组,那么属性组中的属性都是主属性。
  • 非主属性: 不包含在任何一个候选码中的属性称为非主属性。比如在关系——学生(学号,姓名,年龄,性别,班级)中,主码是“学号”,那么其他的“姓名”、“年龄”、“性别”、“班级”就都可以称为非主属性。

No6. 数据库设计步骤

  1. 需求分析 : 分析用户的需求,包括数据、功能和性能需求。
  2. 概念结构设计 : 主要采用 E-R 模型进行设计,包括画 E-R 图。
  3. 逻辑结构设计 : 通过将 E-R 图转换成表,实现从 E-R 模型到关系模型的转换。
  4. 物理结构设计 : 主要是为所设计的数据库选择合适的存储结构和存取路径。
  5. 数据库实施 : 包括编程、测试和试运行
  6. 数据库的运行和维护 : 系统的运行与数据库的日常维护。

二、计算机网络

No1. 应用层

  1. HTTP协议(超文本传输协议)
  2. http协议是基于TCP/IP协议之上的应用层协议
  3. 工作原理:HTTP协议定义Web客户端如何从Web服务器请求Web页面,以及服务器如何把Web页面传送给客户端
  4. HTTP 请求/响应的步骤

    1. 客户端连接到Web服务器:一个HTTP客户端,通常是浏览器,与Web服务器的HTTP端口(默认为80)建立一个TCP套接字连接。例如,http://www.baidu.com
    2. 发送HTTP请求:
      通过TCP套接字,客户端向Web服务器发送一个文本的请求报文,一个请求报文由请求行、请求头部、空行和请求数据4部分组成。
    3. 服务器接受请求并返回HTTP响应
      Web服务器解析请求,定位请求资源。服务器将资源复本写到TCP套接字,由客户端读取。一个响应由状态行、响应头部、空行和响应数据4部分组成
    4. 释放连接TCP连接
      若connection 模式为close,则服务器主动关闭TCP连接,客户端被动关闭连接,释放TCP连接;若connection 模式为keepalive,则该连接会保持一段时间,在该时间内可以继续接收请求;
    5. 客户端浏览器解析HTML内容
      客户端浏览器首先解析状态行,查看表明请求是否成功的状态代码。然后解析每一个响应头,响应头告知以下为若干字节的HTML文档和文档的字符集。客户端浏览器读取响应数据HTML,根据HTML的语法对其进行格式化,并在浏览器窗口中显示
  5. 在浏览器地址栏键入URL,按下回车之后会经历以下流程:

    1. 浏览器向 DNS 服务器请求解析该 URL 中的域名所对应的 IP 地址;
    2. 解析出 IP 地址后,根据该 IP 地址和默认端口 80,和服务器建立TCP连接;
    3. 浏览器发出读取文件(URL 中域名后面部分对应的文件)的HTTP 请求,该请求报文作为 TCP 三次握手的第三个报文的数据发送给服务器;
    4. 服务器对浏览器请求作出响应,并把对应的 html 文本发送给浏览器;
    5. 释放 TCP连接;
    6. 浏览器将该 html 文本并显示内容
  6. 特点:

    1. 无状态保存:引入了cookie技术管理状态
    2. 无连接:HTTP1.1中引入了keep-alive长连接技术
  7. HTTP请求方法
  8. HTTP状态码:

    • 1xx消息——请求已被服务器接收,继续处理
    • 2xx成功——请求已成功被服务器接收、理解、并接受
    • 3xx重定向——需要后续操作才能完成这一请求
    • 4xx请求错误——请求含有词法错误或者无法被执行
    • 5xx服务器错误——服务器在处理某个正确请求时发生错误
  9. URL
    http://www.luffycity.com:80/news/index.html?id=250&page=1 为例, 其中:

http,是协议;
www.luffycity.com,是服务器;
80,是服务器上的默认网络端口号,默认不显示;
/news/index.html,是路径(URI:直接定位到对应的资源);
?id=250&page=1,是查询。

  1. 请求格式
    方法+URL+协议版本+请求首部字段+内容实体(请求数据):

POST /form/entry HTTP/1.1 ........

  1. 响应格式
    协议版本+状态码+状态码描述符+响应头部+响应正文:
    HTTP/1.1 200 Ok.....
  2. 域名解析过程(以baidu.com为例)

    1. 客户机向其本地域名服务器发出 DNS请求报文(递归查询)。
    2. 本地域名服务器收到请求后,查询本地缓存,若没有该记录,则以DNS客户的身份向根
      域名服务器发出解析请求报文(迭代查询)。
    3. 根域名服务器收到请求后,判断该域名属于.com域,将对应的顶级域名服务器 dns.com的P地址返回给本地域名服务器。
    4. 本地域名服务器向顶级域名服务器dns.com发出解析请求报文(迭代查询)。
    5. 顶级域名服务器dns.com收到请求后,判断该域名属于baidu.com域,因此将对应的授权域名服务器 dns.baidu.com 的IP地址返回给本地域名服务器。
    6. 本地域名服务器向授权域名服务器dns.baidu.com 发起解析请求报文(迭代查询)。
    7. 授权域名服务器 dns.baidu.com收到请求后,将查询结果返回给本地域名服务器。
    8. 本地域名服务器将查询结果保存到本地缓存,同时返回给客户机。
      为了提高DNS的查询效率,域名服务器使用了高速缓存
  3. TCP连接(三次握手)

    1. 第一次握手:建立连接时,客户端发送一个报文段到服务器,首部中的同步位SYN=1,同时选择一个初始序号seq=x,并进入SYN_SENT状态,等待服务器确认;SYN:同步序列编号(Synchronize Sequence Numbers)
      结果:Client 什么都不能确认;Server 确认了对方发送正常,自己接收正常
    2. 第二次握手:服务器收到连接请求报文段后,如同意建立连接,则向A发送确认,SYN,ACK位都置1,确认号为ack=x+1,同时为自己选择一个初始序号seq=y,此时服务器进入SYN_RECV状态
      结果:Client 确认了:自己发送、接收正常,对方发送、接收正常;Server 确认了:对方发送正常,自己接收正常
    3. 第三次握手:户端收到服务器的确认后,向服务器发送确认,确认报文段的ACK置1,确认号ack=y+1,自己的序号为seq=x+1,此包发送完毕,客户端和服务器进入ESTABLISHED(TCP连接成功)状态,完成三次握手
      结果:Client 确认了:自己发送、接收正常,对方发送、接收正常;Server 确认了:自己发送、接收正常,对方发送、接收正常

imgimg

  1. 为啥是三次握手?不是两次
    为了防止已失效的连接请求报文段突然传送到了B,发生错误,导致B的资源浪费
  1. 释放TCP连接(四次挥手)

    1. 第一次挥手:客户端进程发出连接释放报文,并且停止发送数据。释放数据报文首部,FIN=1,其序列号为seq=u(等于前面已经传送过来的数据的最后一个字节的序号加1),此时,客户端进入FIN-WAIT-1(终止等待1)状态。 TCP规定,FIN报文段即使不携带数据,也要消耗一个序号
    2. 第二次挥手:服务器-收到这个 FIN,发出确认,确认序号为收到的序号加 1,即ack=u+1,报文段的序号为seq=v 。和 SYN 一样,一个 FIN 将占用一个序号
    3. 第三次挥手:服务器-关闭与客户端的连接,发送一个 FIN 给客户端
    4. 第四次挥手:客户端-发回 ACK 报文确认,并将确认序号设置为收到序号加 1

imgimg

为什么需要时间等待2MSL(Maximum Segment Lifetime 报文最大生存时间)?

       1. 防止第四次挥手的报文段丢失,服务器端无法正常关闭。如果第四次挥手丢失,服务器端会重新发送第三次挥手的报文,请求断开连接。
    2. 2MSL时间可以保证本次连接所有报文失效,防止“已失效的连接请求报文段”出现在本连接中,避免被服务器端认为是一个新的连接请求。
  1. HTTP与HTTPS的区别
  • 端口号 :HTTP 默认是 80,HTTPS 默认是 443。
  • URL 前缀 :HTTP 的 URL 前缀是 http://,HTTPS 的 URL 前缀是 https://
  • 安全性和资源消耗 : HTTP 协议运行在 TCP 之上,所有传输的内容都是明文,客户端和服务器端都无法验证对方的身份。HTTPS 是运行在 SSL/TLS协议 之上的 HTTP 协议,SSL/TLS 运行在 TCP 之上。所有传输的内容都经过对称加密,对于”对称加密”带来的密钥传输问题,则由”非对称加密”来解决。所以说,HTTP 安全性没有 HTTPS 高,但是 HTTPS 比 HTTP 耗费更多服务器资源。

No2. 运输层

  1. TCP: TCP(Transmission Control Protocol 传输控制协议)是一种面向连接的、可靠的、基于字节流的传输层通信协议
  2. UDP: UDP 协议全称是用户数据报协议,在网络中它与 TCP 协议一样用于处理数据包,是一种无连接的协议
  3. TCP和UDP的区别:
    TCP 用于在传输层有必要实现可靠传输的情况。由于它是面向有链接并具备顺序控制、重发控制等机制的,所以他可以为应用提供可靠的传输。

而在一方面,UDP 主要用于那些对高速传输和实时性有较高要求的通信或广播通信。
我们举一个通过 IP 电话进行通话的例子。如果使用 TCP,数据在传送途中如果丢失会被重发,但这样无法流畅的传输通话人的声音,会导致无法进行正常交流。而采用 UDP,他不会进行重发处理。从而也就不会有声音大幅度延迟到达的问题。即使有部分数据丢失,也支持会影响某一小部分的通话。此外,在多播与广播通信中也是用 UDP 而不是 TCP

No3. 网络层

负责相邻计算机之间的通信
  1. 路由选择:指按照复杂的分布式算法,根据从各相邻路由器所得到的关于整个网络拓扑
    的变化情况,动态地改变所选择的路由。

1.1 RIP(路由信息协议):一种分布式的基于距离向量的路由选择协议、仅和相邻路由器交换信息、交换的信息是当前路由器所知道的全部信息,即自己的路由表、按固定时间间隔交换路由信息,如30s
1.2 OSPF(开发最短路径优先协议):适合规模较大,使用洪泛法向本自治系统中的全部路由器发送信息,当链路状态发生变化时,每个路由器重新计算到各目的网络的最优路径,构造新的路由表

  1. 转发分组:指路由器根据转发表将用户的IP数据报从合适的端口转发出去

No4. 数据链路层

为网络层提供服务、链路管理、帧定界、帧同步和透明传输、流量控制和差错控制

主要设备有网桥(将两个或多个以太网通过网桥连接起来变成一个网段)、交换机

  1. 封装成帧:将网络层传输下来的数据报前后分别添加首部和尾部,构成一个帧。首部和尾部可进行帧定界:当数据是可打印的ASCII码组成的文本文件时,帧定界可使用特殊的帧定界符,SOH在前,EOT在后,只有接收端收到的数据有明确的帧定界符,这才是一个完整的帧
  2. 透明传输:不管所传数据是怎么样的比特组合,都应当能在链路上传送。当发送端的数据中有出现控制字符SOH和EOT时,在其前面插入一个转义字符“ESC”,表示这并不是一个帧定界符,在接收端的数据链路层把数据往网络层之前删除这个插入的转义字符
  3. 差错检验:防止传输错误,确保可靠传输。使用循环冗余检验CRC的检错技术:CRC运算就是在数据M的后面添加供差错检验用的n位冗余码FCS,构成一个帧发送出去

No5. 物理层

  1. 典型设备:中继器(放大信号,补偿信号衰减)、集线器(对接收到的信号进行再生整形放大,以扩大网络的传输距离)、网线等
  2. 数据单元:比特bit
  3. 描述:为上层协议提供一个传输数据的可靠的物理媒体,确保原始的数据可在各种物理媒体上传输

No6. TCP/IP

  1. TCP/IP 是互联网相关的各类协议族的总称,比如:TCP,UDP,IP,FTP,HTTP,ICMP,SMTP 等都属于 TCP/IP 族内的协议

No7. TCP可靠传输

  1. 序号:TCP首部的序号字段用来保证数据能有序提交给应用层
  2. 确认:TCP首部的确认号是期望收到对方的下一个报文段的数据的第一个字节的序号
  3. 重传:超时;冗余ACK

三、数据结构

No1. 红黑树

红黑树是一种自平衡的二叉查找树

红黑树特点 :

  1. 每个节点非红即黑;
  2. 根节点总是黑色的;
  3. 每个叶子节点都是黑色的空节点(NIL节点);
  4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
  5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。

红黑树的应用 :TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。

为什么要用红黑树? 简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构

保证红黑树始终平衡 :变色+旋转

四、操作系统

No1. 概念与系统调用

  1. 操作系统是控制和管理整个计算机系统的硬件与软件资源,合理地组织、调度计算机的工作与资源的分配,进而为用户和其他软件提供方便接口与环境的程序集合。它是计算机系统中最基本的系统软件
  2. 特征:并发、共享、虚拟、异步
  3. 根据进程访问资源的特点,进程在系统上的运行可分为用户态和系统态

    1. 用户态:用户态运行的进程可以直接读取用户程序的数据
    2. 系统态:系统态运行的进程或程序几乎可以访问计算机的任何资源,不受控制
  4. 在我们运行的用户程序中,凡是与系统态级别的资源有关的操作都必须通过系统调用方式向操作系统提出服务请求,并由操作系统代为完成

No2. 进程与线程

  1. 进程 :指在系统中正在运行的一个应用程序;程序一旦运行就是进程;进程——资源分配的最小单位。
  2. 线程 :系统分配处理器时间资源的基本单元,或者说进程之内独立执行的一个单元执行流。线程——程序执行的最小单位
  3. 进程的状态

    • 创建状态(new) :进程正在被创建,尚未到就绪状态。
    • 就绪状态(ready) :进程已处于准备运行状态,即进程获得了除了处理器之外的一切所需资源,一旦得到处理器资源(处理器分配的时间片)即可运行。
    • 运行状态(running) :进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
    • 阻塞状态(waiting) :又称为等待状态,进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲,该进程也不能运行。
    • 结束状态(terminated) :进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。
  4. 进程间的通信方式

    1. 管道/匿名管道(Pipes) :用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
    2. 有名管道(Names Pipes) : 有名管道严格遵循先进先出,有名管道以磁盘文件的方式存在,可以实现本机任意两个进程通信。
    3. 信号(Signal) :信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生;
    4. 消息队列 :消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。
    5. 信号量 :信号量是一个计数器,用于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
    6. 共享内存 :使得多个进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作,如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
    7. 套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元,可以看做是不同主机之间的进程进行双向通信的端点,简单的说就是通信的两方的一种约定,用套接字中的相关函数来完成通信过程。
  5. 进程的调度算法

    为了实现最大的CPU利用率
    1. 先到先服务算法:从就绪队列中选择一个最先进入该队列的进程为之分配资源,使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度
    2. 短作业优先调度算法:从就绪队列中选出一个估计运行时间最短的进程为之分配资源,使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度
    3. 时间片轮转调度算法:每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间
    4. 多级反馈队列调度算法:多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。它是时间片轮转调度算法和优先级调度算法的综合和发展
    5. 优先级调度算法:为每个流程分配优先级,首先执行具有最高优先级的进程,依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求,时间要求或任何其他资源要求来确定优先级

No3. 死锁

  1. 概念:多个进程因竞争资源而造成的一种僵局(相互等待)
  2. 产生的条件:

    • 互斥:一段时间内某资源仅为一个进程占有
    • 不剥夺:进程所获得的资源在未使用完之前,不能被其他进程强行夺走
    • 请求并保持:一个进程因请求资源而阻塞时,对已经获得资源保持不放
    • 循环等待:若干进程之间形成一种头尾相接的循环等待资源的关系
  3. 死锁预防:设置限制,破坏产生死锁的条件之一
  4. 避免死锁:银行家算法(设法保证系统动态分配资源后不进入不安全状态,以避免可能产生的死锁)
  5. 死锁的处理:预防死锁、避免死锁、检测死锁、解除死锁

No4. 内存管理

  1. 主要负责内存的分配与回收,地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作系统内存管理做的事情
  2. 内存管理方式

    1. 块式管理 :将内存分为几个固定大小的块,每个块中只包含一个进程。如果程序运行需要内存的话,操作系统就分配给它一块,如果程序运行只需要很小的空间的话,分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间,我们称之为碎片。
    2. 页式管理 :把主存分为大小相等且固定的一页一页的形式,页较小,相对相比于块式管理的划分力度更大,提高了内存利用率,减少了碎片。页式管理通过页表对应逻辑地址和物理地址。
    3. 段式管理 : 段式管理把主存分为一段段的,段是有实际意义的,每个段定义了一组逻辑信息,例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。 段式管理通过段表对应逻辑地址和物理地址
    4. 段页式管理机制就是把主存先分成若干段,每个段又分成若干页,也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的

No5. 虚拟内存

虚拟内存是操作系统虚拟性的一个体现,实际的物理内存大小没有变,只是在逻辑上进行了扩充,虚拟内存的实现需要建立在离散分配的内存管理方式的基础上

  1. 虚拟内存的实现方式

    • 请求分页存储管理
    • 请求分段存储管理
    • 请求段页式存储管理

五、计算机组成原理

No1. 冯诺依曼体系结构的计算机分为哪几层

  1. 输入设备、运算器、控制器、存储器、输出设备
none
最后修改于:2022年03月24日 21:37

添加新评论