敬畏自然绿水青山

Month: February 2025

  • SLAM系列之ORB-SLAM3开源系统代码解析-地图回环及合并检测

    这篇文章将向大家介绍回环和地图合并检测相关实现逻辑，和局部建图器类似，回环检测实现的类为LoopClosing（该类同时也实现了回环矫正和地图合并及矫正，其中矫正和合并的内容将于后续文章介绍），和局部建图器模块一样，该模块也在背景线程中运行，线程运行函数为LoopClosing::run()，为一个随着系统一直运行的while(1)循环。该模块的总体功能是检测地图回环和可能的地图合并，整体地图的维护和所有关键帧的位姿和地图点的全局优化，这篇文章将向大家介绍LoopClosing中的地图回环及合并检测。具体的回环和合并矫正的内容将在下一篇文章中较为详细的分析介绍。 回环检测首先从回环检测队列中取出一个关键帧进行处理，首先调用NewDetectCommonRegions函数来判断当前帧和历史帧是否存在着共同的区域，如果存在，有可能是检测到了回环或者是合并的场景，如果合并条件成立，则调用MergeLocal或MergeLocal2对地图进行合并；如果检测到回环，则进行回环校正。 NewDetectCommonRegions函数的大体逻辑是如果还没有检测到回环或合并发生的次数（mnLoopNumCoincidences，mnMergeNumCoincidences刚开始回环检测或者期间没有检测到匹配候选时重置为0）。回环的检测并不是在当前帧与回环候选关键帧之间的第一次匹配时就直接确认回环存在，而是需要连续几帧都与回环候选帧的匹配度和几何验证通过，才会最终确认回环。其中mnLoopNumCoincidences为检测到回环发生的次数记录，mnLoopNumCoincidences>3说明需要至少连续三帧的匹配才算有效的回环检测，以增加回环检测的鲁棒性，合并状态检测的情形类似。 NewDetectCommonRegions函数首先通过调用KeyFrameDatabase类的DetectNBestCandidates函数根据当前帧和关键帧数据库中关键帧的特征点对应的属性“单词”word形成的“文档”（BOW，bag of words）采用余弦相似度或者TF/IDF为度量标准进行相似性计算找出回环关键帧候选集合和合并关键帧候选集合（在同一个地图的为回环候选关键帧，在不同的地图中的为合并候选关键帧），其中BOW为一个“文档向量”，向量中的每一个元素可以表示特征对应的属性单词是否在该关键帧的在词典中出现，关于BOW的相关实现，可以参考文献[2]中的ORBVocabulary的介绍。 然后两次调用DetectCommonRegionsFromBoW函数分别从候选匹配帧集合中找出是否存在回环或需要合并的匹配关键帧，其基本思想是遍历上一个函数返回的候选的回环候选帧和合并候选帧的集合，将每一个候选和当前关键帧进行匹配相似度计算，并采用Sim3Solver进行几何验证，返回最佳的匹配候选帧，该函数分别调用两次，将最优的匹配结果分别更新到变量mpLoopMatchedKF和mpMergeMatchedKF中去。同时通过计算分别获得mg2oLoopSlw和mg2oMergeSlw变量，这两个变量的求解过程使用到了Sim3Solver算法[1]，该变量的含义为从回环匹配关键帧或合并匹配关键帧到当前关键帧进行Sim(3）变换进行纠正后的位姿。 如果检测到了回环的存在，则调用CorrectLoop函数进行回环矫正，如果检测到了合并状态的存在，则调用MergeLocal或MergeLocal2（有IMU的场景）进行地图的合并并进行位姿和地图点的矫正。具体的回环矫正和地图的合并的方法将在后续专门的博客文章里向大家介绍。 References

  • SLAM系列之ORB-SLAM3开源系统代码解析-局部建图器(LocalMapping)

    本篇文章将向大家介绍局部建图器的代码逻辑，局部建图器的类名为LocalMapping，在独立的背景线程中运行，和主线程的跟踪逻辑之间可以并发执行。局部建图器模块的主要作用是当前处理的关键帧及其邻近关键帧的位姿和地图点的联合优化。 LocalMapping的run函数为线程启动的函数，该函数在启动后一直循环运行，按顺序从现有的尚未处理的关键帧列表中依照时间先后顺序pop出关键帧进行处理(调用函数为ProcessNewKeyFrame)，ProcessNewKeyFrame的处理逻辑大体为：1、从关键帧列表中按时间顺序pop出一帧关键帧进行处理；2、在先前已经进行ORB特征点和特征描述符的基础上计算BOW以用于后面的回环检测，检查和更新地图点的观测关系；3、通过调用UpdateConnections函数更新关键帧的共视图相关属性，如连接的共视帧及其共享地图点等信息，具体解释可以参考文献[1]中的详细介绍。以及在地图中插入关键帧。 MapPointCulling函数对最近加入的地图点（如通过立体视觉加入，或者最近在跟踪的过程中发现的新的地图点）执行地图点清除工作，将发现率较低的点，较长时间未被观测到的等一些质量较低的地图点清除，以保证地图点的质量。 CreateNewMapPoints的功能是：1、通过关键帧找到最佳的邻近的共视关键帧集合；2、当前关键帧和每一个邻近的共视关键帧中的关键点之间进行特征点匹配，并将匹配的但尚未分配地图点的特征点进行三角化测量算法求出新的地图点，并更新地图点和关键帧之间的关联关系等，最后将地图点加入到地图点集合变量mlpRecentAddedMapPoints中。 调用Optimizer::LocalBundleAdjustment进行局部线束调整优化，在优化时，以当前的关键帧及其共视的关键帧作为优化的范围，更新关键帧集合和地图点集合，并采用g2o的基于李代数的Levenberg-Marquardt 算法来联合优化多帧相机位姿和地图点坐标。 通过调用KeyFrameCulling进行冗余关键帧剔除操作，其粗略主线逻辑为：首先根据当前关键帧获取最佳共视邻近关键帧集合；然后对于集合里的每一个关键帧，统计其地图点的观测属性，如果发现超过一定量的地图点都被较多的重复观测到，则定义该关键帧为冗余关键帧，标记该关键帧为无效（SetBadFlag），减少地图中的关键帧数量，简化后续的优化过程。 接下来的步骤中需要判断是否有IMU支持，如果有IMU的场景下，则在系统启动时间（minit的变量）一定范围内对IMU启动两轮惯性标定优化，然后根据设定的时间窗口综合IMU的测量和关键帧数据（关键帧和地图点数据）对地图的尺度进行调整，确保地图的精度。 最后通过调用mpLoopCloser->InsertKeyFrame(mpCurrentKeyFrame)语句，将当前关键帧加入到闭环检测模块中。关于回环和合并检测，可以参考后续相关连载主题详细说明。 References

  • SLAM系列之ORB-SLAM3开源系统代码解析-mono(+imu)tracking

    这篇文章将向大家介绍orbslam3开源系统中的单目（+惯导）跟踪算法模块的实现逻辑分析。 跟踪模块在orbslam3中作为计算频率最高的算法模块，在实现中也作为程序的主线程来运行，其他的模块如局部建图（LocalMapping），回环检测（LoopClosing）以及可视化模块（Viewer）均以其他背景线程来并发运行。跟踪模块的主要作用为相机的运动模型（位姿）的实时跟踪和优化。 跟踪模块作为整个系统的入口，其接收从感知传感器捕获的环境数据，如图像数据，IMU，Lidar等，这里将以单目(+imu)场景，且以跟踪+定位（也有只跟踪的模式）的模式为例来进行分析介绍。 一、接收图像并进行处理的函数调用路径（以mono_euroc的example为例）为mono_euroc.cc文件中的SLAM.TrackMonocular(im,tframe)->system.cc文件中的mpTracker->GrabImageMonocular(imToFeed,timestamp,filename)->tracking.cc文件中的GrabImageMonocular函数将图像先转换成灰度图，然后构建Frame类的对象，最后调用Track()函数进行跟踪。这里对Frame构造数据帧对象做一下补充说明：Frame类支持多态的构造函数以支持多个应用场景，如单目，双目，深度相机等，在构造函数里首先直接在畸变的图像上进行ORB特征点和特征描述符的计算提取，然后对特征点进行去畸变的处理。 二、跟踪过程初始化：跟踪过程先判断当前的跟踪状态，跟踪的状态候选有[NOT_INITIALIZED, LOST, RECENTLY_LOST, OK]，当判断到系统当前跟踪状态还尚未初始化时（状态为NOT_INITIALIZED），则首先进行单目的初始化工作，其实现函数为MonocularInitialization，初始化的状态由mbReadyToInitializate变量来表示，系统启动时为false，其状态的判别和转换的逻辑详见[1]，完整的初始化过程需要两个间隔较短的图像帧且两帧的特征点的数量都超过了设定的阈值。当满足这样的条件时，根据这前后临近的两帧的匹配特征点集合基于对极几何和三角化测量方法（ReconstructWithTwoViews）去初始化相机位姿和地图点坐标，如果成功初始化相机位姿，则调用函数CreateInitialMapMonocular创建初始地图，将初始帧和当前帧作为关键帧加入到当前地图里，同时更新对应的地图点和关键帧之间的关联关系，并进行全局的BA优化以进一步优化相机初始位姿。 三、当跟踪状态为OK时，如果运动模型不可用，则调用TrackReferenceKeyFrame，如果运动模型可用，则先调用TrackWithMotionModel，如果用运动模型跟踪不成功，则回退到用TrackReferenceKeyFrame进行跟踪。其中: (1)、TrackReferenceKeyFrame将当前帧和参考关键帧（临近创建的关键帧）进行特征点匹配（如果匹配的特征点不够，则返回跟踪失败，需要进行重定位），并基于此通过Optimizer的PoseOptimization函数对当前帧进行位姿优化；（2）、TrackWithMotionModel根据运动模型预测当前的相机位姿，并将当前帧和上一帧进行投影搜索，如果匹配点过少，将加大阈值再次将当前帧和上一帧进行投影搜索，满足匹配条件则跟踪成功调用PoseOptimization函数进行优化，否则如果有IMU辅助预测，直接返回true，如果既搜索失败又没有IMU辅助预测，则返回false。TrackReferenceKeyFrame和TrackWithMotionModel分别基于参考关键帧和运动模型对当前帧的特征点进行匹配，并得到和参考关键帧或上一帧所匹配的特征点对应的地图点，Optimizer的PoseOptimization函数主要采用了前面帧得出的地图点世界坐标和对应的当前帧关键点的运动映射所建立的最小化重投影误差模型对相机的位姿和地图点进行联合优化，其具体采用了李代数和g2o的图优化方法，具体的介绍见后续的相关博文。 四、当跟踪的状态为RECENTLY_LOST，如果有IMU，则用IMU进行状态的辅助预测，保持状态为RECENTLY_LOST不变；否则调用Relocalization函数进行重定位，如果重定位成功，则状态转换为OK，否则状态转换为LOST。这里对重定位函数的实现也做一下说明，其主要基于当前帧从地图里查找候选关键帧(调用mpKeyFrameDB->DetectRelocalizationCandidates去检测)，然后基于每个候选帧分别和当前帧进行位姿优化（先采用的MLPnPSolver的优化求解方法，实时速度快，只优化相机位姿，找到匹配较优秀的结果作为初始值，和PoseOptimization相结合去进行进一步的更高精确度的位姿优化，具体的实现逻辑参考[2]。 五、当跟踪的状态为LOST，则重新创建新的地图，开始进入新的跟踪初始化状态。 六、当前帧本身的跟踪任务完成后，接下来需要调用TrackLocalMap对局部地图进行跟踪和相关的位姿和地图点的优化，在上一篇文章里也介绍过，局部地图没有专门的封装类，其主要的信息数据在Tracking类的两个变量中，分别为mvpLocalKeyFrames和mvpLocalMapPoints，在实现内部，其通过UpdateLocalMap函数的调用实现了局部关键帧和局部地图点的更新（只对当前的参考帧的匹配的地图点作为约束，约束量偏少，在更大的局部地图点中去搜索更多的匹配点，从而有更多的地图点加入到重投影误差的计算中来，对当前帧的位姿优化也更加准确），然后通过函数SearchLocalPoints去搜索匹配和当前帧在视锥体范围内的匹配的特征点，并基于这些特征点和地图点以及相机位姿等信息进行相机位姿优化。 七、接下来需要通过函数NeedNewKeyFrame来判断是否需要加入关键帧，根据多种条件，比如时间，比如有足够多的新的“接近点”等等，如果需要创建关键帧则调用CreateNewKeyFrame函数来创建关键帧，并将关键帧插入到局部建图器以便进行局部建图的工作。其中局部建图器的大体作用有：1、从尚未处理的关键帧队列里取出关键帧，对关键帧的地图点相关信息进行更新；2、更新关键帧的共视关键帧的图连接；3、将关键帧加入到地图集的当前地图中。这些具体的内容将会在局部建图器的文章中专门介绍。 问题：TrackLocalMap也是通过地图点和特征点的重投影误差采用的Optimizer的PoseOptimization函数进行的相机位姿和地图点的联合优化，为什么在当前帧的跟踪后面还要加上这个过程，其利用了更多的关键帧搜索地图点，因此优化会更准确些吗?回答：在 跟踪阶段，位姿优化依赖当前帧与前一帧（或参考关键帧）之间的特征点匹配关系，但 TrackLocalMap 可以通过当前帧的地图点去搜索局部的多个共视关键帧，查找更多的匹配的地图点。以从更多的视角来优化进一步提升定位精度和地图精度，使得SLAM系统在面对动态场景或挑战性环境时更加稳健。 References

  • SLAM系列之ORB-SLAM3开源系统代码解析-基本数据结构简介

    感谢读者的关注，近期准备向大家介绍ORB-SLAM3的源码解读，准备主要从基本的数据结构、跟踪模块、局部建图模块、回环检测和回环纠正模块、可视化模块以及系统概览这些主题内容分别向大家介绍。欢迎大家的反馈和意见建议以便纠错和补充更新。 这篇短文将向大家介绍ORBSLAM3的基本关键的数据及相关计算的抽象，具体表现为以下几个有代表性的类， 帧（Frame），图像帧数据结构，是视觉slam中基本的传感器单元数据，在单目场景下，一帧的数据为camera某个时间戳对应的图像数据。帧的类中还包含对图像进行ORBExtractor所获取的特征点，特征描述符以及BOW（bag of words，将特征描述符向量根据k叉树结构的词汇表模型进行遍历搜索获得，便于后面的回环检测算法的需要）。帧的类实现中还包括保存优化后当前帧对应的相机的位姿(mTcw)，在优化的过程中还有关键点对应的地图点（成员mvpMapPoints，见MapPoint部分的介绍），帧中也维护了camera的内参信息，以及如果是双目立体视觉场景，一帧的数据中还包含右侧camera的图像数据，以及对应的特征点等相关数据。 关键帧（KeyFrame），并不是所有的帧都作为关键帧（这里借鉴了视频压缩里类似的概念，由于camera的帧率一般较高，进行局部和全局相机位姿和地图点优化时一般以关键帧的数据为优化对象），在跟踪逻辑里，会检查是否需要将当前帧作为关键帧的逻辑，比如根据时间和跟踪效果等（具体在跟踪逻辑在NeedNewKeyFrame函数里进行的实现[1]）。关键帧主要用于局部地图位姿优化和全局位姿优化，也是构成地图数据的基本单元。keyframe的类实现中也对共视关键帧进行了维护，通过地图点结构就可以得出共视的关键帧，具体的函数实现为UpdateConnections函数，其根据和当前关键帧共视地图点的数量对共视的关键帧进行排序，其中变量mvpOrderedConnectedKeyFrames按和当前关键帧共视的地图点数量的多少将共视关键帧进行排序存放到数组里，mvOrderedWeights存放对应的共视的地图点的权重（数量），mConnectedKeyFrameWeights记录共视关键帧和共视地图点数量的映射关系（以STL中的字典map容器实现）。并根据需要建立关键帧之间的父子关系（父子关键帧通常共享大量的地图点，如果当前关键帧为第一次建立连接且不是地图的初始关键帧则选择排序中的第一个共视关键帧为父关键帧），关键帧按照先后顺序构建成双向的链表，CreateNewKeyFrame的函数里有对这个双向链表进行维护的操作。 关键帧数据库（KeyFrameDatabase），存放了关键帧的集合，并且实现了基于BOW等信息的关键帧查找的一系列方法函数供相关模块使用，比如在回环检测模块，提供了基于根据当前帧查找相似度较大的回环匹配帧候选集合和合并关键帧候选集合等。 地图点（MapPoint），地图点为物理世界中的具体位置点的抽象，包括地图点的世界坐标，观测到该地图点的关键帧集合（mObservations），以及对应的每个关键帧图像中的哪个特征点和该地图点相关联等信息（双目的时候分左右camera的特征点的关联索引）。 地图（Map），地图管理的类里包含了关键帧集合(mspKeyFrames)和地图点的集合(mspMapPoints)[2]，在orbslam3中没有专门的类用来抽象局部地图，局部地图的相关数据的维护和更新体现在tracking模块（代码见tracking.cc)的两个相关的成员变量：局部关键帧（mvpLocalKeyFrames）和局部地图点（mvpLocalMapPoints）中，通过TrackLocalMap()函数根据当前帧进行更新和维护[3]。 地图集(Atlas)，多个地图的集合（mspMaps），地图集会维护多个map，当系统初始化的时候，或者跟踪出现了LOST状态时，一般也会创建新的map，会生成新的地图并加入到地图集中。关于地图的合并，将在回环检测和全局优化的部分做专门介绍。 ORBVocabulary，为ORB特征的词汇表，其结构为一个KD树（k-dimensional tree），基于大量的多样的场景数据（如KITTI，EUROC，TUM RGB-D等）经过层次聚类而生成，这个词典是离线已经构建好的，直接加载使用就可以。 References

  • riscv-xv6中文件系统的设计和实现

    本篇文章将向大家介绍riscv-xv6中的文件系统的设计和实现思路，在操作系统中，文件是一个更宽泛的概念，其包含对多种资源的抽象，如外围交互设备，存储设备以及网络等，这篇文章将简要介绍我们日常使用的狭义的文件系统(file system)的实现机制。 磁盘的物理结构和读写逻辑结构的理解，与硬件物理结构有关的有设备号，磁道，扇区，柱面等，与读写逻辑结构有关的有设备号和块号（blockno），关于磁盘的物理结构和读写逻辑结构以及读写方法可以参考[1]。 缓冲区缓存（buffer cache，在kernel/bio.c中实现）是为磁盘访问提供缓存的实现，可以提高磁盘读写的效率。LRU采用了双向循环链表进行的实现，完整实现思路可以参考[2]，但在riscv-xv6的实现中没有用到哈希函数，而是采用遍历的方式进行的查找，riscv-xv6中的具体的实现参考[3]，当前的head节点为最近访问的节点（哨兵节点），head节点的前驱节点为最久未使用的节点，而后继节点为离当前head最近时间使用过的节点，依此类推。在缓冲区的实现代码中，bget函数用于根据dev和blockno来获取磁盘缓冲区，如果已经在缓存区中缓存，则引用计数加一并用睡眠锁互斥访问；如果在缓冲区中没有，则从LRU中找到离当前最久的未使用的缓冲区并通过睡眠锁实现互斥访问。bread和bwrite是实现磁盘块读写的函数，其中都是基于缓冲区的buf（和磁盘块对应）作为媒介，在riscv-xv6中磁盘块读操作通过函数virtio_disk_rw(b, 0)将磁盘内容读到缓冲区，磁盘块写操作通过virtio_disk_rw(b, 1)函数将缓冲区的内容写到磁盘里，整个磁盘缓冲区以及块读写的实现参考[3]。 inode（索引节点）是 UNIX 文件系统（如 ext4、xfs）中用于描述文件元数据的结构体，它存储了文件的关键信息， inode和dinode结构体中addr数据项用来存放硬盘中具体数据的位置，详细的解释可以参考[4]，整个文件的读写的实现见kernel/fs.c代码文件。在riscv-xv6中，当前运行的活动（active）的inode存放在itable结构里，itable没有实现类似buffer cache这样的LRU访问功能，inode 只有在 ref == 0 时才会被回收，但没有 LRU 淘汰策略。只要 ref > 0，inode 就不会被回收，即使它是最久未使用的 inode。 问题1：inode中的dev和inum和major和minor的关系，dinode中为什么不需要dev和inum？回答可以参考[5]中的结构体的字段的定义作用和对比分析。 问题2：inode加载到内容之后，readi去读取时还是调用到了bread，为什么会这样？回答：inode 是文件在内存中的表示，而 dinode（磁盘上的 inode）是文件在磁盘上的存储形式。它们的结构类似，但 dinode 是存储在磁盘上的，而 inode 是加载到内存中的表示，在dinode数据项的基础之上多了dev和inum以及睡眠锁等。inode 结构不存储文件内容，只包含文件的元信息（例如 size、addrs）。ilock函数会调用bread函数读取inode数据元数据。数据块号 (addrs[]) 是指向实际文件内容的磁盘块，但数据仍然需要 通过调用bread() 读取。inode索引节点以及文件本身数据读写操作实现参考[6]。 问题3：riscv-xv6系统中的文件目录结构组织方法介绍，xv6中文件路径如何和inode关联？回答：riscv-xv6中，文件或目录的结构体数据为dirent，包括名称和inum，inum=0表示目录。在磁盘上，一个目录的inode通过 inode->addrs 指向其数据块，而数据块的内容就是多个dirent 结构体的数组。该数组的每一项表示目录下的文件或子目录。整个文件系统中超级块保存了文件系统的结构，具体信息参考[7]。 问题4：riscv-xv6中读文件的过程中涉及哪些关键函数的调用路径，关键函数的实现机制是怎样的？回答：可以简要概括为sys_read->fileread->readi->bread等，其中sys_read为系统调用的入口，fileread为sys_read判断当前为读文件操作后调用的函数，readi为读取indoe节点的文件数据，其中首先会通过ilock函数实现inode节点的读取（如果inode节点不在内存，也需要通过bread从磁盘读取dinode数据到inode节点里），然后通过inode节点中的addr信息去调用bread函数读取文件的具体数据块内容。 问题5：sys_open打开文件如何实现文件名到inode的映射，具体调用了哪些关键函数路径？回答：主要通过namei，namex，dirlookup等关键函数实现文件路径到inode的映射，会调用iget从itable中获取inode节点。sys_read只读取已经打开的file结构体文件，ilock的作用表现在同一路径的文件被多个进程加载，实现数据的互斥访问(并且如果dinode没有加载，则通过bread等函数实现从磁盘加载对应的dinode数据到inode结构体中)。更多关于文件读写的相关说明见[8]。 References

  • riscv-xv6的进程调度实现分析

    本篇文章将向大家介绍一下riscv-xv6的进程调度的实现分析。 riscv-xv6进程调度发生的时机：xv6中进程为单线程的，进程是调度的单位。xv6采用的是抢占式时间片轮转（Round Robin）调度，分时系统的时间片到达或与硬件交互过程中需要等待从而阻塞当前进程(如read系统调用将当前进程的状态设为睡眠)让出cpu时需要调度在等待队列中的进程； 进程调度中的几个关键函数：2、scheduler，进程调度器，每个cpu共享这个调度器代码，但有独立运行的调度器，其内部会从进程表里循环遍历查找状态为”RUNNABLE”的进程并调用sched函数进行调度运行(不同CPU对应的调度器通过锁机制实现进程的安全访问)，调度器内部执行的swtch函数，此时swtch首先保存cpu里的context状态，也就是当前运行的scheduler的cpu环境上下文，并加载马上在cpu上运行的进程的context上下文到cpu寄存器里。2、调度器外部执行的sched，在sched函数实现内部调用了swtch函数，该函数为当前的进程保存上下文（当前进程准备让出cpu执行，将ra,sp以及cpu的callee registers的寄存器状态保存到进程的结构体的context数据里），并加载cpu结构体数据里的context到cpu的寄存器里（cpu结构体里的context为scheduler函数上次调度进程执行时的上下文环境，从而恢复scheduler调度器的执行上下文，开始进程调度）。sched函数会在几个地方被调用:(1)，进程退出，exit函数执行，调度可执行的进程开始运行；（2），进程阻塞到睡眠状态，调度其他进程执行；(3)，当分时的定时器中断到来，发生trap时，kerneltrap和usertrap里通过调用yield函数让出当前进程的cpu执行权限（当前进程从RUNNING的状态更新为RUNNABLE的状态，即ready的可调度状态）。 关于sleep和wakeup的分析：1、sleep发生的可能的场合，硬件中断，如读写操作（异步交互通信，以及硬件共享时的竞态条件需要用到的睡眠锁等），需要阻塞进程异步等待消息准备好；2、sleep系统调用，让当前进程等待大约多少时间（可以以tickes的count为参数，可以参考实验[2]）；3、wait系统调用，父进程会调用sleep等待子进程结束。wakeup被调用的时候基本为当阻塞的进程满足继续运行的条件，如硬件输入输出相关信息到达，包括定时器时间中断到达（定时器时间中断到达除了会唤醒相关进程到RUNNALBLE状态外，也会调用yield函数调度其他进程开始运行）。相关函数的实现可参考[3]

  • riscv-xv6中的锁机制

    本篇文章主要介绍riscv-xv6中的锁机制，在riscv-xv6系统中，内核有不少的共享变量，如进程表，物理内存空闲链表，用于console读写的缓冲区等，这些共享变量在多个进程中共享需要互斥进行访问，否则就会出现数据一致性问题。 在riscv-xv6中有两种锁机制，一种为自旋锁（spinlock)，一种为睡眠锁（sleeplock）。下面分别介绍一起其实现的机制原理以及应用的场合。 spinlock的实现: 关于__sync_lock_test_and_set函数和__sync_synchronize函数的实现和详细注释可以参考[1]；用push_off关闭中断可以解决在嵌套调用情况下可能会导致的误开中断的问题[2]。 问答：在锁的获取和释放之间的过程中断为什么要关闭，如果中断不关闭，可能会出现哪些问题？自旋锁的临界区代码可以在不同 CPU 上执行吗？也就是自旋锁中为什么加上cpu结构体的指针？ 回答：这三个问题是spinlock实现中的相互有关联的问题，将做一起回答。中断与特定的cpu相关，如果中断没有关闭，有可能会出现中断导致当前进程被挂起，下次调度运行时自旋锁的临界区代码就可以运行在不同的cpu上，这样可能会带来：（1）、cpu缓存一致性问题带来的性能问题；（2）、进程A已经获取锁并由于中断（如定时器中断）被让出cpu进入等待状态，进程B刚好也要获取锁，但由于锁已经被进程A获取，进程B将阻塞，导致系统处于较为复杂的进程间依赖情况，影响调度性能，有可能会导致死锁；（3）如果临界区在同一个cpu上不间断运行，如果当前 CPU 已持有锁并再次尝试获取，就可以直接报错，防止出现递归锁问题和死锁。（4）在多核系统中，调试并发问题是非常困难的，如果锁结构中存有持有锁的 CPU，那么：可以方便地打印日志，追踪哪个 CPU 在哪个时刻 获取了锁。在出现死锁或资源竞争时，能够快速确定哪个 CPU 或线程导致的问题。 睡眠锁的实现：睡眠锁的使用场景可以参考[3]，sleeplock是阻塞式锁，用于长时间拥有资源的使用权限和持有锁的场景，如文件系统。关于acquiresleep和sleep函数的实现，可以参考[4]中的注释说明。在文件系统的缓冲区缓存的访问中，就调用了acquiresleep来访问缓冲区（如果已经被其他进程锁住，则进入睡眠等待，否则加锁并返回缓冲区，见[5]中的bget函数的实现和注释） References

  • riscv-xv6中进程和设备的交互过程分析

    这篇文章以sh进程为例介绍操作系统中进程和设备交互的过程，涉及traps的流程处理，硬件驱动，进程的阻塞、唤醒和调度等部分的相关知识技能点。 1、在xv6中，设备以一种特殊的文件类型（FD_DEVICE）存在，文件结构体的描述见[2]，其中major成员变量记录设备文件的主设备号，用于区分不同设备。参考[3]以sh程序为例介绍了进程和uart硬件交互的过程。从上述过程的分析来看，硬件中断既可以在用户态触发，也可以在内核态触发。 2、从用户态触发的usertrap和内核态触发的kerneltrap都会调用devintr 函数中进行中断处理实现，具体函数的注释见[6] 3、uart设备是遵循串口协议的双工通信的设备，能实现信息的收发，在xv6系统中uart可以模拟输入的键盘和输出的终端（屏幕）设备。以用户进程等待接收字符串为例，可以参考[3]中的具体的示例的流程处理分析。 问题：在sh这样的程序中[4]，console接收用户键盘输入的字符（进程本身处于阻塞挂起状态[5]），同时也要反馈到显示终端，当用户输入回车时才唤醒进程处于ready等待调度，反馈到终端的过程具体时怎样的？ 回答：consoleintr函数里将接收的字符放入接收缓冲区，同时通过consputc函数将字符发送到终端，uartintr驱动响应函数既能够处理接收缓冲区（如某一个进程等待用户输入），也能够处理发送缓冲区（如另外一个进程程序输出内容到终端）。 References

  • riscv-xv6系统启动过程分析

    riscv-xv6是基于多核的riscv指令架构的教学用操作系统的实现，这篇短文将在已有相关启动流程介绍[1]的基础上补充介绍riscv-xv6。 1、入口_entry的汇编代码见entry.S[2]，_entry的代码会加载在kernel加载到内存的起始位置0x80000000，每个hart(hart 的全称是 Hardware Thread，即硬件线程。在 xv6 操作系统中，hart 通常用于表示一个 CPU 核心)会调用start.c的代码执行。在 xv6 操作系统中，stack0 是一个用作临时工作栈的区域（其为全局变量，在内核的数据区），特别是在内核早期启动阶段，操作系统还没有设置完进程的内核栈时。当设置了分页功能，启动了第一个用户进程后，操作系统的内核将会运行在kstack特定的栈区（不同的进程可以并行运行在不同的进程对应的内核栈区位置）。 2、start.c的代码中相关的知识点：mstatus时machine status register，MSTATUS 寄存器用于存储 CPU 的状态信息，包括当前执行模式和中断状态等信息，其代码及注释参考[3]和[4]。 3、这里主要解释main.c函数的相关处理逻辑。start.c的最后通过调用mret指令，进入main函数[5]，其中kinit函数（代码见kernel/kalloc.c）实现了物理内存的初始化(将从end到PHYSTOP的内存空间按照PAGESIZE大小为单元串接成空闲页链表），kvminit（kernel/vm.c）实现了内核页表的生成和虚拟地址到物理地址的直接映射；kvminithart函数将内核页表地址设置到SATP寄存器从而使能分页功能(turn on paging)；procinit函数初始化进程表（编译时生成在内核的数据区），以及进程表中每一个proc结构中对应的内核栈地址，在 riscv-xv6 或其他类似操作系统中，内核的数据区中的一些结构（例如由 kalloc 管理的内存块列表）是 动态变化的，并且内核的数据区是允许这种变化的。kalloc（内存分配器）管理的内存块列表和其他数据结构，虽然会动态修改数据内容（如指针更新、内存块分配和回收），但是并不需要为这些数据结构的变化分配新的内存空间。因此，内核的数据区的大小可以被认为是固定的，也就是说，数据区的大小在系统启动时就已经确定，并且在运行过程中不会扩展或缩小。trapinit函数初始化计时器相关的自旋锁，在xv6系统中有一个全局变量ticks。trapinithart函数将kernelvec的代码段初始地址赋值给stvec寄存器，以便在内核态能响应中断处理（kerneltrap函数进一步会调用devintr函数），关于文件系统和persistent memory驱动相关的内容，后面的文章将有专门介绍。关于user/initcode和不同cpu核的初始化顺序问题，可以分别参考引文[6]和[7]。初始化过程之后，每一个cpu都将调用scheduler()函数调度进程开始执行。 问答： 1、问题：不同的cpu共享内核页，每个cpu的stvec寄存器共享kernelvec和uservec代码段，由于这些代码没有共享变量，为可重入代码，因此可以方便共享，是可以这么理解对吗 回答：kernelvec和uservec分别为在内核态和用户态发生trap时所需要的处理逻辑，没有共享变量（tramponline.S的uservec和kernelvec.S的kernelvec），每个cpu运行有自己的内核栈kstack和trapframe结构体数据，因此不同的cpu的内核态中断处理和用户态中断处理代码可以共享。 2、问题：每个cpu是不是有其自己的定时器，从定时器的中断处理来看，好像只对0号cpu的定时器中断做了处理？ 回答：是的，选择0号cpu处理时间中断，方便了系统统一的时间计数和进程调度处理，虽然在riscv等芯片实现中每个cpu核有自己的定时器，但操作系统选择在0号cpu上统一处理，方便了集中管理时间和进程调度。在芯片的设计中，cpu的每个核心之间有共享cache，cache的作用在于快速的获取数据，根据存储访问速度来看，cpu访问cache的速度比内存的速度快多个数量级。由于进程调度的出现，同一个进程（线程）可能在不同的cpu上运行，因此cpu共享cache是有必要的，但cache也分级数（尽管每个 CPU 核心有自己的 L1 和 L2 缓存，但它们通常共享 L3 缓存。这意味着在多核系统中，多个 CPU 核心之间可以共享 L3 缓存来加速数据访问。但由于每个 CPU 核心的 L1 和 L2 缓存是独立的，因此数据迁移和缓存一致性依然是一个重要问题。）。不同cpu共享内核的代码，但有其独立运行的内核栈，其逻辑计算相对独立且可以并行执行。 References