嵌入式笔面试知识储备

2020-12-28 14:34:12 浏览数 (1)

文章目录

    • @[toc]
    • 堆和栈的区别
      • 数据结构中的堆和栈
      • 内存分配中的堆和栈
    • 数据结构
      • 二叉树的性质
      • 判断合法的出栈序列
    • 算法相关
      • 排序算法的时间复杂度和空间复杂度
      • this指针
    • 以太网相关
      • OSI参考模型
      • TCP/IP五层模型
    • Linux相关
      • 文件权限符号
      • 修改文件权限
      • 目录结构
      • 常用命令
      • 文件系统
      • 存储设备
        • Flash
        • RAM（Random Access Memory）
    • C/C 相关
      • volatile作用
      • 位操作
      • 可重入函数和不可重入函数
      • 防止头文件和全局变量重复定义
    • 协议相关
      • IIC
    • 操作系统相关
      • 进程与线程的关系
      • 操作系统的功能
      • 系统中的资源
      • 产生死锁的必要条件
    • 原码、反码、补码
    • ADC中的指标

堆和栈的区别

数据结构中的堆和栈

栈：是一种可以实现“先进后出”的存储结构。操作仅限于栈的顶部。常应用于实现递归功能方面的场景

堆：是一种经过排序的完全二叉树。其中，节点是从左到右填满的，并且最后一层的树叶都在最左边；每个节点的值都小于（或者都大于）其子节点的值。因为堆有序的特点，一般用来做数组中的排序，称为堆排序。

内存分配中的堆和栈

分配方式

​ 栈：由编译器自动分配和释放的，处于相对较高的地址，其栈地址是向下增长的。

​ 堆：由程序员手动完成申请和释放，地址是向上增长的。

存储内容

​ 栈：主要用于存放函数的参数与局部变量等

​ 堆：具体存储内容由程序员根据需要决定存储数据

生存周期

​ 栈：其生存周期也只在函数的运行过程中，在运行后就释放，并不可以再次访问

​ 堆：动态内存的整个生存期是由程序员自己决定的，使用非常灵活。但必须及时释放它，否则将会导致运行的程序出现内存泄漏等错误。

分配效率

​ 栈：栈内存分配运算内置于处理器的指令集中，它的效率一般很高

​ 堆：由函数库提供，机制复杂（由链表记录空闲内存区域），分配效率比栈要低得多

内存碎片

​ 栈：不会存在这个问题

​ 堆：频繁分配和释放不同大小的堆空间会造成内存空间的不连续，从而造成大量碎片，导致程序效率降低

数据结构

  • 满二叉树：二叉树中除了叶子结点，每个结点的度都为 2。
  • 完全二叉树：二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布。
  • 一颗完全二叉树上有 1001 1001 1001个结点，求叶子节点个数： 除以2向上取整 二叉树性质 n 0 = n 2 1 n_0 = n_2 1 n0​=n2​ 1 因为 n 0 n 1 n 2 = 1001 n_0 n_1 n_2 = 1001 n0​ n1​ n2​=1001 所以 2 n 2 1 n 1 = 1001 2n_2 1 n_1 = 1001 2n2​ 1 n1​=1001 由于该等式右边为奇数,左边的 n 1 n_1 n1​只能是偶数 又因为完全二叉树中度为 1 1 1结点个数 n 1 n_1 n1​要么是 0 0 0要么是 1 1 1，所以只能是 0 0 0 因此 n 2 = 500 n_2 = 500 n2​=500 所以 n 0 = 501 n_0 = 501 n0​=501

二叉树的性质

  1. 二叉树中，第 i i i 层最多有 2 i − 1 2^{i-1} 2i−1 个结点。
  2. 如果二叉树的深度为 K K K，那么此二叉树最多有 2 K − 1 2^{K-1} 2K−1 个结点。
  3. 二叉树中，终端结点数（叶子结点数）为 n 0 n_0 n0​，度（子树数量）为 1 1 1 的结点为 n 1 n_1 n1​，度为 2 2 2 的结点数为 n 2 n_2 n2​，则 n 0 = n 2 1 n_0=n_2 1 n0​=n2​ 1。总结点 n=n_0 n_1 n_2=n_1 2*n_2 1。
  4. 包含 n n n个结点的二叉树的高度至少为 l o g 2 ( n 1 ) log_2(n 1) log2​(n 1)。
  5. n n n 个结点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ 1 ⌊log_2n⌋ 1 ⌊log2​n⌋ 1。 ⌊ l o g 2 n ⌋ ⌊log_2n⌋ ⌊log2​n⌋ 表示取小于 log_2n 的最大整数。
  6. 当 i > 1 i>1 i>1 时，父亲结点为结点 [ i / 2 ] [i/2] [i/2] 。（ i = 1 i=1 i=1 时，表示的是根结点，无父亲结点）
  7. 如果 2 ∗ i > n 2*i>n 2∗i>n（总结点的个数） ，则结点 i i i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2 ∗ i 2*i 2∗i 。
  8. 如果 2 ∗ i 1 > n 2*i 1>n 2∗i 1>n ，则结点

判断合法的出栈序列

按顺序入栈的序列，任意元素 e ，比 e 先入栈的元素，并且比 e 后出栈的元素，一定是逆序的。

例： 设栈的入栈序列是 1 2 3 4，则下列不可能是其出栈序列的是（ ）。 A. 1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 E. 3 1 2 4

**解法：**以E选项讲解

  1. 选择任意元素e ，这里选择3
  2. 比3后出栈的有三个元素 1 2 4
  3. 其中比3先入栈的有两个元素 1 2
  4. 但是1 2是正序的，而不是逆序的
  5. 所以这个序列不是合法出栈序列

算法相关

排序算法的时间复杂度和空间复杂度

this指针

​ this指针指向被调用的成员函数所属的对象。本质是一个指针常量，储存了调用他的对象的地址。

用途：

  • 当形参和成员变量同名时，可用this指针来区分
  • 在类的非静态成员函数中返回对象本身，可使用return *this

特点：

  1. 只能在成员函数中使用，在全局函数、静态成员函数中都不能使用 this 。this始终指向当前对象，静态成员函数属于类。
  2. this 指针是在成员函数的开始前构造，并在成员函数的结束后清除 。和函数的其他参数生命周期一样。
  3. this 指针会因编译器不同而有不同的存储位置，可能是栈、寄存器或全局变量 。编译器在生成程序时加入了获取对象首地址的相关代码并把获取的首地址存放在了寄存器中。
  4. 大多数编译器是在创建对象的时候，向ecx寄存器传递this指针。

以太网相关

OSI参考模型

OSI(Open System Interconnect)，开放式系统互联。

TCP/IP五层模型

Linux相关

文件权限符号

  • 第一个字符表示文件类型：
    • 普通文件：-
    • 目录文件：d
    • 字符设备文件：c
    • 块设备文件：b
    • 符号链接文件：l
    • 命名管道文件：p
    • socket文件：s
  • r：读权限。
  • w：写权限。
  • x：可执行权限。
  • -：没有权限。
  • s：SET位可执行权限。
    • SUID：只对二进制文件有效
    • SGID：对普通文件和目录有效
  • t：粘滞位权限。Sticky。在该目录创建的文件或目录只有创建者才有权限删除。
  • -rwxr-xr-x：文件类型(普通文件-)，所有者权限(r读/w写/x可执行)，所属组的权限(r读/x可执行)，其它用户权限(x可执行)
  • 权限属性后面有点(.)，表示该文件带有"SELinux的安全上下文"；
  • 权限属性后面标记为加号( )，表示使用了ACL(Access Control List)权限。
  • 如果文件权限后面附加一个空格，则表示系统没有可替换的访问控制措施。

修改文件权限

u = user, g = group,o = other, a = all

目录结构

  • / ：根目录 只有root用户具有该目录下的写权限
  • /bin：用户二进制文件 包含二进制可执行文件，包含常见的Linux命令。
  • /sbin：系统二进制文件 包含二进制可执行文件，但该目录下的Linux命令通常由系统管理员使用，对系统进行维护
  • /etc：配置文件 包含所有程序所需的配置文件，也包含了用于启动/停止单个程序的启动/关闭shell脚本
  • /dev：设备文件 包括终端设备、USB或连接到系统的任何设备
  • /proc：进程信息 这是一个虚拟的文件系统，包含正在运行的进程的信息。
  • /var：变量文件 可以找到内容可能增长的文件。包括： /var/log：系统日志文件 /var/lib：包和数据库文件 /var/mail：电子邮件 /var/spool：打印队列 /var/lock：锁文件
  • /tmp：临时文件 包含系统和用户创建的临时文件，系统重启后，文件都将删除
  • /usr：用户程序 包含二进制文件、库文件、文档和二级程序的源代码。包括： /usr/bin：包含用户程序的二进制文件 /usr/sbin：包含系统管理员的二进制文件 /usr/lib：包含/usr/bin和/usr/sbin用到的库 /usr/local：包含从源安装的用户程序
  • /home：HOME目录 所有用户用home目录来存储他们的个人档案
  • /lib：系统库 包含支持位于/bin和/sbin下的二进制文件的库文件
  • /boot：引导加载程序文件 把汗引导加载程序相关的文件
  • /opt：可选的附加应用程序 包含从个别厂商的附加应用程序。附加应用程序应该安装在/opt或/opt的子目录下
  • /mnt：挂载目录 临时安装目录，系统管理员可以挂载文件系统
  • /media：可移动媒体设备 用于挂载可移动设备的临时目录

常用命令

新手必须掌握的Linux命令

常见执行Linux命令的格式：命令名称 [命令参数] [命令对象]

arch：显示机器的处理器架构

uname -a：完整地查看当前系统的内核名称、主机名、内核发行版本、处理器类型等信息

uname -r：显示内核版本

echo [字符串 | $变量]：在中断输出字符串或变量提取后的值

date：显示系统时间

cal：显示日历

shutdown -h now：关闭系统

reboot：重启系统

cd /etc：切换工作路径

cd：进入个人的主目录

ls -al：显示目录中的文件信息

pwd：显示当前路径

tree：以树形结构显示目录

mkdir dir1：创建目录

touch file1.txt：创建文件

rm file：删除文件

rmdir dir1：删除目录

rm -rf dir1：强制删除目录下的文件

mv dir1 newdir：移动/重命名一个目录/文件

cp file1 file：复制文件

cp -a dir1 dir2：复制目录

cat -n file1：查看内容较少的文本文件的内容

tac file1：从最后一行开始反向查看文件的内容

more file1：查看内容较多的文本文件的内容

head -n 2 file.txt：查看文本文件的前2行

tail -n 2 file.txt：查看文本文件的后2行

tail -f log.txt：实时查看最新的日志文件

cat file.txt | tr [a-z] [A-Z]：替换文本文件中的字符，tr [原始字符] [目标字符]

wc file.txt：统计置顶文本的行数、字数、字节数

stat file.txt：查看文件的具体存储信息和时间等信息

diff -c file.txt file2.txt：查看文件内容具体的不同

file file.txt：查看文件的类型

tar czvf etc.tar.gz /etc：将/etc目录打包

tar xzvf etc.tar.gz /etc：将文件解压到/etc目录

ln -s file1 link1：创建指向文件/目录的软链接（若被指向的原文件被删除，则相关软连接就变成了死链接）

ln file1 link1：创建指向文件的硬链接（如果删除硬链接对应的源文件，则硬链接文件仍然存在，而且保存了原有的内容）

wget [参数] 下载地址：在终端中下载网络文件

ps -aux：查看系统中的进程状态（短格式和短格式之间是可以合并的，合并后仅保留一个-即可）

top：动态地坚实进程活动于系统负载等信息，查看系统运维状态

pidof sshd：查询某个指定服务进程的PID值

kill 2156：中止某个指定PID的服务进程

kill httpd：中止某个指定名称的服务所对应的全部进程

ifconfig：获取网卡配置和网络状态等信息

uptime：查看系统的负载信息，数值越低越好

free -h：显示当前系统中内存的使用情况

last：查看所有系统的登录记录

history：显示历史执行过的命令

history -c：清空所有的命令

sosreport：手机系统配置及架构信息并输出诊断文档

chmod ugo rwx dir1：设置目录的所有人u、群组g、其他人o，以读r、写w、执行x的权限

chmod ugo-rwx dir1：删除ugo的rwx权限

insmod led.o：向内核加载模块

文件系统

文件系统是针对于存储器分区而言的，而非存储芯片。

  1. 基于FLASH的文件系统（基于MTD驱动层）
    • jffs2（Journalling Flash FileSystem v2）日志闪存文件系统 主要用于NOR型闪存，不适合容量较大的NAND。 特点：可读写的、支持数据压缩的、基于哈希表的日志型文件系统，并提供了崩溃/掉电安全保护，提供“写平衡”支持等。 缺点：当文件系统已满或接近满时，因为垃圾收集的关系而使jffs2的运行速度大大放慢。
    • yaffs（Yet Another Flash File System） 用于NAND型闪存的日志型文件系统。相比jffs2，速度更快，挂在时间很短，内存占用较小。支持跨平台。自带NAND芯片的驱动，可以直接对文件系统操作。
    • Cramfs（Compressed ROM File System）只读的压缩文件系统 以分页压缩方式存储，在运行时解压缩。不支持应用程序以XIP(eXecute In Place，片内运行)方式运行。速度快，效率高，文件只读。
    • Romfs 简单的、紧凑的、只读的文件系统，不支持动态擦写保存，按顺序存放数据。支持应用程序以XIP(eXecute In Place，片内运行)方式运行。
    • 其他 fat/fat32、ext2
  2. 基于RAM的文件系统
    • Ramdisk 将一部分固定大小的内存当做分区使用。并非一个实际的文件系统，而是一种将实际的文件系统转入内存的机制，并且可以作为根文件系统。可以存放一些经常被访问而又不会更改的文件。
    • Ramfs/Tmpfs 基于内存的文件系统，工作于虚拟文件系统层(VFS)，不能格式化，可以创建多个，在创建时可以指定其最大能使用的内存大小。可以存储一些临时性或经常要修改的数据。Tmpfs在系统重新引导时会丢失所有数据。
    • NFS（Network File System）网络文件系统 通过网络共享文件的技术。可以利用该技术，在主机上建立基于NFS的根文件系统，挂载到嵌入式设备，可以很方便地修改根文件系统的内容。

存储设备

Flash

结合ROM和RAM的长处，具备可擦除可编程的性能，不会断电丢失数据，可以快速读取数据。

NOR Flash

  • 接口时序同SRAM，易使用
  • 读取速度较快
  • 擦除速度慢
  • 写入速度慢（需要先擦除）
  • 随机存取速度较快，支持XIP，适用于代码存储。常用于存放引导程序、根文件系统等
  • 单片容量较小

NAND Flash

  • 地址/数据线复用，数据位较窄
  • 读取速度较慢
  • 擦除速度快
  • 写入速度快
  • 顺序读取较快，随机存取速度慢，适用于数据存储。常用于存放用户文件系统等。
  • 单片容量较大

嵌入式平台启动流程

​ 系统从装有启动代码的Nor Flash启动后，初始化对应的硬件，包括SDRAM等，然后将Nand Flash上的Linux 内核读取到内存中，做好该做的事情后，就跳转到SDRAM中去执行内核了，然后内核解压（如果是压缩内核的话，否则就直接运行了）后，开始运行，在Linux内核启动最后，去Nand Flash上，挂载根文件，比如jffs2，yaffs2等，挂载完成，运行初始化脚本，启动consle交互，才允许你通过console和内核交互。至此完成整个系统启动过程。

RAM（Random Access Memory）

随机访问存储器，直接与CPU交换数据，也叫内存。可以随机读写，速度很快。断电后数据丢失。

SRAM（Static RAM）

  • 静态RAM，速度非常快，不需要刷新电路即可保存数据。
  • 集成度较低，非常昂贵，多用于CPU的一二级缓存L1/L2 Cache。

DRAM（Dynamic RAM）

  • 动态RAM，速度比SRAM慢，需要定时刷新充电才能保存数据。
  • 比SRAM便宜很多，多用于计算机内存。

DDR RAM（Double-Data-Rate RAM）

  • 可以在一个时钟读写两次数据，使得数据传输速度加倍了

C/C 相关

volatile作用

​ volatile声明的变量表示该变量随时可能发生变化，与该变量有关的运算，不要进行编译优化，以免出错

位操作

&（与）、|（或）、^（异或）、~（取反）、>>（右移）、<<（左移）

可重入函数和不可重入函数

  • 不可重入函数： ​ 在函数中如果我们使用静态变量了，导致产生中断调用别的函数的过程中，可能还会调用这个函数，于是原来的静态变量被在这里改变了，然后返回主体函数，用着的那个静态变量就被改变了，导致错误。
代码语言：javascript复制
char cTemp;            // 全局变量
void SwapChar1(char* lpcX, char* lpcY)
{
    cTemp = *lpcX;
    *lpcX = *lpcY;
    lpcY = cTemp;     // 访问了全局变量，在分享内存的多个线程中可能造成问题
}

void SwapChar2(char* lpcX, char* lpcY)
{
    static char cTemp;  // 静态局部变量
    cTemp = *lpcX;
    *lpcX = *lpcY;
    lpcY = cTemp;   // 使用了静态局部变量，在分享内存的多个线程中可能造成问题
}
  • 可重入函数： ​ 如果是在函数体内动态申请内存的话，即便新的线程调用这个函数也没事，因为新的线程使用的是新函数的新申请的动态内存（静态变量只有一份，所以多线程对于函数体内的静态变量改变会有无法修复的结果）。
代码语言：javascript复制
void strcpy(char* lpszDest, char* lpszSrc)
{
	while(*lpszDest   = *lpszSrc  );
    *dest=0;
}

​ 在实时系统的设计中，经常会出现多个任务调用同一个函数的情况。如果这个函数不幸被设计成为不可重入的函数的话，那么不同任务调用这个函数时，可能修改其他任务调用这个函数的数据，从而导致不可预料的后果。不可重入函数在实时系统设计中被视为不安全函数。

  • 满足下列条件的函数多数是不可重入（不安全）的：
    • 函数体内使用了静态的数据结构；
    • 函数体内调用了malloc()或者free()函数；
    • 函数体内调用了标准I/O函数。
  • 如何写出可重入的函数：
    • 在函数体内不访问那些全局变量、不使用静态局部变量，坚持只使用缺省态（auto）局部变量，写出的函数就将是可重入的；
    • 如果必须访问全局变量，记住利用互斥信号量来保护全局变量。或者调用该函数前关中断，调用后再开中断；
    • 不能调用任何不可重入的函数；
    • 谨慎使用堆栈。最好先在使用前先OS_ENTER_KERNAL；
    • 浮点一般都是不可重入的（在ISR中做浮点运算是不明智的）。
  • 可重入函数的条件：
    • 不使用任何(局部)静态或全局的非const变量。
    • 不返回任何(局部)静态或全局的非const变量的指针。
    • 仅依赖与调用方提供的参数。
    • 不依赖任何单个资源的锁（mutex等）。
    • 不调用任何不可重入的函数。

防止头文件和全局变量重复定义

协议相关

IIC

操作系统相关

进程与线程的关系

  • 进程是具有一定独立功能的程序，它是系统进行资源分配和调度的一个独立单位
  • 线程是进程的一个实体，是CPU调度和分配的基本单位
  • 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程（通常说的主线程）
  • 资源分配给进程，同一进程的所有线程共享该进程的所有资源
  • 线程在执行过程中，需要协作同步，不同进程的线程间要利用消息通信的方法实现同步
  • 真正在处理机上运行的是线程
  • 线程是指进程内的一个执行单元，也是进程内的可调度实体
  • CPU内核的个数与可同时运行的进程数相同。相反，若进程数超过核数，进程将分时使用CPU资源。

操作系统的功能

  • 处理器管理：处理中断事件，进程管理。
  • 存储器管理：内存管理。
  • 设备管理：管理各类外围设备。当用户使用外部设备时，必须提出要求，待操作系统进行统一分配后方可使用。当用户的程序运行到要使用某外设时，由操作系统负责驱动外设。操作系统还具有处理外设中断请求的能力。
  • 文件管理：对信息资源的管理。
  • 作业管理：每个用户请求计算机系统完成的一个独立的操作称为作业。

系统中的资源

  1. 可剥夺资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU和主存均属于可剥夺性资源；
  2. 不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

产生死锁的必要条件

死锁是指多个进程在运行过程中因争夺资源而造成的一种阻塞的现象。

  • 产生死锁中的竞争资源之一指的是竞争不可剥夺资源（例如：系统中只有一台打印机，可供进程P1使用，假定P1已占用了打印机，若P2继续要求打印机打印将阻塞）
  • 产生死锁中的竞争资源另外一种资源指的是竞争临时资源（临时资源包括硬件中断、信号、消息、缓冲区内的消息等），通常消息通信顺序进行不当，则会产生死锁

产生死锁的原因：

  1. 竞争系统资源
  2. 进程的推进顺序不当

产生死锁的必要条件：

  1. 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
  2. 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
  3. 不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
  4. 环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链。

解决死锁的基本方法：

  • **预防死锁：**通过设置一些限制条件，去破坏产生死锁的必要条件
    • 资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）
    • 只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏请保持条件）
    • 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
    • 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）
  • 避免死锁：在资源分配过程中，使用某种方法避免系统进入不安全的状态，从而避免发生死锁
  • 检测死锁：允许死锁的发生，但是通过系统的检测之后，采取一些措施，将死锁清除掉
    • 首先为每个进程和每个资源指定一个唯一的号码；
    • 然后建立资源分配表和进程等待表。
  • 解除死锁：该方法与检测死锁配合使用
    • 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
    • 撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态.消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。

原码、反码、补码

  • 机器数 一个数在计算机中的二进制表示形式
  • 真值

​ 将带符号位的机器数对应的真正数值称为机器数的真值。

ADC中的指标

  • 采样率：每秒采集信号的个数。采样率越高，采集的点数越多，那么对信号的还原度就越高。
  • 分辨率：最小刻度的指标。如采集的电压范围是0-5V，则16bit的ADC的最小刻度是5/2^16。分辨率也只能算是间接衡量ADC采样准确的变量。
  • 精度：在ADC最小刻度基础上叠加各种误差的参数。是可以直接衡量ADC采样精准的指标。通常ADC的精度=N*LSB Vc_sample Vshift Vnoise Vref … N。
  • 输入电容：用于储存输入信号。但是这个电容会跟输入的滤波电容分压，从而影响输入采样的精度。但一般经过计算，这个输入电容引起的误差非常小，可以忽略不计。
  • 输入漏电流：漏电流作用于输入的串联电阻，这样就会在电阻上产生压降，从而使得采样精度受到影响。如果电阻有10K级别，那产生的压降就是mV级，对精度的影响就很大了。
二叉树 缓存 node.js linux flash

0 人点赞