logo
ZhangKeyaoo
banner
NEWS LETTER

5-磁盘

Scroll down

COA5 磁盘

  • 外部存储器——磁盘的模拟。
  • 工作主要集中在模拟磁头结构
  • Disk.java # 磁盘类，需要修改
  • Scheduler.java # 磁盘调度算法类，需要修改
  • 注：磁盘存储容量 ＝ 磁头数 × 磁道(柱面)数 × 每道扇区数 × 每扇区字节数
  • 读写方法中接收的addr参数，是二进制表示的该数据起始位置在虚拟磁盘文件中的字节数
  • seek方法表示每次数据读写之前将磁头移动到指定位置，addPoint表示将磁头往后移动一个字节

一、 Disk

  • 结合read和write方法的源码，理解seek方法和addPoint方法在其中起到什么作用，然后实现这两个方法。
  • 注意，由于我们规定该磁盘有8个磁头即8个盘面，所以每个盘面的大小为8MB。在不同盘面上，磁头的位置都是相同的（具体可以看ppt上的图）。因此，在我们的模拟规则下，第0个字节、第8MB个字节、第16MB个字节（以此类推），它们的磁头位置都应该是相同的。

1. seek

  • 用来将磁盘的指针移动到指定的 addr 地址
  1. 将指针point移动到start位置
  2. 计算start所在的扇区数——指针sector
    • 当前字节数 / 每扇区字节数
  3. 计算start所在的磁道数——指针track
    • 当前扇区数 / 每磁道扇区数
1
2
3
this.point=start;
this.sector=start/BYTE_PER_SECTOR;//起始点/每扇区字节数，得start对应的总扇区数
this.track=this.sector/SECTOR_PER_TRACK;//总扇区数/每磁道扇区数，得到磁道数

2. addPoint

  1. 将磁头往后移动一个字节,point++。
  2. 如果指针移动到当前扇区的末尾（512字节），则重置point为0，并移动到下一个扇区。
    • point=0
    • sector++
  3. 如果扇区移动到当前磁道的末尾（64个扇区），则重置扇区并移动到下一个磁道。
    • sector=0
    • track++
  4. 如果磁道移动到磁盘的末尾（磁道数），则重置磁道号为0，即磁头回到磁盘的起始位置。
    • track=0;
1
2
3
4
5
6
7
8
9
10
11
12
 this.point++;
if(this.point==512){
    this.point=0;
    this.sector++;
}
if(this.sector==64){
    this.sector=0;
    this.track++;
}
if (this.track == TRACK_NUM) {//如果磁道号等于【磁道数】，则重置磁道号为0，即磁头回到磁盘的起始位置
    this.track = 0;
}

二、Scheduler

  • 每个方法都会传入磁头初始磁道号与请求访问的磁道号数组
  • 需要计算出平均寻道长度并返回

1.先来先服务算法FCFS

  • 先请求的先进行
  1. 初始化
    • 总路程为0
    • 当前磁道号为start
  2. 遍历整个request
    • 总路程累加
    • 当前磁道号变化
  3. 最后返回 总路程 / 请求length
1
2
3
4
5
6
7
8
9
10
public double FCFS(int start, int[] request) {
    //TODO
    int sumdistance=0;
    int currentTrack=start;
    for(int i=0;i<request.length;i++){
        sumdistance+=Math.abs(request[i]-currentTrack);
        currentTrack=request[i];
    }
    return (double)sumdistance/request.length;
}

2.最短寻道时间优先算法 SSTF

  • 优先处理起始位置与当前磁头位置最接近的读写任务
  1. 初始化
    • sumDistance：总寻道距离，初始为0。
    • currentTrack：当前磁头所在的磁道号，初始为 start。
    • n：请求数组的长度。
    • visited：记录每个请求是否被访问过，初始为 false。
  2. 遍历请求：
    • 外层循环：遍历 n 次，每次找到一个最接近当前磁头位置的请求。
    • 内层循环：遍历所有请求，找到距离当前磁头位置最近且未被访问过的请求。
  3. 更新状态：
    • 标记找到的请求visited为true。
    • 累加最短距离到 sumDistance。
    • 更新 currentTrack 为找到的请求位置。
  4. 返回平均寻道长度：
    • 返回 sumDistance 除以请求数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public double SSTF(int start, int[] request) {
    //TODO
    int sumDistance = 0;
    int currentTrack = start;//当前磁头所在的磁道号
    int n = request.length;
    boolean[] visited=new boolean[n];//是否访问过
    
    for (int i=0;i<n;i++){
        int closest = -1;//最接近当前磁头位置的请求 下标
        int minDistance = Integer.MAX_VALUE;//每一次先初始化为最大值
        for(int j=0;j<n;j++){//遍历找最短距离
            if(!visited[j]&&Math.abs(currentTrack-request[j])<minDistance){//没被访问过+距离最近
                minDistance=Math.abs(currentTrack-request[j]);
                closest=j;
            }
        }
        //找到，更新
        visited[closest]=true;
        sumDistance+=minDistance;
        currentTrack=request[closest];
    }
    return (double)sumDistance/request.length;
}

3. 扫描算法 SCAN

  • 总是按照一个方向进行磁盘调度，直到该方向上的边缘，然后改变方向
  • 磁道总数，这个数字需要与Disk类中的TRACK_NUM保持一致。（256）
  • Arrays.sort(request); 对请求数组进行升序排序
  1. 初始化：
    • sumDistance：总寻道距离，初始为0。
    • n：请求数组的长度。
    • 对请求数组进行升序排序：Arrays.sort(request);。
  2. 判断初始移动方向：(题上说了true是增大方向)
    1. 如果 direction 为 true，表示初始移动方向是增大方向。
      • start <= request[0]，表示磁头在最小请求之前，直接移动到最大请求位置。
        • 易错：不是直接移动到磁道最后！
      • start 在请求数组中间，先移动到磁道最大位置(255)，再返回到最小请求位置。
    2. 如果 direction 为 false，表示初始移动方向是减小方向。
      • start >= request[n - 1]，表示磁头在最大请求之后，直接移动到最小请求位置。
      • start 在请求数组中间，先移动到磁道最小位置，再返回到最大请求位置。
  3. 返回平均寻道长度：
    • 返回 sumDistance 除以请求数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double SCAN(int start, int[] request, boolean direction) {
    //TODO
    int sumDistance = 0;
    int n = request.length;
    Arrays.sort(request);//升序

    if(direction){//初始移动方向是增大方向
        if(start<=request[0]){
            sumDistance+=request[n-1]-start;
        }else{//在中间
            sumDistance+=(255-start)+(255-request[0]);
        }
    }else{//初始移动方向是减小方向
        if(start>=request[n-1]){
            sumDistance+=start-request[0];
        }else{
            sumDistance+=start+request[n-1];
        }
    }
    return (double)sumDistance/n;
}

4. C-SCAN算法：默认磁头向磁道号增大方向移动

  • 只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不做任何处理
  1. 初始化
    • sumDistance：总寻道距离，初始为0。
    • currentTrack：当前磁头所在的磁道号，初始为 start。
    • n：请求数组的长度。
    • 对请求数组进行升序排序：Arrays.sort(request);。
  2. 查找当前磁头位置：
    • 使用 Arrays.binarySearch(request, currentTrack) 查找当前磁头位置在请求数组中的索引。
    • 如果未找到，计算当前磁头位置应该插入的位置：index = -index - 1。
  3. 初始移动方向是增大方向：
    • 如果 start <= request[0]，表示磁头在最小请求之前，直接移动到最大请求位置。
    • 如果 start 在请求数组中间或者右边，先移动到磁道最大位置，再返回到起点，然后移动到start前一个位置。
      • 易错：路径记得加上磁道最右到最左距离！
  4. 返回平均寻道长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double CSCAN(int start,int[] request){
    //TODO
    int sumDistance = 0;
    int n = request.length;
    int currentTrack = start;//当前磁头所在的磁道号
    Arrays.sort(request);//升序

    int index = Arrays.binarySearch(request, currentTrack);//查找当前磁头位置在请求中的索引
    if(index<0){//如果当前磁头位置不在请求中
        index = -index-1;//计算当前磁头位置应该插入的位置
    }

    //初始移动方向是增大方向
        if(start<=request[0]){
            sumDistance+=request[n-1]-start;
        }else{//在中间 或者 右边
            sumDistance+=(255-start)+255+(request[index-1]);
        }

    return (double)sumDistance/n;
}

5.LOOK算法

  • SCAN算法的升级，只要磁头移动方向上不再有请求就立即改变磁头的方向
  1. 初始化：
    • sumDistance：总寻道距离，初始为0。
    • n：请求数组的长度。
    • 对请求数组进行升序排序：Arrays.sort(request);
  2. 查找当前磁头位置：
    • 使用 Arrays.binarySearch(request, start) 查找当前磁头位置在请求数组中的索引。
    • 如果未找到，返回一个负数，该负数的绝对值减一即为start 应该插入的位置。
      • 计算当前磁头位置应该插入的位置：index = -index - 1。
  3. 判断初始移动方向：
    1. 如果 direction 为 true，表示初始移动方向是增大方向。
      • 从 index 开始向右遍历请求数组，累加距离。
        • sumDistance += Math.abs(currentTrack - request[i]);
      • 然后从 index - 1 开始向左遍历请求数组，累加距离。
    2. 如果 direction 为 false，表示初始移动方向是减小方向。
      • 从 index - 1 开始向左遍历请求数组，累加距离。
      • 然后从 index 开始向右遍历请求数组，累加距离。
  • 返回平均寻道长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public double LOOK(int start,int[] request,boolean direction){
    //TODO
    int sumDistance = 0;
    int n = request.length;
    Arrays.sort(request);//升序

    int index = Arrays.binarySearch(request, start);//查找当前磁头位置在请求中的索引
    if(index<0){//如果当前磁头位置不在请求中
        index = -index-1;//计算当前磁头位置应该插入的位置
    }

    if(direction){//初始移动方向是增大方向
        for (int i = index; i < n; i++) {
            sumDistance += Math.abs(start - request[i]);
            start = request[i];
        }
        for (int i = index - 1; i >= 0; i--) {
            sumDistance += Math.abs(start - request[i]);
            start = request[i];
        }
    }else{//初始移动方向是减小方向
        for (int i = index-1; i >=0; i--) {
            sumDistance += Math.abs(start - request[i]);
            start = request[i];
        }
        for (int i = index;  i <n; i++) {
            sumDistance += Math.abs(start - request[i]);
            start = request[i];
        }
    }
    return (double)sumDistance/n;
}

6.C-LOOK算法

  • 默认磁头向磁道号增大方向移动
  • C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回起点
  1. 初始化
    • sumDistance：总寻道距离，初始为0。
    • currentTrack：当前磁头所在的磁道号，初始为 start。
    • n：请求数组的长度。
    • 对请求数组进行升序排序：Arrays.sort(request);。
  2. 查找当前磁头位置：
    • 使用 Arrays.binarySearch(request, currentTrack) 查找当前磁头位置在请求数组中的索引。
    • 如果未找到，计算当前磁头位置应该插入的位置：index = -index - 1。
  3. 初始移动方向是增大方向：
    • 从 index 开始向右遍历请求数组，累加距离。
    • 然后从 0 开始向右遍历到 index - 1，累加距离。
  4. 返回平均寻道长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public double CLOOK(int start,int[] request){
    //TODO
    int sumDistance = 0;
    int n = request.length;
    int currentTrack = start;//当前磁头所在的磁道号
    Arrays.sort(request);//升序

    int index = Arrays.binarySearch(request, currentTrack);//查找当前磁头位置在请求中的索引
    if(index<0){//如果当前磁头位置不在请求中
        index = -index-1;//计算当前磁头位置应该插入的位置
    }

    //初始移动方向是增大方向
    for (int i=index;i<n;i++){
        sumDistance+=Math.abs(currentTrack-request[i]);
        currentTrack=request[i];
    }
    for(int i =0;i<=index-1;i++){
        sumDistance+=Math.abs(currentTrack-request[i]);
        currentTrack=request[i];
    }

    return (double)sumDistance/n;
}

If you like my blog, you can approve me by scanning the QR code below.

Other Articles
cover
计算机组织与结构
6-虚拟存储器
  • 25/02/22
  • 15:45
  • 3.7k
  • 14
cover
计算机组织与结构
4-cache
  • 25/02/22
  • 15:44
  • 1.9k
  • 8
你走过的弯路，都是通向正轨的必经之路。
Article table of contents TOP
  1. 1. COA5 磁盘
  2. 2. 一、 Disk
    1. 2.1. 1. seek
    2. 2.2. 2. addPoint
  3. 3. 二、Scheduler
    1. 3.1. 1.先来先服务算法FCFS
    2. 3.2. 2.最短寻道时间优先算法 SSTF
    3. 3.3. 3. 扫描算法 SCAN
    4. 3.4. 4. C-SCAN算法：默认磁头向磁道号增大方向移动
    5. 3.5. 5.LOOK算法
    6. 3.6. 6.C-LOOK算法
Please enter keywords to search
  • to close