初入数据可视化

视图编码(可视化编码) = 标记 + 视觉通道

可视化设计的三部曲

可展示数据的筛选 -> 可视化编码映射(视图编码) -> 视图与交互设计

数据可视化设计的注意事项

在对数据可视化之前,要选择合适的标记和视觉通道,选择合适的视觉通道编码能够更加清晰,直观地展现出数据的特点,同时能够使用户更加容易地分析数据特征。

不同的视觉通道编码信息会产生不同的效果,这种效果也被称为表现力和有效性

表现力和有效性决定着数据可视化的最终效果。

在表现力排序中,无论是定量型视觉通道还是定性型视觉通道,空间位置都具有最大表现力

决定表现力的四个维度:
  1. 精准性
  2. 可辨认性
  3. 可分离性 -> 不同的视觉通道编码之间互相干扰的程度
  4. 视觉突出 -> 人依靠本能,在很快的时间内快速感应到图形中的异常点。此维度在发现异常数据的可视化分析中至关重要。
提升表现力的方法:
  1. 聚焦:通过恰当的技术手段就将可视化结果中的最重要的部分重点突出。

  2. 均衡:空间布局要合理,将重要的元素位于中心区域,其余元素均衡分布。

  3. 简单:元素尽量简单,避免画面过于复杂。

  4. 隐喻:尽量用人们所熟悉的某样事物去表达信息,从而使得可视化内容更加直观、易懂。

数据按照它们之间的特征,可以大致分为以下的三类:

数值型数据,分类型数据,有序性数据

小说一下-过度焦虑

想到什么就写什么,杂记一些想法

回想今年年初到八月份这段时间,不知道是不是因为实习期间太过于顺利,导致我总是无法直面一些崎岖坎坷,一旦遇到一些不顺的事情,第一时间想到的不是去解决它,而是去逃避,尽可能不去面对它。这也间接导致我一旦遇到一些无法避开的坎坷,就会变得异常焦虑

有必要过度焦虑吗?

现在静下心来,我就开始思考这个问题,焦虑是正常的,但是过度焦虑却会起反作用(比如面试结果出的那几天,我睡觉都睡不着),做事情效率都会因为焦虑而降低甚至没有。与其焦虑,不如做好现在的每一件事,过好现在的每一分钟,因为它已经发生了,你肯定不可能改变过去,但却可以改变未来,而现在正在做的每一分钟,正是为“改变未来”而做准备


为何会过度焦虑,其实就是没有直面崎岖坎坷,总是想着一帆风顺,哪有那么美好的事情。

反而,总是一帆风顺,这一路上反而会少了些期待,少了些波澜起伏,少了些走过艰难坎坷后的激动。

想过这一切后,好像确实如此。

直面眼前的困难吧,试着去找各种办法解决它,克服它。正是有着这样的经历,生活才算过的有意义。

谈谈保研经历

这篇博客主要记录的是保研的大概过程以及作者今年从六月份到九月份的保研经历,希望能够让未来保研的学弟学妹们更清晰地了解保研的整个过程以及其中的一些避坑指南。

本人基本情况📖

  • 本科院校:电子科技大学/信息与软件工程学院

  • 均分:87.5

  • 排名:18/186(10%)

  • 四级:500

  • 六级:492

  • 无科研经历

  • 竞赛获得奖项

    • 中国软件杯国家三等奖
    • 三创杯四川省二等奖
    • 微信小程序开发大赛西南赛区三等奖
  • 最终去向:电子科技大学/计算机科学与工程学院(电子信息)

从上述基本情况可以看出,本人在本科期间不算优秀,没有任何科研经历,竞赛也是一些较小的比赛,不过好在大三时去字节跳动实习过半年,这也算是一个加分项。

保研基本流程

  • 总的来说,保研基本分为三个阶段:

    1. 夏令营(六月 - 八月)
    2. 预推免(八月末 - 九月)
    3. 九推(九月 - 十月系统关闭)(这里的系统是指国家推免招生系统,后续会提到)
  • 其中,需要注意的是前两个阶段,即夏令营和预推免

夏令营

  • 夏令营是可以等效理解为高考录取的提前一批,各位学生通过学校研究生院官网了解到对应院校的夏令营信息,通过报名,学院筛选后,进入到院校夏令营中。如下的两个链接。

南京大学夏令营信息

电子科技大学夏令营信息

  • 一般来说,每个高校的夏令营流程如下:
    • 了解学院基本情况 -> 了解学院中的各个实验室(即了解导师) -> 学院组织统一面试(筛选优秀营员) -> 夏令营结束
  • 注意,大多数学院的夏令营优秀营员相当于已经被学院拟录取了,所以夏令营的面试一定要提前好好准备一下,毕竟多一个offer不亏。
夏令营注意事项
  1. 一定,一定,一定要保证信息的流通!保研其实就是再打一场信息战,谁掌握的信息多,谁的优势就越大,不要有“好麻烦啊,我不想去找消息”的想法,要善于利用渠道去获得各个院校的夏令营的开放时间,免得错过(本人就是错过了非常多的夏令营,没有拿到保底offer,最后九推差点没书读)。

    • 一般来说,可以从下面两个渠道来获得各个院校夏令营信息:

      1. 全国各地保研学生自发组织的QQ群 -> 每个专业的QQ群不一样,比如计算机保研交流群:605176069
      2. GitHub仓库:由全国各地用爱发电同学实时更新的夏令营信息集合。如下链接(可能需要梯子)

      2021年CS保研夏令营通知公告

      1. 关注微信公众号:保研夏令营
  2. 最好在夏令营阶段就联系好导师,因为越好的导师越抢手,而好的导师则是决定着你未来三年读研体验,因为在读研期间,大多数时间都是跟着自己的导师做科研/项目。

  3. 多报几个学校的夏令营,由于现在疫情影响,基本所有院校的夏令营都是线上进行,于是没有了空间上的成本,多报几个夏令营则是多给自己选择的机会,防止到保研后期手足无措

预推免

  • 预推免的举行时间一般是每年的八月中旬到九月底(开推免系统之前),和夏令营类似,各个院校会在自己的研究生院上公布对应的预推免报名时间。
  • 预推免的流程只有两步,即初审和复试。初审是报名的研究生院老师根据学生提交的信息而进行简单的评估,而复试则和夏令营类似,由学院专家组对学生进行20分钟左右的面试。一般在面试结束后的一天到两天左右就会出结果。
预推免注意事项
  1. 和夏令营类似,要及时了解到各个学校学院的预推免报名时间,以免错过。
  2. 有些学校在夏令营时没有给出推免名额,他们把所有名额都放到了预推免上,比如电子科技大学
  3. 同理,预推免也可以多报几个学校,如果说只报了一个学校,并且面试的时候发挥失常了,那可能就要寄了(当然在九推时也可以捡漏,后面会提到)。

九推

何为推免系统?
  • 在说九推之前,先说一下什么是国家推免生系统
    • 前面有提到,各个学院会在夏令营和预推免时发放拟录取offer,需要注意,这里只是拟录取,并不是真正的拟录取,因为这只是学院的口头offer,国家是不认的。
    • 真正的录取则是要通过上述提到的推免系统来进行录取,它类似于高考填报志愿的系统,通过该系统进行录取的推免生,才算是真正拟录取(为何说是拟录取,因为后期如果推免生本人做了一些违反规定的事情,那会被取消资格,这里只是保证学校层次不会把你咕了)
    • 如下所示,是推免系统的界面

推免系统界面

正文
  • 关于九推,如果说你在夏令营或预推免已经拿到了学校offer了,那直接根据学校要求,在志愿系统上填报对应院校即可
  • 可如果你之前一个offer都没拿到,或者只是在某个学校的wl(候补名单)中,那可能需要在九推的时候捡漏了
  • 每年都会出现学院招不满推免学生的情况,特别是近几年疫情期间,没了空间成本,这种鸽的现象越来越严重,甚至有的学校会被鸽穿,比如今年的华中科大和湖南大学
  • 于是,这个时候就可以捡漏了,可以从以下两种比较常见的办法捡漏:
    1. 直接联系学院的研招办,询问具体情况,有些学院你甚至没有去面试,都可以被录取,比如这次我联系的华中科大计算机学院,可惜我们学校先录取的我,于是只能放弃了。
    2. 有些学院会开二次预推免招生进行补录,冲就完事了。
  • 有关于推免系统填报的相关流程和细节,可以参照下面的微信公众号文章。

2021推免系统填报指南

本人保研经历

说完正常的保研流程,这里谈谈我自己的保研经历,总的来说,我的这次保研是很失败的,夏令营没有抓住机会,预推免也过分自信,导致最后九推填系统时没有完全确定的学校。

但是,我认为还是有必要拿出来说一说,毕竟越是失败的经历,越能展示一些坑点所在,最后希望我的经历能够带给你一些帮助。

六月 -> 夏令营报名进行时 -> 因为躺平心态而错过

  • 基本从六月开始,各个院校的夏令营通知就陆续发出来了,可我那个时候却在忙于实习工作的离职交接,基本都到了六月二十号,我才把工作那边的事情忙完并成功离职。按道理说,这个时候去准备投递夏令营完全不迟,但是由于才从10-9-5.5的工作中解脱出来,我非常想躺平了。
  • 所以我没有主动去找各个院校的夏令营通知,而是从我们班级保研群里(班长创建)随便了解到的几个学校中选了两所进行投递,一个中科大和南大。
  • 中科大:由于我报名的是中科大的先研院,所以那边要求先联系导师,然后夏令营才有可能被筛选进。此时我的心想“好麻烦啊,还要找导师,不想去弄”,于是乎,我失去了参加先研院夏令营的资格。
  • 南大计院:南大今年的夏令营需要先进行一轮初试,即通过网上做题来达到筛选的目的,我也收到了初试的通知,但我当时也是因为摸鱼 + 不敢去试试(我怕南大的题难)的双重心态,于是也放弃了本次南大初试(我现在回想起来,真想给我那个时候一拳,且不谈摸鱼,不敢去试完全是扯谈,因为这根本没有任何成本,试一试又不亏,说不定就过了,所以希望学弟学妹能够引以为鉴,不要害怕这些初试和面试,要相信自己)

南京大学

于是六月是没有任何成果的一个月

七月,八月 -> 夏令营进行时 + 预推免开始报名

  • 七月,八月各个院校的夏令营热火朝天的进行着,但我最终只报名了电子科技大学的计算机学院的夏令营,可惜的是,学院夏令营不分配推免名额,它全部留给了预推免。通过学院的夏令营,我了解到一个实验室和我之前实习做的方向很接近,于是我便提前联系了那个实验室的老师,和实验室的学长学姐以及老师进行简单的交流后,学长学姐以及老师都比较喜欢我,于是很快就和老师达成了双向选择。

  • 这也是这两个月中的唯一一件好事了,但恰恰这一件事情,却间接导致了我后续夏令营以及预推免的报名

  • 因为双向选择 + 所谓的听说的本校照顾政策,那个时候我的心就已经留在本校了,因为听说本校的面试只是走流程(后来的事实表面不可能是这样的),所以我更加坚信,我百分百能够留本校了。

  • 所以我没有报名其他任何学校的夏令营,包括八月中旬开始的预推免。

  • 而这将近两个月的时间,我一直在准备本校的预推免面试,这里我因为掌握信息不够充分的缘故,又吃了一次大亏。我以为我校和其他院校一样,预推免时会重点考察408的内容,于是直接从网上买了王道的408-2022考研资料抱着啃。谁想到,我们本校的预推免面试重点考察数据结构算法那一块的内容,并且只问一道题。所以,一定要保证信息的流通,当时的我应该提前去找之前面试过的学长学姐了解一下,然后再来有针对性地复习

九月 -> 预推免面试 -> 九推填报捡漏

  • 由于前面所说,我因为过分信任自己能够上岸,所以只选择了本校的预推免,其他学校都没有去报名。
  • 结果在面试当天,我拉了大跨:首先进行英语自我介绍,用英语回答了一些基本的常规问题,随后便是自己选择了一道题,我选了一道多路归并算法的时间复杂度计算,这直戳我的软肋,因为关于时间复杂度的计算我一直都是懵的,加上多路归并我也只是了解过,但是了解的不多,所以这道题最后以“毫无思路”告终,最后便是介绍自己的项目,然后回答一些项目中遇到的问题,然后就结束了
  • 9.26号出成绩时,看到我在本校的候补名单里,我瞬间感觉天都塌下来了,并不是因为我在候补(因为我有预料到),而是因为我没有去准备其他保底学校的offer,我那天没睡着觉,我不断安慰自己,实在找不到书读,就直接上班吧。但我内心深处是很想继续深造的,所以这样的安慰效果甚微。
  • 在推免系统开放的那天,我从朋友那里了解到,今年华科被鸽穿了,现在去联系还来得及,这次我没有放弃这个机会,直接到华科的官网去寻找华科各个实验室的简介以及联系方式,然后开始疯狂地联系导师。我的运气还不错,联系的第二个导师告诉我,他的名额正好多出一个(因为刚好有人把他鸽了),问我有没有兴趣,我就像抓住救命稻草一样,马上把自己简历发给他,然后经过简单交流后,他同意为我留一个指标,但最关键的还是要看招办那边有没有名额,于是我马上打电话给招办询问,得知有机会后,我在志愿系统上马上填报了华中科大

华科老师联系

系统填报

  • 至于上图的湖南大学,也是因为在填报系统前一天得知,湖大也被鸽穿了,于是想投一投试试运气。

极限上岸

  • 不过今年貌似我们学校计算机学院被鸽的有点惨,所以即使我在候补的第十七位,在下午三点十分的时候,招办给我打电话说,我被补录到了。我很高兴,因为我最初的想法就是能够在本校深造,于是我马上接受了我校计院的待录取(极限上岸属于是)。

待录取

  • 不过华科在下午四点多钟的时候也决定录取我了,不过因为我已经接受了本校的录取,所以只能拒绝了。

小小地总结一下

  • 从本人的经历来看,虽然结果差强人意,但过程却是非常失败的,千万不要有躺平或摸鱼的心态(除非你已经有确定的院校offer),我这次很大程度上就是被这种心态所影响所以导致最后一个保底offer都没有。
  • 其次,一定要保证自己掌握到充足的信息,信息的不流通会间接导致保研的失败,比如我这次面试本校计院,就是因为没有提前去了解面试的内容,所以复习时做了许多无用功。
  • 再者,千万不要有我是本校的,那就有照顾政策的思想,如今的社会,能力才是最根本的保证,千万不要抱有侥幸心理,努力提升自我才是根本,如果自我实力够强,还需要去担心本校有没有照顾政策吗?那直接是“手到擒来”了。
  • 最后,千万不要放弃,即使在前两个阶段没有拿到offer,也可以尽力在九推时捡漏,因为疫情期间,海王遍地是,很多学校在最后填报系统时都多多少少被鸽了一些名额,所以要抓住这个时机,有的学校可能会开二次预推免面试,有的学校可能给招办打电话说一下就可以了。总之,是有书读的,关键就是看自己是否能够把握到那个补录机会了。

希望我的经历能够带给未来的保研er一些帮助,如果再给我一次保研的机会,我肯定会努力去争取夏令营和预推免,可惜没有如果。

最后的最后,祝愿未来的保研er能够保研顺利,找到自己心仪的导师!

需要想找我进一步交流的同学,可以通过邮箱联系我runtugo1999@gmail.com

数据结构-杂记

这是一篇不成体系的记录,只是为了记录一些零散的容易忘记的概念知识点

线性表

  • 具有相同数据类型的n(n >= 0)个数据元素的有限序列。

顺序表

  • 线性表的顺序存储又称为顺序表, 即用一组连续的存储空间来存储线性表中的元素。
  • 顺序表特点:逻辑顺序和物理顺序相同。
  • 高级语言中,顺序表的代表为数组

线性表的链式存储

  • 地址没有要求连续,即要求逻辑上相邻的数据在物理存储上没有要求,数据与数据之间通过指针来进行联系。

线性表一般有两种表现方式(根据存储方式的不同):顺序表和链表

  • 一种特殊的线性表,不过要求只能在一端进行数据的读写(推入push和弹出pop)。

  • 计算机中一种特殊的数据结构,它通常被看作是用一棵树的数组对象。
  • 它有两个特性:
    1. 堆一定是一颗完全二叉树(所以才可以用数组来表示)
    2. 二叉树里所有的子树的根节点都大于(或小于)它的子节点,即大根堆和小根堆的区别。

计算机网络-网络层

网络层被设计成“向上提供简单灵活的,无连接的,尽最大努力交付的数据报服务”的特性,即所传输的分组没有保证,可能出错,丢失,重复,失序,或超时。

但这样设置好处是:网络的造价大大降低(比如路由器),运行方式灵活,能够适应多种应用(即在网络层之上的传输层可以基于灵活的网络层作很多拓展工作)

异构网络互联

  • 不同协议的网络子系统通过中间设备(中继设备)相互连接起来,形成更大的系统。(P135)
    • 中继设备:
      • 物理层:中继器,集线器(Hub)
      • 数据链路层:网桥或交换机
      • 网络层:路由器
      • 网络层之上:网关

路由与转发

  • 路由器的两功能:路由选择(确定哪一条路径 => 构建和维护路由表)和分组转发(当一个分组到达时要完成的动作 => 查询,转发以及队列管理和任务调度等)。

拥塞控制

  • 网络进入拥塞状态的方法:观察网络吞吐量和负载的关系
    • 如果随着网络负载的增加,网络的吞吐量明显小于正常吞吐量(或者不增反降),则说明可能(一定)进入了拥塞状态。(注意:正常情况下,负载越高,吞吐量越大)

拥塞控制和流量控制(联系到链路层的流量控制)的区别

  • 流量控制是在发送端和接受端点对点通信时的数据传输控制,它数局部性控制,且是接收端来控制发送端
  • 而拥塞控制则是一个全局性的问题,它确保的是一个子网内的数据能够成功传输到彼此。
拥塞控制的方法
  1. 开环控制:静态的预防方法,系统启动后,设置的控制调度算法不能改版。
  2. 闭环控制:动态方法,采用监测网络系统去监视,及时检测哪里发生了拥塞,然后将拥塞的信息传输到合适的地方,以便调整网络系统的运行。

路由算法

  1. 静态路由算法 => 网络管理员手动配置的路由信息,它不能适应网络状态的变化
  2. 动态路由算法 => 通过路由器之间相互传递信息并且根据一定的算法,实时更新路由表的信息

动态路由算法的两个主要算法

  1. 距离-向量路由算法 => 实现协议RIP(路由信息协议) => 应用层协议,使用了UDP传送数据
    • 所有结点定期地将它们的整个路由选择表(下面统称为路由表)传送给其所有的相邻结点。
    • 每个结点从相邻结点拿到路由表信息后,迭代计算到每个结点的最短距离,并实时更新自己的路由表。
  2. 链路状态路由算法 => 实现协议OSPF(开放最短路径优先) => 网络层协议,使用ip数据包传递数据
    • 每个结点(路由器)向本自治系统的所有节点发送自己和自己相邻路由器之间的链路状态,即先把信 息发送给相邻的路由器,然后通过相邻的路由器再次发送给它的相邻路由器,这样不断迭代传递,最终所有结点都能获得发送结点的相邻链路状态。 => 泛洪法
    • 最后每个路由器都能获得自治系统内所有节点的相邻链路状态,然后按照一定的算法,更新自己的路由转发表。
    • 所以该算法要求每个参与算法的结点都具有完全的网络拓扑信息

层次路由

  • 设想一下,如果对网络中众多的路由不分层次,则会使得每次转发的路由表(或链路信息)异常庞大,无论是更新还是查阅都会非常消耗性能,其次灵活性也不高,因为没有分层,导致整个路由系统必须统一协议标准,而不能“因地制宜”
  • 所以考虑把整个互联网划分为较小的自治系统(每个自治系统有多个局域网),每个较小的自治系统可以设置自己的路由协议,同时也需要自治系统间的协议来屏蔽不同路由协议自治系统的通信
  • 自治系统内使用的路由选择协议叫做内部网关协议(IGP) => 例如RIP,OSPF等
  • 自治系统间使用的路由选择协议叫做外部网关协议(EGP) => 例如BGP等。

ipv4

  • ipv4分组格式如下所示

ipv4分组格式

注意:有些描述存储大小的字段是有单位的,比如首部长度,总长度等,这些会在下面单独说明

  1. 首部长度单位: 32位(4Byte)
  2. 总长度:首部加数据段的总长度,单位:Byte
  3. 片位移:由于MTU的限制,ip数据报如果过长会被分片,那么该字段则表示该片段在原分组的相对位置,用于之后在目的地拼接。长度单位:8Byte,所以每个分片的长度一定是8B的整数倍(除最后一片)

网络地址转换(NAT)

  • 将专门网络地址转换为公用地址,从而隐藏内部管理的IP地址。这样做的好处是可以增多主机的ip分配,一个局域网的主机可以用多个内网ip标识,而它们的公网地址则只需要用一个ip标识即可,而NAT就做的是这其中的转换工作

  • 即一台主机可以用 一个公网ip + 一个内网ip 唯一标识。

  • 实现了NAT协议的路由器也叫做NAT路由器,其中维护着NAT表。

    • NAT转换表存放着「本地ip地址:端口」 : 「全球ip地址」:端口的映射。

ipv4几种分类方式(概述)

传统分类(A,B,C,D,E)两级分类

  • 每个ip地址分成网络号(第一级)和主机号(第二级)两部分。根据网络号占用的位数不同,以及网络号首几位的数值不同可以分为A-E五个类别。
  • 从上述描述可以看出,这种分类方式灵活性很差,每一类占用的网络号是固定的,如果按照网络号占用的位数来分类,实际上只能分成三类(即A,B,C三类常用ip地址)

子网划分

  • 两级ip地址的空间利用率有时候很低,因为网络号的位数是固定的,当给一个物理网络分配网络号后,路由表就会变得很大而使网络性能变差。
  • 所以考虑引入子网号字段,使二级ip地址变为三级ip地址,这种做法也叫做子网划分。
  • 子网号是从主机号中借用若干bit而形成的,所以就出现了「<网络号>,<子网号>,<主机号>」这样的结构。
  • 需要注意的是:子网划分是一个单位内部的事情,它对于外部表现是透明的,即对外部仍然表现为没有划分子网的网络。此时需要下面描述的子网掩码来解决子网掩码的识别问题。

子网掩码

  • 为了告诉外界主机或路由器对A,B,C类网络进行了子网划分,使用了子网掩码来表示子网号对主机号的借位。借位的位数可以通过子网掩码上的“1”来进行判断,即如果没有借位,则默认子网掩码为255.0.0.0,255.255.0.0,255.255.255.0.

CIDR 无分类域间路由选择(CIDR)

  • 消除了传统A,B,C类网络划分,可以更有效地分配IPv4的地址空间。
  • CIDR分类中的IP格式:「<网络前缀>,<主机号>」,或者使用“斜线记法”: IP地址/网络前缀。其中网络前缀对应于网络号的部分(位为1的部分)。

ARP协议 => 将ip地址转化为MAC地址

  • 当某路由器获得下一跳路由器的ip地址时,不是通过ip地址去直接访问的,而是通过ARP将ip转化为MAC地址再去访问对应的路由器地址。

DHCP 动态主机配置协议

  • 用户主机动态地分配IP地址,它提供了即插即用的联网机制。

ICMP 网际报文控制协议

  • 网络层使用ICMP来让主机或路由器来报告差错和异常信息。

计算机网络-链路层

链路层重点:组帧,流量控制与可靠传输机制,介质访问控制

  • 数据链路层是在物理层提供服务的基础上为网络层提供相关服务,它能够加强物理层中比特流的传输,也能将物理层上可能会出错的物理链路改造为逻辑上无差错的数据链路,然后为网络层提供对应服务。

为网络层提供的连接服务

  1. 无确认,无连接服务。
  2. 有确认,无连接服务。
  3. 有确认,有连接服务。
  • 需要注意的是:只要是能够连接,则一定会有确认,即不存在无确认,有连接的服务。

帧定界

  • 数据帧的长度由首部,尾部,以及数据三者决定,而首部和尾部包含了许多控制信息,其中就包含了帧边界的标识,这就是所谓的帧定界。(注意:链路层封装的数据帧也称为组帧,它的作用就是解决帧定界,帧同步,透明传输等问题)

    • 透明传输:接受方能够正确识别帧尾部,而不会因为数据段有和尾部相同的标识而提前结束帧识别。
  • 下面列举几种帧定界的方法。

    1. 字符计数法。
    2. 字符填充的首位定界符法。
    3. 零比特填充的首位标志法。
    4. 违规编码法。
  • MTU(最大传输单元):帧数据部分长度的上线(IP数据包)

差错控制

  • 比特传输过程中难免会遇到差错,比如1变为0,0变为1,这种差错也称为比特差错,于是需要通过编码方式对传输的比特实现差错控制,减少或避免误差。

检错编码 => 检验传输的比特是否出错

  1. 奇偶校验法
  2. 循环冗余码(CRC:Cycle Redundancy Code)

纠错编码 => 对出错的比特进行纠错 => 海明校验

流量控制

  • 为了防止发送方的速度过于快而导致接受方来不及接收从而造成的丢帧现象出现,需要对发送方的发送数据速率作一定的限制,而流量控制的常见方法是通过接收方来控制发送方的速率(由接收方感知,如果速率过快,则返回特定的信息)

常见的两种流量控制方法

  1. 停止-等待协议 : 发送方发送一帧后,必须等待这一帧的回复才能继续发送下一帧。
  2. 滑动窗口协议:发送方维持一组能够发送帧的集合,称为发送窗口,同理接收方也维持一组预接收帧的集合,称为接受窗口。发送窗口外的帧不会发送,接收窗口外的帧不会接收。

可靠传输机制

  • 可靠传输同时使用确认和超时传输这两种机制来完成。
    1. 确认是指发送方发送帧后,为了确保该帧顺利到达接收方且没有出错,应该要收到对应的帧回复。
    2. 超时传输指发送方发送帧后,会启动一个定时器,如果超过一定时间还没有收到回复帧,则认为帧丢失,需要重传。

自动重传请求(ARQ:Auto Repeat reQuest)

  • 接收方通过请求发送方重传出错的帧来恢复出错的帧。它是处理信道所带来差错的办法之一。
ARQ分类
  1. 停止-等待ARQ
  2. 后退N帧ARQ(Go-Back-N:GBN)
  3. 选择性重传(Selective Repeat:SR) => 接收方需具备缓存器,缓存出错帧之后已经到达接收方的帧。

介质访问控制(Medium Access Control: MAC)

  • 为使用介质的每个设备与使用同一个介质的其它设备的通信隔离开来,简而言之,就是要保证各个通信设备在使用同一介质时互不干扰,这就是介质访问控制的作用。
  • 常见的介质访问控制分为信道划分MAC(静态划分),随机访问MAC(动态分配),轮询访问MAC(动态分配)

信道划分介质访问控制

  • 顾名思义,按照某种标准,将信道划分为多个部分以供给多个通信设备使用,由于划分是固定的,所以也是静态划分信道的方法。
  1. 频分多路复用(FDM)
  2. 时分多路复用(TDM)
  3. 波分多路复用(WDM)
  4. 码分多路复用(CDM) => 也叫做码分多址(CDMA:Code Division Multiple Access)

随机访问介质访问控制

  1. ALOHA协议 => 不检测,直接传,如果一段时间没收到确认,则重传。

  2. 时隙ALOHA协议 => 时间被划分为一段段等长的时隙(Slot),只能在每个时隙开始的时候才能发送。

  3. CSMA协议(Carrier Sense Multiple Access:载波侦听多路访问):基于ALOHA的改进协议,主要是多了一个载波侦听装置。

    1. 1-坚持CSMA => 监听到信道空闲,就一定会发送(概率为1)
    2. 非坚持CSMA => 监听到信道忙,放弃监听,过一段时间再监听
    3. p-坚持CSMA => 监听到信道空闲,概率p会发送数据,1-p概率推迟到下一个时隙(并不是下一个时隙发送)
  4. CSMA/CD协议(CD => 碰撞检测) -> 一边发送一边监听 -> 适用于有线连接的局域网

    • 检测到碰撞后,实行指数退避算法
    • 引出了最小帧长的概念(注意和MTU区别):保证发送端在发送帧时能够接收到本次发送帧的数据(接收端回复),所以有最小帧长的概念。 => 最小帧长 = 传播时延(单向) * 2 * 传输速率
  5. CSMA/CA协议(CA => 碰撞避免) => 不能完全避免,只是降低碰撞的概率

    • 也有退避算法,但是和CSMA/CD不同,CD是只有碰撞时才会触发,而CA则是遵循除非站点第一次传输数据,否则都要执行对应的退避算法的原则

    • 隐藏站的解决方法 => 预约信道

    • RTS控制帧 => 在发送前广播的特殊帧,请求预约

    • CTS控制帧 => AP广播的特殊帧,给源站允许发送的许可,同时抑制其他站点的发送。

轮询访问介质访问控制 => 令牌传递协议

操作系统-2

本章主要总结操作系统中的内存管理

  • 随着技术的发展,内存的容量再不断增大,但是也不能把所有用户数据和程序一起装入内存,因此操作系统需要对内存空间进行合理的划分和有效的动态分配,从而提高系统的资源利用率。对内存的合理划分以及有效的动态划分就是内存管理的概念。

程序执行过程

  • 每段程序执行前大致需要经过三个过程:编译 -> 链接 -> 装入
    1. 编译:将源代码通过编译器编译为一个个目标模块。
    2. 链接:将每个目标模块和所需库函数链接起来,形成一个完整的装入模块。
      1. 静态链接(装入前链接),即在装入内存之前把所有的模块和对应的库函数进行链接从而形成一个可执行程序,以后不会再拆开。
      2. 装入时动态链接,即在装入内存时,一边装入一边链接。
      3. 运行时动态链接,即在执行对应模块代码时,实时链接。
    3. 装入:将链接后形成的模块装入内存中。
      1. 绝对装入 => 程序相对地址和实际装入的物理地址相同。
      2. 可重定位装入 => 程序相对地址加一个重定位地址形成实际的物理地址。
      3. 动态运行时装入 => 在执行对应的模块时,才开始执行地址转换,地址转换的偏移量则从重定位寄存器中取出。

内存分配管理方式

连续分配方式:用户程序被分配进一个连续的内存空间

  1. 单一连续分配方式: 整个内存中只运行一道用户程序。
  2. 固定分区分配
    • 内存被划分为若干个固定大小的区域。当有程序需要装入内存时,从分区说明表上寻找合适的内存区域并分配给它。
  3. 动态分区分配 => 不预先对内存进行分区,而是等程序装入内存时动态分区。
    1. 首次适应算法
    2. 最佳适应算法
    3. 最坏适应算法
    4. 邻近适应算法(首次适应算法的改进,即下一次分配内存是从上一次分配内存结束位置开始)

区分内部碎片还是外部碎片的关键在于:内存分区是提前分好还是运行时实时分配的。

对于前者,很容易理解每个内存分区就可以称之为“内”,所以就有了内部碎片的说话。

对于后者,由于没有提前分区,所以自然没有“内”的概念,那么所有的内存都是“外”,所以此时产生的碎片也称为外部碎片。

即固定分区会产生内部碎片,动态分区会产生外部碎片。

非连续分配方式

  1. 基本分页存储管理方式 => 一维表示即可,即给定一个地址,便可以算出它的页号以及偏移地址(因为页的大小是确定的)
  2. 基本分段存储管理方式 => 二维表示,因为每段的大小不同,导致一个地址无法算出其它信息,段号和段内位移地址要显式给出
  3. 段页式存储管理方式 => 对代码分段,对内存分页。
  • 分页系统和分段系统的共同之处:

    1. 它们都有对应的“表”,分页系统是页表,分段系统是段表。当然对于表来说也有对应的寄存器(页表/段表寄存器)
    2. 它们都可以加入快表(联想存储器 TLB)来提高地址转移效率。
  • 不同之处:

    1. 分页系统的地址可以进行一维表示,而分段系统的地址需要二维表示。
    2. 分段系统中的每段是具有一定逻辑意义的代码集合(比如一块函数定义),方便代码共享。

虚拟内存

局部性原理 => 高速缓存技术依赖的原理

  1. 时间局部性:程序中的某条指令一旦执行,不久后该指令可能再次执行;某数据被访问,不久后该数据可能再次被访问。产生时间局部性的原因是程序中往往含有大量的循环操作
  2. 空间局部性:一旦程序访问了某个存储单元,不久后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在某个区域

虚拟存储器

  • 根据局部性原理,程序装入时,可以只将程序的部分装入,其余部分留在外存。程序执行过程中,若程序不在内存中,则从外存中调入对应部分的程序代码,然后继续执行程序。另一方面,操作系统也把不再执行的代码重新换出到外存(实际情况是如果代码段没有被修改,则直接丢弃)。这样,系统好像就为用户提供了一个比内存大的多的存储器,称其为虚拟存储。

  • 实现方式

    1. 请求分页存储管理
    2. 请求分段存储管理
    3. 请求段页式存储管理
  • 它们都需要的硬件支持:

    1. 一定的内外存。

    2. 地址转换机构。

    3. 中断机构(程序访问部分不在内存时,发生缺页/段中断)

    4. 页表(段表)机制。

      • 特别说明下页表机制(这里以页表存储管理为例),由于程序在运行时有部分在外存(不像之前直接全部调入),于是需要标记外存的程序段的地址。

      • 另一方面,为了分辨对应页的代码是否在内存中,还需要一个状态位来进行说明。除此之外,为了优化调入换出次数,提高执行效率,则还需要设置访问字段以及修改位

      • 那么上述的字段设置在哪里设置比较好呢?显而易见页表是最适合的位置,即给页表增加几个状态位专门安放上述的几种状态字

页面置换算法

  1. 最佳置换算法(OPT)
  2. 先进先出算法(FIFO)=> 可能会出现Belady异常,即分配物理块数越多,缺页次数反而越大。
  3. 最近最久未使用(LRU)置换算法
  4. 时钟(CLOCK)置换算法 => 最近未使用算法(NRU)
  5. 改进型CLOCK算法
    • 改进型CLOCK算法主要是增加了修改位的判断,即优先换出没有修改的内存页(可以直接扔掉而不是写回外存)

页面分配策略

  • 系统必须考虑给特定的进程分配几个页框比较合适。
分配算法
  1. 固定分配局部置换
  2. 可变分配全局置换
  3. 可变分配局部置换
从何处调入页面
  • 在外存上分为文件区(存放文件)和对换区(存放对换页面)。

  • 文件区:采用离散分配方式,读写速度相对较慢。

  • 对换区:采用连续分配方式,读写速度相对较快。

  1. 如果对换区足够大,则操作系统在程序执行之前把需要调入的页面从文件区复制到对换区。
  2. 如果对换区大小有限,则不会修改的文件都从文件区调入(因为不用写回),可能会被修改的则复制到对换区。这样可以提高写回速度。

抖动: 进程执行过程中,如果换页的时间超过了执行时间,则判断其发生了抖动。

  • 抖动的解决方法:工作集。

操作系统-1

在复试时,很少问及计算题,大多数都是的问题都是和概念直接相关,所以要深刻理解操作系统各个组成部分的概念。

本篇主要归纳操作系统的基本概念以及进程相关概念和算法

操作系统基本概念

首先需要知道操作系统在整个计算机系统中的定位:

​ 计算机系统大致可以分为四个部分(自底向上):计算机硬件 -> 操作系统 -> 应用程序软件 -> 用户。

从上述结构可以轻易看到,操作系统管理着计算机的各个硬件,具体表现为对资源的合理调度,分配等,同时也为上层应用程序软件提供抽象出来的硬件功能。

综上所述,操作系统可以定义为控制和管理整个计算机的硬件和软件资源,并合理地组织,分配资源、调度工作,进而为用户和其它软件提供方便接口与环境的程序集合。 提炼一下,操作系统就是一系列程序的集合,不过这些程序有着上述管理功能。

特征(四大特征)

  1. 并发 => 注意并发和并行的区别。
  2. 共享 (两种共享方式,也对应着后续会提到的资源共享形式)
    1. 互斥共享
    2. 同时访问
  3. 虚拟 => 用逻辑的对应物去映射实际的物理设备,让用户在使用时感觉是在真正使用物理设备。
    • 经典例子: 请求分页系统,SPOOLing技术
  4. 异步 => 进程以不可预知的速度向前执行(进程的异步性)
    • 异步也是操作系统中需要进程控制的原因之一,因为要保证怎么个异步法,各个进程的最终结果都一样。

其中,并发和共享是其它特性的基础,它们两也相互依存。

管理的计算机资源(包括硬件和软件)分类

  1. 处理机管理 => 进程的调度与分配
  2. 存储器管理 => 内存管理
  3. 文件管理 => 文件的存储形式:逻辑存储和物理存储
  4. I/O设备管理 => 外存相关概念以及相关管理

运行环境

  • CPU的状态分为两类:用户态(目态)核心态(管态)
  • 用户的程序运行在目态,而操作系统的内核运行在管态。有一些特殊的特权指令,只有在CPU处于管态时才能调用。
    • 特权指令 -> 操作系统不允许用户直接调用的指令,比如I/O指令,置中断指令等等。
  • 如果说用户程序必须使用特权指令的功能,则需要通过中断或异常操作来达到目的,即发生中断或异常时,CPU状态会从用户态转向核心态。

中断和异常

操作系统的发展过程大体上就是一个想法设法不断提高资源利用率的过程,而提高资源利用率就需要在程序并未使用某种资源时,把它对那种资源释放,而这一行为就需要通过中断来实现。

中断(外中断):CPU执行指令以外的事情发生而引起的中断,即外中断不是由指令本身引起的(比如访问数组越界等),而是外界因素导致的(比如I/O中断,时间片中断),它和当前处理机正在运行的程序有关。

异常(内中断,陷入trap):CPU执行指令时发生的错误异常事件。比如地址越界,请求分页系统的缺页以及专门的陷入指令(这个也是上述用户能够主动进入核心态的办法,也称为系统调用)。

​ 系统调用的本质是用户把CPU的使用权交给了操作系统内核的程序,然后让内核程序去执行对应的特权指令,等执行完毕后,再把使用权返回。即关键指令的调用实质还是内核调用而不是用户直接调用

进程管理

基本概念

  • 在多道程序运行的系统中,由于程序直接“暴露在内存里”,所以导致程序没有封闭性,它们能够彼此看见对方内部的结构,甚至调用,这显然是不行的。于是为了方便描述程序和控制程序的并发,体现操作系统的并发性和共享性,所以引入了进程的概念。
  • 进程(动态的):是程序的一次执行过程(进程实体的运行过程),是CPU资源分配和调度的基本单位(引入线程之前)
    • PCB(Process Control Block)
    • 程序段
    • 相关数据段

状态

  1. 创建态
  2. 就绪态
  3. 运行态
  4. 终止态
  5. 阻塞态
  • 它们各自的定义这里不再描述。
  • 需要说明的是,当进程从运行态变换到阻塞态时,是一个主动的行为(即自己需要去请求某个外设资源或等待某一事件发生而引起的阻塞),这是一种特殊的,由运行的用户态程序去调用操作系统内核过程的形式。
  • 从阻塞态转移到就绪态,这是一个被动过程,因为它需要外界信号进行触发。例如请求的外设已经完成了对应的任务,或是请求的某个资源已经空闲出来等。

进程通信

  1. 共享存储空间通信 -> 多个进程共享内存中的某块空间,当需要通信时,在内存中进行读写即可。
  2. 消息传递 -> 调用操作系统提供的消息传递方法进行进程通信,即通过发送消息和接受消息两个原语进行通信。
    1. 直接通信,即发送进程直接把消息发送给接收消息进程。
    2. 间接通信,即发送进程把消息发送给某个中间实体,使其成为一个信箱,而接受进程直接从实体中取消息即可,反之亦然。
  3. 管道通信 -> 由pipe文件来连接发消息进程和接受消息进程从而达到通信的目的。(消息查看2022王道考研操作系统P35)

线程

由于进程的切换会有较大的时空开销,于是考虑引入线程,从而提高系统的并发性能(因为线程切换所引起的时空开销要远远小于进程)。

  • 线程是轻量级的进程,它是CPU的执行单位。需要值得注意的是,线程本身不占有资源,它共享它所在的进程的资源,即进程的资源被它拥有的线程所共享。
  • 在引入线程的系统里,进程仅仅作为系统资源分配的基本单位,而线程则成为了处理机的分配单元

实现方式

  1. 用户级线程(User-Level Thread: ULT)
    • 线程的管理全部由用户程序来实现,内核意识不到线程的存在。
  2. 内核级线程(Kernel-Level Thread: KLT)
    • 线程的管理工作全部由内核实现,内核为每个线程维护乡下问信息,应用程序不能直接管理线程,只能通过内核级线程接口来进行相关操作。

处理机调度

在系统中,进程的数量绝大多数时候都大于处理机的数量,所以如何分配处理机给进程使用成为了一大难点,如果分配不合理,不仅会极大影响系统的运行效率和资源利用率,严重情况下甚至会造成死锁。

而处理机的调度则是对处理机进行合理的分配,它执行某种公平的算法从而使得处理机能够合理分配给各个进程,以实现进程的并发执行。

调度的层次

  1. 高级调度 -> 作业调度,即把作业从外存调入内存中。
  2. 中级调度 -> 内存调度,作用是提高内存的利用率,当某些进程不能运行时,可以暂时将其调至外存,从而实现资源的释放(此时,该进程的状态也称为挂起态)
  3. 低级调度(进程调度)。按照某种方法或策略从就绪队列中选择对应的进程,并将处理机分配给它。

调度方式(注意和后面的算法区别)

  1. 非剥夺式调度(非抢占调度)
  2. 剥夺式调度(抢占式调度) => 剥夺不是任意性行为,而需要遵循某种原则,这种原则就是后面要提到的调度算法。

调度的衡量标准

这里不一一列举全部标准,只说明几个简单准则

  1. 周转时间:作业从提交到完成的全过程时间
    • 带权周转时间:周转时间 / 作业实际运行时间 。 => 因为在整个周转时间里,作业除了运行时间,还有等待时间。
  2. 等待时间:作业处于等处理机状态的时间总和(创建,就绪,阻塞)。
    • 这里等待时间和上述周转时间中提到的等待时间是同一回事,同时该指标也是衡量算法优劣的重要标准
  3. 响应时间:作业从提交到系统首次响应所经历的时间。

调度算法(重点)

  1. 先到先服务(FCFS:First Come First Serve)
  2. 短作业优先(SJF:Short Job First)
  3. 优先级调度算法
    • 为每个作业进程设置优先级,根据优先级高级来进行调度。
    • 优先度有静态优先级和动态优先级两种分类。注意把这里的动态优先级和下述的高响应比做对比
  4. 高响应比有限调度算法
    • 响应比计算 R = (等待时间 + 要求服务时间) / 要求服务时间
    • 从上述公示可以看出:对于短作业,要求服务时间小,R比较大,优先级一开始较高;对于长作业,虽然一开始R较低,随着时间的推迟,等待时间变大,R随之增大。所以它对于短,长作业都是相对公平的。
  5. 时间片轮转调度算法
  6. 多级反馈队列调度算法
    • 设置多个时间片队列,每个队列内的分配的时间片相同,每个队列之间从第一队列到第n队列分配的时间片依次增大,作业从第一队列开始执行,如果没执行完,则放置下一队列继续执行,依此类推,直到最后一个队列。
    • 需要注意的是,第1 - 第n-1队列对内调度算法为FCFS,第n队列调度算法为时间片轮转算法。

进程同步

相关概念

在多道程序系统中,进程是并发执行的,不同进程之间存在着不同的制约关系,为了能够较好的协调这种制约关系,从而引入了进程同步的概念

临界资源
  • 同一段时间内只能被一个进程访问的资源。
临界区
  • 访问临界资源的代码区。
同步(直接制约关系)
  • 共同完成同一个任务的多个进程之间,在执行任务的某个阶段,需要某种制约关系让它们相互等待,相互传递消息从而使得多个进程能够按照一定速度,并以正确顺序去完成该作业,这种制约关系就称为同步。
互斥(间接制约关系)
  • 一个进程进入到临界区使用临界资源时,另一个进程必须等待,直到前一个进程退出临界区。
  • 四大准则:
    1. 空闲让进
    2. 忙则等待
    3. 有限等待
    4. 让权等待

实现临界区互斥的方法

  1. 软件实现方法(王道考研P76)
  2. 硬件实现方法
    1. 中断屏蔽方法(开关中断)
    2. 硬件指令方法(即设置原子操作去访问临界区)

信号量

  • 信号量是一种功能较强的机制,它能够用来解决互斥和同步的问题,它只能被wait(S)和signal(S)两个原语访问。

管程

计算机中的软件资源或硬件资源,都可以用某种数据结构的特性抽象地描述其特性。即用少量的信息和对对资源的操作来表征某种资源。

  • 管程:代表共享数据的数据结构,以及对共享数据结构实施操作的一组过程所组成的资源管理程序,称为管程。 => 相当于把共享数据的数据结构以及对它的一系列操作抽象出来,抽象成一组管理程序,而这组管理程序就叫做管程,它能够保持进程互斥,无序程序员手动实现互斥。

死锁

当有多个进程持有一定资源时又去争夺其它进程持有的不可剥夺资源,此时便发生了死锁。

  • 死锁:多个进程因争夺资源而造成的一种僵局(互相等待),若无外力作用,则程序无法继续执行下去。

死锁产生的必要条件

  1. 互斥条件:资源的互斥性。
  2. 不可剥夺条件:不可剥夺资源。
  3. 请求并保持条件:每个进程在持有资源的同时又去请求别的进程持有的资源。
  4. 循环等待条件。

死锁处理的策略

  1. 预防死锁
    • 关于死锁的预防,只要打破上述四个必要条件之一,便可以预防死锁。 => 王道P124
  2. 死锁避免
    • 和预防死锁不同的是,预防死锁是在进程执行之前进行一系列操作,而死锁避免是在进程运行过程中(资源动态分配过程中),防止系统进入不安全状态。
    • 解决方法:银行家算法
  3. 死锁检测和解除
    • 检测采用资源分配图辅助分析。
    • 死锁的接触有以下方法可以参考。
      1. 资源剥夺法 => 剥夺死锁进程的资源,把它挂起
      2. 撤销进程法 => 强制撤销部分或全部死锁进程,释放资源
      3. 进程回退法 => 将一个(或多个)死锁进程回退到发生死锁之前。

进程部分结束

0907-开篇说明

随便谈谈

  • 距离上次写博客已经是一年前的事情,老博客的内容也因为自身的一些原因被丢失。同时最近在准备预推免复习时,突然发觉如果一天复习下来不进行总结,大概率第二天会忘记。
  • 所以,为了能获得较好的复习效果,同时也是为了抓回写博客的习惯,又重新搭了个hexo的博客,希望自己能够坚持下去。
  • Github主题链接

大三的遗憾

  • 大三一年可以说是充满挑战的一年,但也是碌碌无为的一年。实习虽去了字节跳动,但发现进去依然干着搬砖的活。本以为可以写点SDK之类的,可惜因为人员缺乏,只能跑去写业务,累呀,也没有什么比较大的收获,因为除了写业务还是写业务。
  • 于是乎,还是打算在六月的某日离职,全力准备夏令营(结果到头来是夏零营)。

  • 不过都过去了,现在最重要还是眼前的预推免,希望自己能够坚持下来,将每日的学习总结以博客的形式呈现于此。

请我喝杯咖啡吧~

支付宝
微信