美团C++开发面试2

操作系统

1.进程线程区别 以及进程线程间通信

进程线程区别：

进程是程序的⼀次执行过程，是⼀个动态概念，是程序在执行过程中分配和管理资源的基本单位，每⼀个进程都有⼀个自己的地址空间。
线程是CPU调度和分派的基本单位，它可与同属⼀个进程的其他的线程共享进程所拥有的全部资源。
区别
① ⼀个线程只能属于⼀个进程，而⼀个进程可以有多个线程，但至少有⼀个线程。线程依赖于进程而存在。
② 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。
③ 进程是资源分配的最小单位，线程是CPU调度的最小单位；
④ 系统开销： 由于在创建或撤消进程时，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，进程切换的开销也远大于线程切换的开销。
⑤进程间不会相互影响，而一个线程挂掉可能导致整个进程挂掉。

线程通信

1.互斥锁
　　- mutex;
　　- lock_guard (在构造函数里加锁，在析构函数里解锁）
　　- unique_lock 自动加锁、解锁
2.读写锁
　　shared_lock
3.信号量
　　c++11中未实现，可以自己使用mutex和conditon_variable 实现

进程通信

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。
1.管道：
管道主要包括无名管道和命名管道:管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。
1.1 普通管道PIPE：
它是半双工的（即数据只能在⼀个方向上流动），具有固定的读端和写端
它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）
它可以看成是⼀种特殊的文件，对于它的读写也可以使⽤普通的read、write等函数。
但是它不是普通的文件，并不属于其他任何⽂件系统，并且只存在于内存中。
1.2 命名管道FIFO：
FIFO可以在⽆关的进程之间交换数据
FIFO有路径名与之相关联，它以⼀种特殊设备文件形式存在于文件系统中。
2.IPC
2.1 消息队列
消息队列，是消息的链接表，存放在内核中。⼀个消息队列由⼀个标识符（即队列ID）来标记。 (消息队
列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点)具有写权限得进程可
以按照⼀定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信
息；
特点：
消息队列是⾯向记录的，其中的消息具有特定的格式以及特定的优先级。
消息队列独⽴于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
消息队列可以实现消息的随机查询,消息不⼀定要以先进先出的次序读取,也可以按消息的类型读取。
2.2 信号量semaphore
信号量（semaphore）与已经介绍过的 IPC 结构不同，它是⼀个计数器，可以⽤来控制多个进程对共享
资源的访问。信号量⽤于实现进程间的互斥与同步，⽽不是⽤于存储进程间通信数据。
特点：
信号量⽤于进程间同步，若要在进程间传递数据需要结合共享内存。
信号量基于操作系统的 PV 操作，程序对信号量的操作都是原⼦操作。
每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
⽀持信号量组。
2.3 信号signal
信号是⼀种⽐较复杂的通信方式，⽤于通知接收进程某个事件已经发⽣。
2.4 共享内存（Shared Memory）
它使得多个进程可以访问同⼀块内存空间，不同进程可以及时看到对⽅进程中对共享内存中数据得更
新。这种⽅式需要依靠某种同步操作，如互斥锁和信号量等
特点：
共享内存是最快的⼀种IPC，因为进程是直接对内存进行存取
因为多个进程可以同时操作，所以需要进行同步
信号量+共享内存通常结合在⼀起使用，信号量用来同步对共享内存的访问
3.套接字SOCKET：
socket也是⼀种进程间通信机制，与其他通信机制不同的是，它可用于不同主机之间的进程通信。

2. 操作系统本身使用什么通信？

没答出来 后面想了想操作系统是在内核栈应该使用的是直接通信？

❓❓

3. 死锁相关

死锁发⽣的四个必要条件如下：
互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直⾄
占有该资源的进程使⽤完成后释放该资源；
请求和保持条件：进程获得⼀定的资源后，⼜对其他资源发出请求，但是该资源可能被其他进程占
有，此时请求阻塞，但该进程不会释放⾃⼰已经占有的资源
不可剥夺条件：进程已获得的资源，在未完成使⽤之前，不可被剥夺，只能在使⽤后⾃⼰释放
环路等待条件：进程发⽣死锁后，必然存在⼀个进程-资源之间的环形链

解决死锁的⽅法即破坏上述四个条件之⼀，主要方法如下：
① 资源⼀次性分配，从而剥夺请求和保持条件
② 可剥夺资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可剥夺的条件
③资源有序分配法：系统给每类资源赋予⼀个序号，每个进程按编号递增的请求资源，释放则相反，
从而破坏环路等待的条件

4. 多路复用相关

1. 什么是IO多路复用
   一句话解释：单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力。、

IO多路复用在Linux下包括了三种，select、poll、epoll，抽象来看，他们功能是类似的，但具体细节各有不同：首先都会对一组文件描述符进行相关事件的注册，然后阻塞等待某些事件的发生或等待超时。IO多路复用都可以关注多个文件描述符，但对于这三种机制而言，不同数量级文件描述符对性能的影响是不同的。

数据库

1. where orderby having groupby的执行顺序

Where, Group By, Having, Order by。

计算机网络

1. 浏览器输入url发生了什么？

过程	使用的协议
1.浏览器查找域名的IP地址(DNS查找过程：浏览器缓存、路由器缓存、DNS缓存)	DNS:获取域名对应IP
2.浏览器向web服务器发送一个HTTP请求(cookies会随着请求发送给服务器)	TCP:与服务器建立TCP连接
3.服务器处理请求(请求 处理请求&它的参数、cookies、生成一个HTML响应)	IP：建立TCP协议时，需要发送数据，发送数据在网络层使用IP协议
4.服务器返回一个HTML响应	OSPF：IP数据包在路由器之间，路由选择使用OSPF协议
5.浏览器开始显示HTML	ARP：路由器在与服务器通信时需要将ip地址转换为MAC地址，需要使用ARP协议
	HTTP: 在TCP建立完成后，使用HTTP协议访问网页

体来说分为以下几个过程:

1. DNS解析

2. TCP连接

3. 发送HTTP请求

4. 服务器处理请求并返回HTTP报文

5. 浏览器解析渲染页面

6. 连接结束

具体可以参考下面这篇文章：

• https://segmentfault.com/a/1190000006879700

HTTPS相关

《图解HTTP》这本书中曾提过HTTPS是身披SSL外壳的HTTP。HTTPS是一种通过计算机网络进行安全通信的传输协议，经由HTTP进行通信，利用SSL/TLS建立全信道，加密数据包。
HTTPS使用的主要目的是提供对网站服务器的身份认证，同时保护交换数据的隐私与完整性。

PS:TLS是传输层加密协议，前身是SSL协议，由网景公司1995年发布，有时候两者不区分。

HTTP特点：

①无状态：协议对客户端没有状态存储，对事物处理没有“记忆”能力，比如访问一个网站需要反复进行登录操作
②无连接：HTTP/1.1之前，由于无状态特点，每次请求需要通过TCP三次握手四次挥手，和服务器重新建立连接。比如某个客户机在短时间多次请求同一个资源，服务器并不能区别是否已经响应过用户的请求，所以每次需要重新响应请求，需要耗费不必要的时间和流量。
③基于请求和响应：基本的特性，由客户端发起请求，服务端响应
④简单快速、灵活
⑤通信使用明文、请求和响应不会对通信方进行确认、无法保护数据的完整性

HTTPS特点：

基于HTTP协议，通过SSL或TLS提供加密处理数据、验证对方身份以及数据完整性保护
通过抓包可以看到数据不是明文传输，而且HTTPS有如下特点：
①内容加密：采用混合加密技术，中间者无法直接查看明文内容
②验证身份：通过证书认证客户端访问的是自己的服务器
③保护数据完整性：防止传输的内容被中间人冒充或者篡改

混合加密：结合非对称加密和对称加密技术。客户端使用对称加密生成密钥对传输数据进行加密，然后使用非对称加密的公钥再对秘钥进行加密，所以网络上传输的数据是被秘钥加密的密文和用公钥加密后的秘密秘钥，因此即使被黑客截取，由于没有私钥，无法获取到加密明文的秘钥，便无法获取到明文数据。
数字摘要：通过单向hash函数对原文进行哈希，将需加密的明文“摘要”成一串固定长度(如128bit)的密文，不同的明文摘要成的密文其结果总是不相同，同样的明文其摘要必定一致，并且即使知道了摘要也不能反推出明文。
数字签名技术：数字签名建立在公钥加密体制基础上，是公钥加密技术的另一类应用。它把公钥加密技术和数字摘要结合起来，形成了实用的数字签名技术。
收方能够证实发送方的真实身份；
发送方事后不能否认所发送过的报文；
收方或非法者不能伪造、篡改报文。

长连接

HTTP 的请求是在 TCP 连接的基础上发送的，而 TCP链接分为长连接和短连接 。

长连接：HTTP 发送请求时，要先创建一个 TCP 连接，并在 TCP 连接上把 HTTP 请求的内容发送并且接收完返回，这是一次请求完成，浏览器与服务器进行协商是否关闭 TCP 链接，若不关闭 TCP 连接会有一定的消耗，好处是如果还有请求可以直接在这个 TCP 连接上发送，不需要经过创建时三次握手的消耗。

短连接：若关闭 TCP 连接，下次请求需要重新创建，这时会有网络延迟的开销，好处是每次请求完关闭 TCP 连接，减少客户端和服务端连接的并发数。

实际情况中，网站的并发量比较大，如果每次都重新创建连接，导致创建过程发生太多，导致创建 TCP 连接的开销，比保持长连接还要高一些。而且长连接可以设置关闭时间，在一定时间内没有请求自动关闭。一般情况都会保持长连接。

算法

翻转链表（leetcode上有）

①迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

②递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

参考

[1] 题目：https://www.nowcoder.com/discuss/628674?type=all&order=time&pos=&page=1&channel=-1&source_id=search_all_nctrack
[2]多路复用：https://zhuanlan.zhihu.com/p/115220699
[3]数据库：https://blog.csdn.net/rj532029887/article/details/39260977
[4]HTTPS：⭐https://blog.csdn.net/xiaoming100001/article/details/811096
[5]长连接：https://zhuanlan.zhihu.com/p/45139114