- 博客(155)
- 收藏
- 关注
RSS订阅原创 Linux——IP协议2
全球主流的IP地址IPV4，共四十多亿IP地址， 每个国家的IP地址，在开始的时候，就已经被划分好了，国际上的路由器都有自己的路由表，可以进行国家和国家的转发。所以，我们需要将IP进行划分，之后就有了各种网络划分的方案。IP地址分为两个部分, 网络号（可表征不同区域）和主机号。不同的子网其实就是把网络号相同的主机放到一起.如果在子网中新增一台主机, 则这台主机的网络号和这个子网的网络号一致, 但是主机号必须不能和子网中的其他主机重复网络号是标识网段的重要依据。
2023-06-28 10:07:30
318
原创 Linux——IP协议1
13位分片偏移：是分片相对于原始IP报文开始处的偏移. 其实就是在表示当前分片在原报文中处在哪个位置. 实际偏移的字节数是这个值 * 8 得到的. 因此, 除了最后一个报文之外, 其他报文的长度必须是8的整数倍(否则报文就不连续了)。报文长度是1500字节，分成三份，第一个片偏移量0，第二个500，第三个1000.更多分片是1代表该分片后面还有分片：如下面这张图里更多分片是1，1，0。虽然有分片，但分片行为不是主流，能一次交付就尽量一次交付。
2023-06-11 15:17:31
783
原创 Linux——TCP协议2
我们所要的是对方的接收缓冲区大小，我们可以通过交换报文获取对方的缓冲区大小，在三次握手的时候我们可以进行交换报文，在三次握手的前俩次是不能携带数据的，因为三次握手没有完成，但是可以交换双方的缓冲区的大小，三次握手就是在交换双方的报文（数据段），因为TCP报头有窗口大小，只不过该数据段没“有效载荷”。TCP根本不关心发的是什么，只负责把数据发过去，不对报文做任何解释，如之前写的网络计算器，\r\nlength x y \r\n,这种格式是我们在应用层定制的，TCP根本不关心格式，只负责把数据发过去。
2023-06-04 08:50:53
617
原创 Linux——TCP协议1
TCP通信的时候，客户端发送信息既不能太快也不能太慢，如何保证发送方发送数据既不快又不慢呢？服务器把自己的同步接收能力告诉客户端，而服务器的接收能力又由什么决定？接收缓冲区中剩余空间的大小。根据对方接收能力，控制数据发送速度，这种策略叫流量控制。16位窗口大小就是接收缓冲区剩余空间大小。16位窗口大小中填的是自己的接收缓冲区大小。这是TCP报头当中的6个标记位6个标记位：是按照1个比特位表示某种含义的，为什么需要多个标记位？我们可能会给对方发送各种类型的TCP报文。
2023-06-03 09:52:28
542
原创 Linux——Udp与Tcp协议
TCP报头里有一个4位首部长度（包括20字节和选项长度）， 范围：0000~1111即0~15，单位是4字节，即共60字节，整个TCP报头最大是60字节，具体是多少要看选项长度，4位首部长度范围（在标准20字节的基础上）即【5,15】，即【0101，1111】，如果报头没有带选项，4位首部长度就是0101。无法判定报文和报文的边界，也不需要判定，TCP只需要把所收到的所有数据拿走，剩下的交给上层，至于数据在2进制字节流当中，该如何被解释这是由应用层关心的。每一个报文，一定是携带了完整报头的TCP报文。
2023-06-02 14:40:22
403
原创 Linux——https2
3.无状态（http并不会记录一个用户上一次的请求，http协议不会对用户的行为做记录），但是我们登录一些网站，如CSDN时，第一次需要输入账户密码和信息，当我们关闭网页之后，再次打开CSDN就发现用户已经登陆好了，即免去了让用户频繁登录的行为。表达：收集用户的数据，把数据推送给服务器，当用户想提交数据给服务器，必须依托于网页的表单，表达的作用提供输入框和提交按钮，之后表达中的数据会被转成http请求的一部分，表达是需要被提交的，提交的时候要指明提交方法。2.把客户端的数据提交到服务器，POST，GET。
2023-06-01 18:25:03
565
原创 Linux——https
加密就是把明⽂(要传输的信息)进⾏⼀系列变换,⽣成密⽂.解密就是把密⽂再进⾏⼀系列变换,还原成明⽂.在这个加密和解密的过程中,往往需要⼀个或者多个中间的数据,辅助进⾏这个过程,这样的数据称为密钥(正确发⾳yue四声,不过⼤家平时都读作yao四声数字指纹(数据摘要),其基本原理是利⽤单向散列函数(Hash函数)对信息进⾏运算,⽣成⼀串固定⻓度的数字摘要。数字指纹并不是⼀种加密机制,但可以⽤来判断数据有没有被窜改。
2023-05-31 10:04:08
559
原创 Linux——http协议2
3.无状态（http并不会记录一个用户上一次的请求，http协议不会对用户的行为做记录），但是我们登录一些网站，如CSDN时，第一次需要输入账户密码和信息，当我们关闭网页之后，再次打开CSDN就发现用户已经登陆好了，即免去了让用户频繁登录的行为。表达：收集用户的数据，把数据推送给服务器，当用户想提交数据给服务器，必须依托于网页的表单，表达的作用提供输入框和提交按钮，之后表达中的数据会被转成http请求的一部分，表达是需要被提交的，提交的时候要指明提交方法。2.把客户端的数据提交到服务器，POST，GET。
2023-05-30 15:16:10
617
原创 Linux——http协议1
应用层：就是程序员基于socket接口之上编写的具体逻辑，做的很多工作，都是和文本处理有关的——协议分析与处理。http协议，一定会有大量的文版分析和协议处理。
2023-05-29 09:56:48
710
原创 Linux——序列和反序列化2
上一篇提到了json，即我们不自己写序列化和反序列化。用json里面得序列化和反序列化。当我们换成fastwriter，fastwriter和stylewriter格式不同。引入了json库之后，在makefile里面要加这个选项。下面代码的演示效果，json版的序列化和反序列化。我们这里写一个简单的代码演示一下这个库的用法。我们对结果的表达式再优化一下。我们在使用库的时候带上路径。json库的路径如下。
2023-05-28 16:37:42
61
原创 Linux——应用层之序列号与反序列化
TCP协议通讯流程tcp是面向连接的通信协议，在通信之前，需要进行3次握手，来进行连接的建立。当tcp在断开连接的时候，需要释放连接，4次挥手。
2023-05-28 09:04:51
722
原创 Linux——网络套接字3|Tcp客户端编写②
根据我们前面写的服务器，server端需要绑定，而client要不要bind呢？不需要，因为客户端一旦和一个非常具体的端口号绑定，可能会导致端口号绑定多个客户端，因此可能会出现某个客户端无法启动。而服务器需要明确的端口号，因为服务器面对的是众多的客户端，服务器端口号一旦被改，所有客户端可能会无法连接服务器。即，服务器端口号一经采纳便不再改变。虽然客户端不需要bind，但一定需要端口号，这里让OS自动选择进行端口号选择。对于客户端最需要的是连接别人的能力。这里用的端口叫connect。
2023-05-27 08:57:02
809
原创 Linux——网络套接字2|Tcp服务器编写
本篇博客先看后面的代码，再回来看上面这些内容。.hpp文件，基本调用服务器基本框架接下来用tcp的方式创建套接字，我们用SOCK_STREAM因为TCP是面向连接的，所以当我们通信的时候需要建立连接，
2023-05-26 10:19:51
1420
原创 Linux——网络套接字1|socket编程
IP地址（公网IP），标定了主机的唯一性。通常情况，把数据送到对方的机器是目的吗？不是的，真正的网络通信过程其实是进程间通信，如客户端进程和服务器进程，我们把数据在主机间转发仅仅是手段，机器收到数据之后，需要将数据交付给指定的进程，当客户端有多个进程在运行时，OS又是如何把数据传送给指定进程的？这个跟端口号有关。认识端口号端口号(port)是传输层协议的内容端口号是一个2字节16位的整数;端口号用来标识一个进程, 告诉操作系统, 当前的这个数据要交给哪一个进程来处理;
2023-05-25 15:08:45
1024
原创 Linux——网络基础1
所谓 "局域网" 和 "广域网" 只是一个相对的概念. 比如, 我们有 "天朝特色" 的广域网, 也可以看做一个比较大的局域网.操作系统内部存在着多种协议，那么操作系统要管理这些协议吗？是，管理方式：先描述，再组织。协议本质就是软件，软件是可以分层的。协议在设计的狮虎，就是被层状划分的。为什么要划分称为层状结构？答：一般要面对的场景比较复杂，可以进行功能解耦（每层可解决不同的问题），便于人们进行各种维护，因此网络协议也是层状结构。通信的复杂，本质是和距离成正相关的。复杂体现在哪里？
2023-05-24 10:23:08
560
1
原创 Linux——线程7|线程池
上面的代码可能会遇到这种情况，多个线程同时调用getThreadPool，当第一个线程用if语句判断时，可能被切走，被且走后第二个线程进来，通过了if判断，然后new出对象，此时第一个线程又被切回来，但这个时候已经在执行new代码了，影刺可能会出现new重复执行的情况，所以我们上面的代码并不是线程安全的。代码这样改，当再想获取单列的时候，先进行判断而不是加锁，当后续的线程来的时候ptr已经不为空了，直接进行返回，避免了中间的多次加解锁。通常而言，在读的过程中，往往伴随着查找的操作，中间耗时很长。
2023-05-22 09:09:10
300
原创 Linux——线程6
我们在访问线性结构时用下标进行访问，下标从0开始，最后一个下标是n，实际元素个数是n+1,如果这里让index去访问线性结构，当访问到下标为n的位置时，index++，此时要访问下标为0的元素，这里我们用index%=(n+1)，即用模运算来模拟环状结构，因为这里有n+1个元素，所以模n+1。我们可以用一个格子来进行判断，如果当前位置的下一个位置下标为0，则说明满了，则在这个格子中不放入任何的数据，即为空的时候，俩者都指向同一个位置，为满的时候，生产者指向最后一个位置，消费者指向第一个位置。
2023-05-21 15:11:42
532
原创 Linux线程5——生产消费模型
当队列满时，往队列里存放元素的操作也会被阻塞，直到有元素被从队列中取出(以上的操作都是基于不同的线程来说的，线程在对阻塞队列进程操作时会被阻塞)，这里的阻塞队列就是交易场所。生产消费模型效率提高体现在：当消费者要花很多时间处理数据时，当消费者正在处理数据的时候，他并没有访问锁，因为这个数据已经被拿到了消费者线程的上下文当中，所以，此时生产者线程可以生产数据甚至把数据放到仓库里，因此，实现了俩个线程的并发，提高了俩个线程的并发度，效率提高就体现在了这里。生产者和消费者角色由线程承担，也就是给线程角色化。
2023-05-20 08:53:00
584
原创 Linux——线程4|线程同步
同步：主要是为了解决访问临界资源合理性问题的（如抢票的时候不能只让一个进程把所有的票抢走），同步是按照一定的顺序，进行临界资源的访问。
2023-05-19 11:27:34
409
原创 Linux——线程3|线程互斥和同步
我们单个申请一把锁是原子的，当一把锁申请完再去申请另一把锁，可能会出问题，如这里的线程A,B，俩个同时运行线程A拿锁1，线程B拿锁2，接下来线程A申请锁2，线程B申请锁1，此时就会出现问题，双方想要的锁都被对方拿到。当执行完第一条语句之后，线程有可能被切换，线程被切走的时候是带着数据走的，走的时候带走了寄存器里放进去的0，当新线程来了之后，新线程照样从第一句语句开始执行（这是加锁操作必须的），新线程把0放了进来，也就是说此时俩个线程都有0，进而说明，寄存器是共享的，但寄存器里面的内容是私有的。
2023-05-18 21:14:39
432
原创 Linux——线程2|线程控制
在一个程序里的一个执行路线就叫做线程（thread）。更准确的定义是：线程是“一个进程内部的控制序列”。一切进程至少都有一个执行线程线程在进程内部运行，本质是在进程地址空间内运行在Linux系统中，在CPU眼中，看到的PCB都要比传统的进程更加轻量化透过进程虚拟地址空间，可以看到进程的大部分资源，将进程资源合理分配给每个执行流，就形成了线程执行流线程的优点创建一个新线程的代价要比创建一个新进程小得多与进程之间的切换相比，线程之间的切换需要操作系统做的工作要少很多线程占用的资源要比进程少很多。
2023-05-15 09:48:53
468
2
原创 Linux——线程1
若我们已经创建好一个进程，此时再创建进程，此时就会有俩套task_struct,mm_struct,页表我们想在一个进程的基础上，在创建一个进程，而且这个新的进程只创建PCB（task_struct），这个PCB指向父进程对应的地址空间。我们想以上面这种方式创建多个进程，而且通过一定的技术手段，将当前进程的“资源”，以一定的方式划分给不同的task_struct（如多个进程执行不同的代码）。而且对于CPU来说，这么多PCB不会影响到CPU。
2023-05-14 09:23:18
208
1
原创 Linux——进程信号3
内核如何实现信号的捕捉信号捕捉的方法出了我们之前的signal之外，还有其它方法sigactionsigaction：检查或更改一个信号的动作即捕捉信号第一个参数，要捕捉的信号对应的编号，第二个参数：结构体（这个结构体类型名和函数名一样，这里不是回调这个函数），该类型是输入型参数，第三个参数 输出型参数，对于这个信号的老的处理方法，类似于sigprocmask。成功返回0，失败返回-1，并设置错误码sigaction结构体第一个是信号捕捉对应的回调函数，第2，4，5个参数暂时不考虑。
2023-05-13 08:47:44
387
原创 Linux——进程信号2
在进程终止的时候，帮我们执行设定好的用户返回调用。当执行进程切换的代码时：当进程时间片到了，操作系统底层硬件发送时钟中断，由于当前进程还在CPU上，操作系统在CPU中找到当前正在执行的进程，然后通过该进程的地址空间找到对应的切换进程的函数，然后在进程的上下文中进行切换，因此能直接访问该进程在CPU中的临时数据，然后所有的临时数据被压倒PCB当中，进而把进程放下去，然后选择一个进程再上来，操作系统继续使用下一个进程3-4G的地址空间和内核级页表，然后恢复上下文代码和数据，然后把上一个进程恢复上来。
2023-05-12 14:55:42
574
1
原创 第五章——动态规划3
n-1表示最后一类，从0到j，可看作0到k，k到j，其中k到j是固定的，我们只需要求0到k的最短路径即可。f[i,j]表示所有从0走到j，走过的所有点是i的所有路径，i用二进制表示，表示的是当前的这个点是否走过了，若i=1110011表示第0，1点走过了2，3点没走过，4，5，6点走过了。在下图中 ，i在第二列，j统计的是i前面的列是否伸出小方格到第i列，第一行有是1，第二行没有是0，第三行没有是0第四行有是1，第五行没有是0，j表示为10010。输出一个整数，表示最短 Hamilton 路径的长度。
2023-04-30 09:29:02
468
原创 第五章——动态规划2
a[i]和b[j]选不选共有四种组合情况，我们划分成四个子集，00表示都不选，01不选a[i]，选b[j]，10选a[i]，不选b[j]，11俩个都选。我们先把7去掉，左边计算的就是从起点到8路径的最大值，8的坐标是i-1,j-1，即左边状态可以表示为f[i-1,j-1]含义是从起点走到8这个位置的最大值，最后再给加7。我们以第i-1个数来分类，第一个格子0，表示没有第i-1个数，即序列长度是1，之后分别是 i-1是第一个数，i-1是第2个数，i-1是第三个数……f[i,j]=max（左边，右边）。
2023-04-28 18:51:35
1054
原创 第五章——动态规划1
f(N,V)表示从前N个物品选，总体积不超过V的集合，状态计算表示的是集合的划分，状态计算是把当前的集合表示成更小的子集，即把当前状态用前面更小的状态表示出来，我们这里采用把f(i,j)所有的选法表示成俩大类，以含i和不含i为划分标准。该集合表示的是第i个物品选0个，第i个物品选1个，第i个物品选2个，第i个物品选3个，第i个物品选4个……右边也变成了从i到i-1中选，由于没去掉第i个物品时，总体积不超过j，去掉了第i个物品后，总体积不超过j-vi。从左到右分别是第i组物品选第0个，第i组物品选第1个……
2023-04-27 11:49:29
383
原创 第四章——数学知识3
上三角形式有三种：①完美阶梯型——有唯一解，②非完美阶梯型，左边没有未知数，右边的系数是非0的，即0=非0，此时无解。6，6关于红颜色这条边做轴对称对应的坐标是5，7，即从0，0到6，6的所有路径中，减去0，0到5，7的所有路径，即可得到正确答案。我们转化成从原点走路径的问题，当有6个0和6个1，需要计算从0，0走到6，6共有多少种方案，上述题目求的是从0，0到3，3的距离。从0，0到6，6共有C12 6种走法，再减去经过红颜色这条边的数。答案只有三种情况，无解，无穷多组解，唯一解。
2023-04-26 10:20:06
425
原创 第四章——数学知识1
n中最多只包含一个大于sqrt（n）的质因子（假设n中有俩个大于sqrt（n）的质因子，俩俩乘一块之后肯定大于n），因此枚举的时候可以先把小于根号n的枚举出来，如果最后剩余的数大于1，则说明这个数时大于根号n的质因子。上面算法较为麻烦，我们可这样做，以11为例，我们不需要把2-10的所有数都进行判断，我们把2-10中的质数找出来，看11是不是这些质数的倍数，如果不是则说明11是质数，反之不是质数。如果d是n的约数，则n/d也一定能整除n，即我们枚举约数时，枚举到d≤n/d即d≤根号n。
2023-04-25 20:41:08
444
原创 第四章——数学知识2
裴蜀定理：有一对正整数a,b，一定存在非0整数x，y使得ax+by=（a,b）括号表示a和b的最大公约数，即ax+by=d，d一定是a，b的最大公约数的倍数。最顶部的方程有解，等价于最下面的等式有解，而这个等式有解的充分必要条件是，b必须整除a，m的最大公约数。若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a。x (mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b^−1 (mod m)。4的2的2次方是上面结果6的平方模10，结果还是6。
2023-04-24 08:47:37
410
原创 数学知识四
从n个集合当中选若干个集合，所有的选法都在上述公式中，每种选法的符号跟我们所选取的奇偶数有关，我们用位来表示，如果某位为0，则代表没有选，为1，则代表被选。若最开始的异或值是0，则先手的结果一定是0，后手的结果就不是0，即先手拿到的永远是0，后手拿到的永远不是0.如果异或值不是0，我们可以从某一堆中拿走一些石子，让剩下的值异或变成0，即先拿的可以决定后拿的结果。即有3个堆，分别有2，4，7个石子，每次取得时候只能取2个或5个，如果取 不到就失败。任何非0的状态都能到0，任何0状态到不了0状态，
2023-04-23 19:13:52
579
原创 DFS与BFS|树与图的遍历：拓扑排序
蓝色部分是结点4的子树，红色部分我们暂时称为其他部门，因为我们知道树的总结点数n，只要能算出蓝色部分的数目s，那么其他部分的数目就是n-s。若删除结点3，剩下一个数目为1的子树，和一个数目为7的子树，即剩下的最大连通子树的结点数目为7……如这里的1，2，3就是拓扑序列，因为1在2前面，2在3前面，1也在3前面。若删除结点2，则剩下两个数目为1的子树和一个数目为6的子树，即剩下的最大连通子树的结点数目为6；若删除结点1，则剩下三个子树最大的是中间那颗结点有4个，即剩下的最大连通子树的结点数目为4；
2023-04-21 14:20:31
607
原创 数组元素的目标和
让i一开始指向A的第一个数，j指向B的最后一个数，找到AI+Bj>x的数，之后j--，当找到Ai+Bj=x的数就可以break（因为是升序数组，A增大，B就要--，这样才能找到AI+Bj=x）A和B数组都是具有单调性的数组。时间复杂度O(N+M)
2023-04-20 14:44:01
31
原创 哈希表|STL使用
a r r [ i ] = a r r [ i − 1 ] ∗ p + s t r [ i ] arr[i]=arr[i-1]*p+str[i]arr[i]=arr[i−1]∗p+str[i]，其 中 s t r [ i ] 只 要 不 为 0 就 行 其中str[i]只要不为 0 就行其中str[i]只要不为0就行。h [ 4 ] = h[4]=h[4]=“A B C A ABCAABCA” 的哈希值。h [ 1 ] = h[1]=h[1]=“A AA” 的哈希值。
2023-04-19 08:35:38
403
原创 Trie|并查集|堆|
Trie树是用来快速存储和查找字符串集合的数据结构(字典树）是一种用于实现字符串快速检索的多叉树结构。Trie 的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符 c，就沿着当前节点的 c 字符指针，走向该指针指向的节点。Trie树可以支持有一个：凡是用到Trie树的题目，一般来说给出的字符串要么全是小写字母，要么全是大写字母，要么都是数字，要么全是0或1，总之字母类型不是很多。一棵空Trie树，该点的。（1）过程分析当需要S时，我们令一个指针Р起初指向根节点。然后，依次扫描S。
2023-04-18 14:36:37
351
原创 链表与邻接表|栈与队列|kmp
以找窗口中的最小值为例：3和-1都比-3大，而且这俩个数字在窗口滑动的时候都会比-3提前被窗口弹出，所以我们可以删掉这俩个元素，即：在找最小的数只要队列里面前面的数比后面的数大，则前面的数一定没有用，这样我们就可以把大的数删掉，当整个数组都这样操作时，队列就会变成一个单调递增的队列。注意这组数据里的4和2，当我们要找比7小的数字时，左边3，4，2都比7小，但我们找的是离7最近的2，此时返回2即可，但3和4此时没用，在找比5小的数字时，3，4也没用，3和4便可以删除。数组，它存储的是字符串中（一般是模板串。
2023-04-17 14:28:55
375
原创 Linux——进程间通信3
当n一开始是5，client进行n--，减完之后，n还未返回内存，client执行流就被切走，之后执行了好几个进程，使n变为了1，n变为1之后，client又被切回来，client此时将上次被切走时的n（4），直接返回内存，n从1直接变为了4，这就是时许问题。由于各进程要求共享资源，而且有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源。(该说法有点不准确)2.我们把自己的进程，访问临界资源的代码称为临界区。
2023-03-15 15:03:09
363
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人