精华内容
下载资源
问答
  • 在看视频时,或者书籍学习时,有什么感想,疑问,可以停下来,记录好,或者有什么理解,什么启示,收获都可以记下来,笔记看不看重要,重要的是记笔记的过程,眼过千遍不如手过一遍. 让学习以理解为主,而不是以记忆为主!  ...
    • 记笔记的过程,写出自己的问题,感想,边看边总结.

      在看视频时,或者书籍学习时,有什么感想,疑问,可以停下来,记录好,或者有什么理解,什么启示,收获都可以记下来,笔记看不看不重要,重要的是记笔记的过程,眼过千遍不如手过一遍.

      让学习以理解为主,而不是以记忆为主!

       

       

      1. 程序为什么需要内存

      程序运行的目的是

      的到一定结果,这个结果可以解决实际需求问题,新问题不断产生,程序也需要不断重新编写.得到不同结果.

       

      计算机就是在计算数据那么 数据 的重要性不言而喻.

       

       

      计算机程序 = 代码 + 数据

       

      代码用来加工数据,改变数据得到我们想要的结果.

       

       

       

      程序 运行的目的:    结果        过程(不在乎结果,主要是过程是否运行,凡是C语言函数返回值是Void的都不在乎结果)

       

      函数:

      int  add( int a, int b)

      {

      return  a + b;

       

      }

       

      void add(int a, int b)

      {

      int c;

      c = a + b;

      printf("c = %d.\n", c);

      }//这个函数的执行重在过程(printf),返回值不重要。

       

      问题 函数的返回问题

       

      计算机程序运行其实就是很多函数的运行,程序的本质就是函数,函数的本质就是加工数据的动作。

       

       

       

      冯诺依曼机构是数据和代码放在一起、

      哈佛结构是数据和代码分开存放

       

      什么是代码:  函数

      什么是数据: 全局变量、局部变量。

       

      S5PV210中运行的linux系统上,运行程序时,应用程序的代码和数据都在DRAM,所以这种机构就是冯诺依曼机构;在单片机中,程序代码放在FlsahNorflash)中,然后程序在Flash原地运行,程序中的数据(全局变量、局部变量)不能放在RAM,这种就叫哈佛结构

       

       

      问题 DRAM 动态内存  ||  SRAM是静态内存

       

       

       

      为什么需要内存?

      内存用来存储可变数据,数据在程序中表现为全局变量、局部变量等(特殊的:gcc中,其实常量也是存储在内存中的)(大部分单片机中,常量是存储在flash中的,也就是代码段),  

       

      问题 GCC编译

      编程的关键几乎在于 内存管理     譬如  数据结构,数据如何组织、算法,为了更优秀的方法来加工数据,既然与数据有关就里离不开内存

       

      那么如何管理内存?

       

      问题在于 写程序时,如何对内存进行管理,尤其是在程序运行时,内存的消耗量,内存对程序来说是一种的资源,

       

      操作系统掌握多有的硬件系统,因为内存很大,所以操作系统把内存分成一个个的页面(一块,4KB),然后以页面为单位管理。再细分到页里里面 以字节为单位管理。

      操作系统管理内存的原理分厂复杂,但是我们不需要了解这些细节。操作系统给我们提供了内存管理的一些接口,我们只需要用API即可管理内存。

      譬如C语言中使用 malloc free 这些接口 管理内存

       

       

      没有操作系统时,其实就是裸机程序,程序需要操作内存,编程者需要自己计算内存使用和安排

       

      从语言角度: 不同语言提供了不同的操作内存的接口。

      譬如汇编 根本没有任何内存管理,内存管理全靠自己,汇编中操作内存时直接使用内存地址譬如0xd0020010),很麻烦;

      譬如C语言中,通过APImalloc free)来访问系统内存

      譬如C++,用new来创建对象(其实就是为对象分配内存),如果此对象用完后忘记Delete,就会造成这个对象的内存不能释放,这就是内存泄露。

       

       

       

       

      1. 位、字节、半字、字的概念和内存位宽

       

      什么是内存?

      从逻辑角度:内存可以随机访问(给一个地址,就可以访问这个内存地址)、并且可以读写(在裸机上可限制读写,但是一般都是可读写的);内存在编程中天然用来存放变量的。一个变量对应内存中的一个单元。

       

      内存位宽

      从硬件角度讲:硬件内存实现本身是有宽度(内存芯片的实际数据总线数)的,也就是说有些内存条是8位的,而有些就是16位的,那么需要强调的是内存芯片之间是可以并联的。

       

      位和字节

       

      内存单元的大小:

      位(1bit

      字节(8bit

      半字(一般是16bit

      字(一般是32bit

       

      bit就是计算机中信息的最基础单元,

       

      字和半字

       

      历史上曾经出现过16位、32位、64位系统三种,

      平台不一样,子和半字的bit定义不一样,这些单位就提有多少bit 是依赖平台的

       

       

       

       

      问题 有没有8位系统

       

       

      1. 内存编址和寻址、内存对齐

      内存编址方法:

       

      内存地址(一个数字)指向一个空间,一对一且永久不变

       

      在程序运行时,计算机中CPU实际只通过内存地址,不需要找到这个空间在哪里?  

      这个设定由硬件设计保证。

       

      关键:内存编址是以字节为单位的

       

      随便给个内存地址,这个内存地址对应的空间的大小是固定的,就是一个字节(8bit

      如果把内存比为一栋大楼,楼里的一个个房间就是一个个内存空间,这个空间是固定大小 8bit

       

      内存和数据类型的关系:

       

      C语言中基本数据类型:  char short int long float double   

       

      int 整形   (整数类型,整个整体现在它和CPU本身的数据位宽是一样的)譬如32位的CPU,整形就是32位,int就是32位(4个字节)的

      数据类型和内存的关系:

      数据类型是用来定义变量的,而这些变量需要存储、运算在内存中。所以数据类型必须和内存相匹配才能获得做好的性能,否则可能不工作或者效率低下。

       

      32位系统中定义变量做好用int,因为这样效率高。原因在于32位的系统本身配合内存等也是32位,这样的硬件配置天生适合定义32位的int类型变量,效率最高。也能定义8位的char类型变量或者16位的short类型变量,但是实际上访问效率不高。

       

      在很多32位环境下,我们实际定义bool类型变量(实际只需要一个bit就够了)都是用int来实现bool的。

       

      譬如   定义  bool b1;时,编译器实际帮我们32的内存来存储这个bool变量b1,编译器这个做实际浪费了31位的内存,但是好处是效率高

       

      问题:省内存和运行效率,二者需具体情况解决。

       

       

      内存对齐

       

      C int a;   定义哟个int 类型变量,在内存中必须分配4个字节来存储这个a  两种方式:

      第一种:0 1 2 3       

      对齐访问

      第二种 1 2 3 4     或者 2 3 4 5 或者 3 4 5 6

      非对齐访问

       

       

      内存的对齐方式不是逻辑的问题,是硬件的问题。 从硬件角度,32位的内存它 0 1 2 3 四个单元本身裸机就有相关性,这四个字节组合起来当做一个int 硬件上就是合适的,效率就高。

       

      对齐访问很配合硬件,所以效率很高;非对齐访问因为硬件本身不搭配,所以效率不高。

       

       

       

      从内存编址看数组的意义

       

      1. C语言如何操作内存

       

       

      C语言对内存地址的封装

      譬如C语言中   int a;   a = 5;  a += 4;       //  a == 9;

       

       

      结合内存来解析C语言语句的本质:

      int a;     // 编译器帮我们申请了 1 int 类型 的内存格子(长度是4 字节。地址只有编译器知道。我们是不知道的,也不需要知道。)并且把符号 a 和这个格子绑定。

       

      a = 5; // 编译器会把 5 放到 a 这个格子

       

      C语言中数据类型的本质含义是: 表示一个内存格子的长度和解析方法。

      数据类型决定长度的含义:以一个内存地址(一个字节的长度单位(固定的))开始,长度是多少,一次往后面延生多少连续长度

      数据类型决定解析方法: 通过内存地址不同的类型指定这个内存地址(包括整个长度)指向的内存单元格子中二进制数的解析方法。

      问题 强制类型转换

       

       

      int   *0;

       

      C语言中,函数就是一段代码的封装。函数名的实质就是这一段代码的首地址。所以说函数名的本质也是一个内存地址。

       

      用指针来间接访问内存

       

      关于类型(不管是普通变量类型int float 等,还是 指针类型int * float * 等),只要记住:

      类型只是对后面数字或者符号(代表的是内存地址)  所表征的内存的一种长度规定和解析方法而已。

       

      C语言中的指针,全名叫指针变量,指针变量其实很普通没有任何区别。譬如 int a int *p 其实没有任何区别,a p 都代表一个内存地址 (譬如是0x20000000,但是这个内存地址(0x20000000)的长度和解析方法不同。a int 型所以a 的长度是4字节,解析方法是按照int 的规定的;pint * 规定的(0x2000000开头的连续4字节中存储了1个地址,这个地址所代表的内存单元中存放的是一个int类型的数)

       

       

      用数组来管理内存

      数组管理内存和变量其实没有本质区别,只是符号的解析方法不同。 (普通变量、数组、指针变量其实都没有本质差别,都是对内存地址的解析,只是解析方法不一样)

      int a;        //编译器分配4字节长度,并且把首地址和符号a绑定起来

      int b[10];  //编译器分配40字节长度,并且把首元素首地址和符号b 绑定起来

      int *c;       //编译器分配4字节长度,并且把首地址和符号c绑定起来,而与c地址绑定的首地址开始,存放了一个地址,地址的内存单元存放的是一个int 类型的数

       

      数组中第一个元素(a[0])就称为首元素;每一个元素类型都是int,所以长度都是4,其中第一个字节的地址

      就称为首地址;首元素a[0]的首地址就称为首元素首地址。

       

       

       

      1. 内存管理之结构体
        1. 数据结构这门学问的意义
          1. 数据结构就是研究数据如何组织(在内存中排布),如何加工的学问
        2. 最简单的数据结构:数组
          1. 为什么要有数组?
            1. 因为程序中有好多个类型相同、意义相关的变量需要管理,这时候需要管理,这时候如果用单独的变量来做程序看起来比较乱,用数组来管理会更好管理。

      譬如: int ages[20];

      1. 数组的优势和缺陷
        1. 优势:数组比较简单,访问用下标,可以随机访问。
        2. 缺陷:
          1. 数组所有元素类型必须相同
          2. 数组的大小必须在定义时给出,而且一旦确定不能再改
      2. 结构体隆重登场
        1. 结构体发明出来就是为了解决数组的第一个缺陷:数组中多有元素类型必须相同

      譬如:我们要管理三个学生的年龄(int 类型),怎么办?

      第一种解法:用数组   int age[3];

      第二种解法:用结构体  

      struct ages

      {

      int age1;

      int age2;

      int gae3;

      };

      struct ages age;

      分析总结:在这个示例中,数组要比结构体好。但是不能得出结论说数组就比结构体好,在包中元素类型不同时就只能用结构体而不能用数组了;

      struct people

      {

      int age;

      char name[20];

      int height;

      };

      struct people people;

      1. 题外话:结构体内嵌指针实现面向对象
        1. 总的来说:C语言是面向过程的,但是C语言写出的linux系统是面向对象的。
        1. 非面向对象的语言,不一定不能实现面向对象的代码。只是说用面向对象的语言来实现面向对象要更加简单一些、直观一些、无脑一些。
        2. C++java等面向对象的语言来实现面向对象简单一些,因为语言本身帮我们做了很多事情;但是用C来实现面向对象很麻烦,看起来也不容易理解,这就是为什么大多数人学过C语言却看不懂linux代码的原因。

      struct s

      {

      int age;                                 //普通变量

      void (*pFunc)(void);          //函数指针,指向void func(void)这类的函数

      }

      这样包含了函数指针的结构体就类似于面向对象的class,结构体中变量类似与class中的成员变量,结构体中的函数指针类似与class中的成员方法

      1. 内存管理之栈
        1. 什么是栈
          1. 栈是一种数据结构,C语言中使用栈来保存局部变量。
          2. 栈是被发明出来管理内存的
        2. 栈管理内存的特点
          1. 先进后出   FILO    first in last out   
          2. 先进先出   FIFO    first in first put    队列
          3. 栈的特点是入口即出口,只有一个口,另一个是堵死的,所以先进去的必须后出来。
        3. 栈的应用举例:局部变量
          1. 我们在C中定义一个局部变量时(int a,编译器会在栈中分配一段空间(4字节)给这个局部变量用(分配时栈顶指针会移动给出空间,给局部变量a用的意思就是,将这4字节的占的内存地址和我们定义的局部变量名a给关联起来 ),对应栈的操作是入栈。
          1. 注意这里栈指针的移动和内存分配是自动(栈自己完成,不用我们写代码去操作)。
          2. 然后等我们函数退出的时候,局部变量要灭亡。对应栈的操作时弹栈(出栈)。出栈时也是栈顶指针移动将栈空间中与a关联的那4个字节空间释放。这个动作也是自动的,也不用人写代码。

      栈的优点:栈管理内存,好处是方便,分配和最后回收都不用程序员操心,C语言自动完成。

      定义局部变量,其实就是在栈中通过移动栈指针来给程序提供一个内存空间和这个局部变量名绑定。因为这段内存空间在栈上,而栈内存是反复使用的(脏的,上次用完没清零的),所以说使用栈来实现的局部变量定义时如果不显示初始化,值就是脏的。如果你显式初始化怎么样?

      C语言是通过一个小手段来实现 局部变量 的初始化的。

      int a = 15;//局部变量定义时初始化

      //C语言编译器会自动把这行转为:

      int a;                 //局部变量定义

      a = 15;                    //普通的赋值语句

      1. 栈的约束(预定栈大小不灵活,怕溢出)
        1. 栈是有大小的,所以栈内存大小不好设置,如果太小怕溢出,太大怕浪费内存。 (这个缺点有点像数组)
        2. 其次,栈的溢出危害很大,一定要避免。所以我们在C语言中定义局部变量时不能定义太多或者太大(譬如不能定义局部变量时int a[10000];使用递归来解决问题时一定要注意递归收敛)      
      1. 内存管理之堆
        1. 什么是堆?
          1. 堆(heap)是一种内存管理方式。 内存管理对操作系统来说是一件非常复杂的事情
            1. 内存容量很大
            2. 内存需求在时间和大小块上没有规律(操作系统上运行着大量的进程随时都会申请或者释放内存,申请或者释放的内存块大小随意)
          2. 内存管理方式特点就是自由(随时申请、释放;大小块随意)。堆内存是操作系统划归给堆管理器(操作系统中的一段代码,属于操作系统中的一段代码,属于操作系统的内存管理单元)来管理的,然后向使用者(用户进程)提供APImalloc free)来使用堆内存
          3. 什么时候使用堆内存?    需要内存容量比较大时,需要反复使用及释放时;很多数据结构(譬如链表,二叉树)的实现都要使用堆内存。
        2. 堆内存的特点
          1. 容量不限,常规使用的需求容量都能满足
          2. 申请及释放都需要手工进行,需要程序员写代码明确进项申请malloc及释放free,如果程序员申请内存并使用后未释放,这段内存就丢失了(在对管理器的记录中,这段内存仍然属于你这个进程,但是进程自己又以为内存已经不用了,再用的时候又回去申请新的内存块,这就叫吃内存),称为内存泄露。在C/C++ 语言中,内存泄露是最严重的程序bug,这也是别人认为Java/C#优秀的地方。
        3. C语言操作堆内存的接口(malloc   free
          1. 堆内存释放时最简单,直接调用free释放即可。    void free(void *ptr)
          2. 堆内存申请时,有3个可选择的类似功能的函数:malloccalloc, realloc
            1. void *malloc(size_t size);
            2. void *calloc(size_t nmemb,size_t size);  //nmemb 个单元,每个单元size 个字节
            3. void *realloc (void *ptr, size_t size);  //改变原来申请的空间的大小的

      譬如要申请10int 元素的内存:

      malloc(40);                    malloc(10*sizeof(int));

      calloc(10,4);                  calloc(10, sizeof(int));

      1. 数组定义时必须同时给出数组元素个数(数组大小),而且一旦定义再无法更改。

      语法技巧可以更改数组大小,但其实这只是一种障眼法。他的工作原理是:先重新创建一个新的数组大小为要更改后的数组,然后将原数组的所有元素复制进新的数组,然后释放原数组,最后返回新的数组给用户;

      堆内存申请时给定大小,然后一旦申请完成大小不变,如果要变只能通过realloc接口(原理与上述语法技巧一致)

      1. 优势与劣势(管理大块内存、灵活、容易内存泄露)

      优势:灵活

      劣势:需要程序员去处理各种细节,所以容易出错,严重依赖程序员的水水平。

      1. 复杂数据结构
        1. 链表、哈希表、二叉树、图等
          1. 链表是最简单且最重要的,链表在linux内核中使用非常多,驱动、应用编程很多时候都需要使用链表。所以对链表必须掌握,掌握到:  会自己定义结构体实现链表、会写链表的节点插入(前插、后插)、节点删除、节点查找、节点遍历等。
          2. 哈希表不是很常用,一般不需要自己学实现,而直接使用别人实现的哈希表比较多。对我们来说最重要的是要明白哈希表的原理、从而知道哈希表的特点,从而知道什么时候该用哈希表,当看到别人用了哈希表的时候要明白别人为什么要用哈希表。合不合适?有没有好的选择?
            1. 哈希表类似于数组,但是在索引节点时是利用某种映射方式的
          3. 二叉树、图等。在嵌入式开发中这些数据结构用的很少很少,且这些数据结构一般用来解决特定问题的。
        2. 为什么需要更复杂的数据结构?
          1. 因为现实中的实际问题是多种多样的,问题的复杂度不同,所以需要解决问题的算法和数据结构也不同。
          2. 所以在处理不同复杂度的问题,就去针对性解决的数据结构和算法
        3. 数据结构和算法的关系
          1. 数据结构的发明都是为了配合一定的算法
          2. 算法是为了处理具体问题,算法的实现依赖于相应的数据结构。
          3. 当前我们所的算法和纯数学是不同的(算法是基于数学的),因为计算机算法要求以数学算法为指导,并且结合计算机本身的特点来改进,最终实现一个在计算机上可以运行的算法(即代码可以表示的算法)。
        4. 应该怎样学习这部分?
          1. 数据结构和算法是相辅相成的,要一起研究。
          2. 数据结构和算法对嵌入式来说不全是重点,不要盲目去研究这个。
          3. 一般在实际应用中实现数据结构和算法的人和使用数据结构和算法的人是分开的。实际中有一部分人的工作就是研究数据结构和算法,并且试图用代码来实现这些算法(表现为库);其他真正做工作的人要做的就是理解明白这些算法和数据结构的意义、优劣、特征,然后在合适的时候选择合适的数据结构和算法来解决自己碰到的实际问题。

      举个例子:linux内核在字符设备驱动管理时,使用了哈希表(hash table,散列表)。所以字符驱动的很多特点都和哈希表的特点有关。

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

       

    展开全文
  • 算法与数据结构入门必看(通俗易懂)

    千次阅读 多人点赞 2019-10-01 19:27:40
    算法与数据结构开篇 你真的会数据结构吗? 公司开发一个客服电话系统,小菜需要完成客户排队模块的开发,经过三次修改: 第一次:小菜使用了数据库设计了一张客户排队表,并且设置了一个自动增长的整型id字段,来...

    算法与数据结构开篇

    你真的会数据结构吗?

    公司开发一个客服电话系统,小菜需要完成客户排队模块的开发,经过三次修改:

    第一次:小菜使用了数据库设计了一张客户排队表,并且设置了一个自动增长的整型id字段,来一个用户,就在这张表的末尾插入一条数据,等客服系统一空闲,就将表中最前的的客户提交,然后删除这条记录。

    • 实时排队模块,在内存中实现即可,无序用数据库

    第二次:小菜用数组变量重新实现了这个功能,害怕数组不够大,选择远大于实际情况的100作为数组长度

    • 数组虽然可以满足一定需求,但是需要考虑溢出问题,以及新增和删除后的数据移动,显然不是很方便

    第三次:小菜使用了数据结构中的 “队列结构” 终于满足了需求

    说明:此例子归纳参考自《大话数据结构》

    为什么你的程序比别人的慢?(算法问题)

    来看一个问题:

    公元前五世纪,我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?请设计一个“高效”的算法求解。

    也就是说:

    买一只公鸡要五文,买一只母鸡要三文,而一文可以买三只小鸡,共有100文,问公鸡母鸡小鸡各能买几只?

    话不多说,我们先给出一种最容易想到的方式,也就是列两个三元方程组

    也就是满足鸡的总数为100,同时花钱数也为100,我们来看一下代码实现

    方式一:

    //i j k 分别代表公鸡 母鸡 雏鸡的数量 
    //20、34、300 为100元最多能买公鸡、母鸡、小鸡的数量
    for (int i = 0; i < 20; i++) {
    	for (int j = 0; j < 34; j++) {
    		for (int k = 0; k < 300; k = k + 3) { //k = k + 3 是为了满足小鸡实际存在的要求
    			if (5*i + 3*j +  k/3 == 100 && i + j + k == 100) {
    				cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl;
    			}
    		}
    	}
    }
    

    我们用了三层循环,有没有办法能简化以下代码呢?能不能减少循环层数呢?这显然是可行的,上面小鸡的数量这一层明显可以省略的,因为总数是已知的

    方式二

    for (int i = 0; i < 20; i++) {
    	for (int j = 0; j < 34; j++) {
    			
    		k_temp = 100 - i - j;
    			
    		if (k_temp % 3 == 0)
    			k = k_temp;
    		
    		if (5*i + 3*j +  k/3 == 100 && i + j + k == 100) {
    			cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl;
    		}
    	}
    }
    

    确实程序更加优化了一些,但是这样是不是就可以了呢?其实还可以优化为一层循环!

    方式三

    int i, j, k, t;
    for (int t = 0; t <= 25/7; t++) {
    	i = 4 * t;
    	j = 25 - 7 * t;
    	k = 75 + 3 * t;
    	cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl; 
    } 
    

    上例中对程序的优化涉及到了数学的运算

    //根据花钱的总数为100列式
    5x + 3y + (100 - x - y)/3 = 100
    
    //对上式进行化简
    y = 25 -(7/4)x
      = 25 - 2x + x/4
        
    //设 x/4 = t,原式子可变为
    y = 25 - 7t
        
    //可以得到三个不等式
    x = 4t >= 0
    y = 25 - 7t >= 0
    z = 75 + 3t >= 0
    
    //解得
    t >= 0
    t <= 25/7
    

    为了增加说服力,我们测试每一个程序的运算时间,不太熟悉的朋友我下面已经贴出了代码

    #include<ctime>
    clock_t startTime,endTime;
    startTime = clock();
    
    ......测试代码
    
    endTime = clock();
    cout << "The run time is: " << (double) (endTime - startTime) / CLOCKS_PER_SEC << "s" << endl; 
    

    我们将数据放大一些,方便体现差异,我们将总金额和总数量均改为1000 下面是三种方式的运算时间

    The run time is: 0.114s
    The run time is: 0.03s
    The run time is: 0.026s
    

    很显然程序逐步的到了优化,减少了for循环 大大的减少了循环次数,所以节省了时间

    ##为什么要一起学习数据结构和算法?

    想要回答这个问题,我们先开看一下数据结构和算法的概念

    数据结构概念

    数据结构是指相互之间存在一种或多种特定关系数据元素的集合

    也就是说,计算机在对数据进行存储的时候并不是杂乱无序的而是拥有一定规则的,一个或多个数据元素之间拥有一定的相互关系,所以也可以说数据结构是计算机存储和组织数据的方式

    算法的概念

    算法是一种可以被计算机使用来解决问题的的方法,这种方法也正是解决问题的具体步骤

    对于小型的程序而言,即使这个算法比较差劲,解决问题的步骤比较累赘繁琐,也不会有很大的关系,只要能解决问题的就是好程序,但是如果对于数据量较大的中大型程序,我们就需要对方法的时间和空间进行有效的利用,也就是设计一个高效的算法,在同样硬件设备的情况下,有时候甚至可以将速度提高十倍甚至百倍

    程序 = 数据结构 + 算法

    数据结构是对计算机所存储的数据之间的一种组织管理,算法是对数据进行操作从而将你解决问题的方法在计算机中具体实现,也就是说,在计算机中而言,其实这两者单独拿出来讨论是没有什么实际意义的,就像鱼离不开水一样,即使一个优秀的算法,如果数据之间没有任何结构关系可言,算法也就无从实现,也就没有意义了,而即使数据之间有了组织关系,但是不对其进行操作这显然也没有意义。

    简单总结:只有数据结构的程序是没有灵魂的,只有算法的程序却只有魂魄,没有躯体

    不可否认,数据结构是非常重要的,但我更加倾向于算法为核心,正如 Algorithms(4th.Edition) 中的观点,数据结构是算法的副产品或者结果,在我看来,如何建立一个有效且高效的算法以及模型是更重要一些的,开发的最终目的就是通过程序利用科技设备实现我们实际生活中的一些需求,我们遇到问题的第一步都是在现实中对问题进行分析,然后设计出合适的方法,然后就要想办法将这种方法表达给计算机设备,但是这个时候就需要数据结构这样一种满足需要的产物,来支持我们对我们的设备具体表达我们的方法,尤其随着数据量的检验,不同的算法就会对解决实际问题的效率产生更大的影响,我用一个不是很恰当却很形象的例子表达就是:你的身体(数据结构)死了,你可能还活着,但你的灵魂(算法)死了,你即使活着也已经死了

    当然数据结构的重要性也是不容置疑的,一个好的数据结构,可以帮助我们的程序更加高效,如果什么时候,模型以及算法的选用已经可以根据数据的特点以及需求选用,我们就可以将更多的精力投入到数据结构的设计中去,不过这也仅仅是一种美好的假想,所以我们还是要学好算法,但是学好算法,我们也就要对支持我们算法的数据结构进行一定的研究

    说了一些个人的观点,那让我们赶紧介绍一些入门的必备知识

    数据结构的基本概念和术语

    • 数据:描述客观事物的数字和符号,是能够被计算机识别且进行处理的的符号集合

      • 整型和实数型数据是可以直接进行数值计算的

      • 文字、图像、图形、声音、视频等多媒体信息则可以通过合适的编码保存处理

        例如:文本通过字符编码处理、声音通过储存波形 (WAV) 或在波形分解后存储其振幅特性然后压缩 (MP3)

    • 数据元素:组成数据且有意义的的基本单位 (个体)

      • 例如:猫和狗都是动物群体中的一个数据元素
    • 数据项:组成数据元素具有特定意义的最小不可分割单位

    • 作为人这个类群中具体的个体,一个人而言,其所拥有的手、脚、眼、鼻,亦或者姓名、年龄、身高、等都属于数据项

    • 数据对象:性质相同的数据元素的集合,是数据的子集

      • 例如:人类中一些人的生日、身高相同

    逻辑结构和物理结构(存储结构)

    逻辑结构

    逻辑结构:数据对象中数据元素之间的相互关系

    集合结构:数据元素之间的唯一关系就是属于同一个集合

    线性结构:数据元素之间存在一对一的关系(除首尾元素均存在前驱和后继)

    树形结构:数据元素之间存在一对多的关系

    图形结构:数据元素之间存在多对多的关系

    • (每一个数据元素看做一个节点,元素之间的逻辑关系用连线表示,如果关系有方向则连线带箭头)

    物理结构(存储结构)

    物理结构:数据的逻辑结构关系在计算机中的存储形式

    顺序存储结构:把元素分别放在地址连续的存储单元中的存储方式

    • 也就是说:元素一个一个有序的排好队,各自占据一定的空间,例如定义一个含有6个浮点型数据的数组:然后内存中的一块大小为6个浮点型数据大小空间就会被计算机所开辟,然后数据存入时,依次顺序摆入

    链式存储结构:把元素存储在任意的存储单元中的存储方式

    • 因为数据元素位置不确定,所以需要通过指针指向到元素的存储地址,从而确定不同数据元素之间的位置

    • 举例:200人同时在一个阶梯教室上课,同学们坐的位置是没有关系的,老师点名签到的时候,你只需要关注你学号前一位的同学有没有被点到,点到后,你就知道下一个该你了

    散列 (哈希) 存储方式:是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术

    • 你别慌,我这就来解释了,它的原理就是,将一个节点的关键字key作为自变量,通过一个确定的函数运算f(key),其函数值作为节点的存储地址,将节点存入到指定的位置上,查找的时候,被搜索的关键字会再次通过f(key)函数计算地址,然后读取对应数据

    • 我们后面会专篇讲解这个内容,现在做一个简单的了解即可

    索引存储方式:存储时,除了存储节点,还附加建立了索引表来表示节点的地址

    算法的特征

    • 输入:算法具有零个或者多个输入(零个的情况例如打印输出字符串,或者算法自身已经给定了初始条件)

    • 输出:算法具有一个或者多个输出,用来反映算法对输入数据加工后的结果

    • 有穷性:算法必须在执行有限个步骤后终止

      • “有限” 的定义不是绝对的,而是实际应用中合理的可接受的
    • 确定性: 算法的每一步骤都具有确定的含义,不会出现二义性

      • 也就是说,唯一的输入只有唯一的输出
    • 可行性:算法的每一步都是可行的,通过有限步骤可以实现

    算法的设计要求

    • 正确性:合理的数据输入下,最终可以输出能解决问题需求的正确答案

      • 对正确的理解:
        • 无语法错误
        • 输入合法和非法的数据均可以得到正确答案
        • 输入刁难的数据依旧可以输出满足需要的答案
    • 可读性:算法便于阅读和理解

      • 算法应该层次分明,易读易懂,方便二次调试和修改

      • 复杂一些的算法,变量的命名尽量恰当一些,用阿里的开发手册中的一句话就是说:“正确的英文拼写和语法可以让阅读者易与理解避免歧义”“为了达到代码自解释的目标,任何自定义编程元素在命名时,使用尽量完整的单词组合来表达其意”

    • 健壮性:当数据不合理的时候,算法也能对各种情况作出处理,而不是报出异常,或者输出错误的答案

    • 高效性:尽量满足时间效率高,存储率低的需求

    函数的渐进增长

    次数算法A :2n + 4算法B :3n + 3算法C :2n算法D :3n
    n = 16623
    n = 28946
    n = 3101269
    n = 1024332030
    n = 100204303200300

    n = 1的时候 算法 A 和 B 的效率一致,但是从n = 2的时候开始算法 A 的效率已经大于算法 B 了,n值变大后,算法 A 相比 B 变的更加快速

    • -所以在n值没有限定的情况下,只要在超过某数值N后,函数值就一直大于另一个函数,那么我们称函数是渐进增长的

      函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的渐近增长快于g(n)

    • 接着我们分别用 AC 、BD进行对照,你会发现其实后面的加数对算法的影响几乎是忽略不计的,所以我们一般选择忽略这些加法常数

    次数算法A :2n + 6算法B :3n² + 3算法C :n算法D :n²
    n = 18611
    n = 2101524
    n = 3123039
    n = 102630310100
    n = 1002063000310010000

    算法 A 和 B 比较的时候,n = 1的时候 B效率更高,从n = 2开始 算法 A 就比较高效,随着数据的输入,体现的越明显,但是我们同时将这两个算法去掉最高次项的系数,接着可以看到对数据的走向仍然影响不大

    • 最高次项的系数对数据走向的影响不大

    • 最高项的指数大的函数,随着n的增长,结果也会快速增长

    • 判断算法效率的时候,应主要关注最高次项,其他次要项或者常数项常常可以忽略

    算法的时间复杂度

    算法的时间复杂度是一个函数 T(n),它定性描述该算法的运行时间,通常用大O表示法,记作:T(n) = O(f(n)) 例如3n² + 2n + 1 的时间复杂度为 O(n²)

    注意:

    • T(n) = O(f(n)) 解释:随着n增大算法执行时间的增长率和f(n)的增长率相同,同时也考察输入值大小趋于无穷的情况,也称作算法的渐进时间复杂度

    • 在这个过程中,不考虑函数的低阶项、常数项和最高项系数,

    常见的时间复杂度

    O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)

    实际开发中,我们常见到的还是前几个加粗的

    我们还需要提到两个概念:

    最坏情况平均情况

    最坏情况就是,运行时间的最大值,情况不能再坏了

    平均时间就是

    一般情况下,我们都是指最坏时间复杂度,但平均时间是最有意义的时间,因为它与我们的期望值更接近

    作者的话

    这些文章,当然谈不上算什么有深度的技术,但是我在尽可能的将一些概念通过举例、图表等方式给对这方面知识有需要的朋友,快速的入门,通过一些通俗的说法,先对一些知识有一定的了解,在此基础上,去看一些深入的权威书籍,或者大牛的博文,就会不至于劝退,自知技术有限,但仍然想给一些刚刚接触这部分知识的朋友们一些帮助,总得一个人,经历一些难捱的日子,你才会变得更加强大!

    结尾:

    如果文章中有什么不足,或者错误的地方,欢迎大家留言分享想法,感谢朋友们的支持!

    如果能帮到你的话,那就来关注我吧!如果您更喜欢微信文章的阅读方式,可以关注我的公众号

    在这里的我们素不相识,却都在为了自己的梦而努力 ❤

    一个坚持推送原创Java技术的公众号:理想二旬不止

    展开全文
  • 操作系统中的I/O设备管理

    千次阅读 2020-02-12 16:08:43
    I/O设备即输入/输出设备,是用于计算机系统与人通信或与其他机器通信的所有设备,以及所有外存设备。 1. I/O系统的组成 I/O系统不仅包括各种I/O设备,还包括与设备相连的设备控制器,有些系统还配备了专门用于输入...

    本章节目录

    1. I/O系统的组成

    1.1 I/O系统的结构

    1.1.1 微机I/O系统

    1.1.2 主机I/O系统

    1.2 I/O设备的分类

    1.2.1 按传输速率分类

    1.2.2 按信息交换单位分类

    1.2.3 按设备的共享属性分类

    1.3 设备控制器

    1.3.1 设备控制器的定义

    1.3.2 设备控制器的组成

    1.3.3 设备控制器的功能

    1.4 I/O通道

    2. I/O控制方式

    2.1 轮询控制方式

    2.1.1 轮询控制方式原理

    2.2 中断控制方式

    2.2.1 中断控制方式原理

    2.3 DMA控制方式

    2.3.1 DMA控制器结构

    2.3.2 DMA控制器中的寄存器

    2.3.3 DMA工作原理

    3. 缓冲管理

    3.1 缓冲区的定义

    3.2 缓冲区存在的意义

    3.3 缓冲的引入

    3.4 单缓冲

    3.5 双缓冲

    3.6 循环缓冲

    3.6.1 循环缓冲过程

    3.6.2 缓冲池

    4. 设备分配

    4.1 设备分配中的数据结构

    4.1.1 设备控制表DCT

    4.1.2 控制器控制表COCT

    4.1.3 通道控制表CHCT

    4.1.4 系统设备表SDT

    4.2 设备分配

    4.3 设备独立性

    4.3.1 实现设备独立性的好处

    4.3.2 设备独立软件的功能

    4.4 SPOOLing技术

    4.4.1 SPOOLing技术的定义

    4.4.2 SPOOLing的组成

    4.4.3 应用SPOOLing技术的优点

    5. I/O软件原理

    5.1 设备管理的4个层次

    5.2 设备管理软件的功能

    5.3 中断处理程序的作用

    5.4 设备驱动程序

    5.5 与硬件无关的I/O软件功能

    6. 磁盘管理

    6.1 磁盘结构

    6.2 磁盘调度

    6.3 提高磁盘I/O速度的方法


    I/O设备即输入/输出设备,是用于计算机系统与人通信或与其他机器通信的所有设备,以及所有外存设备。

    1. I/O系统的组成

    I/O系统不仅包括各种I/O设备,还包括与设备相连的设备控制器,有些系统还配备了专门用于输入/输出控制的专用计算机,即通道。此外,I/O系统要通过总线与CPU、内存相连。

    1.1 I/O系统的结构

    分为两大类:微机I/O系统、主机I/O系统

    1.1.1 微机I/O系统

    CPU与内存之间可以直接进行信息交换,但是不能与设备直接进行信息交换,必须经过设备控制器

    1.1.2 主机I/O系统

    主机I/O系统采用四级结构,包括主机、通道、控制器和设备

    一个通道可以控制多个设备控制器

    一个设备控制器也可以控制多个设备

    1.2 I/O设备的分类

    1.2.1 按传输速率分类

    1. 低速设备,鼠标、键盘等

    2. 中速设备,打印机系列

    3. 高速设备,光盘系列

    1.2.2 按信息交换单位分类

    1. 块设备,磁盘,数据的存取以数据块为单位

    2. 字符设备,打印机,传送字节流,不使用块结构

    1.2.3 按设备的共享属性分类

    1. 独占设备,例如打印机,必须作为临界资源以互斥方式访问

    2. 共享设备,例如磁盘,允许多个进程共同访问的设备

    3. 虚拟设备,通过虚拟技术把一台物理设备变成若干逻辑设备

    1.3 设备控制器

    1.3.1 设备控制器的定义

    1. 设备控制器是CPU与I/O设备之间的接口,接收I/O的命令并控制设备完成I/O工作

    2. 设备控制器是一个可编址设备,连接多个设备时可有多个设备地址

    1.3.2 设备控制器的组成

    1. 设备控制器与处理机的接口: 数据线、控制线、地址线

    2. 设备控制器与设备的接口: 接口中3类信号为数据、状态、控制信号

    3. I/O逻辑:主要由指令译码器和地址译码器两部分功能部件构成 将CPU的命令和地址分别译码,控制指定设备进行I/O操作

    1.3.3 设备控制器的功能

    1. 接收和识别命令

    2. 数据交换:通过数据寄存器进行数据交换

    3. 设备状态的了解和报告

    4. 地址识别

    5. 数据缓冲

    6. 差错控制

    1.4 I/O通道

    一种特殊的处理机,它具有执行I/O指令的能力,并通过执行通道程序来控制I/O操作

    引入通道能够使CPU从控制I/O操作的任务中解脱,使CPU与I/O并行工作, 提高CPU利用率和系统吞吐量

    2. I/O控制方式

    分为四种:轮询控制方式、中断控制方式、DMA控制方式、通道控制方式

    2.1 轮询控制方式

    2.1.1 轮询控制方式原理

    主机试图发送I/O控制命令之前,先通过反复检测设备控制器状态寄存器的忙/闲标志位

    若设备“忙”,主机继续检测该标志位

    直到该位为“空闲”,主机发送I/O指令

    缺点:使CPU经常处于循环测试状态,造成CPU的极大浪费,影响整个进程的吞吐量

    2.2 中断控制方式

    现在计算机系统广泛采用中断控制方式完成对I/O控制。

    2.2.1 中断控制方式原理

    1. CPU执行过程中,发出输入/输出请求,若此时I/O设备忙,则进程阻塞等待。

    2. 当处于“忙”状态的设备工作完毕,通过中断控制器发出中断请求信号,CPU响应中断,执行对应该设备的中断处理程序,然后唤醒因等待该设备而被阻塞的进程。

    3. CPU继续执行这个进程时,向设备控制器发送I/O指令,然后CPU被调度程序分配给某个进程,继续执行某个进程。

    4. 本次I/O结束后,设备控制器通过向CPU发送中断请求信号告知CPU本次数据传输结束

    优点:使CPU和I/O设备在某些时间段上并行工作,提高CPU的利用率和系统的吞吐量

    2.3 DMA控制方式

    2.3.1 DMA控制器结构

    DMA控制器的逻辑组成包括3部分:

    DMA与主机的接口、DMA与设备的接口,以及I/O控制逻辑

    2.3.2 DMA控制器中的寄存器

    命令/状态寄存器CR:用于接收从CPU发来的I/O命令或有关控制信息、设备状态

    内存地址寄存器MAR:在输出数据时,存放输出数据在内存的起始地址,指示DMA应该从内存的什么地方读取输出数据;在输入数据时,存放输入数据将要被放入内存的起始地址,指示DMA应该把输入数据放在内存的什么地方

    数据寄存器DR:用于暂存DMA传输中要输入或输出的数据

    数据计数器DC:指示DMA,本次向CPU发中断信号前要读或写数据的次数

    2.3.3 DMA工作原理

    1. 当CPU要从磁盘读入一个数据块时,就向磁盘控制器发送一条读命令。

    2. 该命令被送到DMA的命令寄存器CR中,同时CPU将本次读入数据将要放在内存中的起始地址送DMA的MAR寄存器,将本次要读的字节数送入DC寄存器。

    3. 然后启动DMA控制器进行数据传输,在DMA控制输入过程中,CPU可以执行其他的进程,当本次读入的数据全部传输完毕后,DMA向CPU发送中断请求。

    3. 缓冲管理

    3.1 缓冲区的定义

    缓冲区是用来保存两个设备之间或设备与应用程序之间传输数据的内存区域

    3.2 缓冲区存在的意义

    由于CPU的速度远远高于I/O设备,为了尽可能使CPU与设备并行工作,提高系统的性能,通常需要操作系统在设备管理软件中提供缓冲区管理功能。

    3.3 缓冲的引入

    在数据到达速率与数据离去速率不同的地方,都可以引入缓冲区。

    引入缓冲的主要原因:

    1. 处理数据流的生产者与消费者之间的速度差异

    2. 协调传输数据大小不一致的设备

    引入缓冲的主要作用:

    引入缓冲区除了可以缓和CPU与I/O设备之间速度不匹配的矛盾,还能提高CPU和I/O设备之间的并行性。

    3.4 单缓冲

    最简单的缓冲类型,在主存储器的系统区中只设立一个缓冲区。

    用户进程发出I/O请求时,操作系统为该操作分配一个位于主存的缓冲区。

    3.5 双缓冲

    当一个进程往这一个缓冲区中传送数据(或从这个缓冲区读取数据)时,操作系统正在清空(或填充)另一个缓冲区,这种技术称为双缓冲(Double Buffering),或缓冲交换(Buffering Swapping)

    3.6 循环缓冲

    在数据到达和数据离去的速度差别很大的情况下,需要增加缓冲区的数量。

    看上图,R代表空缓冲区,G代表已装满数据的缓冲区,C代表现行工作缓冲区

    Nextg:用于指示消费者进程下一个可用的装有数据的缓冲区

    Nexti:用于指示生产者进程下一个可用的空缓冲区

    Current:用于指示进程正在使用的工作缓冲区

    3.6.1 循环缓冲过程

    Getbuf过程:

                  1. 消费者进程要使用缓冲区中数据时调用

                  2.生产者进程要使用空缓冲区装数据时调用

    Releasebuf过程:进程使用完缓冲区后,调用Releasebuf过程释放缓冲区

    3.6.2 缓冲池

    公共缓冲池中设置多个可供若干进程共享的缓冲区,提高缓冲区的利用率

    缓冲池的组成:

    缓冲区:空缓冲区、装满输入数据的缓冲区、装满输出数据的缓冲区

    缓冲队列:空缓冲度列、输入队列、输出队列

    工作缓冲区:收容输入数据的缓冲区、提取输入数据的缓冲区、收容输出数据的缓冲区、提取输出数据的缓冲区

    4. 设备分配

    4.1 设备分配中的数据结构

    支持设备分配的数据结构需要记录设备的状态(忙或空闲)、设备类型等基本信息

    4.1.1 设备控制表DCT

    英文全称为Device Control Table。

    系统为每个设备建立一张设备控制表,多台设备控制表构成设备控制表集合。 每张设备控制表包含设备类型、设备标识符、设备状态(忙/闲)等信息。

    4.1.2 控制器控制表COCT

    英文全称为Controller Control Table

    系统为每个控制器设置一张用于记录该控制器信息的控制器控制表,通常包含控制器标识符、控制器状态等信息。

    4.1.3 通道控制表CHCT

    英文全称为Channel Control Table

    系统为每个通道设备设一张通道控制表,通常包含通道标识符、通道状态等信息。

    4.1.4 系统设备表SDT

    英文全称为System Device Table

    记录了系统中全部设备的情况,每个设备占一个表目,其中包括设备类型、设备标识符、设备控制表及设备驱动程序的入口地址。

    4.2 设备分配

    设备分配应考虑以下3个因素:

    1.设备的固有属性:独占性、共享性、可虚拟性

    2. 设备分配算法

    3. 设备分配方式

    设备的三个固有属性:

    1. 独占性:独享分配策略

    2. 共享性:可同时分配给多个进程使用

    3. 可虚拟性:可同时分配给多个进程使用

    设备的分配算法:

    1. 先来先服务:根据进程对某设备提出请求的先后顺序分配

    2. 基于优先权的分配算法:对高优先权进程所提出的I/O请求也赋予高优先权

    设备的分配方式:

    1. 安全分配方式:发出I/O请求后进入阻塞状态,摒弃“请求和保持”条件,是设备分配是安全的

    2. 不安全分配方式:仅当请求的设备被占用,进程才进入阻塞状态,可能具备“请求和保持”条件,从而可能造成死锁

    4.3 设备独立性

    设备独立性意思就是说,应用程序独立于具体使用的物理设备

    应用程序中,使用逻辑设备名称来请求使用某类设备

    系统在实际执行时,必须使用物理设备名称

    4.3.1 实现设备独立性的好处

    1. 应用程序与物理设备无关:系统增减或变更外围设备时不需要修改应用程序

    2. 易于处理输入/输出设备的故障:替换设备不需要修改应用程序

    3. 提高了系统的可靠性,增加了设备分配的灵活性

    4.3.2 设备独立软件的功能

    执行所有设备的公有操作:包括独占设备的分配与回收、将逻辑设备名转换为物理设备名、对设备进行保护等。

    向用户层软件提供统一的接口:向应用软件和最终用户提供简单、统一的访问接口

    4.4 SPOOLing技术

    4.4.1 SPOOLing技术的定义

    英文全称 Simultaneous Peripheral Operations On-Line

    在多道程序环境下,利用一道程序来模拟脱机输入时的外围控制机的功能,把低速I/O设备上的数据传送到高速输出磁盘上,再利用另一道程序来模拟脱机输出时外围控制机的功能,把数据从磁盘传送到低速输出设备上。这种在联机情况下实现的同时外围操作称为SPOOLing。

    4.4.2 SPOOLing的组成

    1. 输入井和输出井

    2. 输入缓冲区和输出缓冲区

    3. 输入进程SPi和输出进程SPo

    4. 请求I/O队列

    4.4.3 应用SPOOLing技术的优点

    1. 提高了I/O速度

    2. 将独占设备改造为共享设备

    3. 实现了虚拟设备功能

    5. I/O软件原理

    输入输出软件的总体目标是将软件组织成一种层次结构

    低层软件用来屏蔽硬件的具体细节

    高层软件则主要是为用户提供一个简洁、规范的界面

    5.1 设备管理的4个层次

    用户层软件:向系统发出I/O请求,显示I/O操作的结果,提供用户与设备的接口

    与设备无关的软件层:完成设备命名、设备分配、设备独立性和缓冲管理等功能

    设备驱动程序:与硬件关系最密切

    中断处理程序(底层)

    5.2 设备管理软件的功能

    1. 实现I/O设备的独立性

    2. 错误处理

    3. 异步传输

    4. 缓冲管理

    5. 设备的分配和释放

    6. 实现I/O控制方式

    5.3 中断处理程序的作用

    I/O中断处理程序的作用是将发出I/O请求而被阻塞的进程唤醒。

    5.4 设备驱动程序

    设备驱动程序是I/O进程与设备控制器之间的通信程序,其主要任务是接受上层软件发来的抽象的I/O请求,如read和write命令,把它们转换为具体要求后,发送给设备控制器启动设备去执行。

    5.5 与硬件无关的I/O软件功能

    1. 设备命名

    2. 设备保护

    3. 提供独立于设备的块大小

    4. 为块设备和字符设备提供必要的缓冲技术

    5. 块设备的存储分配

    6. 分配和释放独立设备

    7. 错误处理

    6. 磁盘管理

    磁盘存储器不仅容量大,存取速度快,而且可以实现随机存取,是存放大量程序和数据的理想设备。

    磁盘管理的重要目标是提高磁盘空间利用率和磁盘访问速度。

    6.1 磁盘结构

    一个物理记录存储在一个扇区上,磁盘存储的物理记录数目是由扇区数、磁道数及磁盘面数决定的。

    磁盘类型:

    1. 固定头磁盘:在每条磁道上都有读写磁头

    2. 活动头磁盘(移动头):每个盘面上仅配有一个磁头

    磁盘的访问时间:

    1. 寻道时间:磁头移动到指定磁道所经历的时间

    2. 旋转延迟时间:指定山区移动到磁头下面所经历的时间

    3. 传输时间:把数据从磁盘读出或向磁盘写入数据时所经历的时间

    6.2 磁盘调度

    磁盘调度的一个重要目标是使磁盘的平均寻道时间最少

    磁盘调度遵循的规则:

    1. 先来先服务原则FCFS,First Come First Served

    2. 最短寻道时间有限SSTF,Shortest Seek Time First

    3. 扫描算法SCAN

    4. 循环扫描算法CSCAN

    5. NStepSCAN和FSCAN调度算法

    6.3 提高磁盘I/O速度的方法

    1. 提前读,减少度数据的时间

    2. 延迟写,减少写磁盘的次数

    3. 优化物理块的分布,减少磁臂移动的距离

    4. 虚拟盘,存放临时文件

    5. 磁盘高速缓存,逻辑上属于磁盘,物理上在内存中

    展开全文
  • 嵌入式系统的数据结构与算法

    千次阅读 2019-01-13 15:07:49
    这里特意区分是数据结构还是算法,两者我把它们作为一个整体进行描述,因为数据结构往往伴随着相关的算法,而算法也往往需要基础数据结构作为支撑。 由于本人处于服务于消费电子产品的SOC芯片产品线,并且比较倾向...

    ? [Github pages] ?

    嵌入式系统也有自己的数据结构与算法,而且还不少。

    本文对嵌入式系统里面所用到的数据结构与算法进行一个简要的介绍,主要是为了对嵌入式领域的数据结构与算法做一个简单的描述总结,非算法原理性描述。这里不特意区分是数据结构还是算法,两者我把它们作为一个整体进行描述,因为数据结构往往伴随着相关的算法,而算法也往往需要基础数据结构作为支撑。

    由于本人处于服务于消费电子产品的SOC芯片产品线,并且比较倾向于编码终端产品(非手机类),它们通常没有非常大量的复杂数据要存储,通常是用作物理世界的信息采集传递接口,不涉及到后端服务器那大量的数据存储、查找等等操作,所以可能说的东西不够全面,也仅仅是针对终端产品开发所涉及到的那些数据结构与算法而言,难免一家之言,有失偏颇。

    本文数据结构与算法不做特意区分,并且内核特指 Linux 内核,SOC 特指 ARM 平台。

    字符串查找类

    像是字符串查找类的算法,常常能够接触到但是并不需要如何如何深究其实现的算法有很多,其最常见的载体函数就是 strcmp/strncmp,strstr,C++ 里面的 find 等等,最常见的命令有 grep、find、sed 等等。其中会涉及到 KMP、BM、Sundy 等字符串匹配算法,抑或是其中的混合,在这里这几种算法的基本实现不需要依赖于非常特殊的数据结构,仅使用「普通」的数组就可以搞定。

    这几种算法是我们会经常在无意识当中使用过,但是嵌入式领域来讲,通常情况下我们很少去关注其内部的具体实现,不是说没有那个意识,有两个理由:一是嵌入式里面没必要去关注这种算法的实现;而是也不一定知道里面有这种算法存在。

    再者,在平时的代码编译与执行过程当中,我们可能会用到一些自己实现的字符串匹配算法,比如要实时的解析一个字符串文件用作程序的配置文件,可能会用到一些 fscanf,strcmp 抑或是自己实现的字符串对比函数。

    其中编译时候最常用的就是一些脚本命令如 grep 等,还有就是 Makefile 里面自带的 make 语法函数,执行的时候通常简单的例程一般就会使用自己实现的字符串匹配(最常见暴力匹配法哈),大点的程序会用到 lua 来解析字符串。

    与字符串有关的数据结构与算法最常接触到的就是暴力匹配、没那么暴力的 RK 算法、KMP 系及其改进与变种,像字典树这种更加高级一点的在搜索引擎里面可以看到,但是嵌入式领域就万万是不怎么常见的,可以说根本就见不到的。

    队列

    队列是目前在用户态编程当中最为常见的一种数据结构了,因为编码、解码系列产品代码里面需要大量的视频数据处理,自然就少不了视频数据的传递,而数据的传递就非常满足先进先出的特性,而且整个代码工程里面大部分数据传递的地方都满足这个特征,也就是常说的「生产者消费者」模型。

    于是软件里面的视频数据传递与管理、消息处理队列、环形缓冲区、命令处理队列、事件分发模块等等都适用于队列这个数据结构,而最常用的组织方式有自行实现的单向链表、内核数据结构中的 list 双向链表。C++ 模板库中的 queue 组织方式就是一种队列结构。

    队列的实现方式有不同的途径,并且队列的使用范围有一定的限定。比如我最常用的队列,在同一个队列实例下,可能会有一个或者多个生产者,但是只有一个消费者,如果要实现多个消费者的一般会创建多个队列实例,减少编码难度。

    说到这里,想象一下如果要一个实例多个消费者要如何实现,消费者可以实时加入,只需要多一个引用计数即可,正常情况下,消费者应该享有完全一致的生产资料,也就是说某一个生产元素只有等到所有的消费者都取用完毕之后其引用计数才能够减为0并被丢弃,还要考虑万一有个消费者挂了,需要有一个超时机制,如果超过某个时间计数没有减为0,就得强行丢弃这个数据。综合考虑在内存没有极度紧张的前提下,还不如多点空间换取更加简单的编码,不易出错,易理解,易维护。

    常见队列模型比如环形缓冲区[参考],通常就会用数组来实现,实现的方式便是不难,不过如果要编写的极致一点的话就参考内核里面的 kfifo 的实现,属于鬼斧神工一类的。其它的类型更加常用内核的 list 双向链表[参考]实现,特点是通用,如果需要使用只需要把 list_head 结构体嵌入到需要管理的结构体里面即可使用,并且双向链表也带来了数据访问的灵活性。还有就是自己实现的特定数据类型的单向链表,不过很不常用。

    栈的结构特点是先进后出,那么在嵌入式系统里面会常用于参数的传递,不仅包括函数的参数传递,还包括一些自定义参数的传递,比如在模块解耦的情况下会使用迪米特法则对参数传递进行设计,在参数的 push 与 pop 过程当中就可能会用得到栈这种数据结构,当然使用队列也未尝不可。

    还有用到栈的地方见于需要使用递归结构的时候,比如内核里面 V4L2 框架的 pipeline 管理中的流开启函数,里面用到了图的广度优先遍历,其中为了避免整个函数的嵌套调用,就使用了栈这种数据结构对 pipeline 节点进行保存,完全符合先进后出的特点。

    其它地方比如函数的栈回溯,比如 gdb 调试时候的函数调用过程回溯,比如函数执行过程中的栈式存储,比如某些 log 系统对函数调用的跟踪也用到栈式存储结构,就比如谷歌的开源日志系统 glog,内核的 oops 也会有栈式存储结构的身影。

    栈的实现更常见与数组结构,使用链表结构实现也可以,但是由于栈这种比较特殊的先进先出的结构,我们不需要对删除与添加的灵活性有太多的要求,所以为了访问的效率与存储空间的适度节省,通常使用数组结构来实现。平时需要自己实现的栈结构的模块并不多。

    图和位图

    图结构常用于表示有着非单一性的、有着多方联系的复杂关系,比如说社交关系这种就属于相对比较复杂的图类型。在嵌入式编程里面由于不怎么涉及到这种复杂的相互关联的结构,所以图这一结构基本上不会出现在平时的编程实现当中去。

    不过在内核里面会用到图结构,其中我了解的有 V4L2 的 pipeline 开启函数,这个函数里面不仅用到了图遍历,还用到了位图(bitmap),还用到了栈,这个函数可以说是很吊了,那个函数的名字叫做media_entity_pipeline_start。这里的图结构是一个单向无权无环图,主要用来表示整个 V4L2 视频输入设备框架下属管理的视频输入硬件模块,比如 CSI、ISP、SENSOR 等等,它们的数据流向是单向的,并且是无环的,因为视频数据流的大体流向始终是从硬件到驱动到用户空间的,中间是不会有回环的操作。

    位图一般用于标记,标记某个对象是否是有效的、存在与否等等,总之被标记的对象只有两种(因为 bit 只有 0 和 1 这两种取值)。而上面说到的函数里面位图是用于标记一个图的端点是否被访问到,访问到就会置 1,否则的话就置0,具体的位图操作在内核的 bitmap.h、bitmap.c 等文件里面有相关描述,也可以直接看内核的 bitmap 相关的文档。

    位图在 buffer 管理的时候也用的上,就比如我最近开发的一个视频处理子模块,里面就用到了一个 unsigned long long (ARM-32 64bit)长度的位图变量,用于存储并标记 buffer 是否正在被使用,以此为基础应用于 buffer 的 push 与 pop 标记。当然一个通用的 bitmap 结构应该是可以自定义长度的。

    位图结构的特点是短小,以及精悍,只使用一个位就可以代替平常一个字节的功能,可想而知,位图这种数据结构就必须使用数组结构来实现,链表想都不要想。位图可以实现一种有序进出的数据标记管理,但是大多数时候用来实现一种无序进出的数据标记管理,常见使用哈希数据结构来实现从数据到位图的索引,升级版的还有布隆过滤器(Bloom Filter)这一类位图应用。

    排序类

    首先最常见的排序的目的是为了索引(筛选)与查找,这几乎是排序的大部分需求,一种是排序出来之后方便找到极值,比如淘宝购物的按时间顺序排序或者按照金额顺序排序,这是为了满足我们主观的筛选等需求。还有的是排序是为了更快的拿到想要的值,也就是方便查找,比如搜索引擎,比如数据库,比如内核里面的进程树。

    需要注意的是,这里指的排序并不是限定与从大到小或者从小到大,只要是满足一定的规则,按照我们的设计去依照一定的顺序规则排列的都算是排序。拿内核里面维护的一个用于调度的进程树来讲,它是用红黑树实现的排序类结构,里面的元素是进程描述符,最左子节点是最急切需要调度的进程。每次新建一个进程或者调度完毕一个进程的时候内核会按照进程的加权执行时间把它重新插入到红黑树里面并保持从小到大的顺序,需要取出的时候就从最左子节点取出,需要删除就从树里面剔除。

    上面的操作涉及到查找(插入与删除)、索取(取最左子节点)这些操作,而红黑树能够把查找的时间复杂度降低到 OlogN。还有其它的有利于查找、插入、删除的数据结构与算法有哈希表、跳表、桶排序、快排等等。其中内核的 V4L2 control 模块[参考]就用到了类似桶排序的概念.

    编解码产品最核心的地方是视频的编码与解码以及相关的处理,比如ISP特效等等,而针对视频的管理来说由于内存的限制,也不可能缓存太多的帧,自然这一部分就用不到排序了,甚至大部分场景下,哈希表都可以完全的被双向链表来代替,效率上完全够用。

    综合来讲,排序类的算法多存在于内核里面,以及我们常用的 sqlite 数据库内部,但是数据库内部是不需要我们自己去实现一个排序函数的,用户可能会用到的排序操作并不多。

    非通用类

    在嵌入式系统里面显得不是非常的“通用”,这里说的通用是指的大众化,广范围,比如内核的 CFS 调度算法,它虽然广泛使用在 Linux 内核里面,但是并没有太多的人需要关注并去实现一个这样的算法,它的应用面没有那么的广,所以我定义为非通用。

    在嵌入式编解码产品中,「同步」是一个非常大的类别,音视频播放时候的同步、音视频采集时候的同步,涉及到同步,那问题就麻烦了,问题麻烦的点在于两个方面:

    1. 物理采集到的音频与视频与其打上时间戳的时间间隔不是非常确定。
    2. 视频对于音频的对应关系不是一对一,而是一对多的。
    3. 音视频采集一旦某一帧同步失败,就必须得丢弃或者主动补齐,并且不能够阻塞下一次采集。

    其实这种音视频采集比解码多了一个物理采集的部分,物理采集可是硬实时,采集不等人的,你错过了这一帧就是错过了,没得后悔的,要说解码还可以有一定的延迟容忍,那么采集是丝毫不跟你讲道理的。音视频虽然涉及到的硬件以及整体的流程比较复杂,但是好歹还有 200ms 的容忍度在,除了音视频的同步之外,还有其它的同步,比如常见的基于陀螺仪的在线实时防抖算法,这个要求就更过分了,要求基本上在几十甚至几毫秒级别的同步(陀螺仪数据与视频帧数据)。

    还有内存分配算法,比如 slab、虚拟内存页管理算法、畸变校正、ISP 特效等等,其中有一些是属于文件系统管理类的,有一些就属于计算机视觉类的了。非通用类的算法在以后的学习总结过程当中不是属于重点,因为我也可能、极大可能没有那么多的精力去研究这些东西,更多的是关注现在已经总结出来的,比较通用的数据结构与算法。

    End

    本文只对嵌入式涉及到的数据结构与算法做一个简单的概述,必然有其局限性,不过我觉得无伤大雅。之后的学习过程中会更多的关注不限于嵌入式领域的算法,包括计算机科学里面一些比较通用的算法以及思想,拓展思维与界限。下一篇文章不出意外应该会是从队列开始,应该不止有一篇文章来描述队列,因为这个在嵌入式领域有着广泛的应用,所以有可能会实现一些实用性的工具模块,从中去领会队列的应用精髓。

    打算尽量结合一些切实可用的代码一起总结学习,其实这个之前已经有在做了。如果你看到这里了,我在 github 上面搭建了一个仓库,叫做 Newbie-C,顾名思义就是用 C 来写的,目前仅有个大体的框架,内容仅有一个环形缓冲区的模块实现,还待慢慢添加完善,所以这里就不放链接了。

    如果有同学有心去找着看下,也欢迎往上提交一些自己的代码,不过我还是会尽量靠自己去完善它的,我还得把那个编译模块完善一下,不然目前编译起来还是挺麻烦的,每次都是得全局编译。下面是本文的一些参考文章,其实还是自己写的啦,进去看下吧。是时候开启一个新的篇目了。

    ?????

    [返回]环形缓冲区可以参考这篇文章:环形缓冲区
    [返回]list 双向链表可以参考这篇文章:C语言之list_head双向链表
    [返回]类似桶排序的概念可以参考这篇文章:V4L2框架-control的数据结构


    想做的事情就去做吧
    展开全文
  • 数据存储层所涉及的主要数据结构为逻辑数据记录、逻辑块、逻辑存取路径。 存取层的任务主要包括: 提供一次一个元组的查找、插入、删除、修改的等基本操作。 提供元组查找所循的存取路径以及对存取路径的维护操...
  • 设备管理

    千次阅读 多人点赞 2021-04-29 00:54:11
    设备管理
  • 数据结构--树

    万次阅读 2020-06-09 18:06:55
    二叉树:每个节点最多有两个子树结构 完全二叉树、平衡二叉树、排序二叉树 满二叉树:除了叶节点(最后一层),每个节点都有两个子树 完全二叉树:在满二叉树的基础上,最后一层,从左到右排序,排节点(排满) 树的两...
  • 深入理解操作系统原理之设备管理

    千次阅读 2017-07-03 11:30:28
    设备管理是指计算机系统对除CPU和内存以外的所有输入、输出设备的管理。设备管理不但要管理实际I/O操作的设备(如磁盘机、打印机),还要管理诸如设备控制器、DMA控制器、中断控制器、I/O处理机(通道)等支持设备。...
  • 第1章 数据结构基础 结构之美无处不在 说到结构,任何一件事物都有自己的结构,就如可以看得见且触摸得到的课桌、椅子,还有看不见却也存在的分子、原子。...试想一下,管理大量数据是否也需要数据结构呢?
  •   前面聊过内存的表示由 node -&... page ,聊聊 page 结构。 内核把物理页作为内存管理的基本单位. 尽管处理器的最小可寻址单位通常是字, 但是, 内存管理单元MMU通常以页为单位进行处理. 因此,从虚拟内存的上...
  • 进程相关的数据结构

    千次阅读 2016-05-11 21:56:25
    这些正是进程描述符的作用——进程描述符都是task_struct数据结构,它的字段包含了与一个进程相关的所有信息。因为进程描述符存放了那么多的信息,所以它是相当复杂滴。。。。不过别怕,我们解决主要矛盾,其他
  • 文章目录4.1 设备管理概述4.2 输入输出系统4.2.2 输入输出系统的控制方式4.3 设备分配与回收4.4 设备处理与I/O软件 4.1 设备管理概述 一、设备管理基本功能 外设管理:是指计算机系统中除了CPU和内存以外的所有...
  • 产品数据管理(PDM)技术概述

    千次阅读 2018-11-02 15:47:44
    1产品数据管理系统(PDM)发展及现状   1.1PDM技术的基本概念及产生的背景   产品数据管理(PDM)是以软件技术为基础,以产品为核心,实现对产品相关的数据、过程、资源一体化集成管理的技术。PDM明确定位为面向...
  • Linux设备驱动之IIO子系统——IIO框架及IIO数据结构由于需要对ADC进行驱动设计,因此学习了一下Linux驱动的IIO子系统。本文翻译自《Linux Device Drivers Development 》--John Madieu,本人水平有限,若有错误请...
  • 2019工程伦理慕课答案(2019秋)习题及期末答案

    万次阅读 多人点赞 2019-11-08 18:19:53
    下列哪一项不是工程与技术的区别 内容和性质 目的 活动主体 任务、对象和思维方式 单选题 (1/1 point) 下列哪一项不是工程活动的特征 自主性 创造性 社会性 确定性 多选题 (1points) ...
  • 此字段应包含devicetree数据结构的总大小(以字节为单位)。这个大小应包含所有结构的各个部分:标题,内存预留块,结构块和字符串块,以及任何块之间或最终块之后的自由空间间隙。 off_dt_struct 该字段应包含...
  • NuttX文件系统学习之关键数据结构设备注册
  • 华中科技大学计算机组成原理慕课答案

    万次阅读 多人点赞 2020-01-26 00:09:18
    计算机系统层次结构中,微程序属于硬件级 2、完整的计算机系统通常包括( A ) A.硬件系统与软件系统 B.运算器、控制器、存储器 C.主机、外部设备 D.主机和应用软件 3、CPU地址线数量与下列哪项指标密切相关...
  • HALCON中的重要数据结构

    千次阅读 2016-08-05 23:29:47
    Halcon中重要的数据结构和概念
  • 数据结构试题

    千次阅读 2009-08-20 08:15:00
    11、以下数据结构不属于线性数据结构的是(C)  A )队列  B )线性表  C )二叉树  D )栈 12、在一刻二叉树上第5层的结点数最多是(B)  A )8  B )16  C )32  D )15 13、下面描述中,...
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    因为Linux与Windows不同,其后台运行着许多进程,所以强制关机可能会导致进程的数据丢失,使系统处于稳定的状态,甚至在有的系统中会损坏硬件设备(硬盘)。在系统关机前使用 shutdown命令,系统管理员会通知所有...
  • linux下,USB四大主要数据结构

    千次阅读 2011-11-28 21:32:46
    USB内核(USB驱动,USBD )处于系统的中心,...它为客户端驱动和主机控制器驱动提供了主要数据结构和接口函数,主要有四类功能:客户端驱动管理,USB设备的配置和管理,主机控制器的管理,协议控制命令集和数
  • VFS之基本数据结构

    千次阅读 2015-12-12 21:04:12
    在Linux系统中,所有的设备、进程都是以文件的形式存在,字符设备、块设备以及这些设备的驱动均要依靠文件系统来实现,设备管理的基础框架也要以来文件系统(sysfs),所以文件系统在Linux操作系统中担任着重大的...
  • 《数据库原理》— 数据库系统概论第五版习题解析

    万次阅读 多人点赞 2017-05-29 14:57:48
    1.试述数据、数据库、数据库系统、数据库管理系统的概念。答: (l)数据(Data):描述事物的符号记录称为数据数据的种类有数字、文字、图形、图像、声音、正文等。数据与其语义是可分的。解析在现代计算机系统...
  • 转载|数据链路层设备有哪些

    千次阅读 2018-11-08 00:19:57
    数据链路层的设备与组件是指那些同时具有物理层和数据链路层功能的设备或组件。数据链路层的设备与组件主要有网卡、网桥和交换机。 数据链路层设备有哪些——网卡  网卡是局域网中提供各种网络设备与网络通信介质...
  • 第四章 图形的表示与数据结构如何在计算机中建立恰当的模型表示不同图形对象。如何组织图形对象的描述数据以使存储这些数据所要的空间最省,检索、处理这些数据的速度较快。基本概念——几何信息与拓扑信息刚体运动...
  • 【数据库学习】数据库总结

    万次阅读 多人点赞 2018-07-26 13:26:41
    1,数据库 1)概念 ...数据库是长期存储在计算机内、有组织的、可共享的大量数据的集合。...常见数据库管理系统有...数据结构化 数据的共享性,冗余度,易扩充 数据独立性高 逻辑数据独立性(logical data...
  • 5G核心网中的数据管理

    千次阅读 2020-03-13 14:48:08
    今天,我们来说说5G核心网中的数据管理相关的内容。 数据管理,说白了就是人类的大脑,存储着人在生存期间的所有信息。数据管理、数据库都是从人类大脑不断发展而来的,是因为随着人类的进化和人的成长,人类大脑...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 139,457
精华内容 55,782
关键字:

以下不属于设备管理数据结构

数据结构 订阅