组织方式思维导图
Linux中有关组织方式的思维导图，包括哈希表、双向循环链表、运行队列、进程的运行队列链表
树图思维导图提供 组织方式思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 组织方式思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：349ebf6634e4ebb2bd79353e8e9c1a76
思维导图大纲
组织方式思维导图思维导图模板大纲
哈希表
进行快速查找的一种有效的组织方式
Linux 利用链地址法来处理冲突的 PID
每一表项是由冲突的 PID 组成的双向链表，这种链表是由 task_struct 结构中的 pidhash_next 和 pidhash_pprev 域实现的，同一链表中 pid 的大小由小到大排列
哈希表 pidhash 中插入和删除一个进程时可以调用 hash_ pid( ) 和 unhash_ pid( )函数
双向循环链表
定义
反映进程创建的顺序
反映进程之间的亲属关系
注意 init_task 的作用
空进程是一个永远不存在的进程，因此用它做链表的头和尾是安全的
进程的双向循环链表是一个临界资源，因此在使用这个宏时一定要加锁，使用完后开锁
运行队列
寻找一个新的进程在 CPU 上运行时，必须只考虑处于可运行状态的进程（即在TASK_RUNNING 状态的进程）
扫描整个进程链表是相当低效的，所以引入了可运行状态进程的双向循环链表，也叫运行队列（runqueue）
运行队列容纳了系统中所有可以运行的进程，它是一个双向循环队列
进程的运行队列链表
该队列通过 task_struct 结构中的两个指针 run_list 链表来维持
“空进程”
是队列的长度
两个特殊的进程
当前进程
当出现某种调度时机引发了进程调度，先前运行着的进程处于什么状态是不可知的，多数情况下处于等待状态，所以这时候 current 是没有意义的，直到调度程序选定某个进程投入运行后，current 才真正指向了当前运行进程
空进程
是个比较特殊的进程，只有系统中没有进程可运行时它才会被执行，Linux 将它看作运行队列的头，当调度程序遍历运行队列，是从 idle_task 开始、至 idle_task 结束的，在调度程序运行过程中，允许队列中加入新出现的可运行进程，新出现的可运行进程插入到队尾，这样的好处是不会影响到调度程序所要遍历的队列成员
idle_task 是运行队列很重要的标志
沪公网安备 31011502019485号
上海工商