- 博客(65)
- 收藏
- 关注
RSS订阅原创 MIT_6.828_2018_Homework:bigger files for xv6
地址：bigger files for xv6题目要求：原来的一个文件的最大大小为12+128=140个blocks，现在将前12个直接块取一个出来存放另一个“doubly-indirect”块，这样就新增了128*128-1个块了。有点类似与计算机组成原理里面的存储器间接寻址。准备工作首先修改Makefile:CPUS := 1加入QEMUEXTRA = -snapshot修改param.h： #define FSSIZE 20000 // size of file
2020-05-12 11:17:38
838
原创 MIT_6.828_2018_Homework:Barriers
地址：Barriers这次作业的目的是实现线程间的同步。具体实现参考别人如下：static void barrier(){ //bstate.round++; pthread_mutex_lock(&bstate.barrier_mutex ); bstate.nthread++; if (bstate.nthread == nthread) { // 最后一个进...
2020-02-29 18:57:21
419
原创 MIT_6.828_2018_Homework:User-level threads
地址：User-level threads之前的swtch()是在内核中进行切换的，这次的切换实在用户态。实现如下：.text/* Switch from current_thread to next_thread. Make next_thread * the current_thread, and set next_thread to 0. * Use eax as a temp...
2020-02-27 22:37:15
496
原创 MIT_6.828_Lab4 Part A
项目地址：Lab 4Getting Started在merge的时候发生了冲突，需要手动消除。Multiprocessor Support该内核支持多核，BSP用低物理地址来引导其他的CPU加载系统。利用LAPIC做的三件事情：得知当前代码运行在哪一个CPU上BSP利用IPI中断唤醒其他CPU利用LAPIC的定时器实现分时复用Exercise 1. Implement mm...
2020-02-21 20:29:09
901
原创 MIT_6.828_2018_Homework:xv6 locking
作业地址：xv6 locking此次作业让我们对xv6里面应用的锁有更进一步的了解。
2020-02-19 11:04:00
751
原创 MIT_6.828_2018_Homework: Threads and Locking
作业地址：Threads and Locking这次作业的目的在于让我们对多线程有个大概的了解，以及多线程可能引发的问题，通常可以通过加锁来解决。源码下载地址：ph.c源码如下：#include <stdlib.h>#include <unistd.h>#include <stdio.h>#include <assert.h>#inc...
2020-02-16 21:57:38
935
原创 MIT_6.828_2018_Homework_xv6_CPU_alarm
作业地址：xv6 CPU alarm此次作业就是添加一个系统调用alarm()，可以周期性的进行某个函数的调用。Step 1在user.h中添加这个系统函数的声明：int alarm(int ticks,void(*handler)());Step 2在syscall.h中添加该调用的号码：#define SYS_alarm 22Step 3在usys.S里面添加进入内核的...
2020-02-16 12:09:28
552
1
原创 MIT_6.828_Lab_3: User Environments Part B
项目地址：Lab 3Handling Page FaultsExercise 5. Modify trap_dispatch() to dispatch page fault exceptions to page_fault_handler(). You should now be able to get make grade to succeed on the faultread, faul...
2020-02-14 23:05:53
287
原创 MIT_6.828_Lab_3: User Environments Part A
项目地址：Lab 3Environment State在文件inc/env.h文件中，定义了环境(进程)结构体：struct Env { struct Trapframe env_tf; // Saved registers struct Env *env_link; // Next free Env envid_t env_id; // Unique environment i...
2020-02-13 16:12:12
1264
原创 MIT_6.828_2018_Homework_xv6_system_calls
作业地址：System calls用户程序调用系统函数的流程1.创建一个新的进程创建一个新的进程的时候，在内核态，会对该进程进行相应的初始化工作：设置该进程的内核栈(PGSIZE),用户的空间(起初是一个PGSIZE的大小),pid,trapret，设置该进程的虚拟地址映射(这就做到了隔离)。2.执行进程接下来切换到用户态(trapfram里面的eip即为在用户态下执行第一条语句的地址)...
2020-02-06 11:21:50
1172
原创 MIT_6.828_Lab2 Part2
实验地址：Lab2虚拟地址翻译为物理地址的流程如下： Selector +--------------+ +-----------+ ---------->| | | | | Segmentation | | ...
2020-02-02 19:43:56
490
原创 MIT_6.828_Lab2 Part1
实验地址：Lab2Lab2的第一部分为物理地址的管理，其中包括物理内存的初始化，分配以及释放。首先，在inc/mmu.h中定义了几个宏：#define NPDENTRIES 1024 // page directory entries per page directory#define NPTENTRIES 1024 // page table entries per page tab...
2020-01-31 23:25:04
419
原创 MIT_6.828_2018_Homework_shell
shell源码地址：sh.c执行简单命令找到sh.c中case ' '处，在此书写执行普通命令的代码。注意到：struct execcmd { int type; // ' ' char *argv[MAXARGS]; // arguments to the command to be exec-ed};和函数 int execv(const c...
2020-01-30 16:21:48
549
原创 一个C语言指针的练习题及其解释
练习题地址：原文指针代码如下：#include <stdio.h>#include <stdlib.h>voidf(void){ int a[4]; int *b = malloc(16); int *c; int i; printf("1: a = %p, b = %p, c = %p\n", a, b, c);...
2020-01-30 11:31:12
539
原创 Homework: boot xv6(MIT6.828 LEC2作业)
地址：Homework: boot xv6环境部署复制项目到本地在目录6.828下面使用命令：git clone git://github.com/mit-pdos/xv6-public.git将项目复制到本地。之后使用make即可。使用gdb调试打开两个终端，都进入6.828/xv6-public目录下。第一个终端使用命令make qemu-gdb,第二个使用命令gdb[1]。...
2020-01-29 18:01:41
545
1
原创 MIT 6.828 2018 Lab_1
教学大纲：教学日历实验地址：Lab1本次实验共分为以下三个部分：PC BootstrapThe Boot LoaderThe Kernel1.PC Bootstrap32位PC物理地址空间+------------------+ <- 0xFFFFFFFF (4GB)| 32-bit || memory mapped || de...
2020-01-28 22:44:31
720
原创 POJ3537,SG函数和SG定理
题目链接：Crosses and Crosses分析：对于每个位置i，可以分成两个子问题i-3和n-i-2.深搜一下就行了.代码如下：/************************************************************************* > File Name: main.cpp > Author:Eagles > M...
2018-11-08 20:11:19
394
原创 POJ2975,Nim游戏求方案总数
题目链接：Nim题目大意：给定一个Nim状态，求该状态能够到达获胜状态的方案总数。分析：若该状态为P状态，则Nim和为零，肯定方案总数为0,；若Nim和不为零，则表明该状态处于N状态，由于该位置是N位置，所以Nim和不为零，我们要求有多少总方案，改变其状态，使Nim和为零。Nim和的求法为x1,x2,x3…xn的异或和，考察第一堆石头，设a=x1,b=+(x2+x3+…+xn)，那么: ...
2018-11-08 19:49:43
604
1
原创 POJ2425,组合游戏
题目链接：A Chess Game首先需要了解SG函数及SG定理：博弈论 SG函数，Nim游戏与SG函数 ——博弈论小结在了解了以上之后就好做了。首先对于一个有向图来说，每个点都有一个sg函数值，如果该值为0，则此位置为先手必败即P位置，否则为先手必胜即N位置。而所有的棋子的位置的sg值异或之和为0即输，否则则赢。现在的目标就是求每个点的sg值，按照sg函数的定义，求出每个点的sg值。注意：...
2018-11-06 21:23:01
407
原创 HDU1260,简单dp
题目链接：Tickets题目的大意是:有n个人，每个人买票有一个时间，如果两人买，又有一个时间，求所需要的最短时间。用动态规划的思想：设dp[i]为前面i个人所需要的最短时间。那么，dp[i]=min(dp[i-1]+time[i],dp[i-2]+pair[i-1])表示，dp[i]可以由前i-1个人加上第i个人的时间或者前i-2个人加上i-1和i这一对儿。代码如下:/*********...
2018-10-28 14:29:17
427
原创 POJ3469,最大流，最小割
题目链接：Dual Core CPU题意是：每个点有两个选择，要么选择A,要么选择B,选择A和选择B有相应的时长，但是二者不能同时选。最小割就是，求最小的代价，使得源点和汇点不在联通，也就是这道题中的不能同时选择。建图：1.源点为A，汇点为B，由A向点i连边，点i向B连边。2.对于有特殊关系的两个点，相互连边代码如下：/********************************...
2018-10-05 19:26:58
274
原创 HDU3605,最大流，状态压缩
题目链接：Escape二分图的多重匹配，有最大流做的。如果按照普通的最大流建图，会TLE，这里考虑到m的范围是0-10,故用二进制状态压缩，最多也就2^10多种可能。详见代码：/************************************************************************* &gt; File Name: main.cpp &gt; A...
2018-10-05 16:17:58
199
原创 POJ2289,最大流，二分
题目链接:Jamie’s Contact Groups建图：从源点向i连边，容量为1；i向i’连边，容量为1；i’向可以放置的代号连边，容量为1,；0-m个容器向汇点连边，容量待定。用二分法判断，在该容量下，最大流是否为n，是则可以，否则不可。代码如下：/*******************************************************************...
2018-10-05 14:38:21
276
原创 HDU3472,混合图的欧拉回路
题目链接：HS BDC建图方法：将一个单词的首位字母视作一个点。对于反转后还成立的单词在最大流的图中建立首到尾的边，反转后不成立的单词则不用建边。之后再用普通的求法就行。注意连通性的判断。详见代码：/************************************************************************* > File Name: main.c...
2018-09-30 15:35:31
291
原创 POJ1637,最大流确定混合图是否存在欧拉回路
题目链接：Sightseeing tour这篇文章讲得很好：混合图的欧拉回路一般求解方法述我的代码：/************************************************************************* > File Name: main.cpp > Author:Eagles > Mail:None > Cr...
2018-09-29 20:47:28
220
原创 POJ3308,最大流最小割
题目链接：Paratroopers好题。首先建立源点和汇点，从源点向每行建立一条边，容量为每行的花费；再从每列向汇点连边，容量为每列的话费。如果在一行与一列的交点处有障碍物，则从该行向该列连一条容量无限的边。由于是求乘积的最小值，故先取对数处理。详见代码：/********************************************************************...
2018-09-28 22:34:36
239
原创 Luogu3944,最小割
题目链接：Earthquake Damage 2题目意思是：在地震中，有些村庄被毁坏了，有些没有。有些没有毁坏的村庄与村庄1失去了联系，要你求最小的毁坏村庄数，使得那几个已知没有被毁坏的村庄与村庄1没有联通。如果将村庄视作边，那么就是求最小割，与源点1无法联通。但是棘手的是村庄是一个点。我们可以转换一个思路，将村庄进行拆点，两点之间用一条容量为1的边连接起来，那么将两点之间的边删掉就等价于删掉...
2018-09-27 20:48:24
162
原创 POJ3281,最大流拆点
题目链接：Dining入手的最大流第一题。题目的意思是说，每个牛都有喜欢的饮料和食物，怎样分配才能最大限度地满足牛的需求。如果去掉一个饮料，那么就是每个牛都有喜欢的食物，怎样最大限度地分配。这就是最大二分图匹配问题，用最大流做就是，从源点向每头牛连一条容量为1的边，然后每头牛向喜欢的食物连一条容量为1的边，最后由食物向汇点连一条容量为1的边，最后求最大流即可解决问题。但是这道题多了饮料，我...
2018-09-27 20:33:03
215
原创 POJ3207，2-sat问题
这也是一道经典的2-sat问题，难在怎样建图。首先我们需要像普通的2-sat问题一样无寻找对立的条件。每条边可以在圆内，也可以在圆外，所以可以把每条边当作一个点p，若在圆内，则为p,若在圆外，则为p’。对于给定的m组数据中，若边x与边y在同一侧要相交的话，就建边&lt;x,y’&gt;,&lt;y,x’&gt;,&lt;y’,x&gt;,&lt;x’,y&gt;,接下来就是判断
2018-09-22 10:24:01
343
原创 POJ2723,2-sat问题，二分查找
入手的第一道2-sat问题，关于怎样建图，迷糊了2天，在网上看到各种各样的解法，感到眼花缭乱，无所适从。于是乎，知道今天才有了一点眉目。做2-sat难在怎样建图。到目前为只，由于做的题数目有限，只能说说自己浅薄的见解。最朴素的2-洒脱问题的形式是，有n个集合，每个集合中两个元素，从0，1，2，…，2*n-1，从每个集合中选出一个元素，并且不同集合之间的元素之间存在某些约束，然后再根据题目求出...
2018-09-21 19:14:01
219
原创 POJ2168,Tarjan算法求强连通度，并查集
题目链接：Popular Cows本题求的是受所有的牛欢迎的牛的个数（每头牛都欢迎它自己）。本题建立的图模型是有向图，在有向图中有这么一个定理：从任意一个点出发，必定到达终点，终点的出度为0。在一个强连通分量中，任意两个点可以相互抵达，也可以说任意两个点是等价的。那么这道题可以这样去解决：将每个连通分量当作一个整体，缩小成为一个点。如果整个图中仅有一点的出度为0，那么在这个点所在的连通分量之外...
2018-09-18 22:56:31
281
转载 Tarjan算法讲解
原文链接：强连通算法–Tarjan个人理解+详解首先我们引入定义：1、有向图G中，以顶点v为起点的弧的数目称为v的出度，记做deg+（v）；以顶点v为终点的弧的数目称为v的入度，记做deg-（v）。2、如果在有向图G中，有一条&lt;u，v&gt;有向道路，则v称为u可达的，或者说，从u可达v。3、如果有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使...
2018-09-18 22:34:35
208
原创 HDU3018,欧拉回路，并查集
求欧拉回路的第一道题，是看的别人的题解做的。 思路就是：对于每个连通块来说，如果该连通块的所有点的入度为偶数，那么就可以一笔画完该连通块。如果为奇数，那么需要的笔画为奇度数顶点之和的一半，比如两个奇数顶点，那么需要1，四个奇数顶点，那么需要2… 代码如下：/*****************************************************************...
2018-09-17 10:14:25
246
原创 HDU2647,拓扑排序
题目链接：Reward 如果a要比b的钱多的话，就要在b的奖金的基础上增加至少1元钱，为了能够花费最少，我们当然是选择增加1元钱。 这道题呢，跟裸的拓扑排序题稍微有点区别。我下面讲讲我的做题的过程(WA到哭的过程…) 我首先想，不就是一个拓扑排序嘛，然后就按照通常的做法，拓扑排序，排好之后比如有4个，那么总和就为888+889+890+891，然后提交之后，wa了。 然后我就想到一种情况，...
2018-09-16 19:22:17
266
原创 POJ3687,拓扑排序
这题首先要明确输出什么——–输出从1-N编号的球的重量，并且尽可能使1号球轻，如果1号轻一样重，则输出2号球尽可能轻的方案，…以此类推. 如果按照正常的思路，就是拓扑排序，每次取出最小的编号，使其重量为当前最小。但是这样存在一个问题，就是：当前最小的编号的球不一定是能够最先接近1球，有可能当前编号最大的那个或者其他球最先接近1号球。所以正向就不能够得到正确的答案。可以这样想：每次我都将编号最大的...
2018-09-16 14:10:28
243
原创 POJ3020,最小边覆盖
说来惭愧，看了别人的题解之后知道解题步骤，却不知道原理，也就是说，不知其所以然，哎… 步骤就是：将所有相邻的点建立无向图，之后求最小边覆盖，即为答案。/************************************************************************* > File Name: main.cpp > Author:...
2018-09-15 23:42:33
192
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人