Computer System

计算机系统常见问题2

计算机系统常见问题

Linux的I/O模型介绍以及同步异步阻塞非阻塞的区别（超级重要）

https://blog.csdn.net/sqsltr/article/details/92762279

https://www.cnblogs.com/euphie/p/6376508.html

（IO过程包括两个阶段：

（1）内核从IO设备读写数据和

（2）进程从内核复制数据）

  • 阻塞：调用IO操作的时候，如果缓冲区空或者满了，调用的进程或者线程就会处于阻塞状态直到IO可用并完成数据拷贝。
  • 非阻塞：调用IO操作的时候，内核会马上返回结果，如果IO不可用，会返回错误，这种方式下进程需要不断轮询直到IO可用为止，但是当进程从内核拷贝数据时是阻塞的。
  • IO多路复用就是同时监听多个描述符，一旦某个描述符IO就绪（读就绪或者写就绪），就能够通知进程进行相应的IO操作，否则就将进程阻塞在select或者epoll语句上。
  • 同步IO：同步IO模型包括阻塞IO，非阻塞IO和IO多路复用。特点就是当进程从内核复制数据的时候都是阻塞的。
  • 异步IO：在检测IO是否可用和进程拷贝数据的两个阶段都是不阻塞的，进程可以做其他事情，当IO完成后内核会给进程发送一个信号。

Epoll是Linux进行IO多路复用的一种方式，用于在一个线程里监听多个IO源，在IO源可用的时候返回并进行操作。它的特点是基于事件驱动，性能很高。

epoll将文件描述符拷贝到内核空间后使用红黑树进行维护，同时向内核注册每个文件描述符的回调函数，当某个文件描述符可读可写的时候，将这个文件描述符加入到就绪链表里，并唤起进程，返回就绪链表到用户空间，由用户程序进行处理。

Epoll有三个系统调用：epoll_create(),epoll_ctl()和epoll_wait()。

  • eoll_create()函数在内核中初始化一个eventpoll对象，同时初始化红黑树和就绪链表。
  • epoll_ctl()用来对监听的文件描述符进行管理。将文件描述符插入红黑树，或者从红黑树中删除，这个过程的时间复杂度是log(N)。同时向内核注册文件描述符的回调函数。
  • epoll_wait()会将进程放到eventpoll的等待队列中，将进程阻塞，当某个文件描述符IO可用时，内核通过回调函数将该文件描述符放到就绪链表里，epoll_wait()会将就绪链表里的文件描述符返回到用户空间。

（4） IO复用的三种方法（select,poll,epoll）深入理解，包括三者区别，内部原理实现？

（1）select的方法介绍：select把所有监听的文件描述符拷贝到内核中，挂起进程。当某个文件描述符可读或可写的时候，中断程序唤起进程，select将监听的文件描述符再次拷贝到用户空间，然select后遍历这些文件描述符找到IO可用的文件。下次监控的时候需要再次拷贝这些文件描述符到内核空间。select支持监听的描述符最大数量是1024.

（2）poll使用链表保存文件描述符，其他的跟select没有什么不同。

（3）epoll将文件描述符拷贝到内核空间后使用红黑树进行维护，同时向内核注册每个文件描述符的回调函数，当某个文件描述符可读可写的时候，将这个文件描述符加入到就绪链表里，并唤起进程，返回就绪链表到用户空间。

详见 https://www.cnblogs.com/Anker/p/3265058.html

coredump产生的条件

  1. shell资源控制限制，使用 ulimit -c 命令查看shell执行程序时的资源 ，如果为0，则不会产生coredump。可以用ulimit -c unlimited设置为不限大小。
  2. 读写越界，包括：数组访问越界，指针指向错误的内存，字符串读写越界
  3. 使用了线程不安全的函数，读写未加锁保护
  4. 错误使用指针转换
  5. 堆栈溢出

Linux理论上最多可以创建多少个进程？一个进程可以创建多少线程，和什么有关

（3） 冯诺依曼结构有哪几个模块？分别对应现代计算机的哪几个部分？（百度安全一面）

  • 存储器：内存
  • 控制器：南桥北桥
  • 运算器：CPU
  • 输入设备：键盘
  • 输出设备：显示器、网卡

如果要你实现一个mutex互斥锁你要怎么实现？

https://blog.csdn.net/kid551/article/details/84338619

实现mutex最重要的就是实现它的lock()方法和unlock()方法。我们保存一个全局变量flag，flag=1表明该锁已经锁住，flag=0表明锁没有锁住。

实现lock()时，使用一个while循环不断检测flag是否等于1，如果等于1就一直循环。然后将flag设置为1；unlock()方法就将flag置为0；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static int flag=0;

void lock(){
  while(TestAndSet(&flag,1)==1);
  //flag=1;
}
void unlock(){
  flag=0;
}
123456789

因为while有可能被重入，所以可以用TestandSet()方法。

1
2
3
4
5

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

线程之间通信：

  • 使用全局变量
  • 使用信号机制
  • 使用事件

进程之间同步：

https://www.cnblogs.com/sonic4x/archive/2011/07/05/2098036.html

  • 信号量
  • 管程

什么时候用多进程，什么时候用多线程

https://blog.csdn.net/yu876876/article/details/82810178

  • 频繁修改：需要频繁创建和销毁的优先使用多线程
  • 计算量：需要大量计算的优先使用多线程 因为需要消耗大量CPU资源且切换频繁，所以多线程好一点
  • 相关性：任务间相关性比较强的用多线程，相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。
  • 多分布：可能要扩展到多机分布的用多进程，多核分布的用多线程。

但是实际中更常见的是进程加线程的结合方式，并不是非此即彼的。

  • 孤儿进程是父进程退出后它的子进程还在执行，这时候这些子进程就成为孤儿进程。孤儿进程会被init进程收养并完成状态收集。
  • 僵尸进程是指子进程完成并退出后父进程没有使用wait()或者waitpid()对它们进行状态收集，这些子进程的进程描述符仍然会留在系统中。这些子进程就成为僵尸进程。

协程就是子程序在执行时中断并转去执行别的子程序，在适当的时候又返回来执行。

这种子程序间的跳转不是函数调用，也不是多线程执行，所以省去了线程切换的开销，效率很高，并且不需要多线程间的锁机制，不会发生变量写冲突。

那协程的底层是怎么实现的，怎么使用协程？

协程进行中断跳转时将函数的上下文存放在其他位置中，而不是存放在函数堆栈里，当处理完其他事情跳转回来的时候，取回上下文继续执行原来的函数。

在执行malloc申请内存的时候，操作系统是怎么做的？/内存分配的原理说一下/malloc函数底层是怎么实现的？/进程是怎么分配内存的？

https://blog.csdn.net/yusiguyuan/article/details/39496057

从操作系统层面上看，malloc是通过两个系统调用来实现的： brk和mmap

  • brk是将进程数据段(.data)的最高地址指针向高处移动，这一步可以扩大进程在运行时的堆大小
  • mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存，这一步可以获得一块可以操作的堆内存。

通常，分配的内存小于128k时，使用brk调用来获得虚拟内存，大于128k时就使用mmap来获得虚拟内存。

进程先通过这两个系统调用获取或者扩大进程的虚拟内存，获得相应的虚拟地址，在访问这些虚拟地址的时候，通过缺页中断，让内核分配相应的物理内存，这样内存分配才算完成。

在网络编程中不同字节序的机器发送和接收的顺序不同。

实现二维码登录通常涉及以下步骤：

  1. 生成二维码：
    • 服务器端生成一个唯一的登录标识（如随机生成的Token或临时会话ID）。
    • 使用生成的标识创建一个包含标识信息的二维码图像。
    • 将二维码图像发送给客户端，以便用户扫描。
  2. 扫描二维码：
    • 用户打开登录应用或扫描工具，并选择扫描二维码选项。
    • 使用手机或摄像头扫描服务器生成的二维码。
  3. 验证二维码：
    • 服务器端需要不断地轮询或等待客户端扫描并验证二维码。
    • 当客户端扫描到二维码后，将扫描到的信息（通常是登录标识）发送回服务器。
  4. 创建登录会话：
    • 服务器接收到扫描信息后，验证该信息是否有效且未过期。
    • 如果验证通过，服务器创建一个登录会话，将用户标识与会话关联，并生成一个会话密钥。
  5. 返回登录结果：
    • 服务器返回登录成功的响应，其中包括会话密钥或其他用于标识用户的信息。
    • 客户端接收到登录成功的响应后，将会话信息存储在本地，以备后续请求使用。
  6. 保持会话状态：
    • 服务器和客户端都需要保持会话状态，以便在后续请求中验证用户身份。
    • 客户端通常会将会话信息存储在本地，而服务器会维护会话状态并提供相应的会话管理机制。
  7. 处理登录超时或失败：
    • 如果用户长时间未扫描或扫描失败，服务器可以定期清除未使用的登录标识。
    • 如果扫描后验证失败，服务器应该返回登录失败的响应，并可能要求用户重新扫描。
  8. 安全性考虑：
    • 实现时需要考虑安全性问题，包括数据的传输加密、二维码生成的随机性、会话标识的有效期限制等，以防止恶意攻击。

请注意，二维码登录是一种方便的登录方式，但需要确保安全性和用户体验。每个应用可能会根据自己的需求和安全标准来实现二维码登录的细节。此外，二维码登录通常与单点登录（SSO）等身份认证机制结合使用，以实现更高级的用户身份管理和认证。

8G的int型数据，计算机的内存只有2G，怎么对它进行排序？（外部排序）（百度一面）

我们可以使用外部排序来对它进行处理。首先将整个文件分成许多份，比如说m份，划分的依据就是使得每一份的大小都能放到内存里。然后我们用快速排序或者堆排序等方法对每一份数据进行一个内部排序，变成有序子串。接着对这m份有序子串进行m路归并排序。

取这m份数据的最小元素，进行排序，输出排序后最小的元素到结果中，同时从该元素所在子串中读入一个元素，直到所有数据都被输出到结果中为止。

BitMap算法评价

  • 优点：

    1. 运算效率高，不进行比较和移位；
    2. 占用内存少，比如最大的数MAX=10000000；只需占用内存为MAX/8=1250000Byte=1.25M。

  • 缺点：

    1. 所有的数据不能重复，即不可对重复的数据进行排序。（少量重复数据查找还是可以的，用2-bitmap）。
    2. 所需要的空间随着最大元素的增大而增大，当数据类似（1，1000，10万）只有3个数据的时候，用bitmap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。

    布隆过滤器原理与优点

    布隆过滤器是一个比特向量或者比特数组，它本质上是一种概率型数据结构，用来查找一个元素是否在集合中，支持高效插入和查询某条记录。常作为针对超大数据量下高效查找数据的一种方法。

    它的具体工作过程是这样子的：

    假设布隆过滤器的大小为m（比特向量的长度为m），有k个哈希函数，它对每个数据用这k个哈希函数计算哈希，得到k个哈希值，然后将向量中相应的位设为1。在查询某个数据是否存在的时候，对这个数据用k个哈希函数得到k个哈希值，再在比特向量中相应的位查找是否为1，如果某一个相应的位不为1，那这个数据就肯定不存在。但是如果全找到了，则这个数据有可能存在。

    为什么说有可能存在呢？

    因为不同的数据经过哈希后可能有相同的哈希值，在比特向量上某个位置查找到1也可能是由于某个另外的数据映射得到的。

    支持删除操作吗

    目前布隆过滤器只支持插入和查找操作，不支持删除操作，如果要支持删除，就要另外使用一个计数变量，每次将相应的位置为1则计数加一，删除则减一。

    布隆过滤器中哈希函数的个数需要选择。如果太多则很快所有位都置为1，如果太少会容易误报。

    布隆过滤器的大小以及哈希函数的个数怎么选择？

    k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率

comments powered by Disqus
© 2018 - 2026 salmone
Built with Hugo
Theme Stack designed by Jimmy