重点

处理器调度的分类和对应内容。上下文。作业调度和进程调度算法,重点注意MFQ。

基本概念

处理器调度划分为3个层次:高级调度、中级调度和低级调度。
用户作业从提交给系统开始,直到运行结束退出系统为止,将经历高级调度、中级调度和低级调度。

高级调度

将用户提交的作业分配到就绪队列。是从硬盘到内存。是对作业的调度。

中级调度

是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。
它根据需要确定被挂起的进程,并在有进程被挂起时确定哪个进程进入内存。

低级调度

低级调度又称为进程调度、短程调度。是从内存到处理器。
它确定就绪进程哪个被执行。

进程调度的基本机制

  1. (一个或多个)就绪队列
  2. 分派程序。将根据进程调度算法将所选中的进程从就绪队列中移出,然后进行进程的上下文切换,并将处理器分配给京城。
  3. 上下文切换机制。实现进程的上下文切换。

上下文

操作系统内核使用一种称为上下文切换的较高层形式的控制流来实现多任务。
内核为每一个进程维持一个上下文。

上下文就是内核重新启动一个被抢占的进程所需的状态。他有一些对象的值组成,这些对象包括:  

  • 各个寄存器
  • 程序计数器
  • 用户栈
  • 内核栈
  • 各种内核数据
    比如描绘地址空间的页表,包含有
Read the rest

重点

进程和线程的各个状态,以及相互的切换。进程的组成,PCB的组织形式。

进程

进程的定义

程序的一次执行过程。

进程的特征

  • 结构性
  • 并发性
  • 独立性

进程的基本状态

进程的三个基本状态分别是:就绪状态、运行状态和阻塞状态。

  • 就绪状态
    进程在内存中已经具备执行条件,等待分配处理器。多个处于就绪状态的进程可以以队列方式组织,称为就绪队列。
  • 运行状态
    进程已经被分配处理器,并且正在执行。在单处理器系统中,一个时刻只有一个进程处于运行状态。

  • 阻塞状态
    当正在运行的程序由于等待某事件的完成而不能继续执行,便转换到阻塞状态。

完整的状态:加上创建、结束和挂起

挂起是把内存中暂时不能或不需要运行的进程从内存换到外存。其和阻塞的区别在于阻塞是应用程序主动的,而挂起是操作系统执行的。

挂起的原因:
1. 系统资源的需要
2. 解决竞争或消除故障
3. 终端用户暂停程序运行
4. 父进程暂停
5. 定期执行的程序在空闲时间

进程的描述

进程包括进程控制块(PCB)、程序块、数据块和系统堆栈。

我们使用进程控制块来描述进程相关参数。其具有如下信息:
1. 进程标志信息 PID
2. 计算机状态信息
3. 进程调度信息
4. 进程控制信息

进程控制块的组织形式分为链接方… Read the rest

前言

我之前在学习操作系统这门课程时就在OneNote上做了总结。现在将它们传到网上,以供需要的人参考学习。使用的教程为刘循的《计算机操作系统》。

重点

操作系统的五大功能、三个特征和批处理、分时、实时三种系统。

计算机的组织结构决定了计算机中信息传送的速度和计算机的性能。
operating system mindmap

操作系统的作用:

  • 直接位于计算机硬件之上,为计算机的应用提供接口(图形、命令、程序)
  • 提供通用的计算机服务,与专用的应用领域无关
  • 实现资源管理策略,为不同的应用提供共享资源

操作系统的定义:

计算机系统中一组控制和管理计算机硬件资源和软件资源,合理地对各类作业进行调度,以方便用户使用的程序的集合。

使用操作系统的目的:

  • 有效地管理计算机资源
  • 方便用户使用计算机资源
  • 扩大计算机功能(如虚拟机)
  • 构筑开放环境(可拓展性)

操作系统的功能:

1. 处理器管理

  1. 进程和线程的描述与控制
  2. 处理器调度
    处理器分为三级调度:作业调度、中级调度和进程调度。
  3. 进程或线程的同步与互斥
  4. 死锁的检测和预防
  5. 进程之间及线程之间的通信

2. 存储器管理(内存管理)

  1. 内存规划、分配及地址映射
  2. 内存保护
  3. 内存扩充

3. 输入输出设备管理

  1. 输入输出设备控制
    主要方式有程序控制方
Read the rest

前言

Java中引用是一个最常用的Object,我们有必要对它有一个基本的理解。而且引用通常出现在一本Java书的开头,这导致,几乎没有Java书敢详细地叙述关于引用的复杂机制。本文剖析了Java的四种引用。

注意,理解这四种引用需要明白:什么是对象,什么是引用。一定注意叙述中的“对象”和“引用”。

本文没有涵盖的内容:

  1. JVM内存管理。
  2. 参数传递过程
  3. 引用的生存周期和finalize()方法
  4. 软引用和弱引用的应用
  5. 常量池中的符号引用

引用和内存管理、参数传递过程都有密切的关系,本文并不探讨引用的引用计数算法、可达性分析等涉及过多内存管理的内容,也不探讨参数传递过程,以免顾此失彼,用力不均。
至于引用的生存周期和finalize()方法,限于篇幅,也不讲解。感兴趣的读者可以见参考文献5。
对软引用和弱引用的应用感兴趣的读者见参考文献4。

如果想深入了解Java的参数传递过程,戳:TBC。

什么是对象

对象是类的实例。
Person person = new Person("张三");
这里new出来(等号右边)的就是一个对象。

什么是引用(reference)

还是刚刚的代码为例
Person person = new Person("张Read the rest

前言

单调栈和单调队列算是栈和队列的高级应用吧,在公司面试中应该是不怎么会出现的(除非算法岗?)。
因为原理比较简单,网络上的相关资料反而对于这两个东西说得都不甚清楚,尤其是它们的应用方法。最基本的两本中文算法书“紫书”和“白皮”都没有提到。

而我因为平日要做的事情也很多,仓促中写下的这篇文章难免表达上会有不清晰的地方和各种疏漏,希望读者不吝赐教=v=。

栈和队列这两种基础数据结构戳:TBC。

先说明一下,无论是栈还是队列,我们把元素进入的一端称作“尾部”,并用双引号标出,另一端称作“尾部”。对于栈,头部即是栈底,尾部即是栈顶。对于队列,头部对应队首,尾部对应队尾。

monotone queue and stack

注:我不确定单调队列是否翻译成monotone queue,算法导论上没有提到这个数据结构,Bing上也没有搜索到对应它的结果(倒是返回了关于优先队列的结果)。

单调栈

我们都已经非常熟悉栈了,它具有先入后出的性质。而单调栈为了满足单调的要求,增加了一个性质:

  • 从栈顶到栈底的元素是严格递增(or递减)

显然,这和我们的正常的流程有一定矛盾之处——如果栈中是5 4 3 2 1,如果压入3怎么办?
原来我们只需要添加到栈尾即可,现在则需要将3 2 1弹出,再… Read the rest

为什么要使用树状数组

比如说,我这里有一组数1, 2, 3, 2, …, k。我想知道第i到第j的和\(\mathop \sum \limits_{n = i}^j v[i]\)是多少?

朴素算法:

for (int k = 0; k < n; k++)
    if (k >= i && k <= j) ans += v[k];

类似这种的写法,虽然在某些点值改变时也依然可以计算(我们称这种问题为动态问题),但复杂度最高到O(n),实在难以接受。

树状数组是通过前缀和思想,用来完成单点更新和区间查询的数据结构。它比之线段树,所用空间更小,速度更快,而且编程的复杂难度也大大减小。和ST相比,它可以动态更新数据。

前缀和

我们可以把查询区间和问题转化为前缀和问题。
前缀和是指:v[1]~v[i]的和,记作sum(i)。

如果我们能够计算s和t的前缀和,用sum(t)−sum(s−1)可以得到区间[s, t]的和。

而树状数组正是一个支持求前缀和的数据结构。

什么是树状数组

(如果你学过线段树,可以先从最后“树状数组的缺陷”看起,树状数组的灵感来源脉络会更加清晰)
Binary Indexed Tree
我们依据二进制的思想,让”为1的最低位”在第一位的数(即奇数),储存长度为1的区间和… Read the rest

前言

本文略去的内容:

  • Java异常简介
    Java异常是Java提供的一种识别及响应错误的机制。
  • 异常处理的基本语法
    try…catch…finally和throw、throws。

这些内容几乎在每一篇参考文献中都有详细的讲解。如果你想先了解关于异常的基础知识,随便挑一篇看就好,它们都是优秀的文章(虽然有的细枝末节存在错误,这也是本文存在的原因之一)。

另外一个原因就是,我想写一个足够全面的总结。

在这里,我先明确一下“处理异常”这个词的意思。它指的是:要么用try-catch捕获处理,要么throws。当然,最好避免直接throws,而是声明throws后依然catch,最后再throw。

Java异常的分类

Java异常的类间关系

Java exception class relationship

  1. Throwable
    Throwable是Java语言中所有错误或异常的超类,它有两个直接子类Error / Exception。
    只有当对象是此类(或其子类之一)的实例时,才能通过 Java虚拟机或者throw语句抛出。类似地,只有此类或其子类之一才可以是catch子句中的参数类型。
    Throwable包含了其线程创建时线程执行堆栈的快照,
Read the rest

Update 04.28.2019:重构了本文的逻辑结构,修改了失效的链接

Jupyter Notebook

Jupyter Notebook是一个交互式笔记本,支持运行 40 多种编程语言。它对于希望编写漂亮的交互式文档的人来说是一个强大工具。

划重点: 支持python、交互式文档。

本文的目的是详细地说明Jupyter Notebook安装过程中可能遇到的问题,保证读者在阅读完本文后能够打开在任何目录下、以.ipynb为后缀的任意Jupyter Notebook文件。
具体如何使用Jupyter Notebook,教程见Jupyter Notebook 快速入门
对于代码无法运行,缺少相关库的问题,见“Anaconda/conda使用指南”(TBC)

背景

因为我大一的时候安装了Enthought Canopy(用它的python.exe作为PyCharm内核),所以一直用的是Canopy来打开.ipynb。

但是因为Canopy的Python版本是Python2.7,加上numpy官方宣布某个时间点后不再支持Python2.7,所以打算… Read the rest

A. Scarborough Fair

多次区间修改字符串
解法:朴素暴力

#include <bits/stdc++.h>
using namespace::std;

string str, s;
int n, m, x, y;

int main() {
    //ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef LOCAL
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    #endif
    cin >> n >> m;
    cin >> str;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        x--, y--;
        cin >> s[0] >> s[1];
        for (int j = x; j <= y; j++) {
            if (str[j] == s[0]) str[j] = s[1];
        }
    }
    cout << str << endl;
    return 0;
}

B. Chtholly’s request

偶数位回文数
解法:利用高n/2位构造回文数

#include <bits/stdc++.h>
Read the rest

为什么用快速幂

对于求解\({a^b}\)的问题,我们能想到的朴素算法:

int ans = 1;
for (int i = 0; i < b; i++)
    ans *= a;

而快速幂可以在O(logn)时间内解出。

什么是快速幂

先举一个例子,我们计算\({5^8}\)只需要3步,即分别求得\({5^2}\)、\({5^4}\)、\({5^8}\)。
因为每次相乘,幂次都增长一倍,我们只需要logn次就可以让幂逼近n。

所以,我们可以将b通过二进制分解为形如10011的数,则\({\rm{b}} = {2^{k1}} + {2^{k2}} + {2^{k3}} \ldots \)。
因为\({a^{{2^{k1}}}}\)到\({a^{{2^{kmax}}}}\)可以通过\({a^{{2^1}}}\)、\({a^{{2^2}}}\)\({a^{{2^3}}}\)这样在递推kmax次中得到,所以\({a^b} = {a^{{2^{k1}}}} * {a^{{2^{k2}}}}\)可以在O(lo… Read the rest