RT-Thread概述
嵌入式实时多线程操作系统,基本属性之一是支持多任务。
一个处理器核心在某一时刻只能运行一个任务。
在RTT中,任务通过线程实现。
RTT主要采用C语言编写,浅显易懂,方便移植。它把面向对象的设计方法应用到实时系统设计中,使得代码风格优雅、架构清晰、系统模块化并且可裁剪性非常好。
相较于Linux操作系统,RTT体积小,成本低,功耗低,启动速度快,实时性高,占用资源小,非常适用于资源受限的场合。
物联网操作系统是指以操作系统内核为基础,包括文件系统、图形库等较为完整的中间件组件,具备低功耗、安全的软件平台。
RTT与其他OS不同,它不仅仅是一个实时内核,还具备丰富的中间层组件。
系统启动
系统启动先从汇编代码开始运行,然后跳转到C代码,进行系统功能初始化,最后进入用户程序入口。
- 初始化与系统相关的硬件;
- 初始化系统内核对象,如定时器,调度器;
- 初始化系统设备,为设备框架做初始化。
- 初始化各个线程,启动调度器。
内核是一个操作系统的核心,是操作系统最基础也是最重要的部分。它负责管理系统的线程、线程间通信、系统时钟、中断及内存等。
int *p1 = new int[10];
int *p2 = new int[10]{};
- p1申请的空间里的值是随机值,p2申请的空间里的值已经初始化。
数组作为函数参数的时候会变为指针,所以数组作为函数参数的时候,通常要传递数组大小。
类中一旦有virtual修饰的成员函数,编译器会构建虚函数表,在该类的对象中会存放一个指向虚函数表的指针。
什么都没有或仅有非虚成员函数的类,占1字节,若该类为基类,其子类不算1字节空间。
对齐规则,代码开头对齐宏#pragma pack
方法重载,返回值类型可以一样,也可以不一样
MyClass c1 = c2; //调用的是拷贝构造函数
MyClass c1;
c1 = c2; //赋值操作
小型机通常采用RISC和unix操作系统。
(n & (n-1) ) == 0的作用
对于一个整数n,如果它是2的幂,那么它的二进制表示中只有一个位是1,其他都是0。
n-1的二进制会将唯一的1变为0,并且它右边的所有位变为1。
n & (n-1),如果n是2的次幂,结果是0。
不含回路的有向图一定存在拓扑排序。
删除小顶堆的堆顶元素后:
- 删除堆顶元素:将数组中的最后一个元素移动到堆顶,并移除最后一个元素。
- 调整堆:从堆顶开始,进行堆的向下调整,确保每个父节点都小于其子节点。
20个节点的三叉树(每个节点都有三个指向孩子节点的指针),有多少个空指针?
- 20个节点,每个节点3个指针,一共60个指针。
- 20个节点,19条边,每个边一条非空指针。
- 空指针:60-19 = 41
要在遍历过程中删除一个std::vector中的元素,要使用erase方法。
使用erase方法时,erase会返回指向删除元素的下一个元素的迭代器。
Linux的系统优势有:
- 多用户多任务、使用者与群组的规划。
- 稳定、高效和安全。
哈夫曼树中权值最小的两个节点互为兄弟节点。
类实例不能用memset。
不管系统是否支持线程,进程都是资源分配的基本单位。
d c b a e
d e c b a
d c e b a
d c b e a
C++程序运行时,地址是否固定要看系统配置和编译选项,如果开启了地址随机化,那么地址是每次都变的,如果没开启,那么地址每次都一样。
堆是优先级队列的底层实现,有N个元素的优先级队列进行一次结构调整的时间复杂度为log N。
堆内存是一种动态分配的内存,其实际占用内存空间的大小随着程序的运行可以动态调整。
只有执行主动关闭端才有TIME_WAIT。
I/O多路复用
I/O多路复用是一种编程技术,用于同时监视多个I/O通道(文件描述符、网络套接字等),以查看哪些通道可以进行非阻塞I/O操作(如读或写)。
通过这种技术,程序可以高效处理多个I/O操作,无需为每个I/O通道单独创建一个线程或进程。
I/O多路复用的工作原理
- 准备文件描述符集合:程序指定一组文件描述符,这些文件描述符可能对应不同的I/O通道(例如网络连接、文件等)。
- 调用多路复用函数:程序调用一个多路复用函数(如select。poll或epoll),该函数会阻塞程序的执行,直到其中一个或多个文件描述符变为就绪。
- 一旦函数返回,程序就会检查哪些文件描述符就绪,并对这些文件描述符执行相应的I/O操作。
- 重复过程:程序通常会在一个循环中重复上述过程,以持续监视和处理多个I/O通道。
select
- 使用一个或多个fd_set来指定要监视的文件描述符。
- 通过遍历文件描述符集合来检查哪些文件描述符就绪。
- 有文件描述符数量限制(通常为1024),处理大量文件描述符时效率较低。
poll
- 使用一个数组来指定要监视的文件描述符及其事件。
- 没有文件描述符数量限制。
- 处理大量文件描述符时,效率仍然不够理想,因为每次调用都要遍历整个数组。
epoll(仅适用于Linux)
- 提供更高效的I/O多路复用机制。
- 使用epoll_create创建一个epoll实例,使用epoll_ctl添加、修改或删除文件描述符,使用epoll_wait等待事件发生。
- 更适合处理大量文件描述符,因为只返回活跃的文件描述符集合,不需要遍历整个集合。
- 支持水平触发和边缘触发模式。
优点
- 程序可以同时监视多个I/O通道,无需为每个通道创建一个线程或进程,从而减少了上下文切换的开销。
- 减少了对线程和进程的需求,从而节省了系统资源。
- 程序可以根据就绪的文件描述符集合来动态执行相应的I/O操作,提高了处理的灵活性和响应性。
I/O多路复用广泛应用于需要处理大量并发连接的网络服务器,如Web服务器等。
epoll比select更高效率,主要是其基于操作系统支持的I/O事件通知机制,而select是基于轮询机制。
计算机操作系统出现死锁的原因是:若干进程因竞争资源而无休止地等等着其它进程释放已有的资源。
NAT(网络地址转换)是一种将私有IP地址转换为公共IP地址的技术,常用于路由器和防火墙中。NAT可以让多个设备共享一个公共IP地址,从而节省IP地址提高网络安全性。
地址转换又称为地址翻译,用来实现私有地址和共用网络地址之间的转换。
当内部网络的主机访问外部网络的时候,一定需要NAT。
地址转换的提出为解决IP地址紧张的问题提供了一个有效途径。
抽象类
A *p;
int *a,b;
定义了一个int型指针a,和一个int型变量b。
- SYN
- SYN + ACK
- ACK
指针p是类A的指针,而类A是类B的父类,使用p指针指向B类时,一般情况下同名成员会指向它的父类成员,而使用virtual关键字能指定成员函数为虚含蓄,这样父类指针能引用到子类的同名函数。
能够支持随机的插入和删除操作,并有较好性能的是链表和哈希表。
二叉排序树,若它的左子树不为空,则左子树所有节点均小于根节点的值;若右子树不为空,则右子树所有节点的值大于根节点的值;左右子树也分别为二叉排序树。中序遍历得到一个递增有序数列。
*b += 2等价于 (*b) = (*b)+2
一个西瓜切三次,最多可以被分成八块。
x[1000][1000]在内存中,是按行进程存储。D选项,操作第i行时,会将第i行后面的部分数据预取到cache。
数组名是指向第一个元素的指针常量,这意味着不能更改数组名指向的地址。
c语言中const是指定这个变量是只读的,而非真正意义上的常量,可以通过指针修改。
C++中常量都会有一张常量表,任何对常量读取都是从这个表里直接读取,而通过指针进行修改,修改的是常量在栈上对应地址空间的内容,本身常量表里的内容不会被修改。
静态分配是指在编译阶段就能确定大小,由编译器进行分配,堆不可以静态分配,堆的申请是在执行过程中进行的。
C++中为什么用模板类的原因?
- 代码复用。
模板类允许编写一次代码,并可以在不同的数据类型上重用,从而减少重复代码。例如,使用模板类可以创建一个通用的容器类,如std::vector,它可以存储任何类型的数据,而不需要为每种数据类型编写单独的类。 - 类型安全。
模板类在编译时进行类型检查,从而提高了类型安全性。通过使用模板类,编译器可以确保在模板实例化过程中类型的一致性,减少运行时类型错误。
可以用来创建动态增长和减小的数据结构。
它是类型无关的,因此有很高的可复用性。
它是平台无关的,可移植性。
封装,把客观事物封装成抽象的类,并且类可以把自己的数据和方法只让可信的类或者对象操作,对不可信的进行信息隐藏。
继承可以使用现有类的所有功能,并在无需重新编写原来类的情况下对这些功能进行扩展。
隐藏是指派生类中的函数把基类中相同名字的函数屏蔽掉了。
线程安全问题一般是由全局变量以及静态变量引起的。线程安全问题通常由于多个线程同时访问或修改共享资源(如全局变量和静态变量)引起的。这种共享访问可能导致竟态条件,数据不一致和未定义行为。
若每个线程中对全局变量、静态变量只有读操作,而无写操作,一般来说,这个全局变量是线程安全的;若有多个线程同时执行写操作,一般都需要考虑线程同步,否则的话就可能影响线程安全。
POSIX线程标准要求C标准库的大多数函数具备线程安全性。例如,大多数线程标准库函数,如malloc、printf等,在POSIX系统中都是线程安全的,允许给多个线程中安全使用。
static数据成员必须在类体之外进行定义。
#include <file.h>和#include “file.h”
- 前者从Standard Library的路径寻找和引用file.h,后者首先从当前工作路径搜索并引用file.h
C++类体系中,不能被派生类继承的有:
- 构造函数
- 静态成员函数
- 赋值操作函数
new/delete都是要分两步操作的:new分配内存,并且调用对象的构造函数初始化一个对象;delete调用相应的析构函数,然后释放内存。
malloc/delete只是分配/回收内存。
malloc需要头文件"stdlib.h"或"malloc.h"。
new/delete是内建的操作符,而malloc是一个函数。
静态成员存在于内存,非静态成员需要实例化才会分配内存。
非静态成员可以直接访问静态的成员。
但静态成员无法访问非静态成员。
switch语句后的控制表达式只能是short、char、int、long整数类型和枚举类型。
ifndef/define/endif 防止头文件被重复引用。
数组比链表速度更快的是原地逆序、返回中间节点、选择随机节点。
C++将父类的析构函数定义为虚函数,目的是为了释放父类指针时能正确释放子类对象。
C++的多台肯定是使用父类的指针指向子类的对象,所以肯定是释放子类的对象,如果不使用虚函数的话,父类的指针只能释放父类的对象。
随机链表的复制
回溯+哈希表
如果是普通链表,我们可以直接按照遍历的顺序创建链表节点。
因为随机指针的存在,当我们拷贝节点时,当前节点的随机指针指向的节点可能还没创建。
我们利用回溯的方式,让每个节点的拷贝操作相互独立。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
unordered_map<Node*, Node*> cacheNode;
Node* copyRandomList(Node* head) {
if(head == nullptr){
return nullptr;
}
if(!cacheNode.count(head)){
Node* headNew = new Node(head->val);
cacheNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cacheNode[head];
}
};
翻转二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr){
return nullptr;
}
TreeNode* leftNode = root->left;
TreeNode* rightNode = root->right;
root->left = invertTree(rightNode);
root->right = invertTree(leftNode);
return root;
}
};