常识：调度
有稀缺需要共享的资源，就会产生调度机制
有如下几种调度机制
进程调度
磁盘调度
设备争用总线
设备控制器：中断机制
IO设备的分配和释放
进程访问共享缓冲区
网络通信中某一层协议传输报文的复用和分用
局域网征用信息道
数据库访问的并发控制
这类调度机制解决了一个问题：资源如何复用
共享的常识是复用和分用，设计算法的精髓是折衷，代价和效率的折衷，使得效用最佳。
算法：FCFS SSTF SCAN CSCAN NStepSCAN FSCAN
常识：存储的目的是为了存取，储存的精髓是冗余
存储空间的分配和回收必然需要冗余的数据
提高存取效率的方法-缓存就是在存储冗余数据
数据可靠存储中，无论是备份日志，检错，纠错实质上也是冗余
数据可靠交换中，校验码，同步位，报文的header和重传实质上也是冗余
问题：
1.存储代价
2数据的不一致性
分析存储的关键是有效存储
最后效用最高的解决办法就是折衷，还有程序的局部性原理
具体实例，银行中的灾备机制，两地三备份。
常识：替换
替换的常识就是，从图书馆借了20本书，我在床头放两本是平时看的，看完去书架上替换。
cache的替换算法：
最佳位置算法:难以实现
FIFO:没有利用局部性原理，会产生抖动现象
LRU：TCP中RTT的估算，个人征信记录都使用了老化算法
CLOCK
NRU
工作集
常识：阻塞
阻塞是多道程序设计的基础，需要解决时间和空间的共享，即是分时复用和存取冗余上的问题
常识：查找
数据库查询，编译和调试程序时符号表的查询，路由器转发（forward分组（packet）时查询转发表（不同于路由表），文件检索，使用搜索引擎查询。
影响查询效率的因素有：
1）查找条目的规模2）存储条目所采用的存储结构。
网络的精缩是更新发送，retransmission
1.发送方如何获得数据发送失败的信息，确认机制，超时机制
2.接发方如何却分首次发送的数据和重传的数据
3.发送方如何发避免过多重传，backoff算法
4.重传有什么问题？导致用塞问题
5.重传机制作用，过多重传导致效率变低。
一、TCP\\\\IP协议体系
一个数据包从协议栈顶向底移动时，是一个不断封包复用服务的过程，而从底部向顶移动时，是一个不断解包分用递交的过程。对等层之间进行通信，对等层之间通信所采用的数据单元（CPU）依次为：TCP——>segment,UDP——>Datagram,IP ——>Datagram,Ethernet/WLAN——>Frame。从应用层看，对等层的通信是使用和文件类似的socket进行进程间通信，从IP层看，是IP地址标定的两台主机之间进行主机到主机的通信，从IP层看，是IP地址标定的两台主机之间进行主机到主机的通信，从更一下层看，是两个接口（控制器）之间的通信。下层的协议为上层提供服务支持，上层协议调用下层的功能而无需理解技术细节。总结之，三句话：对等层通信，上层调用下层，上层服务下层。这种层次化的设计的好处是层与层之间保持了相对独立的松耦合，利用设计和研究。
二、 PPP和 Ethernet,WLAN处于物理层和链路层的最常见的三种接入网。
信道和数据链路不同，信道是数据传送的物理载体，多个主机共享一条信道，存在复用和分用的问题。点对点通信采用了时分，频分，波分，码分的方式共享信道，多对通信之间彼此隔离，不存在冲突竞争。广播通信的主机以广播的方式发送信息，其它主机均可收到，彼此之间不存在隔离，如果多个主机同时发送信息，信号叠加干扰变形，无法进行比特判别。所以广播的方式通信时，主机间存在争用资源，一台主机发送，其它主机应保持“安静“，并且要保证主机彼此之间公平的使用共享资源，所有要采用的多路访问控制的机制。
数据结构算法
时间消耗越少，一般空间消耗越大，存储越冗余 空间消耗越少，一般时间消耗越大，计算越冗余 空间和时间的消耗如果都降低的话，人的智力和脑力消耗越大，包括人思考所用的时间和记忆力。
数据结构其实就是人的头脑中的三种逻辑模式（先后关系[线]，层次关系[树]，交互关系[图]）如何用计算机存储模式(顺序存储[冯诺依曼机的特点]和链接存储[间接寻址]）来实现
网友评论