Starrk的小屋

人是一根会思考的芦苇

排序算法（下）

希尔排序希尔排序简介希尔排序是插入排序的改进方法。它针对插入排序的改进思想有两点：插入排序在对几乎排好序的序列进行操作时效率非常高，几乎接近线性。插入排序对不理想的序列时，每次都要移动数据一位数据，这对M个子序列时需要进行M-1次操作。如何取其长，补其短，便是希尔排序想要的。希尔排序的思想是：重复对序列进行不同子序列的划分并实施插入排序，最后对整个序列进行...

Posted by Starrk的小屋 on April 1, 2020

使用docker搭建文件服务器

简介因为有些敏感软件难以随时搜索，从外网下载限于垃圾宽带异常的便秘。想想还是有做个简单文件服务器的必要。这里使用docker方便快捷，web服务器选择nginx。搭建流程首先使用docker 拉去镜像。 docker pull nginx:latest 建立文件服务器目录在主文件目录下建立 nginx-docker 文件夹，在该文件夹下创建 file-store ...

Posted by Starrk的小屋 on March 20, 2020

排序算法（上）

冒泡算法冒泡算法简介冒泡算法是种直观而又简单的算法，给定一组共有n个元素的序列，对序列中的每个相邻元素进行比较，若右边的大于左边则进行交换。在第一轮遍历后，序列中最大的元素会被置于末尾。总共遍历n-1轮。对于有n个元素的序列，冒泡算法总共需要进行遍历序列：n + n-1 + n-2 + …. + 1 = \(\frac{(n+1)n}{2}\) 对于最好的情况，当序列都为...

Posted by Starrk的小屋 on February 10, 2020

洗牌算法

洗牌算法的背景洗牌算法（Fisher-Yates shuffle) 由Ronald Fisher 和 Frank Yates 提出，他解决的问题为给定一些元素，如何等概率的生成一个序列。打个比方，扑克牌有54张牌，那么共有54！种排序方法，如何等概率的挑选其中的一种了？如果使用哈希表的方法，需要花费的空间复杂度为O(n!)，这肯定是不能容忍的。洗牌算法的思想洗牌算法巧妙的将等概率...

Posted by Starrk的小屋 on February 2, 2020

Nachos系统调用实现

Nachos系统调用 Nachos 只有一些系统调用，同时诸如 exec 、join等系统调用还不完全，需要用户自己去编写。本文目标是编写一个新的系统调用，参照加法的系统调用编写出乘法和除法的系统调用。新的系统调用的实现 test目录下的修改进入 code/test目录，编写一个C程序，模仿add.c，命名为test.c 样例如下：这是等会进行编译测试的程序，Mul和Di...

Posted by Starrk的小屋 on July 2, 2019

Nachos交叉编译器安装

MIPS 介绍 Nachos 模拟了一个MPIS架构的硬件。在进行Nachos上进行用户程序编译执行时需要使用到交叉编译，将原MPIS下的coff可执行程序转化为Nachos能执行的noff程序。交叉编译器的安装默认已完成了Nachos的安装，需要用到Nachos的mips的交叉编译包： mips-decstation.linux.tgz。首先将 mips-decstation...

Posted by Starrk的小屋 on June 25, 2019

Nachos 安装

何为Nachos 它是一个教学用的操作系统平台，运行在宿主机上，通过编译即可运行。它的源码大部分由C和C++组成，涉及少量的汇编。因为是教学使用，源码中有大量注释，方面理解，同时源码也并不复杂。 Nachos已经搭建好了操作系统框架，包括：线程、系统调用、内存管理等等。但是并不完善，诸如线程只能使用4个，内存默认是没有启用TLB快表。这些不完善的地方便是需要自己去学习，扩展，提升的地方。 N...

Posted by Starrk的小屋 on June 18, 2019