学习

操作系统+选择排序

Hello world,hello blog!

Posted by 吴柚 on March 15, 2019

系统调用、异常、中断

源头

  1. 系统调用：应用程序请求操作提供服务

  2. 异常：应用程序意想不到的行为

  3. 中断：外设的请求

响应

  1. 中断：持续的，对用户应用程序是透明的；

  2. 异常：杀死或者重新执行意想不到的应用程序指令；

  3. 系统调用：等待和持续

硬件：设置中断标记【CPU初始化】

  1. 将内部、外部事件设置中断标记

  2. 中断事件的ID

软件

  1. 保存当前处理状态

  2. 中断服务程序处理

3.清除中断标记

  1. 恢复之前保存的处理状态

异常：异常编号

  1. 保存现场

  2. 异常处理

  3. 恢复现场

跨越操作系统边界的开销

（1）在执行时间上的开销超过程序调用

（2）开销：

  1. 建立中断/异常/系统调用号与对应服务

  2. 例程映射关系的初始化开销

  3. 建立内核堆栈

  4. 验证应用程序发来的参数

  5. 内核态映射到用户态的地址空间

  6. 内核态独立地址空间 TLB

挂起操作的引入:

  1. 终端用户的需要，如果终端用户在程序运行期间有什么新的想法或者疑问，就想讲程序暂停执行，以便修改或者观察；

  2. 负荷调节的请求，当实时系统中的任务较重时，可能会影响到对实时任务的控制，则可由系统将一些不重要的进程挂起，以保证系统能正常运行。

调度算法

  1. 先来先服务算法

在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

  1. 短作业优先(SJF)调度算法

短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机

  1. 优先级调度算法

优先级调度算法又称优先权调度算法，该算法既可以用于作业调度，也可以用于进程调度，该算法中的优先级用于描述作业运行的紧迫程度。

  1. 时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片

动态分区分配

  1. 首次适应(First Fit)算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。

  2. 最佳适应(Best Fit)算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。

  3. 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。

  4. 邻近适应(Next Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找

选择排序

  1. 原理：1.第一次选出第一小的，放在第一位置；第二次找出第二小的放在第二位置

  2. 方法：第一个循环从0~n-1（最后一次不用排）；记录当前下标；第二个循环从下一个到结尾比较，如果比他小，并且将下标改成现在的位置。循环完再交换内容（a[i]与最小的内容）a[i]存储最小值是存储位置。

  3. 代码

#include<iostream>
using namespace std;
template<class T>
void print(T *t,int n){
	for(int i=0;i<n;i++){
		cout<<t[i]<<" ";
	}
}

template<class T>
void selectSortUp(T *p,int n){
	for(int i=0;i<n-1;i++){    //控制存储位置（0~n-1），最后一次不用进行
		int index=i;             //用于记录最小值的位置，最开始为i
		for(int j=i+1;j<n;j++){  //从i+1到结尾（n） ，用于找最小值
			if(p[j]<p[index]){     //j的内容小于当前的最小值的内容
				index=j;             //修改，记录现在最小值的位置
			}
		}
		//交换a[i]\a[index]
		T temp;//交换用临时变量
		temp=p[i];
		p[i]=p[index];
		p[index]=temp;
	}
}

template<class T>
void selectSortDown(T *a,int n){
	for(int i=0;i<n-1;i++){
		int index = i;
		for(int j=i+1;j<n;j++){
			if(a[j]>a[index]){
				index=j;
			}
		}
		//交换
		T temp;
		temp =a[i];
		a[i]=a[index];
		a[index]=temp;
	}
	
}


int main(){
	double p[]={4.2,2.3,3.1,1.1,3.1,5,7,8};
	selectSortUp(p,sizeof(p)/sizeof(double));
	print(p,sizeof(p)/sizeof(double));
	float p2[]={1,3,2,2,4.4,99.2,13.84,5,6};
	cout<<endl;
	selectSortDown(p2,sizeof(p2)/sizeof(p2[0]));  //sizeof(p2)/sizeof(p2[0])取数组长度
	print(p2,sizeof(p2)/sizeof(p2[0]));
	return 0;
}
CATALOG
    FEATURED TAGS
    二进制 学习