新一代操作系统的构想

当一堆机器通过puppet、pssh这样的软件在管理的时候,你真想,如果它们共同运行一个操作系统,由那个操作系统统一替你协调这些机器该多好,而这个操作系统不能是openstack那种以机器(运行Linux、Windows这样的操作系统的环境)为单位的,而应该是以我的“程序”为单位的。软件架构,不能太过离散。

日志、定时器事件、用户、安装包……为什么不统一规划呢?以前的OS是面向单机的,现在的OS是面向群集的,这可能就是Elastos该出手的地方。

 | 415 views | 0 comments | 2 flags | 

【转】Linux虚拟地址空间布局

http://www.cnblogs.com/clover-toeic/p/3754433.html

 

在多任务操作系统中,每个进程都运行在属于自己的内存沙盘中。这个沙盘就是虚拟地址空间(Virtual Address Space),在32位模式下它是一个4GB的内存地址块。在Linux系统中, 内核进程和用户进程所占的虚拟内存比例是1:3,而Windows系统为2:2(通过设置Large-Address-Aware Executables标志也可为1:3)。这并不意味着内核使用那么多物理内存,仅表示它可支配这部分地址空间,根据需要将其映射到物理内存。

虚拟地址通过页表(Page Table)映射到物理内存,页表由操作系统维护并被处理器引用。内核空间在页表中拥有较高特权级,因此用户态程序试图访问这些页时会导致一个页错误(page fault)。在Linux中,内核空间是持续存在的,并且在所有进程中都映射到同样的物理内存。内核代码和数据总是可寻址,随时准备处理中断和系统调用。与此相反,用户模式地址空间的映射随进程切换的发生而不断变化。

Linux进程在虚拟内存中的标准内存段布局如下图所示:

其中,用户地址空间中的蓝色条带对应于映射到物理内存的不同内存段,灰白区域表示未映射的部分。这些段只是简单的内存地址范围,与Intel处理器的段没有关系。

上图中Random stack offset和Random mmap offset等随机值意在防止恶意程序。Linux通过对栈、内存映射段、堆的起始地址加上随机偏移量来打乱布局,以免恶意程序通过计算访问栈、库函数等地址。execve(2)负责为进程代码段和数据段建立映射,真正将代码段和数据段的内容读入内存是由系统的缺页异常处理程序按需完成的。另外,execve(2)还会将BSS段清零。

用户进程部分分段存储内容如下表所示(按地址递减顺序):

名称

存储内容

局部变量、函数参数、返回地址等

动态分配的内存

BSS段

未初始化或初值为0的全局变量和静态局部变量

数据段

已初始化且初值非0的全局变量和静态局部变量

代码段

可执行代码、字符串字面值、只读变量

在将应用程序加载到内存空间执行时,操作系统负责代码段、数据段和BSS段的加载,并在内存中为这些段分配空间。栈也由操作系统分配和管理;堆由程序员自己管理,即显式地申请和释放空间。

BSS段、数据段和代码段是可执行程序编译时的分段,运行时还需要栈和堆。

 

以下详细介绍各个分段的含义。

 

1 内核空间

内核总是驻留在内存中,是操作系统的一部分。内核空间为内核保留,不允许应用程序读写该区域的内容或直接调用内核代码定义的函数。

 

2 栈(stack)

栈又称堆栈,由编译器自动分配释放,行为类似数据结构中的栈(先进后出)。堆栈主要有三个用途:

  • 为函数内部声明的非静态局部变量(C语言中称“自动变量”)提供存储空间。
  • 记录函数调用过程相关的维护性信息,称为栈帧(Stack Frame)或过程活动记录(Procedure Activation Record)。它包括函数返回地址,不适合装入寄存器的函数参数及一些寄存器值的保存。除递归调用外,堆栈并非必需。因为编译时可获知局部变量,参数和返回地址所需空间,并将其分配于BSS段。
  • 临时存储区,用于暂存长算术表达式部分计算结果或alloca()函数分配的栈内内存。

持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中,从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时,若超出其容量就会耗尽栈对应的内存区域,从而触发一个页错误。此时若栈的大小低于堆栈最大值RLIMIT_STACK(通常是8M),则栈会动态增长,程序继续运行。映射的栈区扩展到所需大小后,不再收缩。

Linux中ulimit -s命令可查看和设置堆栈最大值,当程序使用的堆栈超过该值时, 发生栈溢出(Stack Overflow),程序收到一个段错误(Segmentation Fault)。注意,调高堆栈容量可能会增加内存开销和启动时间。

堆栈既可向下增长(向内存低地址)也可向上增长, 这依赖于具体的实现。本文所述堆栈向下增长。

堆栈的大小在运行时由内核动态调整。

 

3 内存映射段(mmap)

此处,内核将硬盘文件的内容直接映射到内存, 任何应用程序都可通过Linux的mmap()系统调用或Windows的CreateFileMapping()/MapViewOfFile()请求这种映射。内存映射是一种方便高效的文件I/O方式, 因而被用于装载动态共享库。用户也可创建匿名内存映射,该映射没有对应的文件, 可用于存放程序数据。在 Linux中,若通过malloc()请求一大块内存,C运行库将创建一个匿名内存映射,而不使用堆内存。”大块” 意味着比阈值 MMAP_THRESHOLD还大,缺省为128KB,可通过mallopt()调整。

该区域用于映射可执行文件用到的动态链接库。在Linux 2.4版本中,若可执行文件依赖共享库,则系统会为这些动态库在从0×40000000开始的地址分配相应空间,并在程序装载时将其载入到该空间。在Linux 2.6内核中,共享库的起始地址被往上移动至更靠近栈区的位置。

从进程地址空间的布局可以看到,在有共享库的情况下,留给堆的可用空间还有两处:一处是从.bss段到0×40000000,约不到1GB的空间;另一处是从共享库到栈之间的空间,约不到2GB。这两块空间大小取决于栈、共享库的大小和数量。这样来看,是否应用程序可申请的最大堆空间只有2GB?事实上,这与Linux内核版本有关。在上面给出的进程地址空间经典布局图中,共享库的装载地址为0×40000000,这实际上是Linux kernel 2.6版本之前的情况了,在2.6版本里,共享库的装载地址已经被挪到靠近栈的位置,即位于0xBFxxxxxx附近,因此,此时的堆范围就不会被共享库分割成2个“碎片”,故kernel 2.6的32位Linux系统中,malloc申请的最大内存理论值在2.9GB左右。

 

4 堆(heap)

堆用于存放进程运行时动态分配的内存段,可动态扩张或缩减。堆中内容是匿名的,不能按名字直接访问,只能通过指针间接访问。当进程调用malloc(C)/new(C++)等函数分配内存时,新分配的内存动态添加到堆上(扩张);当调用free(C)/delete(C++)等函数释放内存时,被释放的内存从堆中剔除(缩减) 。

分配的堆内存是经过字节对齐的空间,以适合原子操作。堆管理器通过链表管理每个申请的内存,由于堆申请和释放是无序的,最终会产生内存碎片。堆内存一般由应用程序分配释放,回收的内存可供重新使用。若程序员不释放,程序结束时操作系统可能会自动回收。

堆的末端由break指针标识,当堆管理器需要更多内存时,可通过系统调用brk()和sbrk()来移动break指针以扩张堆,一般由系统自动调用。

使用堆时经常出现两种问题:1) 释放或改写仍在使用的内存(“内存破坏”);2)未释放不再使用的内存(“内存泄漏”)。当释放次数少于申请次数时,可能已造成内存泄漏。泄漏的内存往往比忘记释放的数据结构更大,因为所分配的内存通常会圆整为下个大于申请数量的2的幂次(如申请212B,会圆整为256B)。

注意,堆不同于数据结构中的”堆”,其行为类似链表。

【扩展阅读】栈和堆的区别

管理方式:栈由编译器自动管理;堆由程序员控制,使用方便,但易产生内存泄露。

生长方向:栈向低地址扩展(即”向下生长”),是连续的内存区域;堆向高地址扩展(即”向上生长”),是不连续的内存区域。这是由于系统用链表来存储空闲内存地址,自然不连续,而链表从低地址向高地址遍历。

空间大小:栈顶地址和栈的最大容量由系统预先规定(通常默认2M或10M);堆的大小则受限于计算机系统中有效的虚拟内存,32位Linux系统中堆内存可达2.9G空间。

存储内容:栈在函数调用时,首先压入主调函数中下条指令(函数调用语句的下条可执行语句)的地址,然后是函数实参,然后是被调函数的局部变量。本次调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的指令地址,程序由该点继续运行下条可执行语句。堆通常在头部用一个字节存放其大小,堆用于存储生存期与函数调用无关的数据,具体内容由程序员安排。

分配方式:栈可静态分配或动态分配。静态分配由编译器完成,如局部变量的分配。动态分配由alloca函数在栈上申请空间,用完后自动释放。堆只能动态分配且手工释放。

分配效率:栈由计算机底层提供支持:分配专门的寄存器存放栈地址,压栈出栈由专门的指令执行,因此效率较高。堆由函数库提供,机制复杂,效率比栈低得多。Windows系统中VirtualAlloc可直接在进程地址空间中分配一块内存,快速且灵活。

分配后系统响应:只要栈剩余空间大于所申请空间,系统将为程序提供内存,否则报告异常提示栈溢出。

操作系统为堆维护一个记录空闲内存地址的链表。当系统收到程序的内存分配申请时,会遍历该链表寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点空间分配给程序。若无足够大小的空间(可能由于内存碎片太多),有可能调用系统功能去增加程序数据段的内存空间,以便有机会分到足够大小的内存,然后进行返回。,大多数系统会在该内存空间首地址处记录本次分配的内存大小,供后续的释放函数(如free/delete)正确释放本内存空间。

此外,由于找到的堆结点大小不一定正好等于申请的大小,系统会自动将多余的部分重新放入空闲链表中。

碎片问题:栈不会存在碎片问题,因为栈是先进后出的队列,内存块弹出栈之前,在其上面的后进的栈内容已弹出。而频繁申请释放操作会造成堆内存空间的不连续,从而造成大量碎片,使程序效率降低。

可见,堆容易造成内存碎片;由于没有专门的系统支持,效率很低;由于可能引发用户态和内核态切换,内存申请的代价更为昂贵。所以栈在程序中应用最广泛,函数调用也利用栈来完成,调用过程中的参数、返回地址、栈基指针和局部变量等都采用栈的方式存放。所以,建议尽量使用栈,仅在分配大量或大块内存空间时使用堆。

使用栈和堆时应避免越界发生,否则可能程序崩溃或破坏程序堆、栈结构,产生意想不到的后果。

 

5 BSS段

BSS(Block Started by Symbol)段中通常存放程序中以下符号:

  • 未初始化的全局变量和静态局部变量
  • 初始值为0的全局变量和静态局部变量(依赖于编译器实现)
  • 未定义且初值不为0的符号(该初值即common block的大小)

C语言中,未显式初始化的静态分配变量被初始化为0(算术类型)或空指针(指针类型)。由于程序加载时,BSS会被操作系统清零,所以未赋初值或初值为0的全局变量都在BSS中。BSS段仅为未初始化的静态分配变量预留位置,在目标文件中并不占据空间,这样可减少目标文件体积。但程序运行时需为变量分配内存空间,故目标文件必须记录所有未初始化的静态分配变量大小总和(通过start_bss和end_bss地址写入机器代码)。当加载器(loader)加载程序时,将为BSS段分配的内存初始化为0。在嵌入式软件中,进入main()函数之前BSS段被C运行时系统映射到初始化为全零的内存(效率较高)。

注意,尽管均放置于BSS段,但初值为0的全局变量是强符号,而未初始化的全局变量是弱符号。若其他地方已定义同名的强符号(初值可能非0),则弱符号与之链接时不会引起重定义错误,但运行时的初值可能并非期望值(会被强符号覆盖)。因此,定义全局变量时,若只有本文件使用,则尽量使用static关键字修饰;否则需要为全局变量定义赋初值(哪怕0值),保证该变量为强符号,以便链接时发现变量名冲突,而不是被未知值覆盖。

某些编译器将未初始化的全局变量保存在common段,链接时再将其放入BSS段。在编译阶段可通过-fno-common选项来禁止将未初始化的全局变量放入common段。

此外,由于目标文件不含BSS段,故程序烧入存储器(Flash)后BSS段地址空间内容未知。U-Boot启动过程中将U-Boot的Stage2代码(通常位于lib_xxxx/board.c文件)搬迁(拷贝)到SDRAM空间后必须人为添加清零BSS段的代码,而不可依赖于Stage2代码中变量定义时赋0值。

【扩展阅读】BSS历史

BSS(Block Started by Symbol,以符号开始的块)一词最初是UA-SAP汇编器(United Aircraft Symbolic Assembly Program)中的伪指令,用于为符号预留一块内存空间。该汇编器由美国联合航空公司于20世纪50年代中期为IBM 704大型机所开发。

后来该词被作为关键字引入到了IBM 709和7090/94机型上的标准汇编器FAP(Fortran Assembly Program),用于定义符号并且为该符号预留指定字数的未初始化空间块。

在采用段式内存管理的架构中(如Intel 80×86系统),BSS段通常指用来存放程序中未初始化全局变量的一块内存区域,该段变量只有名称和大小却没有值。程序开始时由系统初始化清零。

BSS段不包含数据,仅维护开始和结束地址,以便内存能在运行时被有效地清零。BSS所需的运行时空间由目标文件记录,但BSS并不占用目标文件内的实际空间,即BSS节段应用程序的二进制映象文件中并不存在。

6 数据段(Data)

数据段通常用于存放程序中已初始化且初值不为0的全局变量和静态局部变量。数据段属于静态内存分配(静态存储区),可读可写。

数据段保存在目标文件中(在嵌入式系统里一般固化在镜像文件中),其内容由程序初始化。例如,对于全局变量int gVar = 10,必须在目标文件数据段中保存10这个数据,然后在程序加载时复制到相应的内存。

数据段与BSS段的区别如下:

1) BSS段不占用物理文件尺寸,但占用内存空间;数据段占用物理文件,也占用内存空间。

对于大型数组如int ar0[10000] = {1, 2, 3, …}和int ar1[10000],ar1放在BSS段,只记录共有10000*4个字节需要初始化为0,而不是像ar0那样记录每个数据1、2、3…,此时BSS为目标文件所节省的磁盘空间相当可观。

2) 当程序读取数据段的数据时,系统会出发缺页故障,从而分配相应的物理内存;当程序读取BSS段的数据时,内核会将其转到一个全零页面,不会发生缺页故障,也不会为其分配相应的物理内存。

运行时数据段和BSS段的整个区段通常称为数据区。某些资料中“数据段”指代数据段 + BSS段 + 堆。

7 代码段(text)

代码段也称正文段或文本段,通常用于存放程序执行代码(即CPU执行的机器指令)。一般C语言执行语句都编译成机器代码保存在代码段。通常代码段是可共享的,因此频繁执行的程序只需要在内存中拥有一份拷贝即可。代码段通常属于只读,以防止其他程序意外地修改其指令(对该段的写操作将导致段错误)。某些架构也允许代码段为可写,即允许修改程序。

代码段指令根据程序设计流程依次执行,对于顺序指令,只会执行一次(每个进程);若有反复,则需使用跳转指令;若进行递归,则需要借助栈来实现。

代码段指令中包括操作码和操作对象(或对象地址引用)。若操作对象是立即数(具体数值),将直接包含在代码中;若是局部数据,将在栈区分配空间,然后引用该数据地址;若位于BSS段和数据段,同样引用该数据地址。

代码段最容易受优化措施影响。

8 保留区

位于虚拟地址空间的最低部分,未赋予物理地址。任何对它的引用都是非法的,用于捕捉使用空指针和小整型值指针引用内存的异常情况。

它并不是一个单一的内存区域,而是对地址空间中受到操作系统保护而禁止用户进程访问的地址区域的总称。大多数操作系统中,极小的地址通常都是不允许访问的,如NULL。C语言将无效指针赋值为0也是出于这种考虑,因为0地址上正常情况下不会存放有效的可访问数据。

在32位X86架构的Linux系统中,用户进程可执行程序一般从虚拟地址空间0×08048000开始加载。该加载地址由ELF文件头决定,可通过自定义链接器脚本覆盖链接器默认配置,进而修改加载地址。0×08048000以下的地址空间通常由C动态链接库、动态加载器ld.so和内核VDSO(内核提供的虚拟共享库)等占用。通过使用mmap系统调用,可访问0×08048000以下的地址空间。

通过cat /proc/self/maps命令查看加载表如下:

【扩展阅读】分段的好处

进程运行过程中,代码指令根据流程依次执行,只需访问一次(当然跳转和递归可能使代码执行多次);而数据(数据段和BSS段)通常需要访问多次,因此单独开辟空间以方便访问和节约空间。具体解释如下:

当程序被装载后,数据和指令分别映射到两个虚存区域。数据区对于进程而言可读写,而指令区对于进程只读。两区的权限可分别设置为可读写和只读。以防止程序指令被有意或无意地改写。

现代CPU具有极为强大的缓存(Cache)体系,程序必须尽量提高缓存命中率。指令区和数据区的分离有利于提高程序的局部性。现代CPU一般数据缓存和指令缓存分离,故程序的指令和数据分开存放有利于提高CPU缓存命中率。

当系统中运行多个该程序的副本时,其指令相同,故内存中只须保存一份该程序的指令部分。若系统中运行数百进程,通过共享指令将节省大量空间(尤其对于有动态链接的系统)。其他只读数据如程序里的图标、图片、文本等资源也可共享。而每个副本进程的数据区域不同,它们是进程私有的。

此外,临时数据及需要再次使用的代码在运行时放入栈区中,生命周期短。全局数据和静态数据可能在整个程序执行过程中都需要访问,因此单独存储管理。堆区由用户自由分配,以便管理。

 | 180 views | 0 comments | 0 flags | 

【转】实时操作系统Vxworks与通用操作系统Linux的比较+实模式等三种模式 DMA

http://blog.chinaunix.net/uid-26404477-id-3343987.html

一个好的实时操作系统需要具备以下功能(必须但非充分):

*多任务和可抢占的;

*任务具有优先级;

*操作系统具备支持可预测的任务同步机制;

*支持多任务间的通信;

*操作系统具备消除优先级转置的机制;

*存储器优化管理(含ROM的管理);

*操作系统的(中断延迟、任务切换、驱动程序延迟等)行为是可知的可预测的。这是指在
全负载的情形下,最坏反应时间可知;

*实时时钟服务;

*中断管理服务。

实时操作系统所遵循的最重要的设计原则是: 采用各种算法和策略,始终保证系统行为的可预测性。可预测性是指在系统运行的任何时刻,在任何 情况下,实时操作系统的资源调配策略都能为争夺资源(包括CPU、内存、网络带宽等)的多个实时任务合理地分配资源,使每个实时任务的实时性要求都能得到 满足。与通用操作系统不同,实时操作系统注重的不是系统的平均表现,而是要求每个实时任务在最坏情况下都要满足其实时性要求,也就是说,实时操作系统注重 的是个体表现,更准确地讲是个体最坏情况表现。

实时系统最关键的部分是实时多任务内核。它的基本功能包括多任务管理、定时器管理、
存储器管理、资源管理、事件管理、系统管理、消息管理、队列管理、信号量管理等。这
些管理功能是通过内核服务函数形式交给用户调用的,也就是实时操作系统的API。

================vxworks和linux的比较===========================

vxWorks       Linux
 

 

内核

结构

 

微内核,

内核只提供

了基本的服

务,如:任

务管理,内

存管理,中

断处理等

   内核    【Monolithic】,

除了基本的

服务,内核

还包括文件

系统,网络

协议

 

运行

模式

应用程序运

行在“实模

式”下,无

用户模式和

内核模式之

采用“保护

模式”,用

户进程、线

程运行在用

户模式下,

内核线程运

行于内核模

内存

访问

和内

存保

内核采用

存储管理方

式,所有任

务运行于同

一物理地址

空间,用户

程序直接操

作物理地

址,不能直

接地提供内

存保护,不

能防止错误

蔓延

内核采用虚

拟存储管理

方式,用户

具有独立的

地址空间

,用户进程

只能访问本

进程的虚拟

空间,提供

了内存保

护,可以防

止错误蔓延

执行

单元

 

 

 

任务

 

 

 

 

进程、线程
请求

内核

服务

方式

 

 

函数调用

更快

系统调用

,更安全

 

 

硬实时 软实时

关于各种周期 http://lionwq.spaces.eepw.com.cn/articles/article/item/17638

时钟周期

时钟周期也称为振荡周期,定义为时钟脉冲的倒数(时钟周期就是单片机外接晶振的倒数,例如12M的晶振,它的时钟周期就是1/12us),是计算机中的最基本的、最小的时间单位。
在一个时钟周期内,CPU仅完成一个最基本的动作。时钟脉冲是计算机的基本工作脉冲,控制着计算机的工作节奏。时钟频率越高,工作速度就越快。

8051单片机把一个时钟周期定义为一个节拍(用P表示),二个节拍定义为一个状态周期(用S表示)。

机器周期

计算机中,常把一条指令的执行过程划分为若干个阶段,每一个阶段完成一项工作。每一项工作称为一个基本操作,完成一个基本操作所需要的时间称为机器周期。8051系列单片机的一个机器周期由6个S周期(状态周期)组成。 一个S周期=2个节拍(P),所以8051单片机的一个机器周期=6个状态周期=12个时钟周期。

例如外接24M晶振的单片机,他的一个机器周期=12/24M 秒;

指令周期

执行一条指令所需要的时间,一般由若干个机器周期组成。指令不同,所需的机器周期也不同。

硬实时与软实时之间最关键的差别在于,软实时只能提供统计意义上的实时。例如,有的应用要求系统在95%的情况下都会确保在规定的时间内完成某个动作,而不一定要求100%。

SYS_CLK_RATE是1000,那么就是1ms。。如果是60那么就大约是16.67ms。。。【我们的设备就是60】通常来讲,vxWorks手册建议不要将时钟率设得太高,否则它就由硬实时变得趋向于软实时了。。因为过高的时钟率使得内核调度频繁进入,可能导致一些低优先级的硬件中断不能得到及时响应。

============================

嵌入式实时系统中采用的操作系统称为嵌入式实时操作系统,它既是嵌入式操作系统,又是实时操作系统。

作为一种嵌入式操作系统,它具有嵌入 式软件共有的可裁剪、低资源、占用、低功耗等特点; 而作为一种实时操作系统,它与通用操作系统(如Windows、Unix、Linux等)相比有很大的 差别,下面我们通过比较这两种操作系统之间的差距来描述实时操作系统的主要特点。

最常用的操作系统是通用操作系统,通用操作系统是由分时操作系统发展而来,大部分都支持多用户和多进程,负责管理众多的进程并为它们分配系统资源。

分时操作系统的基本设计原则是:尽量缩短系统的平均响应时间并提高系统的吞吐率,在单位时间内为尽可能多的用户请求提供服务。由此可以看出,分时操作系统注重平均表现性能,不注重个体表现性能。如对于整个系统来说,注重所有任务的平均响应时间而不关心单个任务的响应时间,对于单个任务来说,注重每次执行的平均响 应时间而不关心某次特定执行的响应时间。

通用操作系统中采用的很多策略和技巧都体现出了这种设计原则,如虚存管理机制中由于采用LRU等页替换算法,使得 大部分的访存需求能够快速地通过物理内存完成,只有很小一部分的访存需求需要通过调页完成,但从总体上来看,平均访存时间与不采用虚存技术相比没有很大的提高,同时又获得了虚空间可以远大于物理内存容量等好处,因此虚存技术在通用操作系统中得到了十分广泛的应用。

而对于实时操作系统,前面已经提到,它除了要满足应用的功能需求以外,更重要的是还要满足应用提出的实时性要求,而组成一个应用的众多实时任务对于实时性 的要求是各不相同的,此外实时任务之间可能还会有一些复杂的关联和同步关系,如执行顺序限制、共享资源的互斥访问要求等,这就为系统实时性的保证带来了很 大的困难。

由于实时操作系统与通用操作系统的基本设计原则差别很大,因此在很多资源调度策略的选择上以及操作系统实现的方法上两者都具有较大的差异,这些差异主要体现在以下几点:

(1)任务调度策略:

通用操作系统中的任务调度策略一般采用基于优先级的抢先式调度策略,对于优先级相同的进程则采用时间片轮转调度方式,用户进程可以通过系统调用动态地调整自己的优先级,操作系统可根据情况调整某些进程的优先级。

实时操作系统中的任务调度策略目前使用最广泛的主要可分为两种,一种是静态表驱动方式,另一种是固定优先级抢先式调度方式。

静态表驱动方式是指在系统运行前工程师根据各任务的实时要求用手工的方式或在辅助工具的帮助下生成一张任务的运行时间表,这张时间表与列车的运行时刻表类 似,指明了各任务的起始运行时间以及运行长度,运行时间表一旦生成就不再变化了,在运行时调度器只需根据这张表在指定的时刻启动相应的任务理即可。静态表 驱动方式的主要优点是:

·运行时间表是在系统运行前生成的,因此可以采用较复杂的搜索算法找到较优的调度方案:1

·运行时调度器开销较小;·系统具有非常好的可预测性,实时性验证也比较方便;

这种方式主要缺点是不灵活,需求一旦发生变化,就要重新生成整个运行时量间表。由于具有非常好的可预测性,这种方式主要用于航空航天、军事等对系统的实时性要求十分严格的领域。

固定优先级抢先式调度方式则与通用操作系统中采用的基于优先级的调度方式基本类似,但在固定优先级抢先式调度方方式中,进程的优先级是固定不变革的,并且 该优先级是在运行前通过某种优先级分配策略来指定的。这种方式的优缺点与静太表驱动方式的优缺点正好完全相反,它主要应用于一些较简单、较独立的嵌入式系 统,但随着调度理论的不断成熟和完善,这种方式也会逐渐在一些对实时性要求十分严格的领域中得到应用。目前市场上大部分的实时操作系统采用的都是这种调度 方式。

(2)内存管理:

关于虚存管理机制在上面已经进行了一些分析。为解决虚存给系统带来的不可预测性,实时操作系统一般采用如下两种方式:

·在原有虚存管理机制的基础上增加页面锁功能,用户可将关键页面锁定在内存中,从而不会被swap程序将该页面交换出内存。这种方式的优点是既得到了虚存 管理机制为软件开发带来的好处,又提高了系统的可预测性。缺点是由于TLB等机制的也是按照注重平均表现的原则进行的,因此系统的可预测性并不能完全得到 保障;

·采用静态内存划分的方式,为每个实时任务划分固定的内存区域。这种方式的优点是系统具有较好的可预测性,缺点是灵活性不够好,任务对存储器的需求一旦有变化就需要重新对内存进行划分,此外虚存管理机制所带来的好处也丧失了。

目前市场上的实时操作系统一般都采用第一种管理方式。

(3)中断处理:

在通用操作系统中,大部分外部中断都是开启的,中断处理一般由设备驱动程序来完成。由于通用操作系统中的用户进程一般都没有实时性要求,而中断处理程序直接跟硬件设备交互,可能有实时性要求,因此中断处理程序的优先级被设定为高于任何用户进程。

但对于实时操作系统采用上述的中断处理机制是不合适的。首先,外部中断是环境向实时操作系统进行的输入,它的频度是与环境变化的速率相关的,而与实时操作 系统无关。如果外部中断产生的频度不可预测,则一个实时任务在运行时被中断处理程序阻塞的时间开销也是不可预测的,从而使任务的实时性得不到保证;如果外 部中断产生的频度中可预测的,一旦某外部中断产生的频度超出其预测值(如硬件故障产生的虚假中断信号或预测值本身有误)就可能会破坏整个系统的可预测性口 其次,实时控制系统中的各用户进程一般都有实时性要求,因此中断处理程序优先级高于所有用户进程的优先级分配方式是不合适的。

一种较适合实时操作系统的中断处理方式为:除时钟中断外,屏蔽所有其它中断,中断处理程序变为周期性的轮询操作。采用这种方式的主要好处是充分保证了系统 的可预测性,主要缺点是对环境变化的响应可能不如上述矿断处理方式快。另外轮询操作在一定程度上降低了CPU的有效利用率。另一种可行的方式是:对于采用 轮询方式无法满足需求的外部事件,采用中断方式,其它时间仍然采用轮询方式。但此时中断处理程序与所以其它任务一样拥有优先级,调度器根据优先级对处于就 绪态的任务和中断处理程序统一进行处理器调度。这种方式使外部事件的响应速度加快避免了上述中断方式带来第二个问题,但第一个问题依然存在。

此外为提高时钟中断响应时间的可预测性,实时操作系统应尽可能少地屏蔽中断。

(4)共享资源的互斥访问:

通用操作系统一般采用信号量机制来解决共享资源的互斥访问问题。

对于实时操作系统,如果任务调度采用静态表驱动方式,共享资源的互斥访问问题在生成运行时间表时已经考虑到了,在运行时无需再考虑。如果任务调度采用基于 优先级的方式,则传统的信号量机制在系统运行时很容易造成优先级倒置问题,即当一个高优先级任务通过信号量机制访问共享资源时,该信号量已被一低优先级任 务占有,而这个低优先级任务在访问共享资源时可能又被其它一些中等优先级的任务抢先,因此造成高优先级任务被许多具有较低优先级的任务阻塞,实时性难以得 到保证。因此在实时操作系统中,往往对传统的信号量机制进行了一些扩展,引入了如优先级继承协议、优先级顶置协议等机制,较好地解决了优先级倒置的问题。

(5)系统调用以及系统内部操作的时间开销:

进程通过系统调用得到操作系统提供的服务,操作系统通过内部操作(加上下文切换等)来完成一些内部管理工作。为保证系统的可预测性,实时操作系统中的所有 系统调用以及系统内部操作的时间开销都应是有界的,并且该界限是一个具体的量化数值。而在通用操作系统中对这些时间开销则未做如此限制。

(6)系统的可重入性:

在通用操作系统中,核心态系统调用往往是不可重入的,当一低优先级任务调用核心态系统调用时,在该时间段内到达的高优先级任务必须等到低优先级的系统调用完成才能获得CPU,这就降低了系统的可预测性。因此,实时操作系统型中的核心态系统调用往往设计为可重入的。

(7)辅助工具:

实时操作系统额外提供了一些辅助工具,如实时任务在最坏情况下的执行时间估算工具、系统的实时性验证工具等,可帮助工程师进行系统的实时性验证工作。

此外,实时操作系统对系统硬件设计也提出了一些要求,如:

DMA 相关:

DMA是一种数据交换协议,主要作用是在无需CPU参与的情况下将数据在内存与其它外部设备间进行交换。 DMA最常用的一种实现方式被称为周期窃取(Cycle Stealing)方式,即首先遇过总线仲裁协议与CPU竞争总线控制权,在获得控制权后再根据用户预设的操作指令进行数据交换。由于这种周期窃取方式会 给用户任务带来不可预测的额外阻塞开销,所以实时操作系统往往要求系统设计时不采用DMA或采取一些可预测性更好DMA实现方式,如Time-slice method等。
[《深入理解计算机系统》第六章403页讲的不错。]
·Cache

Cache的主要作用是采用容量相对较小的快速存储部件来弥补高性能CPU与相对来说性能较低的存储器之间的性能差异,由于它可以使系统的平均表现性能得到大幅提高,因此在硬件设计中得到了极为广泛的应用。

但实时操作系统注重的不是平均表现性能,而是个体最坏情况表现,因此在对系统进行实时性验证时必须考虑实时任务运行的最坏情况,即每次访存都没有命中 Cache情况下的运行时间,所以在利用辅助工具估算实时任务在最坏情况下的执行时间,应将系统中所有的Cache功能暂时关闭,在系统实际运行时再将 Cache功能激活。除此以外,另一种较极端的做法则是在硬件设计中完全不采用Cache技术。

注1:何为嵌入式系统嵌入式系统是指将应用程序和操作系统与计算机硬件集成在一起的系统。简单的说就是系统的应用软件与系统的硬件一体化,类似与BIOS的工作万式。这种系统具育软件代码小,高度自动化,响应速度快等特点,特别适合于要求实时的和多任务的体系。

注2:实时多任务操作系统实时多任务操作系统(Real Time Operating System〉是根据操作系统的工作特性而言的。实时是指物理进程的真实时间。实地操作系统是指真奇实时性,能支持实时撞制系统工作的操作系统。真首要任 务是调度一切可利用的资源完成实时控制任务,真次才着眼于提高计算机系统的使用烈率,这种系统的重要特点是要满意对时间的限制和要求。

三种工作模式

80386处理器有3种工作模式:实模式、保护模式和虚拟86模式。实模式和虚拟86模式是为了和8086处理器兼容而设置的。在实模式 下,80386处理器就相当于一个快速的8086处理器。

保护模式是80386处理器的主要工作模式。在此方式下,80386可以寻址4GB的地址空间,同时,保护模式提供了80386先进的多任务、内存分页管理和优先级保护等机制。为了在保护模式下继续提供和8086处理器的兼 容,80386又设计了一种虚拟86模式,以便可以在保护模式的多任务条件下,有的任务运行32位程序,有的任务运行MS-DOS程序。在虚拟86模式 下,同样支持任务切换、内存分页管理和优先级,但内存的寻址方式和8086相同,也是可以寻址1MB的空间。

由此可 见,80386处理器的3种工作模式各有特点且相互联系。实模式是80386处理器工作的基础,这时80386当做一个快速的8086处理器工作。在实模 式下可以通过指令切换到保护模式,也可以从保护模式退回到实模式。虚拟86模式则以保护模式为基础,在保护模式和虚拟86模式之间可以互相切换,但不能从实模式直接进入虚拟86模式或从虚拟86模式直接退到实模式。 【实模式<->虚拟85】

 

实模式:寻址采用和8086相同的16位段和偏移量,最大寻址空间1MB(原因:20位的地址总线, 因此,也就有了以下行为:由段寄存器的内容乘以 16当做基地址,加上段内的偏移地址形成最终的物理地址,这时候它的32位地址线只使用了低20位。具体来参考http://blog.chinaunix.net/space.php?uid=20791902&do=blog&id=291989),最大分段64KB。可以使用32位指令。32位的x86 CPU用做高速的8086。

保护模式:寻址采用32位段和偏移量,最大寻址空间4GB,最大分段4GB (Pentium Pre及以后为64GB)。在保护模式下CPU可以进入虚拟8086方式,这是在保护模式下的实模式程序运行环境。

 

保护模式同实模式的根本区别是进程内存受保护与否。可寻址空间的区别只是这一原因的果。实模式将整个物理内存看成分段的区域,程序代码和数据位 于不同 区域,系统程序和用户程序没有区别对待,而且每一个指针都是指向”实在”的物理地址。这样一来,用户程序的一个指针如果指向了系统程序区域或其他用户程序 区域,并改变了值,那么对于这个被修改的系统程序或用户程序,其后果就很可能是灾难性的。为了克服这种低劣的内存管理方式,处理器厂商开发出保护模式。这 样,物理内存地址不能直接被程序访问,程序内部的地址(虚拟地址)要由操作系统转化为物理地址去访问,程序对此一无所知。
至此,进程(这时 我们可以称程序 为进程了)有了严格的边界,任何其他进程根本没有办法访问不属于自己的物理内存区域,甚至在自己的虚拟地址范围内也不是可以任意访问的,因为有一些虚拟区域已经被放进一些公共系统运行库。这些区域也不能随便修改,若修改就会有: SIGSEGV(linux 段错误);非法内存访问对话框(windows 对话框)。
CPU启动环境为16位实模式,之后可以切换到保护模式。但从保护模式无法切换回实模式。

1.   实模式 【寻址都是物理地址】

80386处理器被复位或加电的时候 以实模式启动。这时候处理器中的各寄存器以实模式的初始化值工作。80386处理器在实模式下的存储器寻址方式和8086是一样的。 在实模式下,80386处理器不能对内存进行分页管 理,所以指令寻址的地址就是内存中实际的物理地址。在实模式下,所有的段都是可以读、写和执行的。

实模式下80386不支持优先级,所 有的指令相当于工作在特权级(优先级0),所以它可以执行所有特权指令,包括读写控制寄存器CR0等。实际上,80386就是通过在实模式下初始化控制寄 存器,GDTR,LDTR,IDTR与TR等管理寄存器以及页表,然后再通过加载CR0使其中的保护模式使能位置位而进入保护模式的。实模式下不支持硬件 上的多任务切换。

实模式下的中断处理方式和8086处理器相同,也用中断向量表来定位中断服务程序地址。中断向量表的结构也和8086处理器一样,每4个字节组成一个中断向量,其中包括两个字节的段地址和两个字节的偏移地址。

从 编程的角度看,除了可以访问80386新增的一些寄存器外,实模式的80386处理器和8086有什么进步呢?其实最大的好处是可以使用80386的32 位寄存器,用32位的寄存器进行编程可以使计算程序更加简捷,加快了执行速度。比如在8086时代用16位寄存器来完成32位的乘法和除法时,要进行的步 骤实在是太多了,于是考试时出这一类的题目就成了老师们的最爱,所以那时候当学生做梦都想着让寄存器的位数快快长,现在梦想终于成真了,用32位寄存器一 条指令就可以完成(问题是老师们也发现了这个投机取巧的办法,为了达到让学生们基础扎实的目的,也把题目换成了64位的乘法和除法,所以现在晚上做的梦换 成了寄存器忽然长到了64位);其次,80386中增加的两个辅助段寄存器FS和GS在实模式下也可以使用,这样,同时可以访问的段达到了6个而不必考虑 重新装入的问题;最后,很多80386的新增指令也使一些原来不很方便的操作得以简化,如80386中可以使用下述指令进行数组访问:

mov   cx,[eax   +   ebx   *   2   +   数组基地址]

这 相当于把数组中下标为eax和ebx的项目放入cx中;ebx   *   2中的2可以是1,2,4或8,这样就可以支持8位到64位的数组。而在8086处理器中,实现相同的功能要进行一次乘法和两次加法。另外,pushad 和popad指令可以一次把所有8个通用寄存器的值压入或从堆栈中弹出,比起用下面的指令分别将8个寄存器入栈要快了很多:

push         eax

push         ebx

pop   ebx

pop   eax

当然,使用了这些新指令的程序是无法拿回到8086处理器上去执行的,因为这些指令的编码在8086处理器上是未定义的。

2.   保护模式

当 80386工作在保护模式下的时候,它的所有功能都是可用的。这时80386所有的32根地址线都可供寻址,物理寻址空间高达4   GB。在保护模式下,支持内存分页机制,提供了对虚拟内存的良好支持。虽然与8086可寻址的1   MB物理地址空间相比,80386可寻址的物理地址空间可谓很大,但实际的微机系统不可能安装如此大的物理内存。所以,为了运行大型程序和真正实现多任 务,虚拟内存是一种必需的技术。

保护模式下80386支持多任务,可以依靠硬件仅在一条指令中实现任务切换。任务环境的保护工作是由处 理器自动完成的。在保护模式下,80386处理器还支持优先级机制,不同的程序可以运行在不同的优先级上。优先级一共分0~3   4个级别,操作系统运行在最高的优先级0上,应用程序则运行在比较低的级别上;配合良好的检查机制后,既可以在任务间实现数据的安全共享也可以很好地隔离 各个任务。从实模式切换到保护模式是通过修改控制寄存器CR0的控制位PE(位0)来实现的。在这之前还需要建立保护模式必需的一些数据表,如全局描述符 表GDT和中断描述符表IDT等。

DOS操作系统运行于实模式下,而Windows操作系统运行于保护模式下。

3.   虚拟86模式

虚 拟86模式是为了在保护模式下执行8086程序而设置的。虽然80386处理器已经提供了实模式来兼容8086程序,但这时8086程序实际上只是运行得 快了一点,对CPU的资源还是独占的。在保护模式的多任务环境下运行这些程序时,它们中的很多指令和保护模式环境格格不入,如段寻址方式、对中断的处理和 I/O操作的特权问题等。为了在保护模式下工作而丢弃这些程序的代价是巨大的。设想一下,如果Windows或80386处理器推出的时候宣布不能运行以 前的MS-DOS程序,那么就等于放弃了一个巨大的软件库,Windows以及80386处理器可能就会落得和苹果机一样的下场,这是Microsoft 和Intel都不愿看到的。所以,80386处理器又设计了一个虚拟86模式。

虚拟86模式是以任务形式在保护模式上执行的,在 80386上可以同时支持由多个真正的80386任务和虚拟86模式构成的任务。在虚拟86模式下,80386支持任务切换和内存分页。在Windows 操作系统中,有一部分程序专门用来管理虚拟86模式的任务,称为虚拟86管理程序。

既然虚拟86模式以保护模式为基础,它的工作方式实 际上是实模式和保护模式的混合。为了和8086程序的寻址方式兼容,虚拟86模式采用和8086一样的寻址方式,即用段寄存器乘以16当做基址再配合偏移 地址形成线性地址,寻址空间为1   MB。但显然多个虚拟86任务不能同时使用同一位置的1   MB地址空间,否则会引起冲突。操作系统利用分页机制将不同虚拟86任务的地址空间映射到不同的物理地址上去,这样每个虚拟86任务看起来都认为自己在使 用0~1   MB的地址空间。

8086代码中有相当一部分指令在保护模式下属于特权指令,如屏蔽中断的cli和中断返回指令iret 等。这些指令在8086程序中是合法的。如果不让这些指令执行,8086代码就无法工作。为了解决这个问题,虚拟86管理程序采用模拟的方法来完成这些指 令。这些特权指令执行的时候引起了保护异常。虚拟86管理程序在异常处理程序中检查产生异常的指令,如果是中断指令,则从虚拟86任务的中断向量表中取出 中断处理程序的入口地址,并将控制转移过去;如果是危及操作系统的指令,如cli等,则简单地忽略这些指令,在异常处理程序返回的时候直接返回到下一条指 令。通过这些措施,8086程序既可以正常地运行下去,在执行这些指令的时候又觉察不到已经被虚拟86管理程序做了手脚。MS-DOS应用程序在     Windows操作系统中就是这样工作的。

——————————————————————————————————————————————————

什么是保护模式
自从1969年推出第一个微处理器以来,Intel处理器就在不断地更新换代,从8086、8088、80286,到 80386、80486、奔腾、奔腾Ⅱ、奔腾4等,其体系结构也在不断变化。80386以后,提供了一些新的功能,弥补了8086的一些缺陷。这其中包括 内存保护、多任务及使用640KB以上的内存等,并仍然保持和8086家族的兼容性。也就是说80386仍然具备了8086和80286的所有功能,但是 在功能上有了很大的增强。早期的处理器是工作在实模式之下的,80286以后引入了保护模式,而在80386以后保护模式又进行了很大的改进。在 80386中,保护模式为程序员提供了更好的保护,提供了更多的内存。事实上,保护模式的目的不是为了保护程序,而是要保护程序以外的所有程序(包括操作 系统)。
简言之,保护模式是处理器的一种最自然的模式。在这种模式下,处理器的所有指令及体系结构的所有特色都是可用的,并且能够达到最高的性能。
保护模式和实模式
从 表面上看,保护模式和实模式并没有太大的区别,二者都使用了内存段、中断和设备驱动来处理硬件,但二者有很多不同之处。我们知道,在实模式中内存被划分成 段,每个段的大小为64KB,而这样的段地址可以用16位来表示。内存段的处理是通过和段寄存器相关联的内部机制来处理的,这些段寄存器(CS、DS、 SS和ES)的内容形成了物理地址的一部分。具体来说,最终的物理地址是由16位的段地址和16位的段内偏移地址组成的。用公式表示为:
物理地址=左移4位的段地址+偏移地址。
在 保护模式下,段是通过一系列被称之为”描述符表”的表所定义的。段寄存器存储的是指向这些表的指针。用于定义内存段的表有两种:全局描述符表(GDT)和 局部描述符表(LDT)。GDT是一个段描述符数组,其中包含所有应用程序都可以使用的基本描述符。在实模式中,段长是固定的(为64KB),而在保护模 式中,段长是可变的,其最大可达4GB。LDT也是段描述符的一个数组。与GDT不同,LDT是一个段,其中存放的是局部的、不需要全局共享的段描述符。 每一个操作系统都必须定义一个GDT,而每一个正在运行的任务都会有一个相应的LDT。每一个描述符的长度是8个字节,格式如图3所示。当段寄存器被加载 的时候,段基地址就会从相应的表入口获得。描述符的内容会被存储在一个程序员不可见的影像寄存器(shadow register)之中,以便下一次同一个段可以使用该信息而不用每次都到表中提取。物理地址由16位或者32位的偏移加上影像寄存器中的基址组成。实模 式和保护模式的不同可以从图1和图2中很清楚地看出来。
此外,还有一个中断描述符表(IDT)。这些中断描述符会告诉处理器到那里可以找到中断处理程序。和实模式一样,每一个中断都有一个入口,但是这些入口的格式却完全不同。因为在切换到保护模式的过程中没有使用到IDT,所以在此就不多做介绍了。
进入保护模式
80386 有4个32位控制寄存器,名字分别为CR0、CR1、CR2和CR3。CR1是保留在未来处理器中使用的,在80386中没有定义。CR0包含系统的控制 标志,用于控制处理器的操作模式和状态。CR2和CR3是用于控制分页机制的。在此,我们关注的是CR0寄存器的PE位控制,它负责实模式和保护模式之间 的切换。当PE=1时,说明处理器运行于保护模式之下,其采用的段机制和前面所述的相应内容对应。如果PE=0,那么处理器就工作在实模式之下。
切换到保护模式,实际就是把PE位置为1。为了把系统切换到保护模式,还要做一些其它的事情。程序必须要对系统的段寄存器和控制寄存器进行初始化。把PE位置1后,还要执行跳转指令。过程简述如下:
1.创建GDT表;
2.通过置PE位为1进入保护模式;
3.执行跳转以清除在实模式下读取的任何指令。
实模式下,cpu指令访问的地址就是物理地址,形式为:段寄存器:偏移
在保护模式下,cpu可以使用分段机制和分页机制。
分段机制下使用的地址就是逻辑地址,形式为:段选择子:偏移
分页机制下使用的地址就是线性地址,形式为:0xXXXXXXXX
无论是逻辑地址还是线性地址,都要被cpu映射成物理地址。
保护模式下必须采用分段机制。在此基础上可采用分页机制。
逻辑地址被转化为线性地址,如果采用分页机制,则该线性地址通过分页机制被映射成物理地址。如果不采用分页机制,则该线性地址就是物理地址。
实模式下的物理地址只能访问1M以下空间,而保护模式下的物理地址可以访问所有32位空间。并且要注意,物理内存空间只是物理地址空间的一个部分而已。

 | 113 views | 0 comments | 0 flags | 

【转】arm交叉编译器gnueabi、none-eabi、arm-eabi、gnueabihf、gnueabi区别

命名规则

交叉编译工具链的命名规则为:arch [-vendor] [-os] [-(gnu)eabi]

  • arch - 体系架构,如ARM,MIPS
  • vendor - 工具链提供商
  • os - 目标操作系统
  • eabi - 嵌入式应用二进制接口(Embedded Application Binary Interface)

根据对操作系统的支持与否,ARM GCC可分为支持和不支持操作系统,如

  • arm-none-eabi:这个是没有操作系统的,自然不可能支持那些跟操作系统关系密切的函数,比如fork(2)。他使用的是newlib这个专用于嵌入式系统的C库。
  • arm-none-linux-eabi:用于Linux的,使用Glibc

 

 实例

1、arm-none-eabi-gcc

(ARM architecture,no vendor,not target an operating system,complies with the ARM EABI)
用于编译 ARM 架构的裸机系统(包括 ARM Linux 的 boot、kernel,不适用编译 Linux 应用 Application),一般适合 ARM7、Cortex-M 和 Cortex-R 内核的芯片使用,所以不支持那些跟操作系统关系密切的函数,比如fork(2),他使用的是 newlib 这个专用于嵌入式系统的C库。

2、arm-none-linux-gnueabi-gcc

(ARM architecture, no vendor, creates binaries that run on the Linux operating system, and uses the GNU EABI)

主要用于基于ARM架构的Linux系统,可用于编译 ARM 架构的 u-boot、Linux内核、linux应用等。arm-none-linux-gnueabi基于GCC,使用Glibc库,经过 Codesourcery 公司优化过推出的编译器。arm-none-linux-gnueabi-xxx 交叉编译工具的浮点运算非常优秀。一般ARM9、ARM11、Cortex-A 内核,带有 Linux 操作系统的会用到。

3、arm-eabi-gcc

Android ARM 编译器。

4、armcc

ARM 公司推出的编译工具,功能和 arm-none-eabi 类似,可以编译裸机程序(u-boot、kernel),但是不能编译 Linux 应用程序。armcc一般和ARM开发工具一起,Keil MDK、ADS、RVDS和DS-5中的编译器都是armcc,所以 armcc 编译器都是收费的(爱国版除外,呵呵~~)。

5、arm-none-uclinuxeabi-gcc 和 arm-none-symbianelf-gcc

arm-none-uclinuxeabi 用于uCLinux,使用Glibc。

arm-none-symbianelf 用于symbian,没用过,不知道C库是什么 。

 

Codesourcery

Codesourcery推出的产品叫Sourcery G++ Lite Edition,其中基于command-line的编译器是免费的,在官网上可以下载,而其中包含的IDE和debug 工具是收费的,当然也有30天试用版本的。

目前CodeSourcery已经由明导国际(Mentor Graphics)收购,所以原本的网站风格已经全部变为 Mentor 样式,但是 Sourcery G++ Lite Edition 同样可以注册后免费下载。

Codesourcery一直是在做ARM目标 GCC 的开发和优化,它的ARM GCC在目前在市场上非常优秀,很多 patch 可能还没被gcc接受,所以还是应该直接用它的(而且他提供Windows下[mingw交叉编译的]和Linux下的二进制版本,比较方便;如果不是很有时间和兴趣,不建议下载 src 源码包自己编译,很麻烦,Codesourcery给的shell脚本很多时候根本没办法直接用,得自行提取关键的部分手工执行,又费精力又费时间,如果想知道细节,其实不用自己编译一遍,看看他是用什么步骤构建的即可,如果你对交叉编译器感兴趣的话。

ABI 和 EABI

ABI:二进制应用程序接口(Application Binary Interface (ABI) for the ARM Architecture)。在计算机中,应用二进制接口描述了应用程序(或者其他类型)和操作系统之间或其他应用程序的低级接口。

EABI:嵌入式ABI。嵌入式应用二进制接口指定了文件格式、数据类型、寄存器使用、堆积组织优化和在一个嵌入式软件中的参数的标准约定。开发者使用自己的汇编语言也可以使用 EABI 作为与兼容的编译器生成的汇编语言的接口。

两者主要区别是,ABI是计算机上的,EABI是嵌入式平台上(如ARM,MIPS等)。

 

arm-linux-gnueabi-gcc 和 arm-linux-gnueabihf-gcc

两个交叉编译器分别适用于 armel 和 armhf 两个不同的架构,armel 和 armhf 这两种架构在对待浮点运算采取了不同的策略(有 fpu 的 arm 才能支持这两种浮点运算策略)。

其实这两个交叉编译器只不过是 gcc 的选项 -mfloat-abi 的默认值不同。gcc 的选项 -mfloat-abi 有三种值 soft、softfp、hard(其中后两者都要求 arm 里有 fpu 浮点运算单元,soft 与后两者是兼容的,但 softfp 和 hard 两种模式互不兼容):
soft: 不用fpu进行浮点计算,即使有fpu浮点运算单元也不用,而是使用软件模式。
softfp: armel架构(对应的编译器为 arm-linux-gnueabi-gcc )采用的默认值,用fpu计算,但是传参数用普通寄存器传,这样中断的时候,只需要保存普通寄存器,中断负荷小,但是参数需要转换成浮点的再计算。
hard: armhf架构(对应的编译器 arm-linux-gnueabihf-gcc )采用的默认值,用fpu计算,传参数也用fpu中的浮点寄存器传,省去了转换,性能最好,但是中断负荷高。

把以下测试使用的C文件内容保存成 mfloat.c:
#include <stdio.h>
int main(void)
{
double a,b,c;
a = 23.543;
b = 323.234;
c = b/a;
printf(“the 13/2 = %f\n”, c);
printf(“hello world !\n”);
return 0;
}

1、使用 arm-linux-gnueabihf-gcc 编译,使用“-v”选项以获取更详细的信息:
# arm-linux-gnueabihf-gcc -v mfloat.c
COLLECT_GCC_OPTIONS=’-v’ ‘-march=armv7-a’ ‘-mfloat-abi=hard’ ‘-mfpu=vfpv3-d16′ ‘-mthumb’
-mfloat-abi=hard

可看出使用hard硬件浮点模式。

2、使用 arm-linux-gnueabi-gcc 编译:
# arm-linux-gnueabi-gcc -v mfloat.c
COLLECT_GCC_OPTIONS=’-v’ ‘-march=armv7-a’ ‘-mfloat-abi=softfp’ ‘-mfpu=vfpv3-d16′ ‘-mthumb’
-mfloat-abi=softfp

可看出使用softfp模式。

 

交叉编译工具

参考资料

  1. 交叉编译器 arm-linux-gnueabi 和 arm-linux-gnueabihf 的区别:http://www.cnblogs.com/xiaotlili/p/3306100.html
  2. arm-none-linux-gnueabi,arm-none-eabi 与arm-eabi 区别:http://blog.csdn.net/mantis_1984/article/details/21049273
  3. What’s the difference between arm-linux- / arm-none-linux-gnueabi- / arm-fsl-linux-gnueabi- in LTIB?https://community.freescale.com/thread/313490

文章来自VeryARM:http://www.veryarm.com/296.html,转载请保留。

 | 268 views | 0 comments | 0 flags | 

【转】嵌入式系统 Boot Loader 技术内幕

http://www.ibm.com/developerworks/cn/linux/l-btloader/

1. 引言

在专用的嵌入式板子运行 GNU/Linux 系统已经变得越来越流行。一个嵌入式 Linux 系统从软件的角度看通常可以分为四个层次:

1. 引导加载程序。包括固化在固件(firmware)中的 boot 代码(可选),和 Boot Loader 两大部分。

2. Linux 内核。特定于嵌入式板子的定制内核以及内核的启动参数。

3. 文件系统。包括根文件系统和建立于 Flash 内存设备之上文件系统。通常用 ram disk 来作为 root fs。

4. 用户应用程序。特定于用户的应用程序。有时在用户应用程序和内核层之间可能还会包括一个嵌入式图形用户界面。常用的嵌入式 GUI 有:MicroWindows 和 MiniGUI 懂。

引导加载程序是系统加电后运行的第一段软件代码。回忆一下 PC 的体系结构我们可以知道,PC 机中的引导加载程序由 BIOS(其本质就是一段固件程序)和位于硬盘 MBR 中的 OS Boot Loader(比如,LILO 和 GRUB 等)一起组成。BIOS 在完成硬件检测和资源分配后,将硬盘 MBR 中的 Boot Loader 读到系统的 RAM 中,然后将控制权交给 OS Boot Loader。Boot Loader 的主要运行任务就是将内核映象从硬盘上读到 RAM 中,然后跳转到内核的入口点去运行,也即开始启动操作系统。

而在嵌入式系统中,通常并没有像 BIOS 那样的固件程序(注,有的嵌入式 CPU 也会内嵌一段短小的启动程序),因此整个系统的加载启动任务就完全由 Boot Loader 来完成。比如在一个基于 ARM7TDMI core 的嵌入式系统中,系统在上电或复位时通常都从地址 0×00000000 处开始执行,而在这个地址处安排的通常就是系统的 Boot Loader 程序。

本文将从 Boot Loader 的概念、Boot Loader 的主要任务、Boot Loader 的框架结构以及 Boot Loader 的安装等四个方面来讨论嵌入式系统的 Boot Loader。

回页首

2. Boot Loader 的概念

简单地说,Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序,我们可以初始化硬件设备、建立内存空间的映射图,从而将系统的软硬件环境带到一个合适的状态,以便为最终调用操作系统内核准备好正确的环境。

通常,Boot Loader 是严重地依赖于硬件而实现的,特别是在嵌入式世界。因此,在嵌入式世界里建立一个通用的 Boot Loader 几乎是不可能的。尽管如此,我们仍然可以对 Boot Loader 归纳出一些通用的概念来,以指导用户特定的 Boot Loader 设计与实现。

1. Boot Loader 所支持的 CPU 和嵌入式板

每种不同的 CPU 体系结构都有不同的 Boot Loader。有些 Boot Loader 也支持多种体系结构的 CPU,比如 U-Boot 就同时支持 ARM 体系结构和MIPS 体系结构。除了依赖于 CPU 的体系结构外,Boot Loader 实际上也依赖于具体的嵌入式板级设备的配置。这也就是说,对于两块不同的嵌入式板而言,即使它们是基于同一种 CPU 而构建的,要想让运行在一块板子上的 Boot Loader 程序也能运行在另一块板子上,通常也都需要修改 Boot Loader 的源程序。

2. Boot Loader 的安装媒介(Installation Medium)

系统加电或复位后,所有的 CPU 通常都从某个由 CPU 制造商预先安排的地址上取指令。比如,基于 ARM7TDMI core 的 CPU 在复位时通常都从地址 0×00000000 取它的第一条指令。而基于 CPU 构建的嵌入式系统通常都有某种类型的固态存储设备(比如:ROM、EEPROM 或 FLASH 等)被映射到这个预先安排的地址上。因此在系统加电后,CPU 将首先执行 Boot Loader 程序。

下图1就是一个同时装有 Boot Loader、内核的启动参数、内核映像和根文件系统映像的固态存储设备的典型空间分配结构图。

图1 固态存储设备的典型空间分配结构

图1 固态存储设备的典型空间分配结构

3. 用来控制 Boot Loader 的设备或机制

主机和目标机之间一般通过串口建立连接,Boot Loader 软件在执行时通常会通过串口来进行 I/O,比如:输出打印信息到串口,从串口读取用户控制字符等。

4. Boot Loader 的启动过程是单阶段(Single Stage)还是多阶段(Multi-Stage)

通常多阶段的 Boot Loader 能提供更为复杂的功能,以及更好的可移植性。从固态存储设备上启动的 Boot Loader 大多都是 2 阶段的启动过程,也即启动过程可以分为 stage 1 和 stage 2 两部分。而至于在 stage 1 和 stage 2 具体完成哪些任务将在下面讨论。

5. Boot Loader 的操作模式 (Operation Mode)

大多数 Boot Loader 都包含两种不同的操作模式:”启动加载”模式和”下载”模式,这种区别仅对于开发人员才有意义。但从最终用户的角度看,Boot Loader 的作用就是用来加载操作系统,而并不存在所谓的启动加载模式与下载工作模式的区别。

启动加载(Boot loading)模式:这种模式也称为”自主”(Autonomous)模式。也即 Boot Loader 从目标机上的某个固态存储设备上将操作系统加载到 RAM 中运行,整个过程并没有用户的介入。这种模式是 Boot Loader 的正常工作模式,因此在嵌入式产品发布的时侯,Boot Loader 显然必须工作在这种模式下。

下载(Downloading)模式:在这种模式下,目标机上的 Boot Loader 将通过串口连接或网络连接等通信手段从主机(Host)下载文件,比如:下载内核映像和根文件系统映像等。从主机下载的文件通常首先被 Boot Loader 保存到目标机的 RAM 中,然后再被 Boot Loader 写到目标机上的FLASH 类固态存储设备中。Boot Loader 的这种模式通常在第一次安装内核与根文件系统时被使用;此外,以后的系统更新也会使用 Boot Loader 的这种工作模式。工作于这种模式下的 Boot Loader 通常都会向它的终端用户提供一个简单的命令行接口。

像 Blob 或 U-Boot 等这样功能强大的 Boot Loader 通常同时支持这两种工作模式,而且允许用户在这两种工作模式之间进行切换。比如,Blob 在启动时处于正常的启动加载模式,但是它会延时 10 秒等待终端用户按下任意键而将 blob 切换到下载模式。如果在 10 秒内没有用户按键,则 blob 继续启动 Linux 内核。

6. BootLoader 与主机之间进行文件传输所用的通信设备及协议

最常见的情况就是,目标机上的 Boot Loader 通过串口与主机之间进行文件传输,传输协议通常是 xmodem/ymodem/zmodem 协议中的一种。但是,串口传输的速度是有限的,因此通过以太网连接并借助 TFTP 协议来下载文件是个更好的选择。

此外,在论及这个话题时,主机方所用的软件也要考虑。比如,在通过以太网连接和 TFTP 协议来下载文件时,主机方必须有一个软件用来的提供 TFTP 服务。

在讨论了 BootLoader 的上述概念后,下面我们来具体看看 BootLoader 的应该完成哪些任务。

3. Boot Loader 的主要任务与典型结构框架

在继续本节的讨论之前,首先我们做一个假定,那就是:假定内核映像与根文件系统映像都被加载到 RAM 中运行。之所以提出这样一个假设前提是因为,在嵌入式系统中内核映像与根文件系统映像也可以直接在 ROM 或 Flash 这样的固态存储设备中直接运行。但这种做法无疑是以运行速度的牺牲为代价的。

从操作系统的角度看,Boot Loader 的总目标就是正确地调用内核来执行。

另外,由于 Boot Loader 的实现依赖于 CPU 的体系结构,因此大多数 Boot Loader 都分为 stage1 和 stage2 两大部分。依赖于 CPU 体系结构的代码,比如设备初始化代码等,通常都放在 stage1 中,而且通常都用汇编语言来实现,以达到短小精悍的目的。而 stage2 则通常用C语言来实现,这样可以实现给复杂的功能,而且代码会具有更好的可读性和可移植性。

Boot Loader 的 stage1 通常包括以下步骤(以执行的先后顺序):

  • 硬件设备初始化。
  • 为加载 Boot Loader 的 stage2 准备 RAM 空间。
  • 拷贝 Boot Loader 的 stage2 到 RAM 空间中。
  • 设置好堆栈。
  • 跳转到 stage2 的 C 入口点。

Boot Loader 的 stage2 通常包括以下步骤(以执行的先后顺序):

  • 初始化本阶段要使用到的硬件设备。
  • 检测系统内存映射(memory map)。
  • 将 kernel 映像和根文件系统映像从 flash 上读到 RAM 空间中。
  • 为内核设置启动参数。
  • 调用内核。

3.1 Boot Loader 的 stage1

3.1.1 基本的硬件初始化

这是 Boot Loader 一开始就执行的操作,其目的是为 stage2 的执行以及随后的 kernel 的执行准备好一些基本的硬件环境。它通常包括以下步骤(以执行的先后顺序):

1. 屏蔽所有的中断。为中断提供服务通常是 OS 设备驱动程序的责任,因此在 Boot Loader 的执行全过程中可以不必响应任何中断。中断屏蔽可以通过写 CPU 的中断屏蔽寄存器或状态寄存器(比如 ARM 的 CPSR 寄存器)来完成。

2. 设置 CPU 的速度和时钟频率。

3. RAM 初始化。包括正确地设置系统的内存控制器的功能寄存器以及各内存库控制寄存器等。

4. 初始化 LED。典型地,通过 GPIO 来驱动 LED,其目的是表明系统的状态是 OK 还是 Error。如果板子上没有 LED,那么也可以通过初始化 UART 向串口打印 Boot Loader 的 Logo 字符信息来完成这一点。

5. 关闭 CPU 内部指令/数据 cache。

3.1.2 为加载 stage2 准备 RAM 空间

为了获得更快的执行速度,通常把 stage2 加载到 RAM 空间中来执行,因此必须为加载 Boot Loader 的 stage2 准备好一段可用的 RAM 空间范围。

由于 stage2 通常是 C 语言执行代码,因此在考虑空间大小时,除了 stage2 可执行映象的大小外,还必须把堆栈空间也考虑进来。此外,空间大小最好是 memory page 大小(通常是 4KB)的倍数。一般而言,1M 的 RAM 空间已经足够了。具体的地址范围可以任意安排,比如 blob 就将它的 stage2 可执行映像安排到从系统 RAM 起始地址 0xc0200000 开始的 1M 空间内执行。但是,将 stage2 安排到整个 RAM 空间的最顶 1MB(也即(RamEnd-1MB) – RamEnd)是一种值得推荐的方法。

为了后面的叙述方便,这里把所安排的 RAM 空间范围的大小记为:stage2_size(字节),把起始地址和终止地址分别记为:stage2_start 和 stage2_end(这两个地址均以 4 字节边界对齐)。因此:

stage2_end=stage2_start+stage2_size

另外,还必须确保所安排的地址范围的的确确是可读写的 RAM 空间,因此,必须对你所安排的地址范围进行测试。具体的测试方法可以采用类似于 blob 的方法,也即:以 memory page 为被测试单位,测试每个 memory page 开始的两个字是否是可读写的。为了后面叙述的方便,我们记这个检测算法为:test_mempage,其具体步骤如下:

1. 先保存 memory page 一开始两个字的内容。

2. 向这两个字中写入任意的数字。比如:向第一个字写入 0×55,第 2 个字写入 0xaa。

3. 然后,立即将这两个字的内容读回。显然,我们读到的内容应该分别是 0×55 和 0xaa。如果不是,则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

4. 再向这两个字中写入任意的数字。比如:向第一个字写入 0xaa,第 2 个字中写入 0×55。

5. 然后,立即将这两个字的内容立即读回。显然,我们读到的内容应该分别是 0xaa 和 0×55。如果不是,则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

6. 恢复这两个字的原始内容。测试完毕。

为了得到一段干净的 RAM 空间范围,我们也可以将所安排的 RAM 空间范围进行清零操作。

3.1.3 拷贝 stage2 到 RAM 中

拷贝时要确定两点:(1) stage2 的可执行映象在固态存储设备的存放起始地址和终止地址;(2) RAM 空间的起始地址。

3.1.4 设置堆栈指针 sp

堆栈指针的设置是为了执行 C 语言代码作好准备。通常我们可以把 sp 的值设置为(stage2_end-4),也即在 3.1.2 节所安排的那个 1MB 的 RAM 空间的最顶端(堆栈向下生长)。

此外,在设置堆栈指针 sp 之前,也可以关闭 led 灯,以提示用户我们准备跳转到 stage2。

经过上述这些执行步骤后,系统的物理内存布局应该如下图2所示。

3.1.5 跳转到 stage2 的 C 入口点

在上述一切都就绪后,就可以跳转到 Boot Loader 的 stage2 去执行了。比如,在 ARM 系统中,这可以通过修改 PC 寄存器为合适的地址来实现。

图2 bootloader 的 stage2 可执行映象刚被拷贝到 RAM 空间时的系统内存布局

图2 bootloader 的 stage2 可执行映象刚被拷贝到 RAM 空间时的系统内存布局

3.2 Boot Loader 的 stage2

正如前面所说,stage2 的代码通常用 C 语言来实现,以便于实现更复杂的功能和取得更好的代码可读性和可移植性。但是与普通 C 语言应用程序不同的是,在编译和链接 boot loader 这样的程序时,我们不能使用 glibc 库中的任何支持函数。其原因是显而易见的。这就给我们带来一个问题,那就是从那里跳转进 main() 函数呢?直接把 main() 函数的起始地址作为整个 stage2 执行映像的入口点或许是最直接的想法。但是这样做有两个缺点:1)无法通过main() 函数传递函数参数;2)无法处理 main() 函数返回的情况。一种更为巧妙的方法是利用 trampoline(弹簧床)的概念。也即,用汇编语言写一段trampoline 小程序,并将这段 trampoline 小程序来作为 stage2 可执行映象的执行入口点。然后我们可以在 trampoline 汇编小程序中用 CPU 跳转指令跳入 main() 函数中去执行;而当 main() 函数返回时,CPU 执行路径显然再次回到我们的 trampoline 程序。简而言之,这种方法的思想就是:用这段 trampoline 小程序来作为 main() 函数的外部包裹(external wrapper)。

下面给出一个简单的 trampoline 程序示例(来自blob):

.text
.globl _trampoline
_trampoline:
	bl	main
	/* if main ever returns we just call it again */
	b	_trampoline

可以看出,当 main() 函数返回后,我们又用一条跳转指令重新执行 trampoline 程序――当然也就重新执行 main() 函数,这也就是 trampoline(弹簧床)一词的意思所在。

3.2.1初始化本阶段要使用到的硬件设备

这通常包括:(1)初始化至少一个串口,以便和终端用户进行 I/O 输出信息;(2)初始化计时器等。

在初始化这些设备之前,也可以重新把 LED 灯点亮,以表明我们已经进入 main() 函数执行。

设备初始化完成后,可以输出一些打印信息,程序名字字符串、版本号等。

3.2.2 检测系统的内存映射(memory map)

所谓内存映射就是指在整个 4GB 物理地址空间中有哪些地址范围被分配用来寻址系统的 RAM 单元。比如,在 SA-1100 CPU 中,从 0xC000,0000 开始的 512M 地址空间被用作系统的 RAM 地址空间,而在 Samsung S3C44B0X CPU 中,从 0x0c00,0000 到 0×1000,0000 之间的 64M 地址空间被用作系统的 RAM 地址空间。虽然 CPU 通常预留出一大段足够的地址空间给系统 RAM,但是在搭建具体的嵌入式系统时却不一定会实现 CPU 预留的全部 RAM 地址空间。也就是说,具体的嵌入式系统往往只把 CPU 预留的全部 RAM 地址空间中的一部分映射到 RAM 单元上,而让剩下的那部分预留 RAM 地址空间处于未使用状态。 由于上述这个事实,因此 Boot Loader 的 stage2 必须在它想干点什么 (比如,将存储在 flash 上的内核映像读到 RAM 空间中) 之前检测整个系统的内存映射情况,也即它必须知道 CPU 预留的全部 RAM 地址空间中的哪些被真正映射到 RAM 地址单元,哪些是处于 “unused” 状态的。

(1) 内存映射的描述

可以用如下数据结构来描述 RAM 地址空间中的一段连续(continuous)的地址范围:

typedef struct memory_area_struct {
	u32 start; /* the base address of the memory region */
	u32 size; /* the byte number of the memory region */
	int used;
} memory_area_t;

这段 RAM 地址空间中的连续地址范围可以处于两种状态之一:(1)used=1,则说明这段连续的地址范围已被实现,也即真正地被映射到 RAM 单元上。(2)used=0,则说明这段连续的地址范围并未被系统所实现,而是处于未使用状态。

基于上述 memory_area_t 数据结构,整个 CPU 预留的 RAM 地址空间可以用一个 memory_area_t 类型的数组来表示,如下所示:

memory_area_t memory_map[NUM_MEM_AREAS] = {
	[0 ... (NUM_MEM_AREAS - 1)] = {
		.start = 0,
		.size = 0,
		.used = 0
	},
};

(2) 内存映射的检测

下面我们给出一个可用来检测整个 RAM 地址空间内存映射情况的简单而有效的算法:

/* 数组初始化 */
for(i = 0; i < NUM_MEM_AREAS; i++)
	memory_map[i].used = 0;
/* first write a 0 to all memory locations */
for(addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE)
	* (u32 *)addr = 0;
for(i = 0, addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE) {
     /*
      * 检测从基地址 MEM_START+i*PAGE_SIZE 开始,大小为
* PAGE_SIZE 的地址空间是否是有效的RAM地址空间。
      */
     调用3.1.2节中的算法test_mempage();
     if ( current memory page isnot a valid ram page) {
		/* no RAM here */
		if(memory_map[i].used )
			i++;
		continue;
	}

	/*
	 * 当前页已经是一个被映射到 RAM 的有效地址范围
	 * 但是还要看看当前页是否只是 4GB 地址空间中某个地址页的别名?
	 */
	if(* (u32 *)addr != 0) { /* alias? */
		/* 这个内存页是 4GB 地址空间中某个地址页的别名 */
		if ( memory_map[i].used )
			i++;
		continue;
	}

	/*
	 * 当前页已经是一个被映射到 RAM 的有效地址范围
	 * 而且它也不是 4GB 地址空间中某个地址页的别名。
	 */
	if (memory_map[i].used == 0) {
		memory_map[i].start = addr;
		memory_map[i].size = PAGE_SIZE;
		memory_map[i].used = 1;
	} else {
		memory_map[i].size += PAGE_SIZE;
	}
} /* end of for (…) */

在用上述算法检测完系统的内存映射情况后,Boot Loader 也可以将内存映射的详细信息打印到串口。

3.2.3 加载内核映像和根文件系统映像

(1) 规划内存占用的布局

这里包括两个方面:(1)内核映像所占用的内存范围;(2)根文件系统所占用的内存范围。在规划内存占用的布局时,主要考虑基地址和映像的大小两个方面。

对于内核映像,一般将其拷贝到从(MEM_START+0×8000) 这个基地址开始的大约1MB大小的内存范围内(嵌入式 Linux 的内核一般都不操过 1MB)。为什么要把从 MEM_START 到 MEM_START+0×8000 这段 32KB 大小的内存空出来呢?这是因为 Linux 内核要在这段内存中放置一些全局数据结构,如:启动参数和内核页表等信息。

而对于根文件系统映像,则一般将其拷贝到 MEM_START+0×0010,0000 开始的地方。如果用 Ramdisk 作为根文件系统映像,则其解压后的大小一般是1MB。

(2)从 Flash 上拷贝

由于像 ARM 这样的嵌入式 CPU 通常都是在统一的内存地址空间中寻址 Flash 等固态存储设备的,因此从 Flash 上读取数据与从 RAM 单元中读取数据并没有什么不同。用一个简单的循环就可以完成从 Flash 设备上拷贝映像的工作:

while(count) {
	*dest++ = *src++; /* they are all aligned with word boundary */
	count -= 4; /* byte number */
};

3.2.4 设置内核的启动参数

应该说,在将内核映像和根文件系统映像拷贝到 RAM 空间中后,就可以准备启动 Linux 内核了。但是在调用内核之前,应该作一步准备工作,即:设置 Linux 内核的启动参数。

Linux 2.4.x 以后的内核都期望以标记列表(tagged list)的形式来传递启动参数。启动参数标记列表以标记 ATAG_CORE 开始,以标记 ATAG_NONE 结束。每个标记由标识被传递参数的 tag_header 结构以及随后的参数值数据结构来组成。数据结构 tag 和 tag_header 定义在 Linux 内核源码的include/asm/setup.h 头文件中:

/* The list ends with an ATAG_NONE node. */
#define ATAG_NONE	0x00000000
struct tag_header {
	u32 size; /* 注意,这里size是字数为单位的 */
	u32 tag;
};
……
struct tag {
	struct tag_header hdr;
	union {
		struct tag_core		core;
		struct tag_mem32	mem;
		struct tag_videotext	videotext;
		struct tag_ramdisk	ramdisk;
		struct tag_initrd	initrd;
		struct tag_serialnr	serialnr;
		struct tag_revision	revision;
		struct tag_videolfb	videolfb;
		struct tag_cmdline	cmdline;
		/*
		 * Acorn specific
		 */
		struct tag_acorn	acorn;
		/*
		 * DC21285 specific
		 */
		struct tag_memclk	memclk;
	} u;
};

在嵌入式 Linux 系统中,通常需要由 Boot Loader 设置的常见启动参数有:ATAG_CORE、ATAG_MEM、ATAG_CMDLINE、ATAG_RAMDISK、ATAG_INITRD等。

比如,设置 ATAG_CORE 的代码如下:

params = (struct tag *)BOOT_PARAMS;
	params->hdr.tag = ATAG_CORE;
	params->hdr.size = tag_size(tag_core);
	params->u.core.flags = 0;
	params->u.core.pagesize = 0;
	params->u.core.rootdev = 0;
	params = tag_next(params);

其中,BOOT_PARAMS 表示内核启动参数在内存中的起始基地址,指针 params 是一个 struct tag 类型的指针。宏 tag_next() 将以指向当前标记的指针为参数,计算紧临当前标记的下一个标记的起始地址。注意,内核的根文件系统所在的设备ID就是在这里设置的。

下面是设置内存映射情况的示例代码:

for(i = 0; i < NUM_MEM_AREAS; i++) {
		if(memory_map[i].used) {
			params->hdr.tag = ATAG_MEM;
			params->hdr.size = tag_size(tag_mem32);
			params->u.mem.start = memory_map[i].start;
			params->u.mem.size = memory_map[i].size;

			params = tag_next(params);
		}
}

可以看出,在 memory_map[]数组中,每一个有效的内存段都对应一个 ATAG_MEM 参数标记。

Linux 内核在启动时可以以命令行参数的形式来接收信息,利用这一点我们可以向内核提供那些内核不能自己检测的硬件参数信息,或者重载(override)内核自己检测到的信息。比如,我们用这样一个命令行参数字符串”console=ttyS0,115200n8″来通知内核以 ttyS0 作为控制台,且串口采用 “115200bps、无奇偶校验、8位数据位”这样的设置。下面是一段设置调用内核命令行参数字符串的示例代码:

char *p;
	/* eat leading white space */
	for(p = commandline; *p == ' '; p++)
		;
	/* skip non-existent command lines so the kernel will still
    * use its default command line.
	 */
	if(*p == '\0')
		return;
	params->hdr.tag = ATAG_CMDLINE;
	params->hdr.size = (sizeof(struct tag_header) + strlen(p) + 1 + 4) >> 2;
	strcpy(params->u.cmdline.cmdline, p);
	params = tag_next(params);

请注意在上述代码中,设置 tag_header 的大小时,必须包括字符串的终止符’\0′,此外还要将字节数向上圆整4个字节,因为 tag_header 结构中的size 成员表示的是字数。

下面是设置 ATAG_INITRD 的示例代码,它告诉内核在 RAM 中的什么地方可以找到 initrd 映象(压缩格式)以及它的大小:

	params->hdr.tag = ATAG_INITRD2;
	params->hdr.size = tag_size(tag_initrd);

	params->u.initrd.start = RAMDISK_RAM_BASE;
	params->u.initrd.size = INITRD_LEN;

	params = tag_next(params);

下面是设置 ATAG_RAMDISK 的示例代码,它告诉内核解压后的 Ramdisk 有多大(单位是KB):

params->hdr.tag = ATAG_RAMDISK;
params->hdr.size = tag_size(tag_ramdisk);

params->u.ramdisk.start = 0;
params->u.ramdisk.size = RAMDISK_SIZE; /* 请注意,单位是KB */
params->u.ramdisk.flags = 1; /* automatically load ramdisk */

params = tag_next(params);

最后,设置 ATAG_NONE 标记,结束整个启动参数列表:

static void setup_end_tag(void)
{
	params->hdr.tag = ATAG_NONE;
	params->hdr.size = 0;
}

3.2.5 调用内核

Boot Loader 调用 Linux 内核的方法是直接跳转到内核的第一条指令处,也即直接跳转到 MEM_START+0×8000 地址处。在跳转时,下列条件要满足:

1. CPU 寄存器的设置:

  • R0=0;
  • R1=机器类型 ID;关于 Machine Type Number,可以参见 linux/arch/arm/tools/mach-types。
  • R2=启动参数标记列表在 RAM 中起始基地址;

2. CPU 模式:

  • 必须禁止中断(IRQs和FIQs);
  • CPU 必须 SVC 模式;

3. Cache 和 MMU 的设置:

  • MMU 必须关闭;
  • 指令 Cache 可以打开也可以关闭;
  • 数据 Cache 必须关闭;

如果用 C 语言,可以像下列示例代码这样来调用内核:

void (*theKernel)(int zero, int arch, u32 params_addr) =
  (void (*)(int, int, u32))KERNEL_RAM_BASE;
……
theKernel(0, ARCH_NUMBER, (u32) kernel_params_start);

注意,theKernel()函数调用应该永远不返回的。如果这个调用返回,则说明出错。

回页首

4. 关于串口终端

在 boot loader 程序的设计与实现中,没有什么能够比从串口终端正确地收到打印信息能更令人激动了。此外,向串口终端打印信息也是一个非常重要而又有效的调试手段。但是,我们经常会碰到串口终端显示乱码或根本没有显示的问题。造成这个问题主要有两种原因:(1) boot loader 对串口的初始化设置不正确。(2) 运行在 host 端的终端仿真程序对串口的设置不正确,这包括:波特率、奇偶校验、数据位和停止位等方面的设置。

此外,有时也会碰到这样的问题,那就是:在 boot loader 的运行过程中我们可以正确地向串口终端输出信息,但当 boot loader 启动内核后却无法看到内核的启动输出信息。对这一问题的原因可以从以下几个方面来考虑:

(1) 首先请确认你的内核在编译时配置了对串口终端的支持,并配置了正确的串口驱动程序。

(2) 你的 boot loader 对串口的初始化设置可能会和内核对串口的初始化设置不一致。此外,对于诸如 s3c44b0x 这样的 CPU,CPU 时钟频率的设置也会影响串口,因此如果 boot loader 和内核对其 CPU 时钟频率的设置不一致,也会使串口终端无法正确显示信息。

(3) 最后,还要确认 boot loader 所用的内核基地址必须和内核映像在编译时所用的运行基地址一致,尤其是对于 uClinux 而言。假设你的内核映像在编译时用的基地址是 0xc0008000,但你的 boot loader 却将它加载到 0xc0010000 处去执行,那么内核映像当然不能正确地执行了。

5. 结束语

Boot Loader 的设计与实现是一个非常复杂的过程。如果不能从串口收到那激动人心的”uncompressing linux……………… done, booting the kernel……”内核启动信息,恐怕谁也不能说:”嗨,我的 boot loader 已经成功地转起来了!”。

 | 140 views | 0 comments | 0 flags | 

PLT and GOT – the key to code sharing and dynamic libraries

https://www.technovelty.org//linux/plt-and-got-the-key-to-code-sharing-and-dynamic-libraries.html

(this post was going to be about something else, but after getting this far, I think it stands on its own as an introduction to dynamic linking)

The shared library is an integral part of a modern system, but often the mechanisms behind the implementation are less well understood. There are, of course, many guides to this sort of thing. Hopefully this adds another perspective that resonates with someone.

Let’s start at the beginning — - relocations are entries in binaries that are left to be filled in later — at link time by the toolchain linker or at runtime by the dynamic linker. A relocation in a binary is a descriptor which essentially says “determine the value of X, and put that value into the binary at offset Y” — each relocation has a specific type, defined in the ABI documentation, which describes exactly how “determine the value of” is actually determined.

Here’s the simplest example:

$ cat a.c
extern int foo;

int function(void) {
    return foo;
}
$ gcc -c a.c
$ readelf --relocs ./a.o

Relocation section '.rel.text' at offset 0x2dc contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000004  00000801 R_386_32          00000000   foo

The value of foo is not known at the time you make a.o, so the compiler leaves behind a relocation (of type R_386_32) which is saying “in the final binary, patch the value at offset 0×4 in this object file with the address of symbol foo“. If you take a look at the output, you can see at offset 0×4 there are 4-bytes of zeros just waiting for a real address:

$ objdump --disassemble ./a.o

./a.o:     file format elf32-i386

Disassembly of section .text:

00000000 <function>:
   0:    55         push   %ebp
   1:    89 e5                  mov    %esp,%ebp
   3:    a1 00 00 00 00         mov    0x0,%eax
   8:    5d                     pop    %ebp
   9:    c3                     ret

That’s link time; if you build another object file with a value of foo and build that into a final executable, the relocation can go away. But there is a whole bunch of stuff for a fully linked executable or shared-library that just can’t be resolved until runtime. The major reason, as I shall try to explain, is position-independent code (PIC). When you look at an executable file, you’ll notice it has a fixed load address

$ readelf --headers /bin/ls
[...]
ELF Header:
[...]
  Entry point address:               0x8049bb0

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
[...]
  LOAD           0x000000 0x08048000 0x08048000 0x16f88 0x16f88 R E 0x1000
  LOAD           0x016f88 0x0805ff88 0x0805ff88 0x01543 0x01543 RW  0x1000

This is not position-independent. The code section (with permissions R E; i.e. read and execute) must be loaded at virtual address 0x08048000, and the data section (RW) must be loaded above that at exactly 0x0805ff88.

This is fine for an executable, because each time you start a new process (fork and exec) you have your own fresh address space. Thus it is a considerable time saving to pre-calculate addresses from and have them fixed in the final output (you can make position-independent executables, but that’s another story).

This is not fine for a shared library (.so). The whole point of a shared library is that applications pick-and-choose random permutations of libraries to achieve what they want. If your shared library is built to only work when loaded at one particular address everything may be fine — until another library comes along that was built also using that address. The problem is actually somewhat tractable — you can just enumerate every single shared library on the system and assign them all unique address ranges, ensuring that whatever combinations of library are loaded they never overlap. This is essentially whatprelinking does (although that is a hint, rather than a fixed, required address base). Apart from being a maintenance nightmare, with 32-bit systems you rapidly start to run out of address-space if you try to give every possible library a unique location. Thus when you examine a shared library, they do not specify a particular base address to be loaded at:

$ readelf --headers /lib/libc.so.6
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
[...]
  LOAD           0x000000 0x00000000 0x00000000 0x236ac 0x236ac R E 0x1000
  LOAD           0x023edc 0x00024edc 0x00024edc 0x0015c 0x001a4 RW  0x1000

Shared libraries also have a second goal — code sharing. If a hundred processes use a shared library, it makes no sense to have 100 copies of the code in memory taking up space. If the code is completely read-only, and hence never, ever, modified, then every process can share the same code. However, we have the constraint that the shared library must still have a unqiue data instance in each process. While it would be possible to put the library data anywhere we want at runtime, this would require leaving behind relocations to patch the code and inform it where to actually find the data — destroying the always read-only property of the code and thus sharability. As you can see from the above headers, the solution is that the read-write data section is always put at a known offset from the code section of the library. This way, via the magic of virtual-memory, every process sees its own data section but can share the unmodified code. All that is needed to access data is some simple maths; address of thing I want = my current address + known fixed offset.

Well, simple maths is all relative! “My current address” may or may not be easy to find. Consider the following:

$ cat test.c
static int foo = 100;

int function(void) {
    return foo;
}
$ gcc -fPIC -shared -o libtest.so test.c

So foo will be in data, at a fixed offset from the code in function, and all we need to do is find it! On amd64, this is quite easy, check the disassembly:

000000000000056c <function>:
 56c:        55         push   %rbp
 56d:        48 89 e5               mov    %rsp,%rbp
 570:        8b 05 b2 02 20 00      mov    0x2002b2(%rip),%eax        # 200828 <foo>
 576:        5d                     pop    %rbp

This says “put the value at offset 0x2002b2 from the current instruction pointer (%rip) into %eax. That’s it — we know the data is at that fixed offset so we’re done. i386, on the other hand, doesn’t have the ability to offset from the current instruction pointer. Some trickery is required there:

0000040c <function>:
 40c:    55         push   %ebp
 40d:    89 e5                  mov    %esp,%ebp
 40f:    e8 0e 00 00 00         call   422 <__i686.get_pc_thunk.cx>
 414:    81 c1 5c 11 00 00      add    $0x115c,%ecx
 41a:    8b 81 18 00 00 00      mov    0x18(%ecx),%eax
 420:    5d                     pop    %ebp
 421:    c3                     ret

00000422 <__i686.get_pc_thunk.cx>:
 422:    8b 0c 24       mov    (%esp),%ecx
 425:    c3                     ret

The magic here is __i686.get_pc_thunk.cx. The architecture does not let us get the current instruction address, but we can get a known fixed address — the value __i686.get_pc_thunk.cx pushes into cx is the return value from the call, i.e in this case 0x414. Then we can do the maths for the add instruction; 0x115c + 0x414 = 0x1570, the final move goes 0x18 bytes past that to 0x1588 … checking the disassembly

00001588 <global>:
    1588:       64 00 00                add    %al,%fs:(%eax)

i.e., the value 100 in decimal, stored in the data section.

We are getting closer, but there are still some issues to deal with. If a shared library can be loaded at any address, then how does an executable, or other shared library, know how to access data or call functions in it? We could, theoretically, load the library and patch up any data references or calls into that library; however as just described this would destroy code-sharability. As we know, all problems can be solved with a layer of indirection, in this case called global offset table or GOT.

Consider the following library:

$ cat test.c
extern int foo;

int function(void) {
    return foo;
}
$ gcc -shared -fPIC -o libtest.so test.c

Note this looks exactly like before, but in this case the foo is extern; presumably provided by some other library. Let’s take a closer look at how this works, on amd64:

$ objdump --disassemble libtest.so
[...]
00000000000005ac <function>:
 5ac:        55         push   %rbp
 5ad:        48 89 e5               mov    %rsp,%rbp
 5b0:        48 8b 05 71 02 20 00   mov    0x200271(%rip),%rax        # 200828 <_DYNAMIC+0x1a0>
 5b7:        8b 00                  mov    (%rax),%eax
 5b9:        5d                     pop    %rbp
 5ba:        c3                     retq

$ readelf --sections libtest.so
Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
[...]
  [20] .got              PROGBITS         0000000000200818  00000818
       0000000000000020  0000000000000008  WA       0     0     8

$ readelf --relocs libtest.so
Relocation section '.rela.dyn' at offset 0x418 contains 5 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
[...]
000000200828  000400000006 R_X86_64_GLOB_DAT 0000000000000000 foo + 0

The disassembly shows that the value to be returned is loaded from an offset of 0x200271 from the current %rip; i.e. 0x0200828. Looking at the section headers, we see that this is part of the .got section. When we examine the relocations, we see aR_X86_64_GLOB_DAT relocation that says “find the value of symbol foo and put it into address 0x200828.

So, when this library is loaded, the dynamic loader will examine the relocation, go and find the value of foo and patch the .gotentry as required. When it comes time for the code loads to load that value, it will point to the right place and everything just works; without having to modify any code values and thus destroy code sharability.

This handles data, but what about function calls? The indirection used here is called a procedure linkage table or PLT. Code does not call an external function directly, but only via a PLT stub. Let’s examine this:

$ cat test.c
int foo(void);

int function(void) {
    return foo();
}
$ gcc -shared -fPIC -o libtest.so test.c

$ objdump --disassemble libtest.so
[...]
00000000000005bc <function>:
 5bc:        55         push   %rbp
 5bd:        48 89 e5               mov    %rsp,%rbp
 5c0:        e8 0b ff ff ff         callq  4d0 <foo@plt>
 5c5:        5d                     pop    %rbp

$ objdump --disassemble-all libtest.so
00000000000004d0 <foo@plt>:
 4d0:   ff 25 82 03 20 00       jmpq   *0x200382(%rip)        # 200858 <_GLOBAL_OFFSET_TABLE_+0x18>
 4d6:   68 00 00 00 00          pushq  $0x0
 4db:   e9 e0 ff ff ff          jmpq   4c0 <_init+0x18>

$ readelf --relocs libtest.so
Relocation section '.rela.plt' at offset 0x478 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000200858  000400000007 R_X86_64_JUMP_SLO 0000000000000000 foo + 0

So, we see that function makes a call to code at 0x4d0. Disassembling this, we see an interesting call, we jump to the value stored in 0x200382 past the current %rip (i.e. 0x200858), which we can then see the relocation for — the symbol foo.

It is interesting to keep following this through; let’s look at the initial value that is jumped to:

$ objdump --disassemble-all libtest.so

Disassembly of section .got.plt:

0000000000200840 <.got.plt>:
  200840:       98                      cwtl
  200841:       06                      (bad)
  200842:       20 00                   and    %al,(%rax)
        ...
  200858:       d6                      (bad)
  200859:       04 00                   add    $0x0,%al
  20085b:       00 00                   add    %al,(%rax)
  20085d:       00 00                   add    %al,(%rax)
  20085f:       00 e6                   add    %ah,%dh
  200861:       04 00                   add    $0x0,%al
  200863:       00 00                   add    %al,(%rax)
  200865:       00 00                   add    %al,(%rax)
        ...

Unscrambling 0x200858 we see its initial value is 0x4d6 — i.e. the next instruction! Which then pushes the value 0 and jumps to0x4c0. Looking at that code we can see it pushes a value from the GOT, and then jumps to a second value in the GOT:

00000000000004c0 <foo@plt-0x10>:
 4c0:   ff 35 82 03 20 00       pushq  0x200382(%rip)        # 200848 <_GLOBAL_OFFSET_TABLE_+0x8>
 4c6:   ff 25 84 03 20 00       jmpq   *0x200384(%rip)        # 200850 <_GLOBAL_OFFSET_TABLE_+0x10>
 4cc:   0f 1f 40 00             nopl   0x0(%rax)

What’s going on here? What’s actually happening is lazy binding — by convention when the dynamic linker loads a library, it will put an identifier and resolution function into known places in the GOT. Therefore, what happens is roughly this: on the first call of a function, it falls through to call the default stub, which loads the identifier and calls into the dynamic linker, which at that point has enough information to figure out “hey, this libtest.so is trying to find the function foo“. It will go ahead and find it, and then patch the address into the GOT such that the next time the original PLT entry is called, it will load the actual address of the function, rather than the lookup stub. Ingenious!

Out of this indirection falls another handy thing — the ability to modify the symbol binding order. LD_PRELOAD, for example, simply tells the dynamic loader it should insert a library as first to be looked-up for symbols; therefore when the above binding happens if the preloaded library declares a foo, it will be chosen over any other one provided.

In summary — code should be read-only always, and to make it so that you can still access data from other libraries and call external functions these accesses are indirected through a GOT and PLT which live at compile-time known offsets.

In a future post I’ll discuss some of the security issues around this implementation, but that post won’t make sense unless I can refer back to this one :)

 | 203 views | 0 comments | 0 flags | 

[Pthread] Linux中的线程同步机制 — Futex

http://blog.csdn.net/Javadino/article/details/2891385

引子
在编译2.6内核的时候,你会在编译选项中看到[*] Enable futex support这一项,上网查,有的资料会告诉你”不选这个内核不一定能正确的运行使用glibc的程序”,那futex是什么?和glibc又有什么关系呢?

1. 什么是Futex
Futex是Fast Userspace muTexes的缩写,由Hubertus Franke, Matthew Kirkwood, Ingo Molnar and Rusty Russell共同设计完成。几位都是linux领域的专家,其中可能Ingo Molnar大家更熟悉一些,毕竟是O(1)调度器和CFS的实现者。

Futex按英文翻译过来就是快速用户空间互斥体。其设计思想其实不难理解,在传统的Unix系统中,System V IPC(inter process communication),如 semaphores, msgqueues, sockets还有文件锁机制(flock())等进程间同步机制都是对一个内核对象操作来完成的,这个内核对象对要同步的进程都是可见的,其提供了共享的状态信息和原子操作。当进程间要同步的时候必须要通过系统调用(如semop())在内核中完成。可是经研究发现,很多同步是无竞争的,即某个进程进入互斥区,到再从某个互斥区出来这段时间,常常是没有进程也要进这个互斥区或者请求同一同步变量的。但是在这种情况下,这个进程也要陷入内核去看看有没有人和它竞争,退出的时侯还要陷入内核去看看有没有进程等待在同一同步变量上。这些不必要的系统调用(或者说内核陷入)造成了大量的性能开销。为了解决这个问题,Futex就应运而生,Futex是一种用户态和内核态混合的同步机制。首先,同步的进程间通过mmap共享一段内存,futex变量就位于这段共享的内存中且操作是原子的,当进程尝试进入互斥区或者退出互斥区的时候,先去查看共享内存中的futex变量,如果没有竞争发生,则只修改futex,而不用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生,则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说,futex就是通过在用户态的检查,如果了解到没有竞争就不用陷入内核了,大大提高了low-contention时候的效率。Linux从2.5.7开始支持Futex。

2. Futex系统调用
Futex是一种用户态和内核态混合机制,所以需要两个部分合作完成,linux上提供了sys_futex系统调用,对进程竞争情况下的同步处理提供支持。
其原型和系统调用号为
#include <linux/futex.h>
#include <sys/time.h>
int futex (int *uaddr, int op, int val, const struct timespec *timeout,int *uaddr2, int val3);
#define __NR_futex              240

虽然参数有点长,其实常用的就是前面三个,后面的timeout大家都能理解,其他的也常被ignore。
uaddr就是用户态下共享内存的地址,里面存放的是一个对齐的整型计数器。
op存放着操作类型。定义的有5中,这里我简单的介绍一下两种,剩下的感兴趣的自己去man futex
FUTEX_WAIT: 原子性的检查uaddr中计数器的值是否为val,如果是则让进程休眠,直到FUTEX_WAKE或者超时(time-out)。也就是把进程挂到uaddr相对应的等待队列上去。
FUTEX_WAKE: 最多唤醒val个等待在uaddr上进程。

可见FUTEX_WAIT和FUTEX_WAKE只是用来挂起或者唤醒进程,当然这部分工作也只能在内核态下完成。有些人尝试着直接使用futex系统调用来实现进程同步,并寄希望获得futex的性能优势,这是有问题的。应该区分futex同步机制和futex系统调用。futex同步机制还包括用户态下的操作,我们将在下节提到。

3. Futex同步机制
所有的futex同步操作都应该从用户空间开始,首先创建一个futex同步变量,也就是位于共享内存的一个整型计数器。
当进程尝试持有锁或者要进入互斥区的时候,对futex执行”down”操作,即原子性的给futex同步变量减1。如果同步变量变为0,则没有竞争发生,进程照常执行。如果同步变量是个负数,则意味着有竞争发生,需要调用futex系统调用的futex_wait操作休眠当前进程。
当进程释放锁或者要离开互斥区的时候,对futex进行”up”操作,即原子性的给futex同步变量加1。如果同步变量由0变成1,则没有竞争发生,进程照常执行。如果加之前同步变量是负数,则意味着有竞争发生,需要调用futex系统调用的futex_wake操作唤醒一个或者多个等待进程。

这里的原子性加减通常是用CAS(Compare and Swap)完成的,与平台相关。CAS的基本形式是:CAS(addr,old,new),当addr中存放的值等于old时,用new对其替换。在x86平台上有专门的一条指令来完成它: cmpxchg。

可见: futex是从用户态开始,由用户态和核心态协调完成的。

4. 进/线程利用futex同步
进程或者线程都可以利用futex来进行同步。
对于线程,情况比较简单,因为线程共享虚拟内存空间,虚拟地址就可以唯一的标识出futex变量,即线程用同样的虚拟地址来访问futex变量。
对于进程,情况相对复杂,因为进程有独立的虚拟内存空间,只有通过mmap()让它们共享一段地址空间来使用futex变量。每个进程用来访问futex的虚拟地址可以是不一样的,只要系统知道所有的这些虚拟地址都映射到同一个物理内存地址,并用物理内存地址来唯一标识futex变量。

小结:
1. Futex变量的特征:1)位于共享的用户空间中 2)是一个32位的整型 3)对它的操作是原子的
2. Futex在程序low-contention的时候能获得比传统同步机制更好的性能。
3. 不要直接使用Futex系统调用。
4. Futex同步机制可以用于进程间同步,也可以用于线程间同步。

那么应该如何使用Futex,它和glibc又有什么关系呢?下次继续。

在linux中进行多线程开发,同步是不可回避的一个问题。在POSIX标准中定义了三种线程同步机制: Mutexes(互斥量), Condition Variables(条件变量)和POSIX Semaphores(信号量)。NPTL基本上实现了POSIX,而glibc又使用NPTL作为自己的线程库。因此glibc中包含了这三种同步机制的实现(当然还包括其他的同步机制,如APUE里提到的读写锁)。

Glibc中常用的线程同步方式举例:

Semaphore:
变量定义:    sem_t sem;
初始化:      sem_init(&sem,0,1);
进入加锁:     sem_wait(&sem);
退出解锁:     sem_post(&sem);

Mutex:
变量定义:    pthread_mutex_t mut;
初始化:      pthread_mutex_init(&mut,NULL);
进入加锁:     pthread_mutex_lock(&mut);
退出解锁:     pthread_mutex_unlock(&mut);

这些用于同步的函数和futex有什么关系?下面让我们来看一看:
以Semaphores为例,
进入互斥区的时候,会执行sem_wait(sem_t *sem),sem_wait的实现如下:
int sem_wait (sem_t *sem)
{
int *futex = (int *) sem;
if (atomic_decrement_if_positive (futex) > 0)
return 0;
int   err = lll_futex_wait (futex, 0);
return -1;
)
atomic_decrement_if_positive()的语义就是如果传入参数是正数就将其原子性的减一并立即返回。如果信号量为正,在Semaphores的语义中意味着没有竞争发生,如果没有竞争,就给信号量减一后直接返回了。

如果传入参数不是正数,即意味着有竞争,调用lll_futex_wait(futex,0),lll_futex_wait是个宏,展开后为:
#define lll_futex_wait(futex, val) /
({                                          /

__asm __volatile (LLL_EBX_LOAD                          /
LLL_ENTER_KERNEL                          /
LLL_EBX_LOAD                          /
: “=a” (__status)                          /
: “0″ (SYS_futex), LLL_EBX_REG (futex), “S” (0),          /
“c” (FUTEX_WAIT), “d” (_val),                  /
“i” (offsetof (tcbhead_t, sysinfo))              /
: “memory”);                          /
…                                      /
})
可以看到当发生竞争的时候,sem_wait会调用SYS_futex系统调用,并在val=0的时候执行FUTEX_WAIT,让当前线程休眠。

从这个例子我们可以看出,在Semaphores的实现过程中使用了futex,不仅仅是说其使用了futex系统调用(再重申一遍只使用futex系统调用是不够的),而是整个建立在futex机制上,包括用户态下的操作和核心态下的操作。其实对于其他glibc的同步机制来说也是一样,都采纳了futex作为其基础。所以才会在futex的manual中说:对于大多数程序员不需要直接使用futexes,取而代之的是依靠建立在futex之上的系统库,如NPTL线程库(most programmers will in fact not be using futexes directly but instead rely on system libraries built on them, such as the NPTL pthreads implementation)。所以才会有如果在编译内核的时候不 Enable futex support,就”不一定能正确的运行使用Glibc的程序”。

小结:
1. Glibc中的所提供的线程同步方式,如大家所熟知的Mutex,Semaphore等,大多都构造于futex之上了,除了特殊情况,大家没必要再去实现自己的futex同步原语。
2. 大家要做的事情,似乎就是按futex的manual中所说得那样: 正确的使用Glibc所提供的同步方式,并在使用它们的过程中,意识到它们是利用futex机制和linux配合完成同步操作就可以了。

如果只是阅读理解,到这里也就够了,不过我们需要用实际行动印证一下,我们的理解是否正确。在实际使用过程中还遇到什么样的问题? 下次继续。

上回说到Glibc中(NPTL)的线程同步方式如Mutex,Semaphore等都使用了futex作为其基础。那么实际使用是什么样子,又会碰到什么问题呢?
先来看一个使用semaphore同步的例子。

sem_t sem_a;
void *task1();

int main(void){
int ret=0;
pthread_t thrd1;
sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL); //创建子线程
pthread_join(thrd1,NULL); //等待子线程结束
}

void *task1()
{
int sval = 0;
sem_wait(&sem_a); //持有信号量
sleep(5); //do_nothing
sem_getvalue(&sem_a,&sval);
printf(“sem value = %d/n”,sval);
sem_post(&sem_a); //释放信号量
}

程序很简单,我们在主线程(执行main的线程)中创建了一个线程,并用join等待其结束。在子线程中,先持有信号量,然后休息一会儿,再释放信号量,结束。
因为这段代码中只有一个线程使用信号量,也就是没有线程间竞争发生,按照futex的理论,因为没有竞争,所以所有的锁操作都将在用户态中完成,而不会执行系统调用而陷入内核。我们用strace来跟踪一下这段程序的执行过程中所发生的系统调用:

20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
20533 <… futex resumed> )             = 0

20533是main线程的id,20534是其子线程的id。出乎我们意料之外的是这段程序还是发生了两次futex系统调用,我们来分析一下这分别是什么原因造成的。

1. 出人意料的”sem_post()”
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
子线程还是执行了FUTEX_WAKE的系统调用,就是在sem_post(&sem_a);的时候,请求内核唤醒一个等待在sem_a上的线程,其返回值是0,表示现在并没有线程等待在sem_a(这是当然的,因为就这么一个线程在使用sem_a),这次futex系统调用白做了。这似乎和futex的理论有些出入,我们再来看一下sem_post的实现。
int sem_post (sem_t *sem)
{
int *futex = (int *) sem;
int nr = atomic_increment_val (futex);
int err = lll_futex_wake (futex, nr);
return 0;
}
我们看到,Glibc在实现sem_post的时候给futex原子性的加上1后,不管futex的值是什么,都执行了lll_futex_wake(),即futex(FUTEX_WAKE)系统调用。
在第二部分中(见前文),我们分析了sem_wait的实现,当没有竞争的时候是不会有futex调用的,现在看来真的是这样,但是在sem_post的时候,无论有无竞争,都会调用sys_futex(),为什么会这样呢?我觉得应该结合semaphore的语义来理解。在semaphore的语义中,sem_wait()的意思是:”挂起当前进程,直到semaphore的值为非0,它会原子性的减少semaphore计数值。” 我们可以看到,semaphore中是通过0或者非0来判断阻塞或者非阻塞线程。即无论有多少线程在竞争这把锁,只要使用了semaphore,semaphore的值都会是0。这样,当线程推出互斥区,执行sem_post(),释放semaphore的时候,将其值由0改1,并不知道是否有线程阻塞在这个semaphore上,所以只好不管怎么样都执行futex(uaddr, FUTEX_WAKE, 1)尝试着唤醒一个进程。而相反的,当sem_wait(),如果semaphore由1变0,则意味着没有竞争发生,所以不必去执行futex系统调用。我们假设一下,如果抛开这个语义,如果允许semaphore值为负,则也可以在sem_post()的时候,实现futex机制。

2. 半路杀出的”pthread_join()”
那另一个futex系统调用是怎么造成的呢? 是因为pthread_join();
在Glibc中,pthread_join也是用futex系统调用实现的。程序中的pthread_join(thrd1,NULL); 就对应着
20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
很好解释,主线程要等待子线程(id号20534上)结束的时候,调用futex(FUTEX_WAIT),并把var参数设置为要等待的子线程号(20534),然后等待在一个地址为0xb7db1be8的futex变量上。当子线程结束后,系统会负责把主线程唤醒。于是主线程就
20533 <… futex resumed> )             = 0
恢复运行了。
要注意的是,如果在执行pthread_join()的时候,要join的线程已经结束了,就不会再调用futex()阻塞当前进程了。

3. 更多的竞争。
我们把上面的程序稍微改改:
在main函数中:
int main(void){

sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL);
ret=pthread_create(&thrd2,NULL,task1,NULL);
ret=pthread_create(&thrd3,NULL,task1,NULL);
ret=pthread_create(&thrd4,NULL,task1,NULL);
pthread_join(thrd1,NULL);
pthread_join(thrd2,NULL);
pthread_join(thrd3,NULL);
pthread_join(thrd4,NULL);

}

这样就有更的线程参与sem_a的争夺了。我们来分析一下,这样的程序会发生多少次futex系统调用。
1) sem_wait()
第一个进入的线程不会调用futex,而其他的线程因为要阻塞而调用,因此sem_wait会造成3次futex(FUTEX_WAIT)调用。
2) sem_post()
所有线程都会在sem_post的时候调用futex, 因此会造成4次futex(FUTEX_WAKE)调用。
3) pthread_join()
别忘了还有pthread_join(),我们是按thread1, thread2, thread3, thread4这样来join的,但是线程的调度存在着随机性。如果thread1最后被调度,则只有thread1这一次futex调用,所以pthread_join()造成的futex调用在1-4次之间。(虽然不是必然的,但是4次更常见一些)
所以这段程序至多会造成3+4+4=11次futex系统调用,用strace跟踪,验证了我们的想法。
19710 futex(0xb7df1be8, FUTEX_WAIT, 19711, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19711 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb75f0be8, FUTEX_WAIT, 19712, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb6defbe8, FUTEX_WAIT, 19713, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb65eebe8, FUTEX_WAIT, 19714, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAKE, 1)   = 0
(19710是主线程,19711,19712,19713,19714是4个子线程)

4. 更多的问题
事情到这里就结束了吗? 如果我们把semaphore换成Mutex试试。你会发现当自始自终没有竞争的时候,mutex会完全符合futex机制,不管是lock还是unlock都不会调用futex系统调用。有竞争的时候,第一次pthread_mutex_lock的时候不会调用futex调用,看起来还正常。但是最后一次pthread_mutex_unlock的时候,虽然已经没有线程在等待mutex了,可还是会调用futex(FUTEX_WAKE)。这又是什么原因造成的呢?留给感兴趣的同学去分析吧。

小结:
1. 虽然semaphore,mutex等同步方式构建在futex同步机制之上。然而受其语义等的限制,并没有完全按futex最初的设计实现。
2. pthread_join()等函数也是调用futex来实现的。
3. 不同的同步方式都有其不同的语义,不同的性能特征,适合于不同的场景。我们在使用过程中要知道他们的共性,也得了解它们之间的差异。这样才能更好的理解多线程场景,写出更高质量的多线程程序。

至此futex的学习就告一段落了,希望对大家有所帮助。

 | 455 views | 0 comments | 0 flags | 

linux 内核的几种锁介绍

linux 内核的几种锁介绍

spinlock(自旋锁)、 mutex(互斥量)、 semaphore(信号量)、 critical section(临界区) 的作用与区别
Mutex是一把钥匙,一个人拿了就可进入一个房间,出来的时候把钥匙交给队列的第一个。一般的用法是用于串行化对critical section代码的访问,保证这段代码不会被并行的运行。
Semaphore是一件可以容纳N人的房间,如果人不满就可以进去,如果人满了,就要等待有人出来。对于N=1的情况,称为binary semaphore。一般的用法是,用于限制对于某一资源的同时访问。
Binary semaphore与Mutex的差异:
在有的系统中Binary semaphore与Mutex是没有差异的。在有的系统上,主要的差异是mutex一定要由获得锁的进程来释放。而semaphore可以由其它进程释放(这时的semaphore实际就是个原子的变量,大家可以加或减),因此semaphore可以用于进程间同步。Semaphore的同步功能是所有系统都支持的,而Mutex能否由其他进程释放则未定,因此建议mutex只用于保护critical section。而semaphore则用于保护某变量,或者同步。
另一个概念是spin lock,这是一个内核态概念。spin lock与semaphore的主要区别是spin lock是busy waiting,而semaphore是sleep。对于可以sleep的进程来说,busy waiting当然没有意义。对于单CPU的系统,busy waiting当然更没意义(没有CPU可以释放锁)。因此,只有多CPU的内核态非进程空间,才会用到spin lock。Linux kernel的spin lock在非SMP的情况下,只是关irq,没有别的操作,用于确保该段程序的运行不会被打断。其实也就是类似mutex的作用,串行化对 critical section的访问。但是mutex不能保护中断的打断,也不能在中断处理程序中被调用。而spin lock也一般没有必要用于可以sleep的进程空间。
———————————————————————————————
内核同步措施
为了避免并发,防止竞争。内核提供了一组同步方法来提供对共享数据的保护。我们的重点不是介绍这些方法的详细用法,而是强调为什么使用这些方法和它们之间的差别。
Linux 使用的同步机制可以说从2.0到2.6以来不断发展完善。从最初的原子操作,到后来的信号量,从大内核锁到今天的自旋锁。这些同步机制的发展伴随 Linux从单处理器到对称多处理器的过度;伴随着从非抢占内核到抢占内核的过度。锁机制越来越有效,也越来越复杂。目前来说内核中原子操作多用来做计数使用,其它情况最常用的是两种锁以及它们的变种:一个是自旋锁,另一个是信号量。我们下面就来着重介绍一下这两种锁机制。
自旋锁
自旋锁是专为防止多处理器并发而引入的一种锁,它在内核中大量应用于中断处理等部分(对于单处理器来说,防止中断处理中的并发可简单采用关闭中断的方式,不需要自旋锁)。
自旋锁最多只能被一个内核任务持有,如果一个内核任务试图请求一个已被争用(已经被持有)的自旋锁,那么这个任务就会一直进行忙循环——旋转——等待锁重新可用。要是锁未被争用,请求它的内核任务便能立刻得到它并且继续进行。自旋锁可以在任何时刻防止多于一个的内核任务同时进入临界区,因此这种锁可有效地避免多处理器上并发运行的内核任务竞争共享资源。
事实上,自旋锁的初衷就是:在短期间内进行轻量级的锁定。一个被争用的自旋锁使得请求它的线程在等待锁重新可用的期间进行自旋(特别浪费处理器时间),所以自旋锁不应该被持有时间过长。如果需要长时间锁定的话, 最好使用信号量。
自旋锁的基本形式如下:
spin_lock(&mr_lock);     //临界区
spin_unlock(&mr_lock);
因为自旋锁在同一时刻只能被最多一个内核任务持有,所以一个时刻只有一个线程允许存在于临界区中。这点很好地满足了对称多处理机器需要的锁定服务。在单处理器上,自旋锁仅仅当作一个设置内核抢占的开关。如果内核抢占也不存在,那么自旋锁会在编译时被完全剔除出内核。
简单的说,自旋锁在内核中主要用来防止多处理器中并发访问临界区,防止内核抢占造成的竞争。另外自旋锁不允许任务睡眠(持有自旋锁的任务睡眠会造成自死锁——因为睡眠有可能造成持有锁的内核任务被重新调度,而再次申请自己已持有的锁),它能够在中断上下文中使用。
死锁:假设有一个或多个内核任务和一个或多个资源,每个内核都在等待其中的一个资源,但所有的资源都已经被占用了。这便会发生所有内核任务都在相互等待,但它们永远不会释放已经占有的资源,于是任何内核任务都无法获得所需要的资源,无法继续运行,这便意味着死锁发生了。自死琐是说自己占有了某个资源,然后自己又申请自己已占有的资源,显然不可能再获得该资源,因此就自缚手脚了。
信号量
Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个已被持有的信号量时,信号量会将其推入等待队列,然后让其睡眠。这时处理器获得自由去执行其它代码。当持有信号量的进程将信号量释放后,在等待队列中的一个任务将被唤醒,从而便可以获得这个信号量。
信号量的睡眠特性,使得信号量适用于锁会被长时间持有的情况;只能在进程上下文中使用,因为中断上下文中是不能被调度的;另外当代码持有信号量时,不可以再持有自旋锁。
信号量基本使用形式为:
static DECLARE_MUTEX(mr_sem);//声明互斥信号量
if(down_interruptible(&mr_sem))
//可被中断的睡眠,当信号来到,睡眠的任务被唤醒
//临界区
up(&mr_sem);
信号量和自旋锁区别
虽然听起来两者之间的使用条件复杂,其实在实际使用中信号量和自旋锁并不易混淆。注意以下原则:
如果代码需要睡眠——这往往是发生在和用户空间同步时——使用信号量是唯一的选择。由于不受睡眠的限制,使用信号量通常来说更加简单一些。如果需要在自旋锁和信号量中作选择,应该取决于锁被持有的时间长短。理想情况是所有的锁都应该尽可能短的被持有,但是如果锁的持有时间较长的话,使用信号量是更好的选择。另外,信号量不同于自旋锁,它不会关闭内核抢占,所以持有信号量的代码可以被抢占。这意味者信号量不会对影响调度反应时间带来负面影响。
自旋锁对信号量
需求 建议的加锁方法
低开销加锁               优先使用自旋锁
短期锁定                 优先使用自旋锁
长期加锁                 优先使用信号量
中断上下文中加锁         使用自旋锁
持有锁是需要睡眠、调度   使用信号量
———————————————————————————————
临界区(Critical Section)
保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区,那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起,并一直持续到进入临界区的线程离开。临界区在被释放后,其他线程可以继续抢占,并以此达到用原子方式操作共享资源的目的。
在使用临界区时,一般不允许其运行时间过长,只要进入临界区的线程还没有离开,其他所有试图进入此临界区的线程都会被挂起而进入到等待状态,并会在一定程度上影响。程序的运行性能。尤其需要注意的是不要将等待用户输入或是其他一些外界干预的操作包含到临界区。如果进入了临界区却一直没有释放,同样也会引起其他线程的长时间等待。虽然临界区同步速度很快,但却只能用来同步本进程内的线程,而不可用来同步多个进程中的线程。
互斥量(Mutex)
互斥(Mutex)是一种用途非常广泛的内核对象。能够保证多个线程对同一共享资源的互斥访问。同临界区有些类似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。与其他几种内核对象不同,互斥对象在操作系统中拥有特殊代码,并由操作系统来管理,操作系统甚至还允许其进行一些其他内核对象所不能进行的非常规操作。互斥量跟临界区很相似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。

信号量(Semaphores)
信号量对象对线程的同步方式与前面几种方法不同,信号允许多个线程同时使用共享资源,这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore()创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数,每增加一个线程对共享资源的访问,当前可用资源计数就会减1,只要当前可用资源计数是大于0的,就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目,不能在允许其他线程的进入,此时的信号量信号将无法发出。线程在处理完共享资源后,应在离开的同时通过ReleaseSemaphore()函数将当前可用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。信号量是通过计数来对线程访问资源进行控制的,而实际上信号量确实也被称作Dijkstra计数器。
PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数,S大于等于零时代表可供并发进程使用的资源实体数,但S小于零时则表示正在等待使用共享资源的进程数。
P操作申请资源:
(1)S减1;
(2)若S减1后仍大于等于零,则进程继续执行;
(3)若S减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转入进程调度。
V操作释放资源:     (1)S加1;
(2)若相加结果大于零,则进程继续执行;
(3)若相加结果小于等于零,则从该信号的等待队列中唤醒一个等待进程,然后再返回原进程继续执行或转入进程调度。
信号量的使用特点使其更适用于对Socket(套接字)程序中线程的同步。例如,网络上的HTTP服务器要对同一时间内访问同一页面的用户数加以限制,这时可以为没一个用户对服务器的页面请求设置一个线程,而页面则是待保护的共享资源,通过使用信号量对线程的同步作用可以确保在任一时刻无论有多少用户对某一页面进行访问,只有不大于设定的最大用户数目的线程能够进行访问,而其他的访问企图则被挂起,只有在有用户退出对此页面的访问后才有可能进入。
总结:
1.互斥量与临界区的作用非常相似,但互斥量是可以命名的,也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多,所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建,就可以通过名字打开它。
2.互斥量(Mutex),信号灯(Semaphore)都可以被跨越进程使用来进行同步数据操作,而其他的对象与数据同步操作无关,但对于进程和线程来讲,如果进程和线程在运行状态则为无信号状态,在退出后为有信号状态。
3.通过互斥量可以指定资源被独占的方式使用,但如果有下面一种情况通过互斥量就无法处理,比如现在一位用户购买了一份三个并发访问许可的数据库系统,可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作,这时候如果利用互斥量就没有办法完成这个要求,信号灯对象可以说是一种资源计数器。

 | 240 views | 0 comments | 0 flags | 

【转】函数式思维和函数式编程

http://www.linuxeden.com/html/news/20140905/155374.html

作为一个对Hashell语言[1]彻头彻尾的新手,当第一次看到一个用这种语言编写的快速排序算法的优雅例子时,我立即对这种语言发生了浓厚的兴趣。下面就是这个例子:

quicksort :: Ord a => [a] -> [a]  
quicksort [] = []  
quicksort (p:xs) =  
    (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

我很困惑。如此的简单和漂亮,能是正确的吗?的确,这种写法并不是“完全正确”的最优快速排序实现。但是,我在这里并不想深入探讨性能上的问题 [2]。我想重点强调的是,纯函数式编程是一种思维上的改变,是一种完全不同的编程思维模式和方法,就相当于你要重新开始学习另外一种编程方式。

首先,让我先定义一个问题,然后用函数式的方式解决它。我们要做的基本上就是按升序排序一个数组。为了完成这个任务,我使用曾经改变了我们这个世界的快速排序算法[3],下面是它几个基本的排序规则:

  • 如果数组只有一个元素,返回这个数组
  • 多于一个元素时,随机选择一个基点元素P,把数组分成两组。使得第一组中的元素全部 <p,第二组中的全部元素 >p。然后对这两组数据递归的使用这种算法。

那么,如何用函数式的方式思考、函数式的方式编程实现?在这里,我将模拟同一个程序员的两个内心的对话,这两个内心的想法很不一样,一个使用命令式 的编程思维模式,这是这个程序员从最初学习编码就形成的思维模式。而第二个内心做了一些思想上的改造,清洗掉了所有以前形成的偏见:用函数式的方式思考。事实上,这程序员就是我,现在正在写这篇文章的我。你将会看到两个完全不同的我。没有半点假话。

让我们在这个简单例子上跟Java进行比较:

public class Quicksort  {  
  private int[] numbers;
  private int number;
  public void sort(int[] values) {
    if (values == null || values.length == 0){
      return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
  }
  private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];
    while (i <= j) {
      while (numbers[i] < pivot) {
        i++;
      }
      while (numbers[j] > pivot) {
        j--;
      }
      if (i <= j) {
        swap(i, j);
        i++;
        j--;
      }
    }
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
  }
  private void swap(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
  }
}

哇塞。到处都是ij,这是干嘛呢?为什么Java代码跟Haskell代码比较起来如此的长?这就好像是30年前拿C语言和汇编语言进行比较!从某种角度看,这是同量级的差异。[4]

让我们俩继续两个”我”之间的对话。

JAVA:

好 ,我先开始定义Java程序需要的数据结构。一个类,里面含有一些属性来保存状态。我觉得应该使用一个整数数组作为主要数据对象,针对这个数组进行排序。还有一个方法叫做sort,它有一个参数,是用来传入两个整数做成的数组,sort方法就是用来对这两个数进行排序。

public class Quicksort {  
    private int[] numbers;
    public void sort(int[] values) {
    }
}

HASKELL:

好,这里不需要状态,不需要属性。我需要定义一个函数,用它来把一个list转变成另一个list。这两个list有相同 之处,它们都包含一样的元素,并有各自的顺序。我如何用统一的形式描述这两个list?啊哈!typeclass….我需要一个typeclass来实现 这个…对,Ord.

quicksort :: Ord a => [a] -> [a]

JAVA:

我要从简单的开始,如果是空数组,如果数组是空的,我应该返回这个数组。但是…该死的,当这个数组是null时,程序会崩溃。让我来在sort方法开始的地方加一个if语句,预防这种事情。

if (values.length == 0 || values == null) {  
    return;
}

HASKELL:

先简单的,一个空list。对于这种情况,需要使用模式匹配。我看看如何使用,好的,非常棒!

quicksort [] = []

JAVA:

好的,现在让我用递归来处理正常的情况。正常的情况下,需要记录sort方法参数状态。需要它的长度,所以,我还需要在Quicksort类里添加一个新属性。

public void sort(int[] values) {  
    if (values.length == 0 || values == null) {
        return;
    }
    this.numbers = values;
    this.length = values.length;
    quicksort(0, length - 1);
}

HASKELL:

这已经是递归了。不需要在再做任何事情。

No code. Nothing. Nada. That's good.

JAVA:

现在,我需要根据上面说明的规则实现快速排序的过程。我选择第一个元素作为基点元素,这不需要使用其它奇异方法。比较,递归。每次比较从两头同时遍历,一个从头至尾(i, 生成<p的list),一个从尾至头(j, 生成>p的list)。每次在i方向遍历中发现有比j方向遍历的当前值大时,交互它们的位置。当i的位置超过j时,停止比较,对形成的两个新队列继续递归调用。

private void quicksort(int low, int high) {  
    int i = low, j = high;
    int pivot = numbers[low];
    while (i <= j) {
        while (numbers[i] < pivot) {
           i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(i, j);
            i++;
            j--;
        }
    }
    if (low < j)
        quicksort(low, j);
    if (i < high)
        quicksort(i, high);
}

交换位置的方法:

private void swap(int i, int j) {  
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

使用Haskell

我先定义一个lesser和一个greater作为每次迭代的两个队列。等一下!我们可以使用标准的headtail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用!

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

非常好,这里我声明了lessergreater两个list,现在我将要用where——Haskell语言里一个十分强大的用来描述函数内部值(not 变量)的关键字——描述它们。我需要使用filter函数,因为我们已经得到除首元素之外的其它元素,我们可以调用(xs),就是这样:

    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

我试图用最详细的语言解释Java里用迭代+递归实现快速排序。但是,如果在java代码里,我们少写了一个i++,我们弄错了一个while循环条件,会怎样?好吧,这是一个相对简单的算法。但我们可以想象一下,如果我们整天写这样的代码,整天面对这样的程序,或者这个排序只是一个非常复杂的算法的第一步,将会出现什么情况。当然,它是可以用的,但难免会产生潜在的、内部的bug。

现在我们看一下关于状态的这些语句。如果出于某些原因,这个数组是空的,变成了null,当我们调用这个Java版的快速排序方法时会出现什么情况?还有性能上的同步执行问题,如果16个线程想同时访问Quicksort方法会怎样?我们就要需要监控它们,或者让每个线程拥有一个实例。越来越乱。

最终归结到编译器的问题。编译器应该足够聪明,能够“猜”出应该怎样做,怎样去优化[5]。程序员不应该去思考如何索引,如何处理数组。程序员应该 思考数据本身,如何按要求变换数据。也许你会认为函数式编程给思考算法和处理数据增添的复杂,但事实上不是这样。是编程界普遍流行的命令式编程的思维阻碍 了我们。

事实上,你完全没必要放弃使用你喜爱的命令式编程语言而改用Haskell编程。Haskell语言有其自身的缺陷[6]。只要你能够接受函数式编程思维,你就能写出更好的Java代码。你通过学习函数式编程能变成一个更优秀的程序员。

看看下面的这种Java代码?

public List<Comparable> sort(List<Comparable> elements) {  
    if (elements.size() == 0return elements;
    Stream<Comparable> lesser = elements.stream()
    .filter(x -> x.compareTo(pivot) < 0)
    .collect(Collectors.toList());
    Stream<Comparable> greater = elements.stream()
    .filter(x -> x.compareTo(pivot) >= 0)
    .collect(Collectors.toList());
    List<Comparable> sorted = new ArrayList<Comparable>();
    sorted.addAll(quicksort(lesser));
    sorted.add(pivot);
    sorted.addAll(quicksort(greater));
    return sorted;
}

是不是跟Haskell代码很相似?没错,也许你现在使用的Java版本无法正确的运行它,这里使用了lambda函数,Java8中引入的一种非常酷的语法[7]。看到没有,函数式语法不仅能让一个程序员变得更优秀,也会让一种编程语言更优秀。 :)

函数式编程是一种编程语言向更高抽象阶段发展的自然进化结果。就跟我们认为用C语言开发Web应用十分低效一样,这些年来,我们也认为命令式编程语言也是如此。使用这些语言是程序员在开发时间上的折中选择。为什么很多初创公司会选择Ruby开发他们的应用,而不是使用C++?因为它们能使开发周期更短。不要误会。我们可以把一个程序员跟一个云计算单元对比。一个程序员一小时的时间比一个高性能AWS集群服务器一小时的时间昂贵的多。通过让犯错误更难,让出现bug的几率更少,使用更高的抽象设计,我们能使程序员变得更高效、更具创造性和更有价值。

标注:

[1] Haskell from scratch courtesy of “Learn you a Haskell for Great Good!”

[2] This quicksort in Haskell that I am showing here is not in-place quicksort so it loses one of its properties, which is memory efficiency. The in-place version in Haskell would be more like:

import qualified Data.Vector.Generic as V  
import qualified Data.Vector.Generic.Mutable as M 
qsort :: (V.Vector v a, Ord a) => v a -> v a  
qsort = V.modify go where  
    go xs | M.length xs < 2 return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

Discussion here.

[3] This version of quicksort is simplified for illustration purposes. It’s always good looking at the source. Boldly go and read this piece of History (with a capital H) by C.A.R. Hoare, “Quicksort”.

[4] Taken from http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html

[4] Will we consider uncontrolled state harmful the same way GOTO statement being considered harmful consolidated structured programming?

[5] This wiki has LOTS of architectural information about the amazing Glasgow Haskell Compiler, ghchttps://ghc.haskell.org/trac/ghc/wiki/Commentary

[6] A big question mark over time on functional programming languages has been the ability (or lack thereof) to effectively code User Interfaces. Don’t despair though! There’s this cool new thing called Functional Reactive Programming (FRP). Still performing babysteps, but there are already implementations out there. One that’s gaining lots of momentum is ReactJS/Om/ClojureScript web app stack. Guess that might be a good follow-up post :)

[7] See http://zeroturnaround.com/rebellabs/java-8-explained-applying-lambdas-to-java-collections/

[英文原文:Programming (and thinking) the functional way ]

转自 http://www.vaikan.com/programming-thinking-functional-way/

 | 209 views | 0 comments | 0 flags | 

【转】Go语言并发之美

http://qing.blog.sina.com.cn/2294942122/88ca09aa33002ele.html

简介
        多核处理器越来越普及,那有没有一种简单的办法,能够让我们写的软件释放多核的威力?答案是:Yes。随着Golang, Erlang, Scale等为并发设计的程序语言的兴起,新的并发模式逐渐清晰。正如过程式编程和面向对象一样,一个好的编程模式需要有一个极其简洁的内核,还有在此之上丰富的外延,可以解决现实世界中各种各样的问题。本文以GO语言为例,解释其中内核、外延。
并发模式之内核
        这种并发模式的内核只需要协程和通道就够了。其中协程负责执行代码,通道负责在协程之间传递事件。
Go语言并发之美
        并发编程一直以来都是个非常困难的工作。要想编写一个良好的并发程序,我们不得不了解线程,锁,semaphore,barrier甚至CPU更新高速缓存的方式,而且他们个个都有怪脾气,处处是陷阱。笔者除非万不得以,决不会自己操作这些底层并发元素。一个简洁的并发模式不需要这些复杂的底层元素,只需协程和通道就够了。
        协程是轻量级的线程。在过程式编程中,当调用一个过程的时候,需要等待其执行完才返回。而调用一个协程的时候,不需要等待其执行完,会立即返回。协程十分轻量,Go语言可以在一个进程中执行有数以十万计的协程,依旧保持高性能。而对于普通的平台,一个进程有数千个线程,其CPU会忙于上下文切换,性能急剧下降。随意创建线程可不是一个好主意,但是我们可以大量使用的协程。

        通道是协程之间的数据传输通道。通道可以在众多的协程之间传递数据,具体可以值也可以是个引用。通道有两种使用方式。

·  协程可以试图向通道放入数据,如果通道满了,会挂起协程,直到通道可以为他放入数据为止。

·  协程可以试图向通道索取数据,如果通道没有数据,会挂起协程,直到通道返回数据为止。

如此,通道就可以在传递数据的同时,控制协程的运行。有点像事件驱动,也有点像阻塞队列。这两个概念非常的简单,各个语言平台都会有相应的实现。在Java和C上也各有库可以实现两者。

Go语言并发之美
        只要有协程和通道,就可以优雅的解决并发的问题。不必使用其他和并发有关的概念。那如何用这两把利刃解决各式各样的实际问题呢?
并发模式之外延
        协程相较于线程,可以大量创建。打开这扇门,我们拓展出新的用法,可以做生成器,可以让函数返回“服务”,可以让循环并发执行,还能共享变量。但是出现新的用法的同时,也带来了新的棘手问题,协程也会泄漏,不恰当的使用会影响性能。下面会逐一介绍各种用法和问题。演示的代码用GO语言写成,因为其简洁明了,而且支持全部功能。
生成器
       有的时候,我们需要有一个函数能不断生成数据。比方说这个函数可以读文件,读网络,生成自增长序列,生成随机数。这些行为的特点就是,函数的已知一些变量,如文件路径。然后不断调用,返回新的数据。
Go语言并发之美

下面生成随机数为例,以让我们做一个会并发执行的随机数生成器。

非并发的做法是这样的:

// 函数rand_generator_1 ,返回 int

funcrand_generator_1() int {

return rand.Int()

}

        上面是一个函数,返回一个int。假如rand.Int()这个函数调用需要很长时间等待,那该函数的调用者也会因此而挂起。所以我们可以创建一个协程,专门执行rand.Int()。

// 函数rand_generator_2,返回通道(Channel)

funcrand_generator_2() chan int {

// 创建通道

out := make(chan int)

// 创建协程

go func() {

for {

//向通道内写入数据,如果无人读取会等待

out <- rand.Int()

}

}()

return out

}

funcmain() {

// 生成随机数作为一个服务

rand_service_handler :=rand_generator_2()

// 从服务中读取随机数并打印

fmt.Printf(“%d\n”,<-rand_service_handler)

}

上面的这段函数就可以并发执行了rand.Int()。有一点值得注意到函数的返回可以理解为一个“服务”。但我们需要获取随机数据时候,可以随时向这个服务取用,他已经为我们准备好了相应的数据,无需等待,随要随到。如果我们调用这个服务不是很频繁,一个协程足够满足我们的需求了。但如果我们需要大量访问,怎么办?我们可以用下面介绍的多路复用技术,启动若干生成器,再将其整合成一个大的服务。

调用生成器,可以返回一个“服务”。可以用在持续获取数据的场合。用途很广泛,读取数据,生成ID,甚至定时器。这是一种非常简洁的思路,将程序并发化。

多路复用

多路复用是让一次处理多个队列的技术。Apache使用处理每个连接都需要一个进程,所以其并发性能不是很好。而Nginx使用多路复用的技术,让一个进程处理多个连接,所以并发性能比较好。同样,在协程的场合,多路复用也是需要的,但又有所不同。多路复用可以将若干个相似的小服务整合成一个大服务。

 

Go语言并发之美

 

那么让我们用多路复用技术做一个更高并发的随机数生成器吧。

// 函数rand_generator_3 ,返回通道(Channel)

funcrand_generator_3() chan int {

// 创建两个随机数生成器服务

rand_generator_1 := rand_generator_2()

rand_generator_2 := rand_generator_2()

 

//创建通道

out := make(chan int)

 

//创建协程

go func() {

for {

//读取生成器1中的数据,整合

out <-<-rand_generator_1

}

}()

go func() {

for {

//读取生成器2中的数据,整合

out <-<-rand_generator_2

}

}()

return out

}        上面是使用了多路复用技术的高并发版的随机数生成器。通过整合两个随机数生成器,这个版本的能力是刚才的两倍。虽然协程可以大量创建,但是众多协程还是会争抢输出的通道。Go语言提供了Select关键字来解决,各家也有各家窍门。加大输出通道的缓冲大小是个通用的解决方法。

多路复用技术可以用来整合多个通道。提升性能和操作的便捷。配合其他的模式使用有很大的威力。

Future技术

Future是一个很有用的技术,我们常常使用Future来操作线程。我们可以在使用线程的时候,可以创建一个线程,返回Future,之后可以通过它等待结果。  但是在协程环境下的Future可以更加彻底,输入参数同样可以是Future的。

 

Go语言并发之美

 

调用一个函数的时候,往往是参数已经准备好了。调用协程的时候也同样如此。但是如果我们将传入的参数设为通道,这样我们就可以在不准备好参数的情况下调用函数。这样的设计可以提供很大的自由度和并发度。函数调用和函数参数准备这两个过程可以完全解耦。下面举一个用该技术访问数据库的例子。

//一个查询结构体

typequery struct {

//参数Channel

sql chan string

//结果Channel

result chan string

}

//执行Query

funcexecQuery(q query) {

//启动协程

go func() {

//获取输入

sql := <-q.sql

//访问数据库,输出结果通道

q.result <- “get” + sql

}()

}

funcmain() {

//初始化Query

q :=

query{make(chan string, 1),make(chan string, 1)}

//执行Query,注意执行的时候无需准备参数

execQuery(q)

 

//准备参数

q.sql <- “select * fromtable”

//获取结果

fmt.Println(<-q.result)

}

上面利用Future技术,不单让结果在Future获得,参数也是在Future获取。准备好参数后,自动执行。Future和生成器的区别在于,Future返回一个结果,而生成器可以重复调用。还有一个值得注意的地方,就是将参数Channel和结果Channel定义在一个结构体里面作为参数,而不是返回结果Channel。这样做可以增加聚合度,好处就是可以和多路复用技术结合起来使用。

Future技术可以和各个其他技术组合起来用。可以通过多路复用技术,监听多个结果Channel,当有结果后,自动返回。也可以和生成器组合使用,生成器不断生产数据,Future技术逐个处理数据。Future技术自身还可以首尾相连,形成一个并发的pipe filter。这个pipe filter可以用于读写数据流,操作数据流。

Future是一个非常强大的技术手段。可以在调用的时候不关心数据是否准备好,返回值是否计算好的问题。让程序中的组件在准备好数据的时候自动跑起来。

并发循环

循环往往是性能上的热点。如果性能瓶颈出现在CPU上的话,那么九成可能性热点是在一个循环体内部。所以如果能让循环体并发执行,那么性能就会提高很多。

 

Go语言并发之美

 

要并发循环很简单,只有在每个循环体内部启动协程。协程作为循环体可以并发执行。调用启动前设置一个计数器,每一个循环体执行完毕就在计数器上加一个元素,调用完成后通过监听计数器等待循环协程全部完成。

//建立计数器

sem :=make(chan int, N);

//FOR循环体

for i,xi:= range data {

//建立协程

go func (i int, xi float) {

doSomething(i,xi);

//计数

sem <- 0;

} (i, xi);

}

// 等待循环结束

for i := 0; i < N; ++i { <-sem }       上面是一个并发循环例子。通过计数器来等待循环全部完成。如果结合上面提到的Future技术的话,则不必等待。可以等到真正需要的结果的地方,再去检查数据是否完成。

通过并发循环可以提供性能,利用多核,解决CPU热点。正因为协程可以大量创建,才能在循环体中如此使用,如果是使用线程的话,就需要引入线程池之类的东西,防止创建过多线程,而协程则简单的多。

ChainFilter技术

前面提到了Future技术首尾相连,可以形成一个并发的pipe filter。这种方式可以做很多事情,如果每个Filter都由同一个函数组成,还可以有一种简单的办法把他们连起来。

 

Go语言并发之美

 

由于每个Filter协程都可以并发运行,这样的结构非常有利于多核环境。下面是一个例子,用这种模式来产生素数。

// Aconcurrent prime sieve

packagemain

 

// Sendthe sequence 2, 3, 4, … to channel ‘ch’.

funcGenerate(ch chan<- int) {

for i := 2; ; i++ {

ch<- i // Send ‘i’ to channel ‘ch’.

}

}

// Copythe values from channel ‘in’ to channel ‘out’,

//removing those divisible by ‘prime’.

funcFilter(in <-chan int, out chan<- int, prime int) {

for {

i := <-in // Receive valuefrom ‘in’.

if i%prime != 0 {

out <- i // Send’i’ to ‘out’.

}

}

}

// Theprime sieve: Daisy-chain Filter processes.

funcmain() {

ch := make(chan int) // Create a newchannel.

go Generate(ch)      // Launch Generate goroutine.

for i := 0; i < 10; i++ {

prime := <-ch

print(prime, “\n”)

ch1 := make(chan int)

go Filter(ch, ch1, prime)

ch = ch1

}

}

上面的程序创建了10个Filter,每个分别过滤一个素数,所以可以输出前10个素数。

Chain-Filter通过简单的代码创建并发的过滤器链。这种办法还有一个好处,就是每个通道只有两个协程会访问,就不会有激烈的竞争,性能会比较好。

共享变量

        协程之间的通信只能够通过通道。但是我们习惯于共享变量,而且很多时候使用共享变量能让代码更简洁。比如一个Server有两个状态开和关。其他仅仅希望获取或改变其状态,那又该如何做呢。可以将这个变量至于0通道中,并使用一个协程来维护。

 

Go语言并发之美


下面的例子描述如何用这个方式,实现一个共享变量。

//共享变量有一个读通道和一个写通道组成

typesharded_var struct {

reader chan int

writer chan int

}

//共享变量维护协程

funcsharded_var_whachdog(v sharded_var) {

go func() {

//初始值

var value int = 0

for {

//监听读写通道,完成服务

select {

case value =<-v.writer:

case v.reader <-value:

}

}

}()

}

funcmain() {

//初始化,并开始维护协程

v := sharded_var{make(chan int),make(chan int)}

sharded_var_whachdog(v)

//读取初始值

fmt.Println(<-v.reader)

//写入一个值

v.writer <- 1

//读取新写入的值

fmt.Println(<-v.reader)

}

这样,就可以在协程和通道的基础上实现一个协程安全的共享变量了。定义一个写通道,需要更新变量的时候,往里写新的值。再定义一个读通道,需要读的时候,从里面读。通过一个单独的协程来维护这两个通道。保证数据的一致性。

一般来说,协程之间不推荐使用共享变量来交互,但是按照这个办法,在一些场合,使用共享变量也是可取的。很多平台上有较为原生的共享变量支持,到底用那种实现比较好,就见仁见智了。另外利用协程和通道,可以还实现各种常见的并发数据结构,如锁等等,就不一一赘述。

协程泄漏

        协程和内存一样,是系统的资源。对于内存,有自动垃圾回收。但是对于协程,没有相应的回收机制。会不会若干年后,协程普及了,协程泄漏和内存泄漏一样成为程序员永远的痛呢?一般而言,协程执行结束后就会销毁。协程也会占用内存,如果发生协程泄漏,影响和内存泄漏一样严重。轻则拖慢程序,重则压垮机器。

C和C++都是没有自动内存回收的程序设计语言,但只要有良好的编程习惯,就能解决规避问题。对于协程是一样的,只要有好习惯就可以了。

只有两种情况会导致协程无法结束。一种情况是协程想从一个通道读数据,但无人往这个通道写入数据,或许这个通道已经被遗忘了。还有一种情况是程想往一个通道写数据,可是由于无人监听这个通道,该协程将永远无法向下执行。下面分别讨论如何避免这两种情况。

对于协程想从一个通道读数据,但无人往这个通道写入数据这种情况。解决的办法很简单,加入超时机制。对于有不确定会不会返回的情况,必须加入超时,避免出现永久等待。另外不一定要使用定时器才能终止协程。也可以对外暴露一个退出提醒通道。任何其他协程都可以通过该通道来提醒这个协程终止。

Go语言并发之美

        对于协程想往一个通道写数据,但通道阻塞无法写入这种情况。解决的办法也很简单,就是给通道加缓冲。但前提是这个通道只会接收到固定数目的写入。比方说,已知一个通道最多只会接收N次数据,那么就将这个通道的缓冲设置为N。那么该通道将永远不会堵塞,协程自然也不会泄漏。也可以将其缓冲设置为无限,不过这样就要承担内存泄漏的风险了。等协程执行完毕后,这部分通道内存将会失去引用,会被自动垃圾回收掉。

funcnever_leak(ch chan int) {

//初始化timeout,缓冲为1

timeout := make(chan bool, 1)

//启动timeout协程,由于缓存为1,不可能泄露

go func() {

time.Sleep(1 * time.Second)

timeout <- true

}()

//监听通道,由于设有超时,不可能泄露

select {

case <-ch:

// a read from ch hasoccurred

case <-timeout:

// the read from ch has timedout

}

}

上面是个避免泄漏例子。使用超时避免读堵塞,使用缓冲避免写堵塞。

和内存里面的对象一样,对于长期存在的协程,我们不用担心泄漏问题。一是长期存在,二是数量较少。要警惕的只有那些被临时创建的协程,这些协程数量大且生命周期短,往往是在循环中创建的,要应用前面提到的办法,避免泄漏发生。协程也是把双刃剑,如果出问题,不但没能提高程序性能,反而会让程序崩溃。但就像内存一样,同样有泄漏的风险,但越用越溜了。

并发模式之实现

        在并发编程大行其道的今天,对协程和通道的支持成为各个平台比不可少的一部分。虽然各家有各家的叫法,但都能满足协程的基本要求—并发执行和可大量创建。笔者对他们的实现方式总结了一下。

下面列举一些已经支持协程的常见的语言和平台。

Go语言并发之美

        GoLang 和Scala作为最新的语言,一出生就有完善的基于协程并发功能。Erlang最为老资格的并发编程语言,返老还童。其他二线语言则几乎全部在新的版本中加入了协程。

令人惊奇的是C/C++和Java这三个世界上最主流的平台没有在对协程提供语言级别的原生支持。他们都背负着厚重的历史,无法改变,也无需改变。但他们还有其他的办法使用协程。

Java平台有很多方法实现协程:

· 修改虚拟机:对JVM打补丁来实现协程,这样的实现效果好,但是失去了跨平台的好处

· 修改字节码:在编译完成后增强字节码,或者使用新的JVM语言。稍稍增加了编译的难度。

· 使用JNI:在Jar包中使用JNI,这样易于使用,但是不能跨平台。

· 使用线程模拟协程:使协程重量级,完全依赖JVM的线程实现。

其中修改字节码的方式比较常见。因为这样的实现办法,可以平衡性能和移植性。最具代表性的JVM语言Scale就能很好的支持协程并发。流行的Java Actor模型类库akka也是用修改字节码的方式实现的协程。

对于C语言,协程和线程一样。可以使用各种各样的系统调用来实现。协程作为一个比较高级的概念,实现方式实在太多,就不讨论了。比较主流的实现有libpcl, coro,lthread等等。

对于C++,有Boost实现,还有一些其他开源库。还有一门名为μC++语言,在C++基础上提供了并发扩展。

可见这种编程模型在众多的语言平台中已经得到了广泛的支持,不再小众。如果想使用的话,随时可以加到自己的工具箱中。

结语 
        本文探讨了一个极其简洁的并发模型。在只有协程和通道这两个基本元件的情况下。可以提供丰富的功能,解决形形色色实际问题。而且这个模型已经被广泛的实现,成为潮流。相信这种并发模型的功能远远不及此,一定也会有更多更简洁的用法出现。或许未来CPU核心数目将和人脑神经元数目一样多,到那个时候,我们又要重新思考并发模型了。

 | 230 views | 0 comments | 0 flags | 

【转】SOC时钟系统驱动分析

http://heljoy.github.io/linux/2013/01/11/introduce-soc-clock-driver/ 【内容复制时不完整,最好看原文】

本文主要介绍SOC片上时钟系统,对应到SPEC文档时钟部分,并不涉及系统的计时、定时等,这部分内容可参考这篇文章。本文所提到的时钟是SOC片上设备工作的时钟,主要介绍时钟相关概念、硬件、核心时钟系统的结构与驱动、部分动态调频的原理。

时钟是设备工作的脉搏,系统各部件正常的工作离不开合适的时钟。嵌入式平台上为降低系统功耗,部分模块的工作电压与时钟都是可以动态调整,并且可单独关闭某一模块的时钟以节省电源,为屏蔽时钟调整寄存器操作细节,方便时钟状态调整,统一访问接口,三星独立与LINUX时钟驱动,开发了平台相关的驱动程序,这里针对EXYNOS4412平台时钟系统,涉及到驱动框架和实现细节。

时钟相关硬件

时钟是一种有规律的电信号,具有特定的周期、频率,最常见的时钟信号的方波、正弦波等,这个是硬件晶振具有的特性。而系统中各模块工作于不同频率,为每个模块单独配置一个晶振显然不现实,并且有些模块可工作在多种频率模式,因此嵌入式时钟系统常具有动态调整频率功能,具体来说就是多路选择和分频,其时钟系统与树结构类似,拥有一个或几个时钟源,经过PLL电路,使用MUX、DIV器件为各模块提供多种工作频率。

  • PLL:锁相环电路,百度百科上有详细的解释,具体就是有反馈机制的电路,可调整部分参数达到输入与输出动态变化的目的,在SPEC文档上有调整PLL相关的寄存器说明,其中最重要的参数为PMS,确定输出频率与输入频率的关系,并有参数的推荐配置。
  • MUX:多路选择电路,从上行多路时钟选择一路输出,必须有一路输出,不能不选,也是通过寄存器配置。另外MUX分为glitch-free和normal两种,只在时钟切换时有区别。
  • DIV:分频电路,将上行时钟分频处理后输出, 分频参数为整数,所以经过电路的时钟频率为几个离散值
  • GATE:开关电路,截断上行时钟到下行设备的输出,一般针对终端设备,不要关闭下行有多个时钟或设备的时钟

片上设备时钟

一般SOC芯片都需要外部提供一个或几个稳定频率的时钟源,时钟源经过片上时钟管理系统最后提供给片上的设备,这部分的硬件连接图一般没有,但SPEC文档会介绍时钟管理系统对时钟源的处理,片上设备连接到哪个时钟域下(一般不会详细列出每个设备的时钟路线,只会给出哪些设备属于哪个时钟管理),以下给出大概的时钟路线图。

     other clock ----------+                              +----> {GATE} DEVICE0
     other clock --------+ |                              |----> {GATE} DEVICE1
                         V V                              |----> {GATE} DEVICE2
clock_src ------>[PLL] ------->[MUX] ------->[DIV] ------------> {GATE} DEVICE3

时钟源clock_src之后到DEVICE之前都属于时钟管理系统,从时钟源到设备通常会经过多个MUX、DIV器件,具体要结合SPEC文档时钟管理器部分寄存器描述。弄清楚上述关系后就可以直接访问寄存器控制时钟系统,适用于没有操作系统的环境,但linux系统屏蔽了这些硬件细节,为上层驱动提供统一的访问接口,下面具体描述统一接口到寄存器操作的映射关系,这也是时钟驱动框架的核心部分。

系统中时钟的表示

时钟驱动中关键要表达以下几个概念:时钟、时钟源、设置/获取频率等操作。

## arch/arm/plat-samsung/include/plat/clock.h struct clk { struct list_head list; //用这个链接到系统全局时钟链表 struct module *owner; //时钟也是系统中的设备 struct clk *parent; //指向父时钟,用于时钟操作等 const char *name; const char *devname; int id; int usage; //使用计数 unsigned long rate; //频率 unsigned long ctrlbit; //寄存器中第几位用于操作时钟 struct clk_ops *ops; //操作接口,set/get等 int (*enable)(struct clk *, int enable); //使能接口,配合usage使用 struct clk_lookup lookup; //Linux驱动中用于时钟索引相关,暂时没有关注 #if defined(CONFIG_PM_DEBUG) && defined(CONFIG_DEBUG_FS) struct dentry *dent; /* For visible tree hierarchy */ #endif }; 

看了这个结构心里还不会太紧张,成员不多,且大分部类型确定,起作用的也只有几个,唯一一个不明白的就是clk_ops了。

## arch/arm/plat-samsung/include/plat/clock.h struct clk_ops { int (*set_rate)(struct clk *c, unsigned long rate); //设置频率 unsigned long (*get_rate)(struct clk *c); //获取频率 unsigned long (*round_rate)(struct clk *c, unsigned long rate);//获取与给定频率最接近的支持频率 int (*set_parent)(struct clk *c, struct clk *parent);//设置父时钟 struct clk * (*get_parent)(struct clk *c); //获取父时钟 }; 

这个结构也没有我们想像的复杂,需要解释的是时钟是由MUX、DIV等出来的,并不是你设置一个频率,时钟就能以这个频率工作,通过设置MUX、DIV,时钟有一个离散工作频率范围。MUX是多选一的选择器,每个上行时钟都可能成为下行时钟的父时钟,下行时钟与父时钟的频率一致,对于DIV分频器,下行时钟只有一个父时钟,下行时钟与父时钟频率关系由分频器控制。

## arch/arm/plat-samsung/include/plat/clock-clksrc.h struct clksrc_clk { struct clk clk; //也是一个时钟,这个成员还是要的 struct clksrc_sources *sources; //时钟列表 struct clksrc_reg reg_src; //寄存器 struct clksrc_reg reg_src_stat; //寄存器 struct clksrc_reg reg_div; //寄存器 }; struct clksrc_sources { unsigned int nr_sources; struct clk **sources; }; struct clksrc_reg { void __iomem *reg; unsigned short shift; unsigned short size; }; 

时钟源的表示,用来描述MUX、DIV器件这类连接有多个时钟,通过寄存器位控制上下行时钟关系。MUX的sources一般包含多个时钟,寄存器reg_src表示设置哪个为父时钟的寄存器位,DIV不用设置sources,使用reg_div设置分频参数。这里寄存器信息只给出了基地址,偏移量和位宽,位段内包含的信息由SPEC文档解释,一般所有MUX的格式统一,所有DIV的格式也统一,故可以使用上面的抽象。

时钟注册接口

这里分两类注册,一种时钟就是单个模块使用,有些可以关闭,且关闭了不会影响其它模块工作;另一类就是生成上面一类时钟的时钟,由选择器、分频器组成,可以说是生成第一种时钟的时钟,为时钟源,对应到上节中的两个结构。

## arch/arm/plat-samsung/clock.c int s3c24xx_register_clock(struct clk *clk) { if (clk->enable == NULL) clk->enable = clk_null_enable; /* add to the list of available clocks */ /* Quick check to see if this clock has already been registered. */ BUG_ON(clk->list.prev != clk->list.next); spin_lock(&clocks_lock); list_add(&clk->list, &clocks); //添加到全局时钟链表 spin_unlock(&clocks_lock); /* fill up the clk_lookup structure and register it*/ clk->lookup.dev_id = clk->devname; clk->lookup.con_id = clk->name; clk->lookup.clk = clk; clkdev_add(&clk->lookup); //与时钟查找相关 return 0; } 

注册时钟的接口比较简单,把时钟添加到全局时钟链表就可以了,与gpio驱动中gpio_desc数组有类似的作用,相比第二类时钟要复杂一些。

void __init s3c_register_clksrc(struct clksrc_clk *clksrc, int size) { int ret; for (; size > 0; size--, clksrc++) { if (!clksrc->reg_div.reg && !clksrc->reg_src.reg) printk(KERN_ERR "%s: clock %s has no registers set\n", __func__, clksrc->clk.name); /* fill in the default functions */ if (!clksrc->clk.ops) { //选择器、分频器操作寄存器接口 if (!clksrc->reg_div.reg) clksrc->clk.ops = &clksrc_ops_nodiv; else if (!clksrc->reg_src.reg) clksrc->clk.ops = &clksrc_ops_nosrc; else clksrc->clk.ops = &clksrc_ops; } /* setup the clocksource, but do not announce it * as it may be re-set by the setup routines * called after the rest of the clocks have been * registered */ s3c_set_clksrc(clksrc, false); //初始化时钟源 ret = s3c24xx_register_clock(&clksrc->clk); //将时钟源的时钟注册进系统 if (ret < 0) { printk(KERN_ERR "%s: failed to register %s (%d)\n", __func__, clksrc->clk.name, ret); } } } 

注册时钟源要有选择或分频寄存器地址,也就是这个时钟源是可配置的,接口配置时钟源时主要是根据clk_reg设置寄存器,后面应用时再具体介绍。时钟源添加到系统时会进行初始化,这里涉及到寄存器操作。

void __init_or_cpufreq s3c_set_clksrc(struct clksrc_clk *clk, bool announce) { struct clksrc_sources *srcs = clk->sources; u32 mask = bit_mask(clk->reg_src.shift, clk->reg_src.size); u32 clksrc; if (!clk->reg_src.reg) { if (!clk->clk.parent) printk(KERN_ERR "%s: no parent clock specified\n", clk->clk.name); return; } clksrc = __raw_readl(clk->reg_src.reg); //选择器开关状态 clksrc &= mask; clksrc >>= clk->reg_src.shift; if (clksrc > srcs->nr_sources || !srcs->sources[clksrc]) { printk(KERN_ERR "%s: bad source %d\n", clk->clk.name, clksrc); return; } clk->clk.parent = srcs->sources[clksrc]; //设置当前时钟的父结点 if (announce) printk(KERN_INFO "%s: source is %s (%d), rate is %ld\n", clk->clk.name, clk->clk.parent->name, clksrc, clk_get_rate(&clk->clk)); } 

初始化主要是设置时钟的父结点,利用选择器寄存器reg_src,从父结点列表中获取当前为选择器提供时钟的父结点,分频率只有一个父结点。

时钟驱动框架结构

EXYNOS4412平台所有的时钟都从以下几个时钟派生:

  • XRTCXTI:实时钟输入,32.768KHZ,用于实时钟模块
  • XXTI:不知道做什么用的,我们没有使用这个
  • XUSBXTI:USB PHY模块使用,同时也用于系统PLL,24MHZ

主要是使用到了XUSBXTI作为时钟来源,为保证系统工作频率稳定,XUSBXTI分别输入到不同的PLL电路,经常见到的有APLL、EPLL、MPLL、VPLL,其主要针对SOC四大部分,XUSBXTI与PLL经过MUX产生SCLK_XPLL,其中APLL要分频输出SCLK_APLL,具体派生结构如下:

                              |\               +-----------+
xusbxit--+------------------->| | MUX(APLL)    |           |
         |   +--------+       | |------------->| DIV(APLL) |----------->SCLK_APLL
         +-->|  APLL  |------>| |              |           |
         |   +--------+       |/               +-----------+
         |   
         |
         |                    |\
         +------------------->| |  MUX(xPLL)            
         |   +------------+   | |-------------> SCLK_xPLL
         +-->| PLL(E,M,V) |-->| |              
             +------------+   | |
                              |/

上述5个时钟输入源,分别是xusbxit、apll_fout、epll_fout、mpll_fout、vpll_fout,根据上图建立驱动使用的模型:

## arch/arm/plat-s5p/clock.c /* Possible clock sources for APLL Mux */ static struct clk *clk_src_apll_list[] = { [0] = &clk_fin_apll, //输入APLL前的时钟,也就是xusbxit [1] = &clk_fout_apll, //从APLL输出的时钟 }; struct clksrc_sources clk_src_apll = { .sources = clk_src_apll_list, .nr_sources = ARRAY_SIZE(clk_src_apll_list), }; ## arch/arm/mach-exynos/clock-exynos4.c static struct clksrc_clk exynos4_clk_mout_apll = { //这个描述APLL后面的MUX .clk = { .name = "mout_apll", }, .sources = &clk_src_apll, //这个MUX的源时钟列表 .reg_src = { .reg = EXYNOS4_CLKSRC_CPU, .shift = 0, .size = 1 }, //用于控制MUX寄存器位 }; static struct clksrc_clk exynos4_clk_sclk_apll = { //这个描述MUX后面的DIV .clk = { .name = "sclk_apll", .parent = &exynos4_clk_mout_apll.clk, //这个的父结点就是MUX出来的时钟 }, .reg_div = { .reg = EXYNOS4_CLKDIV_CPU, .shift = 24, .size = 3 }, //用于设置分频器寄存器位 }; ## arch/arm/plat-s5p/clock.c /* Possible clock sources for EPLL Mux */ static struct clk *clk_src_epll_list[] = { [0] = &clk_fin_epll, [1] = &clk_fout_epll, }; struct clksrc_sources clk_src_epll = { .sources = clk_src_epll_list, .nr_sources = ARRAY_SIZE(clk_src_epll_list), }; ## arch/arm/mach-exynos/clock-exynos4.c static struct clksrc_clk exynos4_clk_mout_epll = { .clk = { .name = "mout_epll", }, .sources = &clk_src_epll, .reg_src = { .reg = EXYNOS4_CLKSRC_TOP0, .shift = 4, .size = 1 }, }; ... 

上面给出了建立sclk_apll和sclk_epll(mout_epll)时钟模型,其余PLL时钟模型相似。SOC上很多设备使用的时钟都是这几个PLL派生来,结合芯片datasheet,从代码中能清楚看到这种派生关系。

4. 时钟驱动接口实现

对时钟的操作首先都要获取时钟,由get_clk实现,由linux系统clk驱动完成,使用lookup成员,细节不作介绍。获取时钟后就可设置时钟频率或关闭时钟了。

## drivers/clk/clk.c unsigned long clk_get_rate(struct clk *clk) { unsigned long rate; mutex_lock(&prepare_lock); rate = __clk_get_rate(clk); mutex_unlock(&prepare_lock); return rate; } unsigned long __clk_get_rate(struct clk *clk) { unsigned long ret; if (!clk) { ret = -EINVAL; goto out; } ret = clk->rate; if (clk->flags & CLK_IS_ROOT) goto out; if (!clk->parent) ret = -ENODEV; out: return ret; } 

获取时钟频率比较简单,在clk结构中有保存时钟频率。设置频率的接口要复杂得多,如果操作的为DIV,根据父时钟频率调整分频参数,找出一个与目标频率最接近的分频参数即可,如果操作的是MUX,可选的频率集合为父时钟频率集合,查找最接近即可。

## arch/arm/plat-samsung/clock.c int clk_set_rate(struct clk *clk, unsigned long rate) { int ret; unsigned long flags; if (IS_ERR(clk)) return -EINVAL; /* We do not default just do a clk->rate = rate as * the clock may have been made this way by choice. */ WARN_ON(clk->ops == NULL); WARN_ON(clk->ops && clk->ops->set_rate == NULL); if (clk->ops == NULL || clk->ops->set_rate == NULL) return -EINVAL; spin_lock_irqsave(&clocks_lock, flags); trace_clock_set_rate(clk->name, rate, smp_processor_id()); //trace相关,不用关心 ret = (clk->ops->set_rate)(clk, rate); //接口调用 spin_unlock_irqrestore(&clocks_lock, flags); return ret; } 

这里就是调用clk设备的操作接口,第一节介绍注册时赋值。(DIV器件才有改变频率接口,MUX器件才有改变父结点接口,clk设备只有使能接口),时钟操作接口,结合时钟源的定义可关联到具体接口。

static struct clk_ops clksrc_ops = { .set_parent = s3c_setparent_clksrc, .get_parent = s3c_getparent_clksrc, .get_rate = s3c_getrate_clksrc, .set_rate = s3c_setrate_clksrc, .round_rate = s3c_roundrate_clksrc, }; static struct clk_ops clksrc_ops_nodiv = { .set_parent = s3c_setparent_clksrc, .get_parent = s3c_getparent_clksrc, }; static struct clk_ops clksrc_ops_nosrc = { .get_rate = s3c_getrate_clksrc, .set_rate = s3c_setrate_clksrc, .round_rate = s3c_roundrate_clksrc, }; 

改变时钟的频率clk_set_rate接口会调用到s3c_setrate_clksrc。

static int s3c_setrate_clksrc(struct clk *clk, unsigned long rate) { struct clksrc_clk *sclk = to_clksrc(clk); struct clk *parent; void __iomem *reg = sclk->reg_div.reg; unsigned int div; u32 mask = bit_mask(sclk->reg_div.shift, sclk->reg_div.size); u32 val; parent = __clk_get_parent(clk); //获取父结点 rate = clk_round_rate(clk, rate); div = clk_get_rate(parent) / rate; //目标频率与当前父结点频率计算分频参数 if (div > (1 << sclk->reg_div.size)) return -EINVAL; val = __raw_readl(reg); val &= ~mask; val |= (div - 1) << sclk->reg_div.shift; __raw_writel(val, reg); //修改reg_div[shift~shift+size],定义时钟源时设置 return 0; } 

其余接口不再介绍,利用上面的方法,分析datasheet文档,核对移植过程中是否存在问题。

总结

这样基础性质的驱动是系统能正常工作的保证,修改时需要认真核对SPEC文档,在移植前并不是所有的时钟都已经正确,最好是代码与文档对照来看,去掉没有的时钟,添加必须使用的时钟。有时候很多时钟的寄存器从来不会被改动,可以不用添加到系统,但为框架树形结构完整以及查找问题方便,还是建议统一都写上,从clock_tree能完整的掌握系统运行状态。

 | 292 views | 0 comments | 1 flags |