目录

1.操作系统原理

1.1 进程的概念

nbsp;1.2 进程的状态

 1.3 进程的控制结构

1.4 进程的切换 

1.5 线程

1.6 进程的调度

1.7 进程间通信的概述

1.8 管道

1.9 消息队列

1.10 共享内存

1.11 信 量

1.12 信

 1.13 socket通信

2.计算机 络协议

2.1 从一个HTTP请求来看 络分层原理

/p>

2.2 HTTP协议

 2.3 HTTP请求的完整过程

 2.4 TCP协议

2.5 https协议

3.数据结构与算法

3.1 数据结构与算法入门基础

3.2 算法特征，时间复杂度，空间复杂度业务场景

3.3 数组与链表

 3.3.1 堆，桟区别和面试题

3.3.2 为什么计算机编程语言要从下标0开始/p>

 3.3.3 链表

3.3.4 课后作业：如何设计一个LRU淘汰算法/p>

3.3.5 数组和链表的区别

3.4 桟

3.4.1 括 匹配

 3.4.2 加减乘除计算

3.4.3 如何设计一个浏览器的前进和后退功能

3.5 队列

3.5.1 课后作业

3.5.2 优先队列

3.5.3 阻塞队列 

3.5.4 线程池问题 

1.操作系统原理

1.1 进程的概念

进程是操作系统管理任务的最小单位。除了进程，还有线程，线程是为了处理进程中更细小的任务，操作系统中的CPU为了处理线程中的任务需要经常切换，这就涉及到串行，并行，并发的概念。

串行：一个任务执行完毕，另外一个任务才能执行。

并行：在单位时间内，多个任务同时执行。现在的多核CPU支持多个任务处理。

并发：在单位时间内，只能处理一个任务，其他任务获取到CPU时间片就会开始执行另外一个任务，操作系统本身会进行用户态和内核态的切换。

 1.3 进程的控制结构

进程内部通过一种PCB结构来存储相应的信息，PCB数据结构：进程管理，存储管理，文件管理。PCB是进程存在的唯一标识，进程消失，PCB也随之消失。

1.4 进程的切换 

进程中一般存在的状态:新建，就绪，运行，阻塞，结束。在真实得java类Thread中通过以下6种状态控制：

线程切换从就绪到运行需要涉及到时间片得切换，需要牵涉到不同得线程调度算法

1.5 线程

线程是CPU调度得最小单位，一个进程可以有多个进程。多线程得切换不需要切换虚拟内存得资源，只需要切换线程私有得寄存器，程序计数器，虚拟机栈即可。

1.6 进程的调度

进程通过调度程序来控制哪些线程可以拿到时间片运行程序，哪些不能运行。常用得调度算法分为两种：非抢占式调度算法和抢占式调度算法。

调度得指标分为5种：CPU利用率，系统吞吐率，周转时间，等待时间，响应时间。

常用得算法：

        先来先服务：哪个进程先来，先使用CPU时间片

        时间片轮转调度：不管什么任务都使用同样得时间处理。

        最短作业优先：哪个作业时间最短先处理哪个，如果有多个最短作业会导致长作业任务无法处理。

        最短剩余剩余时间：哪个任务剩余时间最短处理哪个进程。

        多级反馈队列调度：通过优先级和任务时间判断，分别处理。VIP客户在VIP通道处理。普通客户在普通通道处理。

1.7 进程间通信的概述

进程一般都有独立得用户空间和内存资源，一般是不可以互相通信，但是内核空间是共享得，我们可以通过内核空间进行通信。常用得进程通信得方式：内核空间，管道，信 量，信 ，消息队列。

1.8 管道

管道在linux分为匿名管道和命名管道，匿名管道是单向得，输入完以后就会关闭，命名管道是双向得，在输入以后不会关闭只有读取以后才会关闭。管道得效率很低。

1.9 消息队列

消息队列是内核空间得消息链表，我们只需要将消息通过定义发送方和接收方得消息体结构即可。消息队列是内核空间需要经过用户空间得copy才能通信。

1.10 共享内存

共享内存通过虚拟内存跟真实物理地址得映射，这样就不需要用户空间和内核空间得数据复制开销，大大加快了进程通信，但是在多个进程写入时可能出现覆盖得情况，导致数据不一致得情况。

1.11 信 量

信 量是一个整型的计数器，用来实现互斥和同步。

互斥信 量机制：我们将初始值设置为1，如果执行了P操作，将值改为0，代表内存共享可用，执行了V操作，将值改为-1，代表内存不可用，阻塞进程。

同步信 量机制：初始值设置为0，如果执行了P操作，将值改为-1，代表前一个进程还没生产数据，阻塞，如果执行了V操作，将值改为1，代表前一个进程生产完数据，可以执行。

1.12 信

信 是进程中的一种异步通信机制，我们只需要输入相应的指令即可达到相应的命令。

kill -l 查看信

kill -9 进程 (杀死进程) 9对应sigkill信 。

 1.13 socket通信

上述的几种进程通信方式都属于本机进程通信，如果需要跨 络我们就需要socket套接字来处理。socket内部的处理就需要IP协议://IP:端口 /路径的形式找到相应的机器进程通信。除了这种以外，java还提供了一种RMI通信，只需要继承remote接口即可实现两台java虚拟机进程的通信。 

2.计算机 络协议

2.1 从一个HTTP请求来看 络分层原理

http请求要解决的问题
A主机->数据丢包->数据重复->数据完整性校验->数字转换模型信 ->…->信 衰减->B主机。

为了解决以上问题主流的两种 络分层模型：OSI-7层模型和TCP/IP协议模型。

2.2 HTTP协议

http协议是一个无状态的，以请求/应答方式运作的协议，它采用可扩展的语义和自描述信息格式，与基于 络的超文本信息系统交互。

它主要的组成部分：

        1.起始行：描述请求行和响应行的基本信息

        2.头部字段集合:以key-value形式描述基本信息

        3.消息正文:以文本或图片，视频等形式的二进制数据组成。

 2.3 HTTP请求的完整过程

平常访问的http地址：http/https://(ip:端口 /域名)/URI，http请求分以下几步：

1.DNS域名解析：在解析ip/域名的过程的过程中会先去浏览器缓存查找，如果是谷歌浏览器可以从chrome://net-internals/#events路径拿到浏览器缓存，如果能查到返回，不能查到就会去C:WindowsSystem32driversetchosts文件路径下查找，查不到就去DNS的根服务器查找，查不到回去国际DNS服务器查找，查到就进行下一步。

2. http三次握手协议，https还会有一次TLS握手。

3. 浏览器http请求应用服务器

4. 应用服务器返回http响应 文

5. 如果有其他请求重复3-4步，没有会生成一个DOM结构的树渲染页面

6. 第四次挥手：关闭链接。

 2.4 TCP协议

 TCP协议是一个面向连接，可靠的，基于字节流的传输层协议。

TCP协议传输过程：基于连接，数据传输之前要建立链接，客户端的数据是分段的请求，客户端发送给服务端的请求，服务端需要经历重排序保证与客户端的发送顺序一致，同时处理完毕需要发给客户端响应 文，如果客户端没有收到响应 文，经过一定的超时机制以后会重发 文。

 TCP关闭链接过程如下：中间Time_wait状态(2MSL)等待2次接收发送 文时间的原因是需要确认服务端接收到ack 文，不会一直发送fin 文；还有一个原因是close_wait状态确认有未完成的数据不会造成下一次TCP连接数据紊乱。

 TCP是一个基于字节流的协议，TCP不管是什么的数据包，只管传输，经过重排序和数据丢包重传的操作最后给应用程序的是客户端发送的字节流数据。

 数据可靠性传输保证

1.如果ack 文没有收到会经过等待超时机制重传

2.如果请求 文没有收到会经过一次请求返回时间重传 文

3.上述两种方法比较消耗性能，为了节省性能，还有一种滑动窗口算法计算丢包的数据，通过确认最后一个字节数据包是否收到，如果没有收到，就去看前面连续的数据包是否收到，收到就不重传，没收到就重传后续数据包。

2.5 https协议

 https协议的诞生是为了保证http协议的安全，因为http协议天生明文的特点，请求和返回 文都可能被篡改，https协议在http协议和tcp协议之间加上了一层SSL/TSL协议对请求和返回 文加密。

 常用的加密算法：

1.摘要算法：MD5，sha1，sha2,sha1 256

2. 对称加密算法：加解密都是用相同密钥

3.非对称加密算法：加密使用公钥，解密使用私钥；如果加密使用私钥，解密使用公钥；

https保证安全原理如下：

1.http三次握手协议

2.加密套件选择，验证证书，生成随机密码，使用非对称加密算法获取密码

3. 使用对称加码算法传输保证性能。

我们可以通过查看证书设置查看证书的有效期，颁发者，使用的算法等信息。

3.数据结构与算法

3.1 数据结构与算法入门基础

如何判断一个数是2的N次方/p>

输入：2,4,8，16

输出:Y/N；

3.2 算法特征，时间复杂度，空间复杂度业务场景

算法的五个特征：有穷性，确定性，可行性，有输入，有输出。

设计原则：正确性，可读性，健壮性

算法目的：高效率，低存储

算法标准：

        时间复杂度(高效率)：运行一个程序需要的时间

        空间复杂度（低存储）: 运行一个程序占用的内存

计算时间复杂度的业务场景：

        1. 计算接口运行时间：常用的压测，冒烟，基本都是黑盒测试的范畴，测试人员对业务逻辑不懂或者数据不准确。可以自己计算时间复杂度。

时间复杂度表示法：大0表示法。O(N)/O(nlogn)

计算空间复杂度的业务场景：

        1.找使用了内存的地方：比如Array，arrayList，linkedList，map，queue等地方。