牛客网 8-1 网络基础操作系统编译与体系结构 30题知识点总结笔记

1、系统内可以有无父进程的进程。init进程没有父进程

2、死锁
定义：在一个进程集合中，所有的进程都在等待只能由该进程集合中的其它进程才能引发的事件，这就是死锁
解释：由于进程集合中的所有进程都在等待集合中的其它进程引发唤醒该进程的事件，所以所有进程都会阻塞而无法向前推进。
一般大多数的等待事件都是释放进程集合中其它进程所占有的资源，也叫资源死锁。
资源死锁的四大必须条件：
1>互斥条件:
每个资源要么已经分配给了一个进程，要么是可用的。即就是资源非共享
2>占有和等待条件:
已经得到资源的进程还能继续请求新的资源
3>不可抢占条件:
当一个资源分配给了一个进程后，其它需要该资源的进程不能强制性获得该资源，除非该资源的当前占有者显示地释放该资源
4>环路等待：
死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，环路上的每个进程都在等待下一个进程所占有的资源
死锁预防
防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。
1) 破坏互斥条件
如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。
2) 破坏不剥夺条件
当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。

该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。
3) 破坏请求和保持条件
釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。

这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。
4) 破坏循环等待条件
为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。

这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。
死锁避免
避免死锁同样是属于事先预防的策略，但并不是事先釆取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。
1. 系统安全状态
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，让进程等待。

所谓安全状态，是指系统能按某种进程推进顺序( P1, P2, ..., Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2, ..., Pn 为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可以避免进入死锁状态。
2. 银行家算法银行家算法是最著名的死锁避免算法。它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

3、虚存容量=min(内存容量+外存容量，2^N)(N为计算机的地址总线的长度)

4、tcpdump 是简单可靠网络监控的实用工具
netstat 显示网络有关的信息，比如套接口使用情况、路由、接口、协议等
ifconfig 是查看活动的网卡信息
top 显示活动进程方面的情况

5、默认blocksize=4k情况下，Ext3文件系统支持的最大文件大小是 ______。
【牛客网 8-1 网络基础操作系统编译与体系结构 30题知识点总结】ext3还是使用15个inode来查找数据块，前12个为直接数据块，直接指向存储数据的数据块，接下来分别为一级间接块，二级间接块，三级间接块.
最大文件：
前面直接指向12个数据块，一级间接块最大为block size / 4，block size就是数据块的大小，因为一个索引是4个字节，所以除以4，这样计算下来，最大的文件可以使用的总块数为:12 + (block size/4) + (block size/4)^2+ (block size/4)^3，如果block size大小为4K，则为(12 + 2^10 + 2^20 + 2^30) * 2^12 约等于4T。

6、引入缓冲的主要原因包括：缓和CPU与I/O设备间速度不匹配的矛盾；减少对CPU的中断频率，放宽对中断响应时间的限制；提高CPU和I/O设备之间的并行性。所以采用缓冲技术，可减少对CPU的中断次数，从而提高系统效率。

7、速度：硬盘〉U盘〉光盘〉软盘，不然软盘也不会被淘汰了

8、
对滑动窗口不正确的描述是：

能够提高传输效率

能够提高信道利用率

能够进行流量控制

能够防止报文段顺序出错（x）

提高了整个网络的吞吐率，解决了端到端的通信流量控制问题，允许接收端在拥有容纳足够数据的缓冲之前对传输进行限制

9、作业：向计算机提交任务的任务实体；
作业是指用户在一次解决或一个事务处理过程中要求计算机系统所做的工作的集合，包括用户程序、数据、作业说明书等。
进程：执行实体，是资源分配的基本单位；
线程：处理机调试的基本单位；
程序：先简单粗暴地理解为代码吧。

10、每个进程都有一个页表。在进程执行过程中，将其调入到内存中。

11、单道程序系统几个特点： 1. 资源独占性
任何时候，位于内存中的程序可以使用系统中的一切资源，不可能有其他程序与之竞争
2. 执行的顺序性
内存中只有一个程序，各个程序是按次序执行的。在做完一个程序的过程中，不可能夹杂进另一个程序执行
3. 结果的可再现性
只要执行环境和初始条件相同，重复执行一个程序，获得的结果总是一样的
4. 运行结果的无关性
程序的运行结果与程序执行的速度无关。系统中的作业以串行的方式被处理，无法提高CPU、内存的利用率
本来就是有序的，故不需要同步互斥

12、程序的局部性原理是指在一段时间内，一个程序执行往往呈现高度局部性，对内存访问时不均匀的，这种局部性包括时间局部性和空间局部性。

13、存储保护，是指给外置的存储设备加个保护程序，写不进去数据，也删不掉数据。当多个用户共享主存时，为使系统能正常工作，应防止由于一个用户程序出错而破坏其它用户的程序和系统软件，还要防止一个用户程序不合法的访问不是分给它的主存区域。为此，系统提供存储保护。
通常采用的方法是：存储区域保护和访问方式保护。

14、
一般是客户端先向服务器发送请求：
第一次握手发送一个序列号；
第二次握手的序列号是单独发送的，第二次握手的确认号是第一次握手序列号+1；
第三次握手的序列号是第二次握手的确认号，第三次握手的确认号是是第二次握手的序列号+1；

15、/etc/hosts 主机名到 IP 地址的映射关系的文件
/etc/resolv.conf DNS 服务的配置文件
/etc/gateways 建立动态路由需要用到的文件

16、在TCP/IP建立连接过程中,客户端和服务器端的状态转移

经历SYN_RECV状态

经历SYN_SEND状态

经历ESTABLISHED状态

经历TIME_WAIT状态

服务器在收到syn包时将加入半连接队列

17、冯诺依曼体系结构的特点是：
(1)计算机处理的数据和指令一律用二进制数表示
(2)顺序执行程序：计算机运行过程中，把要执行的程序和处理的数据首先存入主存储器（内存），计算机执行程序时，将自动地并按顺序从主存储器中取出指令一条一条地执行，这一概念称作顺序执行程序。
(3)计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成。

18、pthread_spin_lock 自旋锁，在进入阻塞队列之前先跑几个循环，然后再去尝试获取锁，直到自旋的次数超过阈值，才进入阻塞队列，此时才切换状态
关键路径上不会产生系统调用从而减少用户态到内核态的上下文切换

19、1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4）需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]

20、同一进程中的多条线程将共享该进程中的全部系统资源，如虚拟地址空间，文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈（call stack），自己的寄存器环境（register context），自己的线程本地存储（thread-local storage）。

21、以太网卡的工作模式有哪几种？

广播模式

多播传送

直接模式

混杂模式

22、X.25协议是数据终端设备（DTE）和数据电路终接设备（DCE）之间的接口规程

23、工作在应用层的协议，才有源端口与目的端口之分。

24、假设一个系统包括A到G七个进程，R到W六中资源。资源间的所有权关系，如下：
1、进程A占有资源R，请求资源S
2、进程B不占有任何资源，请求资源T
3、进程C不占任何资源，请求资源S
4、D占有资源U，请求资源S和T
5、E有资源T，请求资源V
6、F有资源W，请求资源S
7、G有资源V，需要资源U
成环路的就是死锁进程

25、cache，是内存高速缓存，而页表使用的缓存是特殊高速缓存，叫TLB。
虚存访问时首先去TLB中查找相应页表项，找到对应实地址。
如果没有找到页表项，根据页号使用普通方法找实地址，而此时的页表可能庞大，所以会
采取虚存（磁盘）保存页表，
当然也会有部分页表在内存中（主存）