3 silence1772

尚未进行身份认证

为者常成,行者常至

等级
TA的排名 10w+

Linux内核简单分析(2)——进程调度与切换

进程的调度与切换是一个很复杂的话题,这里我更关心内核是如何实现的,而不是使用了什么策略,所以只讲进程的组织和切换方式,而对调度程序的实现和算法不作分析。如何组织进程?回顾一下进程的task_struct结构,在里面有一个structlist_headrun_list;字段,内核通过这个run_list将处于TASK_RUNNING状态的进程连成一个链表,而处于睡眠状态的进程则处于另一个等待...

2019-04-15 15:23:04

Linux内核简单分析(1)——进程管理

何为进程?许多的内核书籍都会把进程放在比较靠前的章节介绍,因为进程是内核中一个比较重要的概念,很多东西都是围绕进程来展开的,毕竟系统的任务就是运行进程嘛,这里我也把进程放到最前面来介绍。进程的概念学过操作系统的都懂,比较字面的解释也就不说了,进程一般是一个正在运行的程序,它还包括这个进程所拥有的资源,比如打开的文件,CPU寄存器里面的数据,进程所拥有的地址空间(例如申请的变量,堆和栈等)。从...

2019-04-09 19:02:50

C++11线程池简洁实现

C++11标准里新增了多线程库,可以有效简化多线程代码的编写。下面的代码是基于C++11的线程池实现,原理也很简单,类似于生产者消费者,即有n个线程,相当于消费者,还有一个任务队列,相当于生产者。当任务队列被塞入任务时,线程们就去竞争这些任务,但每次只有一个线程能够得到任务。下面来说说具体的实现,首先任务的类型就是一个没有参数,返回值为void的函数,使用usingTask=std::fu...

2019-01-31 21:04:16

红黑树

红黑树是一种特殊的二叉搜索树,

2018-11-07 20:02:50

二叉搜索树及AVL平衡二叉搜索树

二叉搜索树二叉搜索树是二叉树的的一种,只不过多了个限制条件,即左子树节点的值都小于该点,右子树节点的值都大于该点。定义://树节点template<typenameT>classNode{public: Tkey; Node*parent; Node*left; Node*right; Node(Tk,Node*p=nullptr,...

2018-11-06 13:39:54

并查集

并查集的实现比较简单,注意一点在查找时执行路径压缩即可。vector<int>Parent(100);vector<int>Rank(100,0);voidInit(){ for(inti=0;i<Parent.size();++i) Parent[i]=i;}intFind(intx){ if(x!=P...

2018-11-04 16:52:19

KMP字符串匹配算法

“看毛片”算法可以说是许多人学习数据结构路上的一道坎,虽说代码并不算难,但总是写了就忘,其算法思想也是难以理解。其实多写几遍就会发现,也就那么回事。主要思想:kmp算法主要是通过一个next数组来加速匹配的过程,这个next数组也称为失配数组。现在我们来考虑下面这种情况,母串与匹配串匹配到了如图箭头位置,但此时A和B并不匹配,怎么办呢?注意到图中蓝色部分是相等的子串,因此我们直接移动匹配串让A...

2018-11-04 14:42:01

二分查找

二分查找主要思想就是在一个排好序的数组中,取到位于中间的元素,根据这个元素与要查找的值进行比对,来判断是往左边走还是右边。时间复杂度为O(logn),是许多题目的解题关键。三分支版传入数组的起始和结束边界,以及要查找的值,查找到则返回下标,否则返回-1,因为最坏情况下要进行两次比较,所有时间复杂度的常数项稍微高一点。intBinarySearch(vector<int>&amp...

2018-11-03 23:25:32

二叉树的Morris遍历

二叉树的普通遍历算法有很多,但它们都无法做到额外空间复杂度O(1),因为它们总要用到栈来保存信息,才能够从下层回到上层。这里介绍Morris遍历,能够做到时间复杂度为O(n),额外空间复杂度为O(1)。Morris中序遍历Morris遍历其实就是利用了树中大量的null指针。如下图,我们现在先来考虑中序遍历,对于节点4,什么时候会打印它呢?由中序遍历的序列得知,在节点4的左子树都打印完毕后,...

2018-11-03 13:34:14

二叉树各种遍历算法

#include<iostream>usingnamespacestd;structNode{ intvalue; structNode*left; structNode*right; Node(intdata):value(data),left(nullptr),right(nullptr){};};//先序遍历voidPre...

2018-11-01 22:15:12

桶排序、基数排序

桶排序主要思想:对于输入的数据(大小范围为0~max),创建0到max个桶,第一步装桶:遍历数据,将与元素值相等的桶计数加1;第二步收集:遍历桶,如果桶计数n不为0,则在原数组中增加n个与桶标号相等的数。代码://需传入数据中的最大值voidBucketSort(vector<int>&a,intmax){ intn=a.size(); int...

2018-10-31 23:50:08

选择、冒泡、归并、插入及希尔排序

选择排序选择排序每次遍历一遍数组,找出最小的数,然后跟数组的第一个元素交换。再从剩下的元素中重复此步骤直至数组排序完毕。时间复杂度与输入数据无关,为O(n^2)。代码:voidSelectSort(vector<int>&a){ intn=a.size(); for(inti=0;i<n-1;++i) { intmin...

2018-10-30 23:16:37

堆排序

基本思想堆排序是利用二叉堆实现的一种排序算法,它的最好、最坏、平均时间复杂度均为O(nlogn),为不稳定排序,可实现就地排序,额外空间复杂度为O(1)。先了解一下堆的结构。堆本质上是完全二叉树,分为大顶堆和小顶堆,每个结点的值都大于或等于左右孩子的称为大顶堆,反之为小顶堆。【图】下面我们都以大顶堆为例。将该二叉堆结构按照层次遍历的次序映射到数组中,则该数组逻辑上也是一个堆。【图】对于...

2018-10-29 22:44:51

快速排序

快速排序快速排序基于分治策略,时间复杂度最好O(nlogn),最差O(n^2),平均O(nlogn),为不稳定排序。算法思想:选取一个数作为轴点,然后把小于轴点的元素移到左边,大于轴点的移到右边,接着递归处理左右两部分,最终处理完毕的数组即为排序后的数组。...

2018-10-29 13:18:40

C++网络编程实战项目--Sinetlib网络库(5)——HTTP服务器设计与实现

Sinetlib内嵌了一个简易的HTTP服务器,实现了url匹配和静态资源访问,可以使用作为RESTfulAPI的后台。整体架构整体是建立在网络库连接的抽象上的,但服务器接收到消息,将其解析成HTTPRequest,然后通过路由器进行匹配,得到匹配的Hander进行处理,如果没有匹配则直接返回404Response。处理完生成对应的Response发送回去。解析对于http请求的解...

2018-10-26 22:27:06

C++网络编程实战项目--Sinetlib网络库(4)——线程池和整体框架

线程池我们已经有了一个Looper类表示事件循环,且每个线程只能有一个Looper,现在我们把Looper和线程绑定在一起,成为一个新的类LooperThread创建该类也就创建了一条新线程,然后该线程上运行着Looper。我们把这些线程都交由线程池管理,也就是ThreadPoolReactor实际上这并不是纯粹的Reactor模式,更应该称之为半同步半异步模式。我们有一个主线程以及线程...

2018-10-25 14:34:01

C++网络编程实战项目--Sinetlib网络库(3)——事件循环与跨线程调用

上一篇文章讲了Reactor模式的关键结构I/O复用和事件分发,现在我们来关注一下它们的使用。事件循环我们已经实现了一个Epoller类来实现I/O复用,具体的使用方法就是Epoller::Poll()函数等待事件的发生,该函数有一个超时时间,超过这个时间即使没有事件发生也会返回,那么我们如何让它一直工作呢?很明显就是使用while循环。一个事件循环的大概逻辑如上图,就是循环反复地调用Po...

2018-10-24 13:30:15

C++网络编程实战项目--Sinetlib网络库(2)——I/O复用与事件分发

从这一节开始讲解网络库代码的实现,在触及完整的运行逻辑之前,我们先来了解底层的Reactor模式关键结构。事件分发让我们先理清一下事件分发的概念。在linux系统中,信奉着一切皆文件的思想,对于我们网络库使用的socket套接字,也是用文件描述符来表示。现在假设我们有一个socket,这个socket连接了一个客户机,那么现在我们想象出下面这一场景:可以看到,socket相当于一个听筒,客户...

2018-10-23 20:33:08

C++网络编程实战项目--Sinetlib网络库(1)——概述

前言这个网络库是我一直想完成的一个个人项目,到现在也只能说完成了基础的一部分,还有很多功能没完成。因为想往linuxc++后台方向发展,所以就打算实现一个网络库,来串联学到的知识,包括APUE、UNP、《EffevtiveC++》等等可以说是该方向必看的书籍。暑假的时候我照着陈硕先生的muduo网络库模仿了一个,学到了很多,但对很多细节不解,所以现在就想重新实现,同时也熟悉整个开发流程。项...

2018-10-22 21:03:32

Vim常用命令及配置方案

几句话很久之前就接触到vim,初学那阵觉得vim很酷炫,但确实对新手不是很友好。我也就简单看了下基本操作就上手了,但又不是长期在vim下工作,这就导致了每一次重新使用vim都要再去回温下基本操作,很是难受,所以就趁这个机会把基本操作都记录下来,一来可以当做自己的笔记,二来希望可以帮到同样和我一样用过vim但却忘得差不多的人。另外,这里也记录一下自己的vim配置,这个配置可能并没有其他网友分享的...

2018-07-16 12:59:18

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。