Author Archives: Yunfei

实时系统研究的主要方向/项目组/期刊会议

实时系统是计算机科学中的一个重要分支,其与嵌入式系统、操作系统、运筹与优化等领域具有较强关联。我读博期间选择了实时系统任务调度方向,多年下来也算有点经验。在这里,我总结一下实时系统领域内目前主流的几个研究方向,希望对初入这个领域的硕士/博士有所帮助。

1. 研究方向

  • 多核任务调度:Global/partitioned multicore scheduling;
  • 多核资源调度:Multiprocessor resource sharing protocols, e.g., MrsP;
  • 实时编程语言:Real-Time Ada/Spark, Real-Time Specification Java (RTSJ);
  • 多关键性系统:Mixed-criticality systems;
  • 虚拟化:Virtualization, dual-os;
  • 硬件相关:Many-cores,GPGPU并行化,ASIC;
  • 实时通信:工业实时总线,CAN消息调度;
  • 大型网络调度:WSN, Network-on-chip (NoC)

2. 研究项目组与大学

这里给出的实时系统研究组主要集中在欧美,国内的情况我不太熟悉,日后再做补充:

Europe

  • Real-Time Systems Research Group, University of York (York, UK)
  • ReTis Lab – Real-Time Systems Laboratory, Sant’Anna School of Advanced Studies (Pisa, Italy)
  • CISTER: Research Centre in Real-Time Computing Systems (Porto, Portugal)
  • Real-Time Systems Research Group (Vienna, Austria)
  • MRTC – Mälardalen Real-Time Research Centre (Vasteras, Sweden)
  • PARTS – Parallel Architectures for Real-Time Systems (Brussels, Belgium)
  • Real-Time Systems at TU Kaiserslautern (Kaiserslautern, Germany)
  • Real-Time and Embedded Systems Group at MPI-SWS (Saarbrücken, Germany)

America

  • Networked Real-Time and Embedded Systems Laboratory, University of Illinoi
  • Real-Time Systems Group, University of North Carolina
  • Cyber-Physical Systems Lab, Washington University in St. Louis

Asia

  • Timing Analysis Group, National University of Singapore

3. 相关学术会议

会议方面有专门针对实时系统的RTSS等,也有嵌入式方面的EmSoft,还有CPS方向的如ICCPS等:

实时系统方向:

  • RTSS (A*, CCF A)
  • RTAS (A, CCF B)
  • ECRTS (B)
  • RTCSA (C)
  • RTNS (C)
  • WCET (C)

嵌入式系统方向:

  • EmSoft (A*, CCF B)
  • Ada-Euorpe (B)
  • FPGA (B, CCF B)
  • NOCS (B, CCF C)

设计自动化方向:

  • DAC (A*, CCF A)
  • CODES+ISSS (A , CCF B)
  • ICCAD (A , CCF B)
  • DATE (B, CCF B)

信息物理系统/物联网方向:

  • ICCPS

以上内容算是抛砖引玉,相关内容我会不断更新。欢迎讨论与补充。

2019年工作展望

回顾2018年,因为科研工作忙碌,几乎没有新写文章,很多设立的目标没有达成。2019年需要再接再厉。

今年,我想主要围绕我自己的工作写一些中/英文的技术文章,在技术深度上稍加挖掘。云飞实验室在2019年设下的计划有:

  1. 增加实时系统相关的文章,包括实时操作系统的原理和任务调度等;
  2. 写若干机器人深度学习/深度增强学习的入门和调研文章;
  3. 自动驾驶中的一些关键技术;
  4. 写一些ROS与深度增强学习的结合使用;
  5. 写一些 系统工程(Systems Engineering) 和 基于模型的系统工程(MBE)方面的文章。

敬请期待。2019年和诸位一起努力。

RTOS实时操作系统杂谈

实时操作系统 (RTOS) 在工业控制、航空航天和电力系统中有大量应用。我自己接触实时操作系统已有几年时间,虽然实际的项目使用经验不多,然而耳濡目染还是积累了一些经验和知识。在这里整理和分享给大家。

实时操作系统(Real-time Operating System, RTOS)是针对有实时性要求的应用而设计的操作系统。这些应用通常包括汽车引擎控制、轨道交通、工业机器人、飞行器控制系统等。实时操作系统一般提供抢占式调度机制,重要的高优先级任务可以剥夺低优先级任务对CPU的使用权;同时,任务在等待使用资源时,RTOS可以将其CPU的使用权释放给其他就绪的任务,从而使得系统的总体响应速度更快。

1. 常见的RTOS

目前市场上常见的商用实时操作系统有:

  • uCosII / uCosIII | Micrium
  • FreeRTOS
  • Nucleus RTOS | Mentor Graphics
  • RTLinux (需要MMU支持)
  • QNX (需要MMU支持)
  • VxWorks | WindRiver
  • eCos
  • RTEMS

其中除了FreeRTOS, RTEMS和RTLinux是免费的之外,其余RTOS都是需要商业授权的。uCos II和FreeRTOS是平时接触比较多的RTOS,相关资料比较多。而VxWorks是安全性公认最佳的,用于航空航天、轨道交通和卫星的应用。如果系统中需要使用复杂的文件、数据库、网络等功能,那么以Linux为基础的RTLinux是比较好的选择;但是如果系统对实时性和确定性的要求非常高,那么可以使用较为简单的RTOS(如 uCosII),再根据需要开发通信协议或者软件包。总体上来说,操作系统的复杂性是与应用软件的复杂性一致的。同时,功能上更复杂的RTOS对硬件系统资源的需求也会更高。

2. RTOS的功能

一般的RTOS会提供以下全部或部分功能:

  • 基于静态优先级(fixed-priority)的抢占式(preemptive)任务调度;
  • 进程间通信(基于消息,消息邮箱,管道);
  • 基于信号量(semaphore)的进程间同步;
  • 任务的创建、暂停、删除;
  • 资源访问控制(并发控制与防止互锁);
  • 临界区(critical section)控制;
  • 驱动程序的管理与接口;
  • MMU内存管理、内存动态申请与分配;
  • 其他功能:如GUI用户界面和TCP/IP相关功能。

3. 选用指标

一般来说,实时操作系统的主要参数指标有:

  • 支持的优先级数量,如64、128或256;
  • 使用的任务调度算法:时间片轮转调度,加权轮转调度(weighted round-robin),先入先出(FCFS),优先级调度;任务调度算法决定了任务响应时间的可分析性;
  • 中断响应速度,即从中断产生到进入中断服务程序的时间;
  • 上下文切换时间,即任务切换时间;
  • 操作系统大小以及资源使用(footprint, ROM及RAM的占用);
  • 授权费用与授权方式,是按产品型号计费、产品数量计费还是一次性授权。

其他的选择指标主要就是文档的完整程度,是否有GUI支持,团队对该OS的了解程度,所支持的CPU型号以及需求功能的规模,以及相应的技术支持。从更专业的角度上来说,还有是否支持防死锁(deadlock)和优先级反转(priority inversion)等提高系统可靠性的功能,操作系统自身服务程序占用的时间大小。对于时间关键性应用,操作系统需要具备相对确定的执行时间(deterministic execution time)。从调试的角度来说,操作系统是否具有调试功能(尤其是多线程、多核)以及支持的调试工具也是重要的指标。

4. 关于RTOS的误区

最后说一下关于实时操作系统的两个误区:

1、用了实时系统后,系统响应速度一定更快。不一定。因为实时操作系统本身引入了执行开销,所以对于小型应用来说,有RTOS的性能也许不如无操作系统的情况。实时操作系统的优势最能体现在中大型系统中,当任务间存在复杂的耦合和依赖关系,并且应用程序经常要长时间等待外部资源时。

2、用实时操作系统就可以保证实时性。不一定。相对来说,使用实时系统可以改善系统的实时性。但是实时操作系统只是作为工具存在的,如果需要提供实时性保障,还需要使用实时系统理论对任务的可调度性和响应时间进行分析,才可以得到科学、系统的响应性保障。

修订历史

  • 2018-05-22 (v1.1) 修改了部分内容,为知乎专栏调整了版式
  • 2015-08-17 (v1.0) 初版,在云飞机器人实验室发表

Linux系统全方位调试与维护工具整理

俗话说:“工欲善其事,必先利其器。”

在多年维护和开发Linux服务器的过程中,我接触了一些常用的开发和调试工具。本文将这些工具整理在一起,便于指导读者选择正确的工具。文中对于工具只有简单的介绍,需要详细的用法可以--help或自行Google。

本文针对的环境是CentOS/RedHat服务器 (需要epel库)。其他发行版应该也有相应的命令,但我没有一一测试。

系统管理

  • ssh: 远程登录
  • last, lastlog: 查看用户登录历史
  • cron: 设置周期运行的定时任务
  • at: 设置运行一次的定时任务
  • screen/nohup: 在后台运行程序,程序不会随着shell关闭而退出
  • rsync: 文件夹同步
  • pv: 文件拷贝(重定向方法,含进度条,但会丢失文件的权限信息)
  • lshw: 显示硬件信息
  • lscpu: 显示CPU信息
  • dmesg: 显示系统日志

资源监控

通过查看系统资源使用,快速定位性能瓶颈与系统异常。

  • 内存
    • free: 当前内存使用情况
  • 硬盘
    • df: 硬盘空间使用情况
    • iotop: 磁盘IO使用实时监视
    • ncdu: 分析文件夹使用的磁盘大小
  • CPU
    • 见进程调试
  • 网络
    • nethogs: 监控当前活跃的网络连接
    • nload: 主机上传/下载流量监控
  • 综合
    • glances: 系统资源、进程查看工具(我的最爱)
    • linux-dash/pyDash: 系统资源监控(基于网页)

内核调试

  • perf
  • kgdb: 内核调试工具
  • lsmod: 显示所有被使用的module
  • vmstat

进程调试

  • ps: 查看当前进程
  • top: 查看当前进程以及进程资源占用情况(动态更新)
  • htop: top替代工具,信息丰富,可以查看树状进程信息
  • pidof: 按进程名查PID
  • skill: kill的升级版,通过名字(而不是PID)kill进程

文件调试

  • tree: 将文件夹按树形显示
  • lsof: 显示当前程序文件(包括虚拟文件)打开情况
  • mc: Midnight Commander知名文件管理器

网络调试

  • curl: 发送HTTP, REST请求
  • tcpdump: 抓包工具,通过自带的与或非逻辑可以组合成复杂的过滤条件
  • wireshark: 类似tcpdump的老牌抓包神器
  • nmap: 网络开放端口扫描
  • ip: 网络管理工具集
  • fping: ping升级版
  • netstat
  • nicstat
  • iptraf

程序调试

  • gdb: gnu项目下的代码调试器
  • strace: 打印出进程调用了哪些系统调用。
  • ldd: 查看程序依赖库。
  • objdump: 打印目标码和反汇编结果。
  • xargs: 读取输入流并将读取的文本作为指定命令行工具的命令行参数。
  • ipcs: 显示进程间通信设施状态

其他工具

  • vim/nano: 文本编辑器
  • grep, sed: 文本信息处理
  • awk: 表处理,很强大的二维表处理功能,可以对格式化文本输出进行处理
  • jq: 命令行的json查询和格式化工具,适合查看REST接口的输出

References

[1] 用十条命令在一分钟内检查Linux服务器性能, http://www.infoq.com/cn/news/2015/12/linux-performance
[2] Linux Performance, Brendan D. Gregg, http://www.brendangregg.com/linuxperf

使用Markdown进行写作和文字记录

1. 背景

Markdown是一种语法简洁的标记语言 (Markup Language)。Markdown可以使用任何一种纯文本编辑器进行编辑,同时可以渲染、生成HTML。Markdown虽然是标记语言,但是和HTML比起来具有更好的可读性。与富文本(Rich Format Text, RTF)格式相比,Markdown的纯文本特性让使用者可以更加关注内容,专注于文字的表达。我多年前在友人的推荐下开始尝试用Markdown写作。我一开始并不习惯这种所写和所得分离的方式,但是之后也慢慢习惯、喜欢上了这种内容与格式分离的文字编辑方式。此文我整理了我关于Markdown的认识(本文也是通过Makrdown书写的),同时我推荐大家开始尝试用Markdown生产笔记、日记、文档、博客等文字信息。

2. 使用Markdown的好处

先说一下Markdown语言的优势:

  • 记录速度快:比起其他文字格式,Markdown可以更快地记录信息,编辑过程只需要键盘参与。基本的文字格式 (如标题,粗体,斜体等)可以通过快捷键实现,利用序号、列表功能还可以快速生成层次化的段落结构。
  • Markdown是纯文本格式,可以用普通文本编辑器编辑(nano, VIM, Notepad++等),方便修改和共享。
  • 可移植性好。工具是不断变迁的,对于富文本工具而言,更换工具就意味着文字格式无法完美保留(当初从写字板到word);而对于Markdown而言,因为源文件本身并没有格式编码,所以更换工具几乎不会影响版式。不同工具的渲染结果也几乎没有差别。
  • 重内容,轻版式。很多时候我们会浪费很多精力在文字的排版和格式统一上,而Markdown简单清晰的编辑方式,让我们可以集中于内容的编辑。
  • 可以生成HTML。Markdown在设计时就完全兼容HTML,可以直接插入HTML代码(但是不推荐,会影响纯文本的优点)。Markdown配合不同的CSS可以渲染成不同风格的网页,Markdown还可以导出为pdf。除此之外还可以渲染成多种格式(大多数编辑器有导出功能,或者用Pandoc转换)。
  • 图文分离,备份或者传播时简单、信息的体积小。

3. 使用Markdown的坏处

然而Markdown也并非完美:

  • 所见非所得。编辑器和Live Preview是独立的系统,如果需要实时预览,则需要编辑工具的支持。
  • 插图不方便。在富文本系统中可以直接copy + paste,而一般的Markdown系统则需要单独的文件夹存储图片,还需要额外输入图片路径。
  • 文字的表示形式有限。相比富文本,Markdown无法随心所欲地修改文字的属性(字体、颜色、大小等)。如果需要特殊的文字格式,需要插入额外的html属性,但是这些会破坏纯文本的移植性。
  • 页面版式、布局相对固定。总体来说只能是线性的记录方式。如果需要自由的图文混排,其他工具如Word或者Onenote是更好的平台。

Read more »

如何构建和管理自己的知识系统

1. 背景

三年前,我在做硕士毕业设计的时候第一次使用Evernote(印象笔记)收集资料,之后就一直使用Evernote记录一些备忘和生活琐事,但也没有形成相对完整的系统。开始读博士之后,我习惯随手在论文上记批注和笔记,觉得这样个人观点和原文的耦合度会比较高。但是等到要检索和引用资料时,脑中对这些知识点有些印象,可很多资料就是找不到出处,这时又要重新谷歌或者去翻文件夹。这让我思考是否需要将笔记做成电子形式,这样检索和使用的时候会比较方便,知识也能线性积累。去纸化的过程是比较痛苦的,因为我们从小到大习惯了纸质笔记这种记录方式。我们的工具十分简单(纸和笔),却可以记录各种类别的信息(文字、结构图、流程图、批注)。然而到了电子时代,我们可用的工具很多,但却很难形成和纸质笔记相比的“灵活性”。当然,相比传统的笔记方式,电子笔记可以多次修改、任意排序和整理、发布和分享、互相引用与检索,但有的时候却不如传统笔记那么“直观”和“简单”(想想用pdf做标注 v.s. 在书上直接做批注 或是 用画图软件画一个流程图 v.s. 在纸上随手画一个流程图)。在过去的一年时间里,我一直在思考和实践电子化笔记系统的可行性,以及如何凸显和最大程度发挥电子笔记的优势。而我发现,电子笔记不仅有上述提到的几个优势,还可以成为构建和强化知识系统的有力工具。

这里,我将一切广义上可以提高人对某一事物或领域的认知或记忆的信息(以文字为主)称为知识,而将通过计算机、平板、手机等手段记录个性化知识的方式称为电子笔记。此文分享了我对于知识和记笔记的理解,以及通过电子化工具构建知识系统的思考和经验。

2. 为什么需要记笔记?

上一节聊了我为什么需要将笔记电子化的动机,现在简单说一下我们为什么需要记笔记。每个人都有这样的经历:和别人聊天时,总是有一些感觉在嘴边的东西,大脑却无法回忆起来;或者某天去超市购物时,明明觉得需要买什么,却怎么也想不起来。不管我们认不认同,人脑的潜力不是无限的。理解我们自身局限性的其中之一,就是认识到人脑是有局限性的,并且记忆的容量是有限的。所以构建一个笔记/知识信息系统,就是要补偿人脑的这种局限性,将笔记系统作为我们的第二大脑。这个观点已经得到了主流大众的认可。我们知道记笔记需要花费时间,这种时间实际上是一种对未来的投资。我们一般记录事情的动机有两个:一是为了增强对摄取信息的认知;二是为了日后需要的时候可以回想起来。大部分人也应该可以认同记笔记是强化知识的重要手段。除此之外,记笔记的核心价值是“使用”。也就是说,一个好的笔记应该是有使用价值的。一个shopping list可以让你在逛超市的时候买齐所有的东西;一篇日记让你可以回忆过去自己经历的事情;一篇论文笔记让人在需要的时候可以快速回忆起论文的核心观点;一个programming reference可以让你在编程的时候快速想起API的用法,而不用每次都去Google. 这些都是使用价值,是你记录时投资时间换来的回报。记录信息的本质是提供使用价值,所以评价一个笔记系统也应该用”可使用性”为评价方式。有一种观点是:现在(几乎)所有的信息都能在因特网上搜索到,所以需要信息的时候都可以即刻去搜索。这种观点本身没有问题,但是以目前的搜索技术和因特网的归档程度而言,这种方式的时间开销更高:因为你要从海量信息中筛选、判断、提炼出你想要的那一部分信息。而笔记则是“一次记录,多次使用”,一劳永逸。并且有新的知识点时,可以修改、完善之前的知识(另一点电子笔记的优势就是修改起来十分简单)。我们记笔记,就是让笔记成为知识的载体,也是为了日后需要这个知识时提供便捷。

Read more »

【C语言深入】陷阱:数组溢出导致内存被意外修改

C语言的指针在提供编程便利的同时,却带来了很多潜在的内存安全问题。见以下例子:

#include <stdio.h>

int main() {

	char string_buff[12];
	unsigned int i_not_zero = 0xFF;

	sprintf(string_buff, "Hello,world!");

	printf("i = %x\r\n", i_not_zero);

	return 0;
}

该程序(不正确)的输出为:

i = 0

上述代码使用sprintf修改了string_buff指针所指向的char型数组。但是由于在申明数组长度的时候,没有考虑到字符串结束符’\0’,所以实际写入时不慎篡改了下一位内存地址的内容(此例中为i_not_zero, 使用MinGW gcc)。在实际程序中,此类bug一般很难被发现,尤其是还有其他程序在正常修改该值时,一般先会去排查和该变量有关的程序。

这只是一个因为不慎所导致的内存溢出问题,而在一些极端的黑客代码中,经常会见到通过内存变量和函数的指针地址反向访问、修改堆栈,从而获得系统的权限。可见指针作为C语言的一个重要(但是晦涩的)组成部分,无形中降低了系统的可靠性和安全性,需要挑战programmer的debug能力。

你好,2017!

又是新的一年。岁月匆匆,不给人时间回头看看,就又让人上路了。

今年更新了10篇左右的博文:

  • 新增的”C语言深度”专题来源于我在嵌入式课程助教过程中发现的C语言的错误使用。我觉得C和C++是机器人领域最重要的两个语言,所以希望在这方面增加一些内容。
  • 另几篇博文是介绍新发布的树莓派3代的。今年除了树莓派3,还入手了若干树莓派Zero。因为Zero很难买到,所以一下屯了5、6个。这批Zero准备用在智能家庭的节点中,但是应用场景目前还不明确,所以没有给大家做专题介绍。

明年的工作计划:

  • 承诺的智能家庭系统还没有完全开发完成,全部完成后会找时间公布。目前已完成的部分:中心服务器的部署,NAS,多媒体中心,一个传感器节点部署好了(已经上报了半年的温湿度数据)。二氧化碳、PM2.5传感器和无线组网模块选购好了,但还没有时间调试。另一个困难是控制数据的下发和传感器数据、系统参数的展现,我想基于BS架构(Flask + socket.io / Node.js + Ajax)。我没有网页编程的基础,而且中间涉及Real-time和asynchronous的问题,所以还没有时间解决。
  • More topics on Robotics. 实验室还是以机器人为主题的,去年有点跑偏了(嵌入式系统),今年重新回归到主题上。重点我想要关注的内容点有:增强学习、概率决策、机器视觉、ROS、机器(深度)学习。
  • 博主现在长期在国外生活,关于将网站转换为全英文的想法已有很久。但是还是一直很挣扎,考虑到很多内容对国内的读者会有帮助,所以今年还是保留双语写作。

最后祝大家2017年工作、学习顺利!

【C语言深入】陷阱:数组指针作为函数参数返回

再来看一个指针问题,同样的来自一个本科生的代码。这段代码想要实现将一个全是小写字母的字符串转换成对应的大写字母字符串:

char *covert_to_upper_case(char *string) {
    char p[100];
    int i = 0;
    
    for(; i < strlen(string); i++ ) {
            p[i] = string[i] - ('a' - 'A'); 
    }
    p[i] = '\0';
    
    return p;
    
}

然而这段代码没有能实现期望的功能。原因如下:

  1. 主程序调用convert_to_upper_case()函数后,堆栈为p分配了内存空间;
  2. 函数体正确修改了p对应字符数组的内容,并将p的首地址作为指针返回;
  3. 函数返回后,所有临时变量从堆栈中弹出,包括p[100];
  4. 主程序得到返回的指针,对其进行解析。然而指针指向的字符数组此时已经从堆栈中弹出,解析后的数据无法被定义。

要想正确实现对应的功能,应该将目标指针作为额外参数传递给该函数,并由上层调用者提供内存空间的创建。当然也可以使用malloc()将内存分配在堆中,但是需要注意使用对应的free()释放空间,否则会有内存泄露的问题。

【C语言深入】指针的一个错误赋值

关于指针总是有说不完的故事。

最近给本科的学生带Embedded System课程设计,遇到了一个非常奇怪的bug。有一段代码需要实现I2C通信,核心代码已经由软件库提供了,学生只需要设置结构体后调用API即可。一个学生的代码是这样的:

struct I2C_CONFIG {
  // ...
  char *i2c_buff;
  int length;
  // ...
};

struct I2C_CONFIG cfg;
char *i2c_buff;

void I2C_init() 
{
  // ...
  cfg.buff = i2c_buff;
  cfg.length = sizeof(buff);
  // ...
}

void I2C_send(new_buff)
{
  // ...
  i2c_buff = new_buff;
  I2C_MasterTransferData(LPC_I2C1, cfg);
  // ...
}

初看一下没有什么问题:在I2C_init()函数中首先对结构体cfg进行初始化,而在I2C_send()函数中设置了需要发送的数据指针,之后使用I2C的API发送数据。

因为代码一直无法实现期望的功能,我又仔细看了一下其中的蹊跷。我注意到,这段代码中使用了一个中间变量:char *i2c_buff。在I2C_init()中虽然将cfg.buff指向了i2c_buff,但是因为cfg.buff本身也是指针变量,而非”指向指针的指针”,所以这里只实现了简单的按值传递,即将i2c_buff的值 (初始值为0) 赋给了cfg.buff。之后虽然在I2C_send()中修改了临时变量i2c_buff指向的位置,但却没有影响到cfg.buff中的内容,cfg.buff依然指向之前i2c_buff初始化时指向的内存地址,所以需要发送的缓冲指针new_buff其实并没有传递给之后的I2C_MasterTransferData()函数!为了解决这个问题,必须将更改后的i2c_buff的值再次赋给cfg.buff,即:

void I2C_send(new_buff)
{
  // ...
  i2c_buff = new_buff;
  cfg.buff = i2c_buff;
  I2C_MasterTransferData(LPC_I2C1, cfg);
  // ...
}

另外这段代码还有一个不容易注意的bug,就是在I2C_init()中使用了sizeof()来判断buffer的大小。因为sizeof()函数得到的只是数据类型的大小,所以对于指针char *i2c_buff来说,sizeof(i2c_buff) = 4,而不会返回buffer的实际大小。指针的大小并不等于指针指向缓冲的大小!