Commit f995dd6

1.共享内存 <br>

2.消息队列 <br>

3.信号 <br>

4.信号量 <br>

5.套接字 <br>

6.普通管道 <br>

7.有名管道 <br>

- 共享内存 <br>

- 消息队列 <br>

- 信号量 <br>

- 套接字 <br>

- 普通管道 <br>

- 有名管道 <br>

- 锁机制:包括互斥锁、读写锁、条件变量

* 互斥锁提供了以排他方式防止数据结构被并发修改的方法。

* 读写锁允许多个线程同时读共享数据,而对写操作是互斥的。

* 条件变量可以以原子的方式阻塞进程,直到某个特定条件为真为止。对条

- 信号量机制(Semaphore):包括无名线程信号量和命名线程信号量。

- 信号机制(Signal):类似进程间的信号处理。

Java中与线程同步有关的关键字/类包括： <br>

volatile、synchronized、Lock、AtomicInteger等concurrent包下的原子类。。。等

1.FCFS：先来先服务算法 <br>

2.SSTF：最短寻道时间算法 <br>

3.SCAN：扫描算法（也叫电梯调度算法）<br>

4.CSCAN：循环扫描算法 <br>

- FCFS：算法思想非常简单，就是不论初始磁头在什么位置，都是按照服务队列的先

后顺序依次处理进程，可以类比队列的先进先出。优点是进程处理起来非常简单，但缺点显而易见，就是平均寻道长度会很长。

- Java实现：

public class fcfs {

Scanner x=new Scanner(System.in);

public int[] position;

public int num;

public fcfs()

{

System.out.println("Enter the number of process:");

num=x.nextInt();

position=new int[num];

}

public void input()

{

int i=0;

for(i=0;i<num;i++)

position[i]=x.nextInt();

}

public void algo()

{

int i=1;

for(i=1;i<=num;i++)

System.out.println("Process Accessed "+i+" at "+position[i-1]);

}

}

- SSTF:最短寻道时间算法，算法本质是贪心，已知磁头的初始位置，则最先被处理就是距离

磁头位置最近的进程，处理完成后再处理距离当前磁道最近的进程，直到所有的进程被处理。该

算法的优点是平均寻道长度会大大减少，缺点是距离初始磁头较远的服务长期得不到处理，产生

“饥饿”现象。具体的思路是：通过循环寻找与初始磁头最近的进程，将进程处理，然后将该进程

标记为-1，将初始磁头移动到该进程所在的磁道。然后依次类推，标记为-1的进程不再参与，知

道所有的进程都被标记为-1，磁盘调度完成。

- Java实现

public class sstfAlg{

int num;

int[][] position;

int size;

int initPos;

int[] sequenceOfProcess ;//存储访问序列

int[] sequenceOfNumber;

Scanner sc = new Scanner(System.in);

public sstfAlg(int a,int b,int c){

//a means the amount of process

//b means the inital of position

//c means the size of disk

num = a;

position = new int[a][2];

sequenceOfProcess = new int[a];

sequenceOfNumber = new int[a];

initPos = b;

size = c;

}

public void input(){

System.out.println("input the number of process:");

for(int i=0;i<num;i++){

position[i][0] = sc.nextInt();

position[i][1] = i+1;

}

}

public void myAlg(){

int nearest = 10000;

int index = 0 ;

int initPos1 = initPos;

//复制一个数组用来寻找访问序列

int[][] position1 = new int[num][2];

for(int i=0 ;i<num;i++){

position1[i][0] = position[i][0];

position1[i][1] = i+1;

}

//寻找磁头访问的序列

for(int i=0;i<num;i++){

for(int j=0;j<num;j++){

if(position1[j][0]!=-1){

if(Math.abs(initPos1 - nearest)>Math.abs(position1[j][0]-initPos1)){

nearest = position1[j][0];

index = j;

}

}

}

sequenceOfProcess[i] = nearest;

sequenceOfNumber[i] = index+1;

position1[index][0] = -1;//-1表示此位置的进程已经放在了访问序列,不在进行查询

initPos1 = nearest;

nearest = 10000;

}

for(int i=0;i<num;i++){

System.out.println("进程"+sequenceOfNumber[i]+"在磁道"+sequenceOfProcess[i]+"完成");

}

}

}

- SCAN:磁头仅沿一个方向进行扫描，在扫描途中完成所有没有完成的请求，直到磁头到达磁盘在这个方向上的最后一个磁道或者这个方向上最后一个请求所在的磁道。利用数组存储进程和磁道编号，依据给定的初始磁头，先找到初始磁头在哪两个进程之间，然后向内扫描。当磁头扫描到磁盘最内层即磁道0且进程还没有全部被处理，磁头开始向外扫描，直到所有的进程都完成。

- Java实现

class scanAlgo{

Scanner sc = new Scanner(System.in);

int num; //进程数量

int[] position1;

int initPos; //磁头初始位置

public scanAlgo(){

System.out.println("input the amount of process:");

num = sc.nextInt();

position1 = new int[num+1];

System.out.println("input the initial position:");

initPos = sc.nextInt();

}

public void input(){

System.out.println("input the number of process:");

for(int i=0;i<num;i++){

position1[i] = sc.nextInt(); //记录进程所在的磁道号

}

}

public void adjust(){

//按照磁道编号将进程排序,就是一个冒泡排序

for(int i=0;i<num;i++){

for(int j=1;j<num-i;j++){

if(position1[j-1] > position1[j]){

int temp = position1[j];

position1[j] = position1[j-1];

position1[j-1] = temp;

}

}

}

}

public void algo(){

//寻找磁头初始位置在哪两个进程之间

input();

adjust();

int init;

for(init=0;init<num-1;init++){

if(position1[init] <= initPos && position1[init+1] > initPos)

break;

//此时得到的init值就是磁头初始位置

}

int start = init;

//磁头先向里扫描

for(int i=start;i>=0;i--){

System.out.println("The First Time Scan:"+"Process"+position[i][1]+"At Position"+position[i][0]+"Completed");

}

}

//磁头开始从初始位置向外扫描

if(position1[init+1]!=0){

System.out.println("This Is the Track 0");

}

for(int i=start+1;i<num;i++){

System.out.println("The Second Time Scan:"+"Process"+position[i][1]+"At Position"+position[i][0]+"Completed");

}

}

}

}

- CSCAN：在磁盘扫描算法的基础上改变磁头的扫描路径：扫描到最内层之后从最外层向内继续扫描，即扫描方向一致。

该算法的思路与扫描算法基本一致，也使用二维数组进行进程编号和进程所在磁道号的存储，算法的不同之处在于当磁

头扫描到磁盘的最内层时，磁头跳转到磁盘最外层重新向内扫描，这样就可以有效的避免将已经扫描过的磁道重新扫描

一次，降低了平均寻到距离。

- Java实现

class cscanAlg{

Scanner sc = new Scanner(System.in);

int num;

int[][] position ;

int initPos;

int size;

public cscanAlg (){

System.out.println("input the amount of process:");

num = sc.nextInt();

position = new int[num+1][2];

System.out.println("input the initial position :");

initPos = sc.nextInt();

System.out.println("input the size of Disk:");

size = sc.nextInt();

}

public void input(){

System.out.println("input the number of process:");

for(int i = 0;i<num;i++ ){

position[i][0] = sc.nextInt();

position[i][1] = i+1;

}

}

public void adjust(){//调整数组中进程的记录顺序

for(int i=0;i<num;i++){

for(int j=1;j<num-i;j++){

if(position[j-1][0]>position[j][0]){

int temp1 = position[j][0];

int temp2 = position[j][1];

position[j][0] = position[j-1][0];

position[j][1] = position[j-1][1];

position[j-1][0] = temp1;

position[j-1][1] = temp2;

}

}

}

}

public void algo(){

input();

adjust();

int init;

for(init = 0;init<num-1;init++){

if(position[init][0]<initPos && position[init+1][0]>=initPos){

break;

}

}

int start = init;

System.out.println("第一次扫描：");

for(int i=start;i>=0;i--){

System.out.println("第一次扫描："+"进程"+position[i][1]+"在磁道"+position[i][0]+"完成");

}

if(position[init+1][0]!=0){

System.out.println("磁头已经扫描到磁盘最内层:0");

}

if(position[num-1][0]!=size){

System.out.println("磁头已经移到磁盘最外层:"+size);

}

System.out.println("第二次扫描：");

for(int i=num-1;i>start;i--){

System.out.println("第二次扫描："+"进程"+position[i][1]+"在磁道"+position[i][0]+"完成");

}

}

}

FIFO、LRU、OPT 等。 <br>

这三个置换算法，或者说缓存调度算法，其实来源于操作系统的页置换算法。 <br>

FIFO：即 First In, First Out 。 <br>

LRU: Least recently used，最近最少使用算法。即是将最近最少使用的对象踢出内存。 <br>

OPT: Optimal，最优替换，也就是上帝模式。它是考虑当前内存中的对象，以及将来要放进

内存的对象，然后，将在最远的将来才被访问的页面踢出内存。所以，这个算法在转换时，需

要把将来即将放进内存的对象考虑进去，才能找到要踢出内存的对象。 <br>

一．FIFO：First In, First Out，先进先出算法

1.1 先进先出算法基本思想： <br>

淘汰最先进入的页面，选择在内存中驻留最久的页面的予以淘汰。

基本思想就是将先进入队列的页面先淘汰掉，如果该页面后期被命中，那也不将它的步数重置，

而是按照它第一次进入页面开始记步数。 <br>

1.2具体操作思想 <br>

 <br>

二. LRU: Least recently used，最近最少使用算法。即是将最近最少使用的对象踢出内存。

2.1 LRU置换算法基本思想： <br>

Lru算法和fifo最大相似点就是淘汰前向步数最大的页面，也就是淘汰页面的判断依据是该

页面的从前到后的步数统计，越大表明越是长时间为用到，所以予以淘汰替换。

单很明显是由明显区别的，那就是lru算法当遇到命中时会将该页面重置步数。 <br>

2.2具体操作思想 <br>

 <br>

三．Optimal: Optimal，最优替换，也就是上帝模式。它是考虑当前内存中的对象，以及将来要放进

内存的对象，然后，将在最远的将来才被访问的页面踢出内存。所以，这个算法在转换时，需

要把将来即将放进内存的对象考虑进去，才能找到要踢出内存的对象。 <br>

3.1 最佳置换算法基本思想：

将以后永不使用的淘汰，或者是将在最长（未来）时间内不在访问的页面淘汰。由于不能知道或预测谁是最可能永不使用或者长时间使用的页面，所以不能拿它来作为页面置换实际操作中的算法，但是可以用于评估其他算法。

（未被命中的即为“缺页”，缺页率=未命中数/总数，淘汰率=替换数/总数） <br>

3.2具体操作思想 <br>

首先有一个页面访问顺序的数列2,3,1,5,6,7,6,3,7,8,2。内存块有3个物理块。 <br>

 <br>