Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1519372
  • 博文数量: 177
  • 博客积分: 9416
  • 博客等级: 中将
  • 技术积分: 2513
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-06 16:08
文章分类

全部博文(177)

文章存档

2013年(4)

2012年(13)

2011年(9)

2010年(71)

2009年(12)

2008年(11)

2007年(32)

2006年(25)

分类: C/C++

2013-03-08 23:26:24

记得清华出版社的《数据结构》里面说过,程序的本质是数据结构+算法。这实际上就是编程的本质,至少在目前主流的计算环境里是这样的。其实更通俗点说来,数据+计算构成了编程的本质问题。通常,数据就是现实世界的一些属性的集合,是完成某些计算所需要的输入,并且以另外一种形式作为这些计算的输出。无论所使用的算法如何复杂、系统里各组件之间的通信和交互如何繁琐,本质上都是对一些数据进行计算,而计算本身又可以使用一些数据来进行抽象(例如状态机)。

为了完成“现实→模型→计算机”的转换,抽象是必不可少的一个过程。然而在计算环境中是完美的抽象并不存在,只有适合计算环境的抽象才是最好的抽象。不仅如此,抽象还是分层级的,在现实→模型→计算机”的转换里,每一步转换可能都包含多层抽象,甚至包含对某类实体的不同抽象。举个最简单的例子,在加油站里,汽车抽象为邮箱容积就基本够用,而在卖家那里,则需要抽象为颜色、车型、发动机型号……换句话说,在加油站,汽车只需要提供加油的接口,而在卖家那里,汽车需要提供发动机型号、车型、油耗等接口。

既然抽象需要根据计算环境来确定,那么我们就必须对所使用的计算环境非常了解。比如计算环境的操作系统是什么,需要使用到什么样的第三方组件(库、框架、中间件等等),内存、数据带宽(包括总线、网络、外设等等)都需要根据实际情况考虑到。其中操作系统以及第三方组件的特性是最基本的元素。

那么在考察操作系统的特性时,无外乎这么几种:同步机制、进程间通信、是否支持多任务、上下文切换的代价、是否为抢占式等等。不过,对于应用开发者而言,考虑同步机制以及进程间通信基本就足够了;对于驱动和内核组件开发人员来说,多任务、上下文切换、抢占等因素就显得十分重要。

有了这些背景知识之后,我们便可以开始勾勒一个系统的蓝图。通常来说采用“4+1视图”法来进行设计是不错的选择。当然,我们不要太教条——一定要用UML来建模并形成文档,只需要根据“4+1视图”的原则来分析问题就可以了。通常对于大型应用或者中间件来说,用例视图相当重要,而对于某些用例并不那么明显,只需要提供一些特定数据的组件来说,我们就可以弱化用例视图的作用。

然后我们就可以对问题进行抽象。用例视图里每一个用例都会对应一个操作,这个操作能够映射到一个或者几个数据的集合,于是我们便得到了所需要的数据方面的抽象,即对现实世界某些属性的抽象。这些数据(或者抽象)必然会有相互之间的通信,及相互转换、依赖关系等等,这些便是数据之间的接口,这些接口规定了数据所应当支持的计算。通常说来,数据及接口的抽象属于逻辑视图应当考虑的部分。

为了将数据和接口的抽象与计算环境结合起来,我们就需要考虑计算环境的特性,例如如何设计同步接口,如何设计多任务接口,如何支持抢占等等。为了贴合计算环境,需要增加一些辅助的接口,使得本来的接口能够与计算环境适配。

下面就简要讲一下最近在项目——为单进程多任务抢占式系统内核增加位置服务框架(说白了就是为功能手机增加GPS支持)。由于厂商提供GPS芯片以及一套计算引擎库用于计算GPS接收机所处的位置,因此我们只需要将这套软硬件集成到功能机上。

需求很简单,只需要将芯片产生的裸数据通过设备驱动发送给计算引擎,然后从计算引擎中得到结果,并发送给系统的中间件,最终发送给用户应用程序。如果只有GPS,那么系统架构会非常简单。关键的问题在于需要支持A-GPS功能,这就需要跟网络打交道,同时需要使用SSL协议。那么,我们可以将数据抽象出来:
  • 提供给用户的数据:位置数据、nmea 0183数据
  • 提供给GPS芯片的数据:无
  • 提供给计算引擎的数据:GPS芯片数据、辅助数据
  • 辅助数据来源:SSL连接、蜂窝数据、wifi……
由于系统是单进程多任务抢占式的,系统应该尽量少地使用锁的机制,因此,任务之间的通讯和执行时序就非常重要——基本上采用消息传递和异步通知的方式来进行。对于同一个任务中的异步消息传递,可以使用回调的机制来实现;而对于不同任务中的异步消息传递,应当使用上下文切换的机制来传递消息;如果涉及到对共享资源的操作,就需要封装良好的同步保护机制——当然需要尽量减少保护机制的使用。

由于系统资源有限,很多计算都运行在同一个任务中,那么,在同一个任务中如何进行消息传递就是急需解决的问题。我们采用的是在任务内部的消息延迟传递机制,先把消息存在队列中,在任务的上下文恢复时真正将消息发给自身。该队列是一个轻量级的消息队列实现,因为系统的消息队列实现还是太“重”了,所以我们自己做了一个。

由于系统基本上使用异步方式来执行,因此,许多计算过程都需要抽象为状态机,使得这些计算在数据没有就绪的情况下不会阻塞任务中其他的计算。

另外,由于设备驱动处于另外一个任务中并具有更高的优先级,而且在向位置服务框架所处的任务发送数据时是以中断的形式处理的,而系统又是一个抢占式的系统,因此需要将数据缓冲保护起来(这种保护是不可避免的)。这里又出现了一个问题,那就是计算引擎在初始化芯片时会大量写数据导致通信硬件缓冲区瞬间被写满,那么就需要在设备驱动中增加一个二级缓冲,并使用硬件的中断机制来通知驱动何时能够继续向硬件通信端口写数据。

根据上面的描述,我们从计算过程中又得到了一些数据的抽象:
  • 状态机
  • 消息发送机
  • 定时器(控制时序)
作为系统内核级的框架,需要支持多个客户端的访问,因此又需要定义一套数据与接口用来描述和处理多个客户端的访问请求。

这些数据又隐含了一些接口,如状态迁移、向状态机发送消息、超时消息……最终,位置服务框架的架构如下:
  • 实现中间件的接口:将中间件的接口转化为相应的计算并返回结果
  • 负责计算引擎与框架的通信:回调机制、上下文切换、消息机制、定时器超时
  • 负责计算引擎到芯片的通信:通信接口
  • 负责芯片到框架的通信:通信接口、上下文切换
  • 负责辅助数据来源与框架的通信:消息机制、状态迁移、定时器超时
  • 核心数据:位置信息、nmea数据、GPS卫星信息等
  • 辅助数据:状态机、消息发送机、定时器
将这些数据和计算组合到一起,便形成了位置服务框架。

注1:若采用有指针功能的编程语言是,需要注意在数据搬运过程中指针所指内存所有权的传递——传递指针所有权,使用方释放;还是拷贝指针指向内容,申请方释放。在我的经验中,不注意内存所有权的传递比较常见而且很难调试。 
阅读(6215) | 评论(5) | 转发(1) |
给主人留下些什么吧!~~

fera2013-03-10 16:14:44

moon_rock:什么是操作系统?对硬件的抽象与管理。好的抽象应该是kiss,完全描述硬件特征,完全掌控硬件管理,当然这是不可能的。
从这个角度来看,编程的本质,应该是抽象,如何更好地抽象。
说计算机是图灵机,有限状态机,硬件不断探测下一个状态,然后执行状态切换,依此来模拟时间递增对事物造成的变更。
如果把世界看成是事物的集合、事物的变化、事物间的交流,那么图灵机是完备。
然后在图灵机上具像一些概念。比如多用户,多任务分时复用机制。然后就是如何实现多用户,多任务的分时复用,各种同步机制,内核态与用户态通知机制,如何

抽象确实是本质,因为数据和计算都可以被抽象。其实在单任务系统上,回调机制并不是分时服用,事件机制才是。因为回调机制还是运行于同一个任务的上下文中。

回复 | 举报

moon_rock2013-03-10 11:48:33

分配时间片(schedule),出错通知机制等等。
楼主说的定时器,或者说是时间驱动,只是图灵完备的一部份。
而所谓的回调机制,应该是分时复用的一部分。

moon_rock2013-03-10 11:46:30

什么是操作系统?对硬件的抽象与管理。好的抽象应该是kiss,完全描述硬件特征,完全掌控硬件管理,当然这是不可能的。
从这个角度来看,编程的本质,应该是抽象,如何更好地抽象。
说计算机是图灵机,有限状态机,硬件不断探测下一个状态,然后执行状态切换,依此来模拟时间递增对事物造成的变更。
如果把世界看成是事物的集合、事物的变化、事物间的交流,那么图灵机是完备。
然后在图灵机上具像一些概念。比如多用户,多任务分时复用机制。然后就是如何实现多用户,多任务的分时复用,各种同步机制,内核态与用户态通知机制,如何

moon_rock2013-03-10 11:33:22

个人认为编程的本质是从计算机如何去执行和如何去抽象业务需求这两个方面去寻求统一。

moon_rock2013-03-10 11:30:55

很多想法,思路跟博主不谋而合。