撸起袖子加油干。。俯身落实一百天。。

4.21
一：implement prim and kruskal algorithm and disjoint set
二：计算机网络--数据链路层
链路： 是一条点到点的物理线路段

数据链路data link：除了物理线路外，还必须有通信协议来控制这些数据的传输。即链路加上实现这些协议的硬件和软件，就构成了数据链路。（现在最常用的就是网卡，即适配器，实现这些协议的硬件和软件，一般的网卡都包括了数据链路层和物理层这两层的功能）

数据链路层的信道类型：
点对点信道：使用一对一的点对点通信方式（eg：两个laptop直连，主机到ISP）
广播信道：一对多的广播通信方式。

数据链路层传送的数据单位是帧：将网络层的数据在数据链路层装入帧（有头有尾），在物理层变成比特流传输，在接收处的数据链路层掐头去尾得到数据给网络层。

数据链路层的三个基本问题：
封装成帧 （在一段数据前后添加头部和尾部，确定帧的界限）


透明传输

（帧的头尾往往由特殊的非可打印字符组成，若在数据内部出现非可打印字符时，接收端可能错误的提前结束接受，为解决           这个问题，发送时，在数据内部若出现非可打印字符，会在前面加ESC作为转义字符，接收后，应当去掉ESC来得到原始数据，这一些  列操作对用户网络层是不可见的，故称透明传输）

差错控制（传输过程中会产生比特差错，1可能变成0， 0可能变成1）
误码率：错误的传输比特占所传输比特总数的比率
差错检测措施：帧检验序列FCS，将冗余码FCS添加到数据后面，让接收端处理判断是否出错
接收端看检错方法：循环冗余检验CRC，若检测失败则扔掉这段数据
CRC只保证接收到的数据是以接近1的概率正确，即无比特差错
CRC只是无错传输，并不是可靠传输（没考虑帧丢失，帧重复，帧乱序）

点对点信道的数据链路层

PPP协议（point to point protocol）：全世界使用最多的数据链路层协议，拨号上网一般都是PPP协议
要满足的要求：
封装成帧
透明
支持多种网络协议：TCP/IP 或 IPx
支持多种类型的链路：光纤，双绞线。。。
差错检验
检测链接状态
。。。
组成：（从底向上）
高级数据链路控制协议HDLC
链路控制协议LCP：负责身份验证
网络控制协议NCP：协商IP地址
PPP协议帧格式：

7E表示开头和结尾，FF表示地址（在点对点中是固定的），03表示控制字段（固定），两字节协议表示传输数据类型，FCS帧检验序列保证无错传输
PPP协议不使用序号和确认机制保证可靠传输的原因：
在数据链路层出错概率不大的情况下，使用简单的PPP协议比较合理
PPP传输的是IP数据报，即便数据链路层传输可靠，也无法保证网络层能可靠传输
FCS字段已经保证了无差错传输
PPP协议工作状态
用户拨号接入ISP，路由器的调制解调器对拨号确认，建立一条物理连接
PC机向路由器发送一系列的LCP分组，选择合适PPP参数，和网络层进行配置，NCP给新接入的PC机分配一个临时IP地址，使PC机成为因特网上的一个主机
通信结束后，NCP释放网络层连接，收回IP地址，LCP释放数据链路层连接，最后释放物理层连接
ps：我说了什么。。怎么还需要审核。。

4.22
一：和学长聊了十分钟，算是吃了个定心丸吧
二：chest day
bench press (60*10*3sets 80*6*3sets)
butterfly (60 70 80 90 10reps/set)
cable crossover (30*10reps*3sets)
三：cs61b 37. Amortized analysis  finished lab13
四：leetcode 200. Number of Islands
ps：感觉肩背三头恢复的差不多了，今天推的很稳

4.23
一天没学习。。订好了机票。。认识了一些同专业不同专业的人。。
象征性的做了道题。。leetcode 128. Longest Consecutive Sequence

4.24
一：leg day
squat (100*8reps*5sets 80*10*1set 60*10*1set)
rear leg pull (100 110 120 130 10reps/set)
leg press (270 250 220 190 10reps/set)
二：cs61b 38. Randomized analysis
三：implements splay tree with functions of insert, find and delete
四：计算机网络 数据链路层

广播信道的数据链路层

局域网的拓扑：
星形网（鲁棒性好）
总线网（需要电阻吸收反射信号）
环形网
树形网
局域网特点：
网络为一个单位所拥有，覆盖范围和连接的计算机数目都有限
有广播功能（从一个站点可以访问全网资源）
便于扩展，灵活
以太网(一种局域网技术)通信协议：载波监听多点接入/冲突检测，CSMA/CD协议
多点接入：多台计算机以多点接入的方式连在一根总线上
载波监听：发送数据前先检测总线上是否有其他计算机发送数据，若有需等待一定时间
使用此协议的以太网只能进行半双工通信
每个站点发送之后存在冲突的可能，这种不确定导致以太网的平均通信量远小于最高数据率
争用期：在发送数据帧后最多经过2t时间，就可知道是否发生了冲突。（t是端到端的传输用时）
以太网的争用期：通常取51.2微秒，对于10mb/s的以太网，在争用期内可传输512bit，即64字节，即若前64字节发送成功无冲突，后续数据就可以放心传输
最短有效帧长：以太网规定64字节为最短有效帧长，长度小于64字节的帧会被丢弃
二进制指数类型退避算法：即发生冲突后，双方需要等待一个随机时间，一般是争用期的整数倍，若等待后重传仍冲突，调整倍数继续重传，若重传16次后仍未成功，则丢弃该帧。

以太网
两个标准
DIX Ethernet V2
802.3
提供的服务：不可靠，接收到错误的帧时就丢弃
信道利用率：发送时间/总共时间。 总共时间包括冲突及其后的等待期。即S = T / (T+t+C)，其中T发送时间，t端到端传输时间，C冲突、等待时间
MAC地址：硬件地址或物理地址，即网卡的标识符。接收MAC帧时首先用硬件检查MAC地址是否匹配，不匹配就丢弃。
MAC帧格式：


扩展以太网
扩展传播距离：使用光纤
扩展覆盖范围：
在物理层扩展：用多个集线器连成更大的以太网（冲突增加，效率降低）
在数据链路层扩展：
使用网桥（建立转发表，自动学习减少冲突，但同时增加了时延）
使用交换机（硬件自动转发，更加高效安全）
虚拟局域网VLAN：由一些局域网网段构成的与物理位置无关的逻辑组。这只是局域网给用户提供的一种服务，增加安全性和灵活性。

高速以太网：速率大于等于100mb/s的以太网

4.25
一：leetcode 56. Merge Intervals  57. Insert Interval
二：comparable！！！ class A implements comparable<A>   override the compareTo method, than we can pass the work to the objects of primary type.
Collections.sort(list) and Collections.sort(list, new comparator<>() {   "override the compare method"  })
三：os 第五章 设备管理
I/O特点
I/O性能经常成为系统性能的瓶颈
I/O是操作系统庞大复杂的原因之一：资源多、杂、并发、均来自I/O
传输速度差异很大
不同设备有不同应用
控制接口不同
数据传输单位不同
数据表示不同
出现错误的种类不同
I/O与其他功能密切联系，特别是文件系统

I/O设备分类
按数据组织分类
块设备：以数据块为单位存储，传输。传输速率较高，可以寻址（随机读写）
字符设备：以字符为单位存储，传输。传输速率低，不可寻址
按功能分类
存储设备：磁盘 磁带
传输设备：网卡 Modem调制解调器
人机交互设备：显示器 键盘 鼠标
从资源分配角度
独占设备：在一段时间内只能有一个进程使用的设备，一般为低速I/O设备（打印机 磁带等）
共享设备：在一段时间内可以有多个进程共同使用的设备，多个进程以交叉的方式使用设备，资源利用率高（如硬盘）
虚设备：
定义：在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚设备
目的：将慢速的独占设备改造成多个用户可以共享的设备，提高利用率

I/O管理的任务目标
完成用户的I/O请求（控制设备，完成I/O设备与内存之间的数据交换）
设备分配与回收
纪录设备状态
根据用户请求，根据分配算法，选择一条数据通路
执行设备驱动程序，实现I/O操作
设备中断处理：处理外部设备的中断
缓冲区管理：管理I/O缓冲区
建立方便、统一的独立于设备的接口
方便性：屏蔽设备物理特性，为用户提供方便易用的接口
统一性：在用户程序中使用逻辑设备，对不同设备采用统一的操作方式
提高CPU与设备、设备之间的并行工作能力，提高资源利用率（使用通道，中断，缓冲，异步I/O等技术）
并行性
均衡性
保护：保证设备传送或管理的数据安全，不被破坏

I/O设备组成
机械部分（设备本身，物理装置）
电子部分（设备控制器或适配器）
（端口）地址译码
接收计算机发出的数据和控制信号，或者向计算机发送数据和状态信号（控制器接收到一条命令后，可独立于CPU完成制定操作，完成后，控制器产生一个中断，CPU继而响应中断）
将计算机的数字信号转换成机械部分能识别的模拟信号，或反之
实现设备内部硬件缓冲、数据加工等（控制器将串行的位流装入控制器内部的缓冲区形成以字节为单位的块，在查验无错误后将它们复制到内存中）

I/O控制方式
可编程I/O（轮询/查询）：由CPU代表进程给I/O模块发I/O命令，进程进入忙等待，直到操作完成才继续执行
中断驱动I/O：为了减少设备驱动程序不断的询问控制器状态寄存器的开销，I/O操作结束后，由设备控制器主动通知设备驱动程序
DMA（direct memory access）：内存和设备之间有一条数据通路成块的传送数据而无需CPU干预，世纪操作由DMA直接完成
I/O部件的演化
CPU直接控制外围设备
增加了控制器，CPU使用非中断的可编程I/O（避免了外部设备接口的具体细节）
采用中断方式，CPU无需等待，效率提高
I/O部件通过DMA直接控制存储器，可以自主的从内存中存取一块数据，CPU仅在传送开始或结束的时候参与
I/O部件增强为一个单独的处理器，有专门的指令集，CPU指导它执行内存中的一个I/O程序。可自主的取指令并执行
I/O部件有自己的局部存储器（其本身已经是一台计算机）

I/O软件
（分层设计思想，每一层都执行os所需功能的一个子集，较低层考虑硬件特性，较高层软件提供接口）
用户级I/O软件层：执行输入输出系统调用，对I/O数据进行格式化，为假脱机输入/输出做准备
与设备无关的os软件层：实现设备命名，设备保护，成块处理，缓冲技术和设备分配（设备独立性/无关性：用户程序可以访问任意I/O设备，无需指定，即用户使用逻辑设备，OS实现逻辑设备到物理设备的转换）
设备驱动程序层：设置设备寄存器，检查设备执行状态
中断处理程序层：负责I/O完成时，唤醒设备驱动程序进程，进行中断处理
硬件层：实现物理I/O的操作

I/O相关技术
缓冲技术（OS中最早引入的技术）
解决CPU与I/O设备之间速度不匹配问题（凡是数据到达和离去速度不匹配的地方均可以采用缓冲技术）
提高CPU与I/O设备之间的并行性
减少了I/O设备对CPU的中断请求次数，放宽了CPU对中断响应时间的要求
缓冲技术实现
缓冲区分类
硬缓冲：由硬件寄存器实现（如：设备中设置的缓冲区）
软缓冲：在内存中开辟一个空间用作缓冲区
缓冲区管理
单缓冲（一个缓冲区）
双缓冲（两个缓冲区）
缓冲池（多缓冲，循环缓冲）

4.26
一：back day
pull up (7reps*5sets)
cable rows (75 90 105 10reps/set)
pull down (90 100 110 120 10reps/set)
barbell row (10 15 20 10reps/set)
二：cs61b 39. Garbage collection
1. an object is live if it is _reachable_ from the roots. （ A _root_ is any object reference your program can access directly, without going through another object.）
2. computer’s memory is just one giant array that has no structure. Java saves you a huge amount of time and effort by structuring memory for you.  Java does this by using hidden pointer-based data structures that you can’t access from
   a Java program.
3. A mark-and-sweep garbage collector runs in two separate phases.  The _mark_ phase does a DFS from every root, and marks all the live objects.  The _sweep_ phase does a pass over all the objects in memory.  Each object that was
   not marked as being live is garbage, and its memory is reclaimed.
三：leetcode 435. Non-overlapping Intervals
四：计算机网络 第四章 网络层

网络层关注如何将分组从源端沿着网络路径送达目的端，不负责可靠传输

网络层提供的两种服务
虚电路服务：用于电信网。只是一条逻辑上的连接
数据报服务：用于因特网。网络在发送分组时不需要先建立连接，每一个分组（即IP数据报）独立发送
二者对比


网际协议IP
是TCP/IP体系中最主要的协议之一，与IP协议配套使用的还有三个协议：
地址解析协议ARP（address resolution protocol）
网际控制报文协议ICMP（internet control message protocol）
网际组管理协议IGMP（internet group management protocol）
他们的关系：


网络互联的设备
中间设备（中间系统或者中继系统）
物理层中继系统：转发器（repeater）
数据链路层中继系统：网桥或桥接器（bridge）
网络层中继系统：路由器
注：使用转发器和网桥并不称之为网络互联，只是把一个网络扩大了。互联网指用路由器进行互联的网络。

虚拟互联网：即逻辑互联网路，利用IP协议就可以使这些性能各异的网络在用户看来就是一个统一的网络，又称IP网。

IP地址
（是每一个连接在因特网上的主机或者路由器的每一个接口的在全世界范围的唯一的32位的标识符）
层次化，32位，分为网络ID和主机ID
网络地址：唯一的指定了每个网络。同一网络中的每台计算机都共享相同的网络地址
分类：
                     


几个保留地址：
127. 0. 0. 1  ：本地环回地址，即自己主机进程间通信使用
169. 254. 0. 0  ：Windows给出的当无法获得ip地址时，使用这个地址
10. 0. 0. 0  ：私有地址，无法访问
172. 16. 0. 0 — 172. 31. 0. 0  ：私有地址
192. 168. 0. 0 — 192. 168. 255. 0  ：私有地址
特殊地址：
主机部分不能为0 (全0)：对于192. 168. 0. 0，表示的是192. 168. 0. x 这个网络地址的网段
主机部分不能为255(全1) ：对于192. 168. 0. 255，表示广播

子网掩码（subnet mask）：又叫网络掩码，地址掩码。指出IP地址中哪部分是网络地址，哪部分是主机地址。当计算机之间通信时，先用子网掩码判断自己和目标计算机是否在同一网段，即IP地址中网络地址部分是否相同，若在，则直接通信，若不在，则需要路由器转发

子网划分：由于IP地址资源紧张，而网段划分时，最小单位也有256个地址（对应C类地址），当计算机数目远小于256时，就会浪费，为提高利用率，将子网继续划分，即从主机地址中拿出高几位划入网络地址（相应的改变子网掩码），构造更小的子网。
ps：子网掩码在某种意义上，只为了子网划分而存在。因为我们可以根据ip地址前八位大小判断属于哪一类地址，若不存在子网划分，子网掩码没必要存在。

超网（子网合并）：与子网划分相反，将网络地址的低几位划入主机地址中。

4.27
一：leetcode 206. Reverse Linked List  
二：网络层
IP地址与MAC地址关系
网络层及以上用IP地址，链路层及以下用硬件地址
ARP协议
（不论在网络层使用什么协议，在实际链路上传送数据帧时，必须使用硬件MAC地址）
当主机A需要和主机B通信时，需要知道B的硬件地址，所以A采用广播形式发送ARP分组请求，B接收到请求后，回复A其物理地址
每个主机都有ARP高速缓存，保存所在局域网的所有主机和路由器的IP地址到物理地址的映射关系
若A和B不在同一网段，则A需要知道路由器的物理地址，把分组发送给路由器并让他转发给下一网络
ARP协议可以将IP地址自动解析为链路层所需要的MAC地址
ARP欺骗：主机C可利用A广播，告诉A一个错误的MAC地址，形成ARP欺骗
RARP协议：逆地址解析协议。使知道自己硬件地址的主机知道其IP地址

IP数据报
由首部和数据两部分组成
首部
第一部分是固定长度，共20字节，是所有IP数据报必须具有的
第二部分是可选字段，长度可变
数据部分





IP转发分组流程

(1)从数据报的首部提取目的主机的IP地址D，得出目的网络地址为N。

(2)若N就是与此路由器直接相连的某个网络地址，则进行直接交付，不需要再经过其他的路由器，直接把数据报交付给目的主机（这里包括把目的主机地址D转换为具体的硬件地址，把数据报封装为MAC帧，再发送此帧）；否则就要执行(3)进行间接交付。

(3)若路由表中有目的地址为D的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器，否则执行(4)。

(4)若路由表中有到达网络N的路由，则把数据报传送给路由表中所指明的下一跳路由器，否则执行(5)。

(5)若路由表中有一个默认路由，则把数据报传送给路由表中所指明的下一跳路由器，否则执行(6)。

(6)报告转发分组出错。


ICMP协议
（为了更有效的转发IP数据报和提高成功交付的机会，使用ICMP，使主机和路由器可以报告差错和异常情况）
ICMP差错报告报文
终点不可达
源点抑制
时间超过
参数问题
改变路由（重定向）
ICMP询问报文
回送请求和回答
时间戳请求和回答
例子：分组网间探测PING（Package InterNet Groper），用来测试两个主机之间的连通性。这是应用层跨过运输层直接使用ICMP的例子。使用了ICMP回送请求和回送回答报文。
路由选择协议

RIP：动态的内部网关协议、基于距离向量的路由选择协议
仅由相邻路由器交换信息
交换的是路由表，且按固定的时间间隔交换
实现简单，但若网络出现故障需要很长时间才能通知到所有路由器
OSPF：开放最短路径优先Open Shortest Path First 内部网关协议
BGP：外部网关协议（连接各个使用不同协议的自治系统）

VPN虚拟专用网络
virtual private network
vpn利用公用的因特网作为访问各个专用网的通信载体。所传输的数据必须加密，否则出现安全问题。

NAT网络地址转换
在专用网内部，使用专用的IP地址，仅在连接因特网的路由器时使用公网地址。

4.28
复习了一天项目，中午和学姐吃了饭，畅谈三小时，下午佛系练了上胸，普通又开心的一天。

4.29
一：OS 文件管理
文件与文件系统

文件（对磁盘的抽象）
指一组带有标识（即文件名）的，在逻辑上有完整意义的信息项序列
信息项：构成文件内容的基本单位（单个字节或者多个字节），各项之间有顺序关系
文件分类
按文件性质和用途
普通文件：包含用户信息，一般为ASCII或二进制文件
目录文件：管理文件系统的系统文件
特殊文件：
字符设备文件：模仿串行I/O设备，例如终端，打印机，网卡等
块设备文件：磁盘
文件逻辑结构
流式文件：（基本单位是字符）有逻辑意义、无结构的一串字符的集合
记录式文件：由若干纪录组成，可以按纪录读写，查找等
文件存取
顺序存取、访问
随机存取、访问（需要提供读写位置）

文件系统
是OS中统一管理信息资源的一种软件，管理文件的存储，检索，更新，共享，保护
具体功能
统一管理磁盘空间（分配与回收）
实现文件按名存取（文件名空间到磁盘空间的映射）
实现文件共享，保护
提供方便易用的接口
提高文件系统性能
提供与I/O系统的统一接口

存储介质与物理块

典型存储介质
磁盘（包括SSD）
磁带
光盘
U盘
物理块（块block 簇cluster）
信息存储、传输、分配的独立单位
存储设备划分为大小相等的物理块，统一编号
典型磁盘结构：

磁盘访问
一次访盘请求需要明确：
读/写
磁盘地址（设备号，柱面号，磁头号，扇区号）
内存地址（源/目的）
完成访问分三步
寻道：磁头移动到制定磁道
旋转延迟：等待制定扇区从磁头下面旋转经过
数据传输：数据在磁盘与内存之间的实际传输

文件控制块及文件目录


文件控制块（file control block）
为管理文件而设置，保存文件属性
常用属性：文件名，大小，地址，创建时间，标志（只读，隐藏）。。。
文件目录
统一管理每个文件的元数据，支持文件名到文件物理地址的转换
将所有文件的管理信息组织在一起就构成文件目录
基本单元是目录项，即FCB
目录是文件控制块FCB的有序集合

相关概念
树形目录结构
路径名（文件名）
绝对路径：从根目录开始
相对路径：从当前目录开始

文件的物理结构
（文件在存储介质上的存放方式，当一个文件被划分为N块，该如何存放他们？FCB中如何纪录他们的地址？）
连续结构（存放在若干连续物理块中）

优点：
简单，支持顺序存取和随机存取
所需的磁盘寻道次数少
缺点：
文件不能动态增长
不利于文件插入和删除
产生外部碎片

链接结构（存放在若干不连续的物理块中，通过指针连接）

优点：
提高磁盘利用率，不存在外部碎片
利于文件插入删除
利于文件动态扩充
缺点：
存取慢，不利于随机存取
指针易出错
寻道次数多
指针占用空间
解决方案：FAT文件分配表将所有指针集中存放


索引结构（存放在若干不连续的物理块中，每个文件有一个索引表，即磁盘块地址数组）

优点：
保持了链接结构的优点，解决了其缺点（能随机存取）
缺点：
寻道次数多
索引表本身带来系统开销
索引表的组织方式（当索引表很大需要多个物理块存放时）
链接方式
多级索引方式
综合方式

4.30
不知不觉啊。。一个月又过去了。。上一次和泽镛见面是清明，一转眼就五一了。。
看了传输层的东西，知道了三次握手四次握手可靠传输。。。也就那么回事吧。。。