Hi there 👋

Welcome to my blog, just enjoy.

Linux 线程模型

用户线程与内核线程 想要理解 Linux 线程模型,首先要明确两个概念:用户线程(User Level Thread)和内核线程(Kernel Level Thread),如下所示: 一个进程内部可以包含多个用户线程,这些用户线程是通过线程库创建的,受线程库调度。同一个进程内部的用户线程共享操作系统为该进程分配的诸如内存、文件、外设等资源。可以这样理解:线程库为开发者提供了一个简单易用的抽象模型,该模型可以方便开发者在其程序内部实现并行操作,提高程序的并发性。比如在开发代码编辑器时,我们可以利用线程库将文字渲染、语法检测(Lint)、自动提示(Auto Suggestion)、代码高亮(Highlight)等功能分配给多个单独的用户线程去执行而不用去考虑如何编排它们内部之间的关系。又由于这些用户线程是在代码编辑器这一进程内部创建的,它们之间可以共享资源,使得实现协作更加简单(如果采用多进程的方式实现功能的拆分,那么进程之间的资源共享、进程间通信等都会产生额外的性能开销,唯一的好处是某一个进程挂掉不会导致整个程序的崩溃,应该根据具体场景采用不同的实现方式)。 内核线程则是由操作系统创建的,受内核级别的调度器调度。对于操作系统而言,其只关心内核线程,也只能感受到内核线程的存在。用户线程对于操作系统而言是透明的,内核级别的调度器依据调度策略将内核线程分配给某个进程,进程内部到底是什么样的操作系统并不知道,而进程内部的用户线程之间的编排关系则是由线程库来调度的,分配给某个进程的内核线程究竟该执行哪段代码(哪个用户线程的代码逻辑)取决于线程库的调度(实际上并没有那么复杂,现实的实现中只需要交给内核调度器来调度即可,因为用户线程和内核线程是一对一映射的关系,内核线程调度器即可单独完成调度工作)。 相比于用户线程,内核线程的实现较为复杂,提供给用户使用的线程库是在内核提供的 API 基础上实现的,线程库的开发者并不需要关心不同处理器架构、不同操作系统之间的区别,只需要实现一个抽象的模型即可,而对于内核开发者而言,其需要做的事情就多得多了。 线程映射模型 线程映射模型是 Linux 线程模型的核心,其解决了该以怎样的方式将内核线程与用户线程联系起来的问题。之所以要将用户线程和内核线程映射起来是因为对于操作系统而言,其只知道内核线程的存在,内核级别的调度器在调度时会将内核线程指派到 CPU 的某个核心上执行,而 CPU 实际去执行的内核线程对应着内存中的哪部分代码则必须由一个相应的用户线程来指明,否则整个系统根本就无法正常运行。也可以这样理解:用户线程实际上只是一个逻辑上的虚拟线程,是为了方便用户实现程序的一种抽象,真正指派给 CPU 去执行的是内核线程,如果内核线程和用户线程之间没有对应的话,CPU 根本就不知道要去干什么。 内核线程和用户线程之间存在三种映射关系,即 1:1 映射、N:1 映射和 M:N 映射。1:1 映射表明对于每个用户线程,都有一个相应的内核线程与其对应。同理,N:1 映射将 N 个用户线程映射到 1 个内核线程上,而这种映射方式实际上是 M:N 映射的一个特例,即将 M 个用户线程映射到 N 个内核线程上。 对于一对一映射而言,每个用户线程都对应着一个内核调度实体。此时实际上只需要一个内核级别的调度器即可完成调度。对于多对一或多对多映射而言,由于将多个用户线程映射到了某些内核线程上,用户线程之间需要进行协调以保证调度的公平性,同样的,对于内核线程而言,如何分配使得绑定在其上的用户线程之间保持协调一致也需要花费大量的工作。 三种映射模型的优缺点是非常明确的,首先一对一模型的实现难度相比于后两者而言简单了不少,但是由于一个用户线程对应一个内核线程,在用户线程较多的情况下会对系统性能造成一定的影响(此时内核线程也较多,内核调度器会频繁进行线程上下文切换导致系统整体性能下降)。多对一映射模型的好处是可以将一个进程内部的多个用户线程映射到同一个内核线程上,避免了用户态和内核态的频繁切换。但是倘若该内核线程由于 I/O 操作等出现了阻塞,则其对应的所有用户线程也会阻塞,降低了系统的并发性。多对多模型则避免了多对一模型的缺点,在某个内核线程阻塞时,用户线程还可以通过其绑定的备选内核线程继续获取到 CPU 资源,但是这种多对多模型要求额外的调度器来协调内核线程与用户线程、用户线程与用户线程之间的关系,增加额外开销的同时也加大了实现难度。 在当前 Linux 的线程模型实现中,采用的是一对一映射模型。至于为何采用一对一模型而不是多对多模型,Linux 社区早有讨论,Red Hat 在 The Native POSIX Thread Library for Linux 这篇文章中分别从设计理念、模型利弊、实际需求与实现难度等角度对采用何种模型以及为何采用一对一映射模型进行了阐述,非常值得一看,这里不再赘述。 内核线程和 CPU 核心之间的关系 我们之前提到,内核级线程调度器为内核线程指派 CPU 核心以执行内存中相应的代码逻辑。现代的 CPU 往往具有多个物理核心,每个物理核心又具有 2 个逻辑核心(超线程技术)。内核线程调度器在调度时首先通过线程调度策略从当前待调度的候选内核线程列表中选取一个内核线程,之后依据 CPU 核心的调度策略,挑选出一个 CPU 核心执行该内核线程对应的用户线程代码段。内核线程和 CPU 核心之间并没有明显的对应关系,二者只在调度时产生关联,不同的实现会有不同的内核线程与 CPU 核心调度策略。...

June 4, 2022 · Huo Haodong

LeetCode 周赛-291

第一题 1 问题描述 给你一个表示某个正整数的字符串 number 和一个字符 digit 。 从 number 中 恰好 移除 一个 等于 digit 的字符后,找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。 示例 1: 输入:number = "123", digit = "3" 输出:"12" 解释:"123" 中只有一个 '3' ,在移除 '3' 之后,结果为 "12" 。 示例 2: 输入:number = "1231", digit = "1" 输出:"231" 解释:可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。 由于 231 > 123 ,返回 "231" 。 示例 3: 输入:number = "551", digit = "5" 输出:"51" 解释:可以从 "551" 中移除第一个或者第二个 '5' 。 两种方案的结果都是 "51" 。 提示:...

May 1, 2022 · Huo Haodong

阿拉伯数字转中文

初步想法 下面是一些将阿拉伯数字转为中文的例子: 0 = 零 10 = 十 1000 = 一千 9527 = 九千五百二十七 10051 = 一万零五十一 111111111 = 一亿一千一百一十一万一千一百一十一 一个最直观的想法就是按照从最低位到最高位的顺序,依次将数字映射为相应的中文字符并加上单位,比如: 0 = 零 10 = 一十零 1000 = 一千零百零十零 10051 = 一万零千零百五十一 110010 = 一十一万零千零百一十零 210010 = 二十一万零千零百一十零 但是这样的转换方法对于“零”的处理并不理想,我们中文的习惯一般是将连续出现的多个“零”合为一个,并去除末尾的“零”。因此我们需要对“零”进行单独处理。 此外,对于数字 110010 最高位的 11 而言,我们一般是读成“十一万”而不是“一十一万”,所以还应对位于开头的 10 ~ 19 之间的数字进行处理。 观察上面的例子也很容易注意到,按照这种朴素的处理方法,添加“万”、“亿”等特殊数位的时机也是一个棘手的问题。 通过上述分析可以看到,阿拉伯数字转中文并没有一个统一的规则,且因为中文的阅读习惯比较特殊,还应进行许多特殊处理。 算法设计与实现 以数字 123456789 为例,我们可以将数字从右到左按照每 4 位为一段进行单独处理,之后对每段处理后的结果进行拼接: 将 123456789 分为 1、2345、6789 三段,每段单独处理; 6789 = 六千 七百 八十 九,2345 = 二千 三百 四十 五,1 = 一; 对结果进行拼接,注意拼接的时候带上每段相应的数位,比如“万”和“亿”,拼接后为:一 亿 二千三百四十五 万 六千七百八十九。 按照这样的规则处理就可以解决“万”、“亿”等特殊单位的添加问题。...

March 13, 2022 · Huo Haodong

服务器上实现校园网账号的登录/登出

校园网账号的登录/登出操作在本质上是本机向校内的认证服务器发送了一个含有校园网账号和密码、DHCP 服务器为本机分配的内网 IP,本机的 MAC 地址等信息的网络请求。想要在无图形界面的服务器上实现校园网账号的登录/登出首先需要获取校园网认证服务的 API 接口地址和参数列表。 首先使用浏览器(这里使用网络工具更好用的 Firefox)打开校园网登录界面,F12 打开开发者工具,找到网络一栏。 开发者工具的网络一栏可以实时拦截并解析网页中发送和接收的网络请求,此时输入账号密码并点击登录后即可获得所有相关的网络请求链接。 可以通过过滤 URL 的方式寻找和登录(login)有关的关键字来查找相关网络请求,可以看到这里第一个请求就是校园网账号登录操作的 URL 链接。 浏览器的开发者工具一般都会为每个请求链接提供 cURL 命令格式的复制选项,根据服务器所在的平台不同,复制相应的 cURL 命令即可。由于服务器运行的是 Linux,这里采用 POSIX 标准的命令进行复制。 复制得到的命令中的一些琐碎的参数可以去除,留下关键的参数即可。 原始命令 curl 'https://w.seu.edu.cn:801/eportal/?c=Portal&a=login&callback=dr1003&login_method=1&user_account=校园网账号&user_password=校园网密码&wlan_user_ip=DHCP 服务器为本机分配的内网 IP&wlan_user_ipv6=&wlan_user_mac=000000000000&wlan_ac_ip=&wlan_ac_name=&jsVersion=3.3.2&v=4680' -H 'User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:98.0) Gecko/20100101 Firefox/98.0' -H 'Accept: */*' -H 'Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2' -H 'Accept-Encoding: gzip, deflate, br' -H 'Connection: keep-alive' -H 'Referer: https://w.seu.edu.cn/' -H 'Cookie: PHPSESSID=iallep4oe53qg6uc5osr6ir99e' -H 'Sec-Fetch-Dest: script' -H 'Sec-Fetch-Mode: no-cors' -H 'Sec-Fetch-Site: same-site' 精简后的命令...

March 8, 2022 · Huo Haodong

博客迁移

20 年年初的时候阿里云云翼计划额外赠送了一次学生机购买机会,正好疫情期间在家上网课很无聊,索性就花了亿点时间折腾了一下博客。🤔既然是采用云服务器来部署博客,静态博客这种肯定是不合适的。而市面上可选自部署博客服务的方式太多了,诸如 WordPress 这类成熟的方案简直是傻瓜操作,一键部署搞定。挑了半天,综合考虑了可玩性和易用性,最后选择了 typecho 来搭建博客服务,博客主题选用了代码和文档质量高到不可思议的 handsome 主题。但折腾总归是折腾,折腾到最后都是索然无味🙃。 坚持写了一年多的博客,对于服务器续费的事情早就习以为常。没想到前几天邮箱突然遭到阿里云轰炸,阿里云预付的 0.01 个达不溜竟然无法续费服务器了,起初以为是 bug,最后才发现是学生机优惠续费有次数限制🤡,续费一次的成本直接翻了几十倍,成本过高,于是便想着这几天忙完毕业的事情就把博客迁移到成本更低的静态博客上。 这次博客迁移实际上只用了一下午,但是技术选型和博客风格倒是考虑了几个星期。之前采用的旧博客虽然什么都好,但是有几点还是让我很膈应的。 首先,typecho 本质上是个多用户类型的博客服务,每次用 markdown 写完的文章还需要手动登录账号去后台提交,太过麻烦,因此新博客的第一个要求就是博客提交体验要好。 其次,杜绝一切花里胡哨。这不是说之前的博客太花里胡哨,而是我对博客的需求变了,之前只是为了无聊的时候找找乐子,现在是为了找个地方存放读书笔记和技术文章。博客在文字排版和渲染性能不妥协的前提下,越简洁越好,换句话说就是够用就行。 最后,新博客的容灾性能要高且方便未来的迁移。 其实提这些需求完全等于在报 Github Pages+Hugo/Hexo/Vuepress 等方案的身份证。Github Pages 的静态托管服务区完全满足上述所有需求,接下来要纠结的只剩静态博客生成引擎和主题的选择了。 起初我想用采用 Vuepress 的方案,在折腾过后还是决定不合适,Vuepress 本身还是偏向于项目文档的托管,对于博客这种需求其本身就没有提供合适的解决方案。Hexo 的话则是完全为博客需求量身定做,NexT 主题也是非常有名,但是综合考虑到配置的复杂程度、模板引擎的性能、提交体验等多个方面,最后还是选择了 Hugo。 Hugo 完全不需要自己去定义导航栏的一些信息,在 markdown 文件头部加入文章题目、标签、分类等信息后模板引擎会自动生成对应的导航信息,十分方便。提交体验也是非常好,每次写文章只需要使用 Hugo 来生成新文章,写完后生成模板提交到 Github 上即可。(这里其实有更好的方案,使用 Github Action 脚本可以实现自动模板内容的自动生成,省事了不少)。主题的话则是采用了简洁且够用的 PaperMod 主题,性能强悍,markdown 渲染引擎支持各类主流/非主流语法,出乎意料的强悍。 不出意外的话,这次迁移之后应该可以稳定相当长的一段时间了,其实一开始就该采用这种方案的,不折腾又稳定,希望能坚持写下去吧。

May 23, 2021 · Huo Haodong