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

4.17
一：leetcode 303. Range Sum Query - Immutable   62. Unique Paths   771. Jewels and Stones   746. Min Cost Climbing Stairs   70. Climbing Stairs
二：cs61b 35.Radix sort
三：操作系统第四章
存储管理
存储管理是操作系统的重要组成部分，负责管理计算机系统中的内存储器。

内存空间分为：
系统区：存放操作系统内核程序和数据结构
用户区：存放应用程序和数据

存储管理主要功能：

存储分配（为进程分配内存空间，完成内存的分配与去配工作）
地址映射（将内存抽象，支持用逻辑地址访问物理内存单元，实现地址映射）
存储保护（确保进程独占式的使用内存，防止地址越界）
存储共享（允许多个进程共享内存区）
存储扩充（实现虚拟存储器）

存储器工作原理


存储器层次（自上而下，访问速度从快到慢，容量从小到大，价格从高到低）
寄存器
缓存
内存
磁盘
磁带
地址转换与存储保护（一个应用程序如何在计算机系统上执行）
程序编译（源程序经过编译程序或者汇编程序生成目标模块）
程序链接（根据目标模块之间的调用关系，将主调模块，被调模块和所用的库函数连接成一个完整的可装载执行模块）
静态链接：在程序装载到内存和运行前，将所有目标模块和所需库函数链接装配完成，生成可重定位目标程序，这是在逻辑地址空间的，存放于磁盘中。
动态链接：在程序装载时一边装载一边链接，生成一个可执行程序。若发现所需目标模块已存在于内存中，则无需装载直接链接。
运行时链接：将某些目标模块或者库函数的链接推迟到运行时才进行。
程序装载（装载程序把可执行程序装入内存）
绝对装载：装载模块中的地址都是内存绝对地址
可重定位装载：都是相对地址
动态运行时装载：装入内存的程序可能被对换到磁盘上，当再换入内存时，对换前后所处内存位置可能不同，即支持在不同时候进程的内存映像不同
地址重定位（逻辑地址转换为物理地址）
静态地址重定位：当用户程序加载到内存时，一次性实现地址重定位，无需硬件支持，程序执行过程中不可移动
动态地址重定位：逐条语句执行完成地址转换，需要硬件支持，可以移动
运行时链接地址重定位：支持每次运行时链接装载不同模块

连续存储管理

固定分区存储管理：又称静态分区，即内存空间被划分为数目固定不变的分区，各个分区大小不等，每个分区只装入一个作业。这是支持多道程序设计最简单的存储管理技术。
可变分区储存管理：又称为动态分区模式，按照作业大小来划分分区，划分的时间，大小，位置都是动态的。
为方便内存空间的分配与去配，建立两张表：已分配区表和未分配区表。由于分区数目不定，适合采用链表来管理空闲区。表格或者链表中的空闲区都要按照一定次序排列（按大小或按地址）。
常用可变分区分配算法：
最先适应分配算法：按顺序查表或链表，找到第一个满足的空闲区即可。可能导致小空闲区集中在内存一端。
下次适应分配算法：改进first fit的缺点，从上次查找结束处继续寻找第一个满足的空闲区，使空间利用更加均衡。
最优适应分配算法：扫描所有空闲分区，选出满足的最小空闲区。
最坏适应分配算法：扫描所有空闲分区，选出满足的最大空闲区。
快速适应分配算法：将常用长度的空闲区设立单独的空闲区链表，再设立一个索引表保存所有这些单独的链表，使用时按照进程长度直接搜索能容纳他的最小空闲区链表并分配第一块空闲区即可。
对固定分区：采用静态地址重定位。 对可变分区：采用动态地址重定位。
内存不足的存储管理技术：
移动技术：再可变分区算法中，进程的不断装入和撤销会导致产生内存碎片。可采用移动技术使得碎片汇集起来（内存紧凑）。方法是将内存中的全部进程分区移动到内存的一端，或者只移动部分进程分区，产生足够新进程使用的空闲区就停止移动。
对换技术：将内存中阻塞的进程与磁盘中就绪的进程相互对换，适当时再对换回来。一般选择时间片耗尽的或优先级低的进程换出内存，保存其数据区和堆栈区的内容，在合适时机触发对换。
覆盖技术：针对要执行的程序长度超出物理内存或分区的大小，这时移动和对换都不起作用，需要在程序执行过程中用其不同的模块在内存中相互替代，达到小内存执行大程序的目的。

4.18
就写到这里吧。今天什么都没干，只是打了八个小时电话，结束了一段七年的友谊。
早上八点半，我就接到了他的电话，借钱，五百。紧张的语气，不停的解释让我非常怀疑。这不像他。我们是高中同学，他性格内向但人却温和善良，懂得照顾别人情绪，是那种老好人。由于沉默寡言，可能我是他为数不多的好朋友。上了大学，我们联系的频率可能是一年一通电话，或寒假见一面。直到大三那年，他主动找我倾诉，我才知道他有两次因为打网球摔断小腿以及一次压力太大轻生未遂的经历。他说他找不到活着的意义，但因为害怕，在窗口前退了回来。我忘了我是怎么宽慰他，可能只是一些屁话。再后来，他休学一年，去年回学校考研，我们又联系一次。他还是那样温和，笑着说考不上就找工作吧。但那时的我并不知道，他瞒着所有人把考研方向改成了心理学。我的心越跳越快，借钱一定是有什么事情的。但我这次面对的完全是另一个人，飞快的语速，不断的反驳，一套一套的说辞，以及他的自我称谓：神。经过一个多小时的真假难辨的对话，我勉强梳理出了他的故事。他需要五百块钱去给他的女友买吃的。他的女友，一个大一的，在高中就抑郁症发作过的女生，总是对他提出购物的要求。而他十分珍视这段感情，有求必应。慢慢的，他的网贷账户便达到四万的欠款。紧接着，他找到了网络赌彩来填补这巨大的窟窿。他问我，你相信赌神存在吗？你知道赌博十赌九输家破人亡吗？但我告诉你，我就是那十分之一！他自以为发现了赌彩的秘诀，并且可能是用心理学知识，把自己拔高到了常人无法企及的纬度，不仅在金钱上还有观念上。同时坚信自己可以给别人洗脑，他将拥有的财富将足以毁灭世界。他不断的强调着：我轻生的事情我只跟你一个人说过，我们是最好的朋友，我可以把我成为神的秘诀告诉你，我现在完全不怕死，你对我最好，你懂我，你信我，你就能理解我说的。。。

有点难受，写不下去了。我联系了他的父母，他保证不再买彩票了，但同时，却仍在私聊中对我说：你还没有删我，说明你信我！我就知道我可以洞察人心，我是神，你也会成为神，你现在不理解，你回去慢慢想，压力别太大。
凌晨，我删了他的微信好友，12点44，他用他妈的微信号骂了我。我把他妈也删了。

4.19
一：cs61b 36.Splay trees  hw9
二：os

非连续存储管理

页式存储管理：
页面：将逻辑地址空间(进程地址空间)划分为大小相等的部分，从0开始编号，典型大小：4K 4M
页框：将内存物理地址空间划分为同样的大小相等部分，从0开始编号
分配规则：以页面为单位分配，按进程需要的页面数分配，逻辑上相邻的页面，在内存里不一定相邻
地址转换：由逻辑地址(页号+页内地址)的页号去页表里查出页框号，再与页内地址拼接成物理地址
页表：页表存放在内存中，里面的页表项记录了逻辑页面号和物理内存页框号的映射关系
段式存储管理：
用户进程地址空间：按程序自身的逻辑关系划分为若干程序段
内存空间：动态的划分成不同长度的区域，称为物理段
分配规则：以段为单位进行分配，每个段在内存中占据连续的空间，各段之间不一定相连
逻辑地址：段号+段内地址，不是由机器自动划分，是由用户显式给出的
地址转换：由逻辑地址中的段号查段表，得到在内存中对应的起始地址，再与段内地址计算出物理地址
段表：每个段表项纪录逻辑段号对应的物理段的起始地址和长度
段页式存储管理：
用户进程：先按照段划分，每一段再按照页面划分。
内存划分：同页式存储
内存分配：以页为单位
逻辑地址：段号+页号+页内地址
对每一个进程：包含一个段表（纪录每一段的页表起始地址和页表长度），若干个页表

虚拟存储技术

（虚存：是对内存的抽象，把内存和磁盘有机的结合起来使用，得到一个容量很大的“内存”）

地址保护：
保证每个进程有独立的地址空间
保证进程访问合法的地址范围，防止地址越界
保证进程的操作合法，防止访问越权（eg：只读）
虚拟页式（虚拟存储技术+页式存储管理方案。即以CPU调度时间和磁盘的空间换取内存空间，这是OS中的资源转换技术）
基本思想：进程开始执行之前，只装入部分页面或不装入任何页面，之后再动态的装入其他页面（请求调页和预先调页），若此时内存满，则需要某种算法置换出内存中的某个页面
页表中的页表项：
页框号：物理页面号
有效位：是否装入内存
访问位：是否被访问过
修改位：是否在内存中被修改过
保护位：读写权限
多级页表：页表占据太多内存空间，无法连续存放，需要引入页目录，即页表的页表
地址转换：从虚拟地址空间出发：虚拟地址->查(多级)页表->得到页框号->物理地址
反转（倒排）页表：从物理地址空间出发：建立一张页表，其中页表项纪录某进程的某个虚拟地址与页框号的映射关系
页面置换算法：当有效位非真，内存满时，需要选择内存中的页面置换出来
最佳页面置换算法OPT：置换以后不再需要的页面（理想的，不可实现，可作为衡量其他算法性能的标准）

先进先出算法FIFO：用页面链表实现(queue)
第二次机会算法SCR：先用FIFO选出第一个页面，若其访问位为真，则保留它，并将访问位置零，最后放到链尾
时钟算法CLOCK：针对SCR会有摘掉头页面挂到尾部的操作，将链表优化为环形，设置一指针，通过移动指针选择置换页框
最近未使用算法NRU：根据访问位R和修改位M选择最近未使用过的页框。
具体分为：1. !R,!M  2. !R,M  3. R,!M   4. R,M四类页面，利用时钟算法实现方式，每次扫描整个页框环，若存在1类页框，则随机选一个置换，否则再扫描一遍寻找2类页框，以此类推

最近最少使用算法LRU：选择最后一次访问时间距今最远的一页置换，即置换未使用时间最长的一页。
性能最好，最接近OPT
实现开销大：需要设置时间戳
最不经常使用算法NFU：选择访问次数最少的页框置换
LRU的一种软件近似实现
需要软件计数器
老化算法AGING：模拟LRU，计数器不断右移一位衰减，被访问时在高位加一，最后选取计数器最小的置换

工作集模型：根据程序局部性原理，工作集指在某一段时间内进程执行所需要的页面集合。置换时选择不在工作集的页面。

三：计网第二章：
物理层
物理层解决：如何在链接各种计算机的传输媒体上传输数据比特流，而不在意具体的传输媒体。
物理层主要任务：确定传输媒体的接口特性
机械特性：接口形状，引线数目等
电气特性：规定电压范围
功能特性：规定-5V表示0，+5V表示1
过程特性：规定链接时各个部件的工作步骤

数据通信基础

                                          

相关术语：
数据 信号 模拟信号 数字信号 码元(数字信号中代表离散值的基本波形）
信道：表示向一个方向传送信息的媒体。通常通信线路往往包含一条发送信道和一条接收信道。
单向通信：单工通信
双向交替通信：半双工通信（对讲机）
双向同时通信：全双工通信（手机）
基带信号：来自信源的信号，直接表达了要传输的信息。无法远距离传播
带通信号：将基带信号经过载波调制后的信号。可以远距离传播
根据载波的振幅 频率 初始相位随数字信号而变化分为：调幅、调频、调相
常用编码：
单极性不归零码：只有一个电压值，有电压为1，无电压为0，充满整个码元时间
双极性不归零码：用正负电压分别表示1和0，充满整个码元时间
单极性归零码：在一个码元时间t内，只持续一段时间，其余时间归零
双极性归零码：在一个码元时间t内，只持续一段时间，其余时间归零
曼彻斯特编码：一个时钟周期、即一bit内有跳变时规定0或1，可以表示没有数据传输(即没有跳变)
差分曼彻斯特编码：根据bit之间是否有跳变规定后一个bit内的跳变是0或1，抗干扰性更强
奈氏准则：在任何信道中，码元传输速率存在上限，若超过，会出现码间串扰，接收端不可识别码元
香农公式：确定了信道的极限信息传输速率，信道的带宽越大，信噪比越大，极限传输速率越高。

信道复用技术
频分复用：不同用户占用不同的频率带宽资源
时分复用：不同用户在不同时间占用同样的频带宽度
波分复用：光的频分复用
码分复用：用m个码片对码元进行编码，在接收端利用码片的正交特性用相同码片解码。

宽带接入方法
非对称数字用户线ADSL：用数字技术对现有模拟电话用户线进行改造
光纤同轴混合网HFC：在有线电视网的基础上开发
FTTx技术：光纤到户FTTH（fiber to the home）

4.20
一：shoulder day
seated shoulder press（20*10reps 40*10reps*3sets 50*10reps*2sets）
cable lateral raise（30*10reps*3sets 20*15reps*3sets）
rear delt fly（20*12reps*3sets）
external rotation（30*10reps*3sets）
二：implements Dijkstra and topological sort algorithms in graph
三：听了一场民族音乐会，大阮有点意思。。

ps：得知他已经被送到医院了，没发生什么危险，算是个好消息把。。脑子里总是浮现起他说的话：你不知道我从小开始就多么刻苦的练习网球，可是我第一次代表学校比赛就把腿摔断了，我经历了太多不幸，不是我不努力，这就是造化弄人你懂吗。。 哎，希望每个好人都能被善待吧，希望遭遇不顺时都能找到一个出口，希望他早日康复。

楼主加油，很厉害~顺便为什么图片都是来自qq空间不可用。

4.20 复习springmvc 看了之前实习的项目

lz好能坚持呀，加油加油

lxrmmc921025 发表于 2018-4-21 00:43
楼主加油，很厉害~顺便为什么图片都是来自qq空间不可用。

我也不知道啊。。不过我自己都能看到

楼主帖子很干货~加油加油！

4.21
一：implements kruskal and prim algorithm of graph 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：中午打了会台球，天气又闷又潮，架杆的手总是很涩，带上手套又娘又滑。。我要是开个台球馆，就弄一套通风除湿设备，把环境温度湿度控制好，让手上的摩擦系数控制在最舒服的范围。。
pps：晚上和阿坚去大保健，技师竟然对我说，你这小胖子柔韧性还挺好的啊。。。哪小。。哪胖。。