常见开发问题汇总

整理常见必考知识点。

目录

arm过往面经总结

  1. 多态继承
  2. 链表插入,素数筛选,位运算,翻转链表
    判断质数
  3. linux shell使用,考英语
  4. SDLC
    SDLC:sdlc(系统生命周期,系统生存周期)是软件的产生直到报废的生命周期,是软件工程中的一种思想原则,即按部就班、逐步推进,每个阶段都要有定义、工作、审查、形成文档以供交流或备查,以提高软件的质量。
    包括:
    • 问题定义及规划
      此阶段是软件开发方与需求方共同讨论,主要确定软件的开发目标及其可行性。
    • 需求分析
      在确定软件开发可行的情况下,对软件需要实现的各个功能进行详细分析。需求分析阶段是一个很重要的阶段,这一阶段做得好,将为整个软件开发项目的成功打下良好的基础。“唯一不变的是变化本身。”,同样需求也是在整个软件开发过程中不断变化和深入的,因此我们必须制定需求变更计划来应付这种变化,以保护整个项目的顺利进行。
    • 软件设计
      此阶段主要根据需求分析的结果,对整个软件系统进行设计,如系统框架设计,数据库设计等等。软件设计一般分为总体设计和详细设计。好的软件设计将为软件程序编写打下良好的基础。
    • 程序编码
      此阶段是将软件设计的结果转换成计算机可运行的程序代码。在程序编码中必须要制定统一,符合标准的编写规范。以保证程序的可读性,易维护性,提高程序的运行效率。
    • 软件测试
      在软件设计完成后要经过严密的测试,以发现软件在整个设计过程中存在的问题并加以纠正。整个测试过程分单元测试、组装测试以及系统测试三个阶段进行。测试的方法主要有白盒测试和黑盒测试两种。在测试过程中需要建立详细的测试计划并严格按照测试计划进行测试,以减少测试的随意性。
    • 运行维护
  5. RISC VS CISC
    软件维护是软件生命周期中持续时间最长的阶段。在软件开发完成并投入使用后,由于多方面的原因,软件不能继续适应用户的要求。要延续软件的使用寿命,就必须对软件进行维护。软件的维护包括纠错性维护和改进性维护两个方面。
    区别参考:
    从硬件角度来看CISC处理的是不等长指令集,它必须对不等长指令进行分割,因此在执行单一指令的时候需要进行较多的处理工作。而RISC执行的是等长精简指令集,CPU在执行指令的时候速度较快且性能稳定。因此在并行处理方面RISC明显优于CISC,RISC可同时执行多条指令,它可将一条指令分割成若干个进程或线程,交由多个处理器同时执行。由于RISC执行的是精简指令集,所以它的制造工艺简单且成本低廉。
    从软件角度来看,CISC运行的则是我们所熟识的DOS、Windows操作系统。而且它拥有大量的应用程序。因为全世界有65%以上的软件厂商都理为基于CISC体系结构的PC及其兼容机服务的,象赫赫有名的Microsoft就是其中的一家。而RISC在此方面却显得有些势单力薄。虽然在RISC上也可运行DOS、Windows,但是需要一个翻译过程,所以运行速度要慢许多。
    在这里插入图片描述
  6. a++和++a区别
    • i++,先执行其他操作,再i自加;
    • i--,先执行其他操作,再i自减;
    • ++i,先i自加,再执行其他操作;
    • --i,先i自减,再执行其他操作;
  7. typedef语句解释
    语句:
    typedef int MazeType[25][25];
    解释:
    typedef 基本数据类型 数组类型名[常量表达式];
    这样为这种数组定义了一个别名。
    应用:
    MazeType M; //等价于 int M[25][25];
    typedef和define不同,typedef发生在编译,有检查,define发生在预处理,没有检查
  8. C语言如何调用C++第三方库
    在头文件加入extern “C”
  9. 二分搜索,素数检验(输出第100个素数)
  10. ARM的基础知识
  11. 为什么需要MMU
    MMU是Memory Management Unit的缩写,中文名是内存管理单元,有时称作分页内存管理单元(英语:paged memory management unit,缩写为PMMU)。它是一种负责处理中央处理器(CPU)的内存访问请求的计算机硬件。它的功能包括虚拟地址到物理地址的转换(即虚拟内存管理)、内存保护、中央处理器高速缓存的控制,在较为简单的计算机体系结构中,负责总线的仲裁以及存储体切换(bank switching,尤其是在8位的系统上)。
    TLB(Translation Lookaside Buffer)传输后备缓冲器是一个内存管理单元用于改进虚拟地址到物理地址转换速度的缓存。TLB是一个小的,虚拟寻址的缓存,其中每一行都保存着一个由单个PTE组成的块。如果没有TLB,则每次取数据都需要两次访问内存,即查页表获得物理地址和取数据。
    多进程间频繁切换对TLB有什么影响?现代的处理器是如何面对这个问题的?
    在现代处理器中,软件使用虚拟地址访问内存,而处理器的MMU单元负责把虚拟地址转换成物理地址,为了完成这个映射过程,软件和硬件共同来维护一个多级映射的页表。当处理器发现页表中无法映射到对应的物理地址时,会触发一个缺页异常,挂起出错的进程,操作系统软件需要处理这个缺页异常。我们之前有提到过二级页表的查询过程,为了完成虚拟地址到物理地址的转换,查询页表需要两次访问内存,即一级页表和二级页表都是存放在内存中的。
    TLB( Translation Look- aside buffer)专门用于缓存内存中的页表项,一般在MMU单元内部。TLB是一个很小的 cache,TLB表项( TLB entry)数量比较少,每个TLB表项包含一个页面的相关信息,例如有效位、虚拟页号、修改位、物理页帧号等。当处理器要访问一个虚拟地址时,首先会在TLB中查询。如果TLB表项中没有相应的表项,称为TLB Miss,那么就需要访问页表来计算出相应的物理地址。如果TLB表项中有相应的表项,那么直接从TLB表项中获取物理地址,称为TLB命中。
    TLB内部存放的基本单位是TLB表项,TLB容量越大,所能存放的TLB表项就越多,TLB命中率就越高,但是TLB的容量是有限的。目前 Linux内核默认采用4KB大小的小页面,如果一个程序使用512个小页面,即2MB大小,那么至少需要512个TLB表项才能保证不会出现 TLB Miss的情况。但是如果使用2MB大小的大页,那么只需要一个TLB表项就可以保证不会出现 TLB Miss的情况。对于消耗内存以GB为单位的大型应用程序,还可以使用以1GB为单位的大页,从而减少 TLB Miss的情况。
  12. 中断上半部和下半部区别及作用
  13. cache shader
  14. 全局变量和局部变量
  15. 计算机组成,架构按指令分类
    计算机组成指的是系统结构的逻辑实现,包括机器机内的数据流和控制流的组成及逻辑设计等。主要分为五个部分:控制器,运算器,存储器,输入设备,输出设备。
    哈佛结构(Harvard architecture)是一种将程序指令储存和数据储存分开的存储器结构。中央处理器首先到程序指令储存器中读取程序指令内容,解码后得到数据地址,再到相应的数据储存器中读取数据,并进行下一步的操作(通常是执行)。程序指令储存和数据储存分开,数据和指令的储存可以同时进行,可以使指令和数据有不同的数据宽度,如Microchip公司的PIC16芯片的程序指令是14位宽度,而数据是8位宽度。哈佛结构的微处理器通常具有较高的执行效率。其程序指令和数据指令分开组织和储存的,执行时可以预先读取下一条指令。目前使用哈佛结构的中央处理器和微控制器有很多,除了上面提到的Microchip公司的PIC系列芯片,还有摩托罗拉公司的MC68系列、Zilog公司的Z8系列、ATMEL公司的AVR系列和安谋公司的ARM9、ARM10和ARM11。大多数DSP是哈佛结构的。
    冯.诺伊曼结构(von Neumann architecture),也称普林斯顿结构,是一种将程序指令存储器和数据存储器合并在一起的电脑设计概念结构。该结构隐约指导了将储存装置与中央处理器分开的概念,因此依该结构设计出的计算机又称储存程式型电脑。
    ARM架构过去称作进阶精简指令集机器(AdvancedRISCMachine,更早称作:AcornRISCMachine),是一个32位精简指令集(RISC)处理器架构,其广泛地使用在许多嵌入式系统设计。由于节能的特点,ARM处理器非常适用于移动通讯领域,符合其主要设计目标为低耗电的特性。
    目前的PC架构绝大多数都是Intel的X86架构,貌似也是因为INTEL的这个X86架构早就了目前INTEL如日中天的地位。X86架构(The X86 architecture)是微处理器执行的计算机语言指令集,指一个intel通用计算机系列的标准编号缩写,也标识一套通用的计算机指令集合。

中断的传递过程,信号量监听的函数

当linux内核空间发生中断后怎么使用户空间的应用程序运行相应的函数呢,当芯片有数据到来时内核会产生一个中断,但是怎样通知应用程序来取数据?linux中有异步通知机制,在用户程序中用signal注册一个响应SIGIO信号的回调函数,然后在驱动程序中向该进程发出SIGIO信号便完成该功能,下面是该功能具体实施方法:

  • 在驱动中定义一个static struct fasync_struct * async;
  • 在fasync系统调用中注册fasync_helper(fd, filp, mode, &async);
  • 在中断服务程序(顶半部、底半部都可以)发出信号kill_fasync(&async, SIGIO, POLL_IN);
  • 在用户应用程序中用signal注册一个响应SIGIO的回调函数signal(SIGIO, sig_handler);
  • 通过fcntl(fd, F_SETOWN, getpid())将将进程pid传入内核6.通过fcntl(fd, F_SETFL, fcntl(fd, F_GETFL) | FASYNC)设置异步通知

参考代码

void sig_handler(int sig) {
    if (sig == SIGUSR1) {
        // printf("Receive io signal from kernel!\n");
        spi_test(spifd);
    }
}

int main(int argc, char *argv[]) {
    //......
    signal(SIGUSR1, sig_handler);
    parse_opts(argc, argv);
    spifd = open(device, O_RDWR);
    fcntl(spifd, F_SETSIG, SIGUSR1);
    fcntl(spifd, F_SETOWN, getpid());
    //fcntl(spifd, F_GETOWN, getpid());
    fcntl(spifd, F_SETFL, fcntl(spifd, F_GETFL) | FASYNC);
    printf("waiting key interrupt:\n");
    while(1);
}

在驱动中注册模块时,需要注册中断,中断的回调函数发送信号,即可完成信号的传递。
补充:
我们在使用request_irq申请中断的时候注册的中断服务函数属于中断处理的上半部,只要中断触发,那么中断处理函数就会执行。我们都知道中断处理函数一定要快点执行完毕,越短越好,但是现实往往是残酷的,有些中断处理过程就是比较费时间,我们必须要对其进行处理,缩小中断处理函数的执行时间。比如电容触摸屏通过中断通知 SOC 有触摸事件发生,SOC 响应中断,然后通过 IIC 接口读取触摸坐标值并将其上报给系统。但是我们都知道 IIC 的速度最高也只有400Kbit/S,所以在中断中通过 IIC 读取数据就会浪费时间。我们可以将通过 IIC 读取触摸数据的操作暂后执行,中断处理函数仅仅相应中断,然后清除中断标志位即可。这个时候中断处理过程就分为了两部分:

  • 上半部:上半部就是中断处理函数,那些处理过程比较快,不会占用很长时间的处理就可以放在上半部完成。
  • 下半部:如果中断处理过程比较耗时,那么就将这些比较耗时的代码提出来,交给下半部去执行,这样中断处理函数就会快进快出。

因此,Linux 内核将中断分为上半部和下半部的主要目的就是实现中断处理函数的快进快出,那些对时间敏感、执行速度快的操作可以放到中断处理函数中,也就是上半部。剩下的所有工作都可以放到下半部去执行,比如在上半部将数据拷贝到内存中,关于数据的具体处理就可以放到下半部去执行。至于哪些代码属于上半部,哪些代码属于下半部并没有明确的规定,一切根据实际使用情况去判断,这个就很考验驱动编写人员的功底了。这里有一些可以借鉴的参考点:

  • 如果要处理的内容不希望被其他中断打断,那么可以放到上半部。
  • 如果要处理的任务对时间敏感,可以放到上半部。
  • 如果要处理的任务与硬件有关,可以放到上半部
  • 除了上述三点以外的其他任务,优先考虑放到下半部。

上半部处理很简单,直接编写中断处理函数就行了,关键是下半部该怎么做呢?Linux 内核提供了多种下半部机制。例如软中断、tasklet、工作队列等。

驱动的开发过程

嵌入式系统中,操作系统是通过各种驱动程序来驾驭硬件设备的。设备驱动程序是操作系统内核和硬件设备之间的接口,它为应用程序屏蔽了硬件的细节,这样在应用程序看来,硬件设备只是一个设备文件,可以像操作普通文件一样对硬件设备进行操作。设备驱动程序是内核的一部分,完成以下功能:
驱动程序的注册和注销。

  • 设备的打开和释放。
  • 设备的读写操作。
  • 设备的控制操作。
  • 设备的中断和轮询处理。

Linux主要将设备分为三类:字符设备、块设备和网络设备。字符设备是指发送和接收数据以字符的形式进行,没有缓冲区的设备;块设备是指发送和接收数据以整个数据缓冲区的形式进行的设备;网络设备是指网络设备访问的BSD socket 接口。下面以字符设备为例,写出其驱动编写框架:

编写驱动程序初始化函数

驱动程序的初始化在函数xxx_init()中完成,包括对硬件初始化、中断函数、向内核注册驱动程序等。

  • 首先理解硬件结构,搞清楚其功能,接口寄存器以及CPU怎么访问控制这些寄存器等。
  • 其次向内核注册驱动程序。设备驱动程序可以直接编译进内核,在系统启动的时候初始化,也可以在需要的时候以模块的方式动态加载到内核中去。每个字符设备或是块设备都是通过register_chrdev()函数注册,调用该函数后就可以向系统申请主设备号,操作成功,设备名就会出现在/proc/devices里。
  • 此外,在关闭设备时,需要先解除原先设备的注册,需要有清除函数,在xxx_exit()中通过unregister_chrdev()函数在实现,此后设备就会从/proc/devices里消失。
  • 当驱动程序被编译成模块时,使用insmod加载模块,模块的初始化函数xxx_init()被调用,向内核注册驱动程序;使用rmmod卸载模块,模块的清除函数xxx_exit()被调用。

构造file_operations结构中要用到的各个成员函数

Linux操作系统将所有的设备都看成文件,以操作文件的方式访问设备。应用程序不能直接操作硬件,使用统一的接口函数调用硬件驱动程序,这组接口被成为系统调用。每个系统调用中都有一个与之对应的函数(open、release、read、write、ioctl等),在字符驱动程序中,这些函数集合在一个file_operations类型的数据结构中。以一个键盘驱动程序为例:

struct file_operations Key7279_fops =  
{
    .open = Key7279_Open,  
    .ioctl = Key7279_Ioctl,  
    .release = Key7279_Close,
    .read = Key7279_Read,
};
  1. 设备的打开和释放
    • 打开设备是由open()函数来完成,在大部分设备驱动中open完成如下工作:
      • 递增计数器
      • 检查特定设备的特殊情况
      • 初始化设备
      • 识别次设备号
    • 释放设备由release()函数来完成。当一个进程释放设备时,其它进程还能继续使用该设备,只是该进程暂时停止对该设备的的使用,而当一个进程关闭设备时,其它进程必须重新打开此设备才能使用。Release完成如下工作:
      • 递减计数
      • 在最后一次释放设备操作时关闭设备
  2. 设备的读写操作
    读写设备的主要任务就是把内核空间的数据复制到用户空间,或者是从用户空间复制到内核空间,也就是将内核空间缓冲区里的数据复制到用户空间的缓冲区中或者相反。字符设备使用各自的read()函数和write()函数来进行数据读写。
  3. 设备的控制操作
    大部分设备除了读写能力,还可进行超出简单的数据传输之外的操作,所以设备驱动也必须具备进行各种硬件控制操作的能力. 这些操作常常通过 ioctl 方法来支持。与读写操作不同,ioctl()的用法与具体设备密切相关。以键盘Key7279_Ioctl为例:
    static int Key7279_Ioctl(struct inode *inode,struct file *file,unsigned int cmd, unsigned long arg)
    {
        switch(cmd)  
        {
            case Key7279_GETKEY:
                return key7279_getkey();
            default:
            printk("Unkown Keyboard Command ID.\n");
        }
            return 0;
    }
    cmd的取值及含义都与具体的设备有关,除了ioctl(),设备驱动程序还可能有其他控制函数,比如llseek()等。当应用程序使用open、release等函数打开某个设备时,设备驱动程序的file_operations结构中的相应成员就会被调用。

    设备的中断和轮询处理

    对于不支持中断的设备,读写时需要轮询设备状态,以及是否需要继续进行数据传输。例如,打印机。如果设备支持中断,则可按照中断方式进行。模块在使用中断前要先请求一个中断通道(或者 IRQ中断请求),并在使用后释放它。通过request_irq()函数来注册中断,free_irq()函数来释放。

    驱动程序的测试

    对驱动程序的调试可以通过打印的方式来进行,就是通过在驱动程序中添加printk()打印函数,来跟踪驱动程序的执行过程,以此来判断问题。 以上是我根据自己的学习总结的,可能写的比较简单,对于比较复杂的驱动函数,会添加更多的函数,但是大体的框架就是这样了。
    基于操作系统的驱动就是在无操作系统下的硬件接口函数加上操作系统的接口

    总结

    实现一个嵌入式Linux设备驱动程序的大致流程如下:
  • 查看原理图,理解设备的工作原理。
  • 定义主设备号。设备由一个主设备号和一个次设备号来标识。主设备号唯一标识了设备类型,即设备驱动程序类型,它是块设备表或字符设备表中设备表项的索引。次设备号仅由设备驱动程序解释,区分被一个设备驱动控制下的某个独立的设备。
  • 实现初始化函数。在驱动程序中实现驱动的注册和卸载。
  • 设计所要实现的文件操作,定义file–operations结构。
  • 实现所需的文件操作调用,如read,write等。
  • 实现中断服务,并用request–irq向内核注册,中断并不是每个设备驱动所必需的。
  • 编译该驱动程序到内核中,或者用insmod命令加载模块。
  • 测试该设备,编写应用程序,对驱动程序进行测试。

典型字符设备驱动编写框架:

  1. 编写硬件接口函数
  2. 建立文件系统与设备驱动程序间的接口,如:struct file_operations结构体
  3. 注册设备到chrdevfs全局数组中,注册或注销设备可以在任何时候,但一般在模块加载时注册设备,在模块退出时注销设备。module_init()/module_exit()
  4. 以模块方式编译驱动源码,并将其加载到内核中
  5. 创建设备节点,mknode
  6. 编写应用程序访问底层设备

网卡收集数据传递给上层应用的过程,网卡型号及接口

网络驱动硬件主要组成

  1. MAC和PHY
    有集成mac的soc+phy解决方案和soc+mac/phy一体芯片解决方案,前者带MAC的SOC与PHY相连的接口包括MII/RMII的网络数据接口和MDIO控制接口,优势在于:
    • 内部 MAC 外设会有专用的加速模块,比如专用的 DMA,加速网速数据的处理。
    • 网速快,可以支持 10/100/1000M 网速。
    • 外接 PHY 可选择性多,成本低。
  2. MII/RMII/MDIO接口
    MII表示一种介质独立接口,后者是精简的意思。
    MDIO表示管理数据输入输出接口,包括MDIO数据线和MDC时钟线。
  3. 物理接口RJ45及变压器

驱动架构

  1. Linux 内核使用 net_device 结构体表示一个具体的网络设备,net_device 是整个网络驱动的灵魂。网络驱动的核心就是初始化 net_device 结构体中的各个成员变量,然后将初始化完成以后的 net_device 注册到 Linux 内核中。net_device 结构体定义在 include/linux/netdevice.h 中。
  2. 事实上网络设备有多种,大家不要以为就只有以太网一种。Linux 内核内核支持的网络接口有很多,比如光纤分布式数据接口(FDDI)、以太网设备(Ethernet)、红外数据接口(InDA)、高性能并行接口(HPPI)、CAN 网络等。
  3. net_device 有个非常重要的成员变量:netdev_ops,为 net_device_ops 结构体指针类型,这就是网络设备的操作集。net_device_ops 结构体定义在 include/linux/netdevice.h 文件中,net_device_ops 结构体里面都是一些以“ndo_” 开头的函数,这些函数就需要网络驱动编写人员去实现,不需要全部都实现,根据实际驱动情况实现其中一部分即可。
  4. 网络是分层的,对于应用层而言不用关系具体的底层是如何工作的,只需要按照协议将要发送或接收的数据打包好即可。打包好以后都通过 dev_queue_xmit 函数将数据发送出去,接收数据的话使用 netif_rx 函数即可,我们依次来看一下这两个函数。
  5. sk_buff 是 Linux 网络驱动中一个非常重要的结构体,网络数据就是以 sk_buff 保存的,各个协议层在 sk_buff 中添加自己的协议头,最终由底层驱动讲 sk_buff 中的数据发送出去。 网络数据的接收过程恰好相反, 网络底层驱动将接收到的原始数据打包成 sk_buff,然后发送给上层协议,上层会取掉相应的头部,然后将最终的数据发送给用户。
  6. Linux 里面的网络数据接收也轮询和中断两种,中断的好处就是响应快,数据量小的时候处理及时,速度快,但是一旦当数据量大,而且都是短帧的时候会导致中断频繁发生,消耗大量的 CPU 处理时间在中断自身处理上。轮询恰好相反,响应没有中断及时,但是在处理大量数据的时候不需要消耗过多的 CPU 处理时间。Linux 在这两个处理方式的基础上提出了另外一种网络数据接收的处理方法:NAPI(New API),NAPI 是一种高效的网络处理技术。NAPI 的核心思想就是不全部采用中断来读取网络数据,而是采用中断来唤醒数据接收服务程序,在接收服务程序中采用 POLL 的方法来轮询处理数据。这种方法的好处就是可以提高短数据包的接收效率,减少中断处理的时间。目前 NAPI 已经在 Linux 的网络驱动中得到了大量的应用,NXP 官方编写的网络驱动都是采用的 NAPI 机制。

网络服务器的高速并发处理,降低传输时延

内存管理的方式,什么是内存管理,其作用是什么

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存,从而让程序获得更多的可用内存。
为了更好的管理内存,操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间,这个地址空间被分割成多个块,每一块称为一页。这些页被映射到物理内存,但不需要映射到连续的物理内存,也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时,由硬件执行必要的映射,将缺失的部分装入物理内存并重新执行失败的指令。
从上面的描述中可以看出,虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存,也就是说一个程序不需要全部调入内存就可以运行,这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址,那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存,虚拟内存技术允许该计算机运行一个 64K 大小的程序。

分页系统地址映射

内存管理单元(MMU)管理着地址空间和物理内存的转换,其中的页表(Page table)存储着页(程序地址空间)和页框(物理内存空间)的映射表。
一个虚拟地址分成两个部分,一部分存储页面号,一部分存储偏移量。
下图的页表存放着 16 个页,这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址(0010 000000000100),前 4 位是存储页面号 2,读取表项内容为(110 1),页表项最后一位表示是否存在于内存中,1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 (110 000000000100)。

页面置换算法

在程序运行过程中,如果要访问的页面不在内存中,就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间,系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似,可以将内存看成磁盘的缓存。在缓存系统中,缓存的大小有限,当有新的缓存到达时,需要淘汰一部分已经存在的缓存,这样才有空间存放新的缓存数据。页面置换算法的主要目标是使页面置换频率最低(也可以说缺页率最低)。

  • 最佳OPT, Optimal replacement algorithm

    • 所选择的被换出的页面将是最长时间内不再被访问,通常可以保证获得最低的缺页率。
    • 是一种理论上的算法,因为无法知道一个页面多长时间不再被访问。
    • 举例:一个系统为某进程分配了三个物理块,并有如下页面引用序列:
    • 开始运行时,先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时,产生缺页中断,会将页面 7 换出,因为页面 7 再次被访问的时间最长。
  • 最近最久未使用LRU, Least Recently Used

    • 虽然无法知道将来要使用的页面情况,但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
    • 为了实现 LRU,需要在内存中维护一个所有页面的链表。当一个页面被访问时,将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
    • 因为每次访问都需要更新链表,因此这种方式实现的 LRU 代价很高。
  • 最近未使用NRU, Not Recently Used
    每个页面都有两个状态位:R 与 M,当页面被访问时设置页面的 R=1,当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类:

    R=0,M=0
    R=0,M=1
    R=1,M=0
    R=1,M=1

当发生缺页中断时,NRU算法随机地从类编号最小的非空类中挑选一个页面将它换出。
NRU优先换出已经被修改的脏页面(R=0,M=1),而不是被频繁使用的干净页面(R=1,M=0)。

  • 先进先出FIFO, First In First Out
    选择换出的页面是最先进入的页面。该算法会将那些经常被访问的页面也被换出,从而使缺页率升高。

  • 第二次机会算法

    • FIFO算法可能会把经常使用的页面置换出去,为了避免这一问题,对该算法做一个简单的修改:
      • 当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候,检查最老页面的 R 位。如果 R 位是 0,那么这个页面既老又没有被使用,可以立刻置换掉;如果是 1,就将 R 位清 0,并把该页面放到链表的尾端,修改它的装入时间使它就像刚装入的一样,然后继续从链表的头部开始搜索。
  • 时钟Clock
    第二次机会算法需要在链表中移动页面,降低了效率。时钟算法使用环形链表将页面连接起来,再使用一个指针指向最老的页面。

分段

虚拟内存采用的是分页技术,也就是将地址空间划分成固定大小的页,每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表,有 4 个表是动态增长的,如果使用分页系统的一维地址空间,动态增长的特点会导致覆盖问题的出现。

分段的做法是把每个表分成段,一个段构成一个独立的地址空间。每个段的长度可以不同,并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段,每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护,又拥有分页系统的虚拟内存功能。

分页与分段的比较

  • 对程序员的透明性:分页透明,但是分段需要程序员显示划分每个段。
  • 地址空间的维度:分页是一维地址空间,分段是二维的。
  • 大小是否可以改变:页的大小不可变,段的大小可以动态改变。
  • 出现的原因:分页主要用于实现虚拟内存,从而获得更大的地址空间;分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

内核如何管理内存的页

参考内核如何管理内存的页

TCP/IP协议是否了解,Linux怎么做网络路由

文件系统的制作和优化方式,不同文件系统格式内核是如何管理的

  • 根文件系统之所以在前面加一个”根“,说明它是加载其它文件系统的”根“,既然是根的话,那么如果没有这个根,其它的文件系统也就没有办法进行加载的。它包含系统引导和使其他文件系统得以挂载(mount)所必要的文件。根文件系统包括Linux启动时所必须的目录和关键性的文件,例如Linux启动时都需要有init目录下的相关文件,在 Linux挂载分区时Linux一定会找/etc/fstab这个挂载文件等,根文件系统中还包括了许多的应用程序bin目录等,任何包括这些Linux 系统启动所必须的文件都可以成为根文件系统。Linux启动时,第一个必须挂载的是根文件系统;若系统不能从指定设备上挂载根文件系统,则系统会出错而退出启动。成功之后可以自动或手动挂载其他的文件系统。因此,一个系统中可以同时存在不同的文件系统。在 Linux 中将一个文件系统与一个存储设备关联起来的过程称为挂载(mount)。使用 mount 命令将一个文件系统附着到当前文件系统层次结构中(根)。在执行挂装时,要提供文件系统类型、文件系统和一个挂装点。根文件系统被挂载到根目录下“/”上后,在根目录下就有根文件系统的各个目录,文件:/bin /sbin /mnt等,再将其他分区挂接到/mnt目录上,/mnt目录下就有这个分区的各个目录,文件。
  • 技术上说Linux是一个内核。“内核”指的是一个提供硬件抽象层、磁盘及文件系统控制、多任务等功能的系统软件。一个内核不是一套完整的操作系统。一套基于Linux内核的完整操作系统叫作Linux操作系统,或是GNU/Linux。
  • 文件系统是kernel的一部分。文件系统实现了系统上存储介质和其他资源的交互。kernel tree中的fs目录都是关于文件系统的,可以说它是kernel的一个大子系统。
  • 嵌入式系统在flash中分配了存放内核、根文件系统的区域。bootloader加载了内核,内核启动,加载文件系统,进入Linux系统。
  • 整个嵌入式系统而言,可以分为三个部分1.uboot 2.kernel 3.文件系统。其中kernel中以VFS去支持各种文件系统,如yaffs,ext3,cramfs等等。yaffs/yaffs2是专为嵌入式系统使用NAND型闪存而设计的一种日志型文件系统。在内核中以VFS来屏蔽各种文件系统的接口不同,以VFS向kernel提供一个统一的接口。如打开一个文件时统一使用open,写时采用write,而不用去考虑是那种文件系统,也不用去考虑文件系统是如何将数据写入物理介质的。其中 kernel中的配置,只是让VFS支持这种接口。

参考
vfs
vfs
vfs

操作系统的任务调度方式,你的进程是怎么提高实时性或者优先级的

抢占的原理参考抢占

进程调度算法

不同环境的调度算法目标不同,因此需要针对不同环境来讨论调度算法。

  • 批处理系统
    批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量和周转时间(从提交到终止的时间)。

    • 先来先服务 first-come first-serverd(FCFS)
      按照请求的顺序进行调度。有利于长作业,但不利于短作业,因为短作业必须一直等待前面的长作业执行完毕才能执行,而长作业又需要执行很长时间,造成了短作业等待时间过长。
    • 短作业优先 shortest job first(SJF)
      按估计运行时间最短的顺序进行调度。长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。
    • 最短剩余时间优先 shortest remaining time next(SRTN)
      按估计剩余时间最短的顺序进行调度。
  • 交互式系统
    交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应。

    • 时间片轮转
      将所有就绪进程按FCFS的原则排成一个队列,每次调度时,把CPU时间分配给队首进程,该进程可以执行一个时间片。当时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系:

      • 因为进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
      • 而如果时间片过长,那么实时性就不能得到保证。
    • 优先级调度
      为每个进程分配一个优先级,按优先级进行调度。为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级。

    • 多级反馈队列
      一个进程需要执行 100 个时间片,如果采用时间片轮转调度算法,那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑,它设置了多个队列,每个队列时间片大小都不同,例如 1,2,4,8,..。进程在第一个队列没执行完,就会被移到下一个队列。这种方式下,之前的进程只需要交换 7 次。
      每个队列优先权也不同,最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。
      可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

  • 实时系统
    实时系统要求一个请求在一个确定时间内得到响应。分为硬实时和软实时,前者必须满足绝对的截止时间,后者可以容忍一定的超时。

    nice的默认优先级大小,取值范围

    Linux内核实现了两种不同的优先级范围。第一种是用nice值,它的范围是[-20, 19],默认值是0。越大的nice值意味着优先级越低–你对系统中的别的进程”nice”。相比于那些高nice值(低优先级)的进程来说,低nice值(高优先级)的进程可以获得更多的处理器时间。
    Linux nice命令以更改过的优先序来执行程序,如果未指定程序,则会印出目前的排程优先序,内定的 adjustment 为 10,范围为 -20(最高优先序)到 19(最低优先序)。

    内核的裁剪和配置方式

    数据库是否支持并发,数据库ID是否可以任意数据类型,数据库一定要ID吗

    支持并发,但还是需要锁;
    可以用其他类型,但int方便自增;
    不一定需要,但必须要有主键,ID作为一种范式,是比较好的一种索引的方式。

如何管理数据库的脏数据,掉电未写完的数据

数据库中的并发操作带来的一系列问题
mysql解决脏读、不可重复读、虚读的办法

视频的编解码方式

进程和线程的区别

虚拟地址与物理地址

内核如何分配内存给进程

参考Linux内存分配机制
Linux 的虚拟内存管理有几个关键概念:

  1. 每个进程都有独立的虚拟地址空间,进程访问的虚拟地址并不是真正的物理地址;
  2. 虚拟地址可通过每个进程上的页表(在每个进程的内核虚拟地址空间)与物理地址进行映射,获得真正物理地址;
  3. 如果虚拟地址对应物理地址不在物理内存中,则产生缺页中断,真正分配物理地址,同时更新进程的页表;如果此时物理内存已耗尽,则根据内存替换算法淘汰部分页面至物理磁盘中。

进程的资源分为哪些?漏了代码段

多进程如何共享硬件中断

进程和线程的区别

内核态中断和线程同步的方式,不能用信号量

uboot的作用

arm启动进入操作系统的步骤

const变量在程序的哪个段

静态存储区

驱动中断的响应包括哪些内容

参考Linux设备驱动中断机制

双核的ARM在uboot里面用了吗

strlen和sizeof区别

重写和重载区别

参考重写(Override)与重载(Overload)的区别(面试题)

memcpy和strcpy区别

gdb调试

命令行如何查看进程打开的文件

lsof -p PID

select和epoll区别

参考select、poll、epoll之间的区别(搜狗面试)

char int char char double在32位结构体大小

手撕代码,倒装句子的单词,单词顺序不变,不使用额外的存储

CAN和UART区别,CAN是帧结构吗

参考IIC、SPI、UART、USART、USB、CAN等通讯协议原理及区别

CAN芯片怎么写的,数据怎么与内核交互的,属于网络设备还是字符设备

你觉得最体现你项目能力的是哪个部分,你在其中参与的核心解决的难题是啥,你给我说说三取二的原理,以及你遇到什么困难。

描述你的项目我来复述并评估拟堆项目的理解,项目背景和项目分工以及你的主要工作和难点

动态库和静态库的区别,后缀格式,以及函数的相对地址区别

区别

  1. 命名方式不同:
    静态库libxxx.a:库名前加”lib”,后缀用”.a”,“xxx”为静态库名。
    动态库libxxx.so:库名前加”lib”,后缀变为“.so”。
  2. 链接时间不同:
    静态库的代码是在编译过程中被载入程序中。
    动态库的代码是当程序运行到相关函数才调用动态库的相应函数
  3. 链接方式不同:
    静态库的链接是将整个函数库的所有数据在编译时都整合进了目标代码。
    动态库的链接是程序执行到哪个函数链接哪个函数的库。(用哪个链接哪个)

优缺点?

  • 静态库:
    优点是,在编译后的执行程序不再需要外部的函数库支持,运行速度相对快些;
    缺点是,如果所使用的静态库发生更新改变,你的程序必须重新编译。
  • 动态库 :
    优点是,动态库的改变并不影响你的程序,所以动态函数库升级比较方便;
    缺点是,因为函数库并没有整合进程序,所以程序的运行环境必须提供相应的库。

堆和栈的区别,函数栈、线程栈的区别

你在微电子学与固体电子学专业里面,你觉得自己能力算中上还是最好的那一批?

最开始的:自我介绍,说你最大的和别人不同的

有名管道的父节点和子节点

共享内存的使用注意事

回答锁和不能随意释放

int的长度由什么决定

int 的字节长度是由CPU和操作系统编译器共同决定的,一般情况下,主要是由操作系统决定,比如,你在64位AMD的机器上安装的是32位操作系统,那 么,int默认是32位的;如果是64位操作系统,64位操作系统分为两种,1种是int为32位long为64位,2种int long均为64位。之所以说int同时也与编译器有关,编译器完全可以在32位系统模拟64位整数,例如Unix/Linux下的long long和Windows下的__int64均为64位整数。

cache是什么,有什么作用

Cache存储器,电脑中为高速缓冲存储器,是位于CPU和主存储器DRAM(Dynamic Random Access Memory)之间,规模较小,但速度很高的存储器,通常由SRAM(Static Random Access Memory 静态存储器)组成。它是位于CPU与内存间的一种容量较小但速度很高的存储器。CPU的速度远高于内存,当CPU直接从内存中存取数据时要等待一定时间周期,而Cache则可以保存CPU刚用过或循环使用的一部分数据,如果CPU需要再次使用该部分数据时可从Cache中直接调用,这样就避免了重复存取数据,减少了CPU的等待时间,因而提高了系统的效率。Cache又分为L1Cache(一级缓存)和L2Cache(二级缓存),L1Cache主要是集成在CPU内部,而L2Cache集成在主板上或是CPU上。

寄存器修饰的关键字的理解

volatile,参考C语言中volatile关键字的作用

arm处理器的模式

中断处理流程,中断的现场保护保护什么

响应中断-关中断-根据中断源跳转服务程序-现场保护-中断服务-恢复现场-开中断

CPU开始利用栈保护被暂停执行的程序的现场:依次压入当前程序使用的eflags,cs,eip,errorCode(如果是有错误码的异常)信息护现场就是:当出现中断时,把CPU的状态,也就是中断的入口地址保存在寄存器中,随后转向执行其他任务,当任务完成,从寄存器中取出地址继续执行。保护现场其实就是保存中断前一时刻的状态不被破坏。

kmalloc和vmalloc的区别,内核怎么分配128M连续内存

kmalloc物理地址连续
vmalloc物理地址不连续

TLB是什么

根据功能可以译为快表,直译可以翻译为旁路转换缓冲,也可以把它理解成页表缓冲。里面存放的是一些页表文件(虚拟地址到物理地址的转换表)。当处理 器要在主内存寻址时,不是直接在内存的物理地址里查找的,而是通过一组虚拟地址转换到主内存的物理地址,TLB就是负责将虚拟内存地址翻译成实际的物理内 存地址,而CPU寻址时会优先在TLB中进行寻址。处理器的性能就和寻址的命中率有很大的关系。
参考TLB

原子操作的底层是怎么实现的