オペレーティングシステムのダイナミックパーティション割り当て

概要
本プログラムはjavaプログラミング言語を用いて実現した.ソースの移行:http://download.csdn.net/download/chengshijian2015/10215534
げんり
可変パーティションスケジューリングアルゴリズムには、最初に適応分配アルゴリズム、最適適応分配アルゴリズム、最悪適応アルゴリズムがある.ユーザーはメモリ空間の申請を提出した.システムは申請者の要求に基づいて、一定の分配戦略に従ってメモリ空間の使用状況を分析し、要求を満たす空き領域を探し出し、申請者に分ける.プログラムの実行が完了したり、メモリリソースをアクティブに返却したりすると、システムはメモリ領域または返却されたメモリ領域の一部を回収します.プロセスが作成されるたびに、メモリ割り当てプログラムはまず空きメモリパーティションテーブル(チェーン)を検索し、そこから適切な空きブロックを探して分割し、空きメモリパーティションテーブル(チェーン)を変更します.プロセスの実行が完了してメモリを解放すると、システムは回収領域の最初の場所に基づいて、空き領域テーブル(チェーン)から対応する挿入点を見つけ、この時以下の4つの状況が現れる:1)回収領域は挿入点の前の空き領域F 1に隣接し、この時回収領域を直接F 1と合併し、F 1の大きさを修正することができる;2)回収領域は挿入点の後の空きパーティションF 2に隣接しており、この場合、回収領域を直接F 2にマージし、回収領域の先頭アドレスが最も新しい空き領域の先頭アドレスであり、大きさは両者の和である.3)回収区は同時に挿入点の前、後の二つの空き区分と隣接しており、この時三者を合併する必要がある.4)回収エリアはいずれの空きエリアにも隣接していない.この時、新しい表項目を作る.ソースコード:DynamicPartAllocate.java:

package com.csi.operatesystem;

import java.util.Scanner;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 */

public class DynamicPartAllocate {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("  1503      1511030304");
        final Scanner scanner = new Scanner(System.in);
        new DynamicPartAllocatePresenter().setOnExcuteLisenter(new OnExcuteLisenter() {
            @Override
            public Job getJob() {
                // TODO Auto-generated method stub
                while (true) {
                    System.out.print("     （            ）>");
                    Job job = new Job();
                    int id = scanner.nextInt();
                    if (id < 1) {
                        System.out.println("       0!");
                        continue;
                    }
                    int length = scanner.nextInt();
                    job.setJobId(id);
                    job.setLength(length);
                    return job;
                }
            }

            @Override
            public void onOutOfMemory() {
                // TODO Auto-generated method stub
                System.out.println("      ！");
            }

            @Override
            public void onAllocateSuccess(Partition partition) {
                // TODO Auto-generated method stub
                System.out.println("----------------------------      ------------------------------");
                System.out.println(
                        "                                                                                                                                 ");

                for (PartBlock block : partition.getBlocks()) {
                    System.out.printf("%-15d%-15d%-15d%-30s%-15s
", block.getStartAddress(), block.getEndAddress(),
                            block.getLength(), block.getState(), block.getJobId()==0?"":String.valueOf(block.getJobId()));
                }
                System.out.println("------------------------------------------------------------------");
            }

            @Override
            public int getJobId() {
                // TODO Auto-generated method stub
                System.out.print("     id>");
                return scanner.nextInt();
            }

            @Override
            public void onSearchError(int id) {
                // TODO Auto-generated method stub
                System.out.println("  " + id + "   ！      ！");
            }

            @Override
            public void onRetrieveSuccess(Partition partition) {
                // TODO Auto-generated method stub
                System.out.println("----------------------------      ------------------------------");
                System.out.println(
                        "                                                                                                                                 ");

                for (PartBlock block : partition.getBlocks()) {
                    System.out.printf("%-15d%-15d%-15d%-30s%-15s
", block.getStartAddress(), block.getEndAddress(),
                            block.getLength(), block.getState(), block.getJobId()==0?"":String.valueOf(block.getJobId()));
                }
                System.out.println("------------------------------------------------------------------");
            }

            @Override
            public int onGetMethod() {
                // TODO Auto-generated method stub
                System.out.println("0.                 1.                2.        ");
                System.out.print("       >");
                switch (scanner.nextInt()) {
                case 0:
                    return DynamicPartAllocatePresenter.FIRST_FIT;
                case 1:
                    return DynamicPartAllocatePresenter.BEST_FIT;
                case 2:
                    return DynamicPartAllocatePresenter.BAD_FIT;

                default:
                    return -1;
                }
            }

            @Override
            public int onGetOperate() {
                // TODO Auto-generated method stub

                System.out.println("0.           1.           2.  ");
                System.out.print("   >");
                switch (scanner.nextInt()) {
                case 0:
                    return DynamicPartAllocatePresenter.ALLOCATE;
                case 1:
                    return DynamicPartAllocatePresenter.RETRIVE;
                case 2:
                    System.exit(0);
                    break;
                }
                return -1;

            }
        }).excute();
    }
}

DynamicPartAllocatePresenter.java:

package com.chengshijian.operatesystem;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 *     ，                    
 */
public class DynamicPartAllocatePresenter {

    public static final int FIRST_FIT = 0;//      
    public static final int BEST_FIT = 1;//      
    public static final int BAD_FIT = 2;//      
    public static final int ALLOCATE = 3;//  
    public static final int RETRIVE = 4;//  

    private Partition partition = new Partition();//  
    private int method;//  
    private int operate;//  ，       
    private boolean isAllocateSuccess = false;//      
    private boolean isSearchSuccess = false;//      

    private OnExecuteLisenter lisenter;//       

    //  ．    
    //                     ，                     。
    //  ．    
    //          :        ,        ,      。
    //            ；          ，                    ，
    //            ，     ；                 ，                         。
    //           ，                  （ ），                ，
    //           （ ）。            ，          ，     （ ）         ，          ：
    // 1)                F1   ，          F1  ，   F1   ；
    // 2)                F2   ，          F2  ，                 ，       ；
    // 3)            、         ，        ；
    // 4)               ，         。
    //  ．    
    //                 。     ：      ，    ，               ，         ，
    //            ，               （ ）             。

    public DynamicPartAllocatePresenter setOnExcuteLisenter(OnExecuteLisenter lisenter) {
        this.lisenter = lisenter;
        return this;
    }

    public DynamicPartAllocatePresenter setOperate(int operate) {
        this.operate = operate;
        return this;
    }

    public int getMethod() {
        return method;
    }

    public void setMethod(int method) {
        this.method = method;
    }

    //  
    private void retrieve() {
        int id = lisenter.getJobId();//     
        int index = 0;//      Block   0
        for (int i = 0; i < partition.getBlocks().size(); i++) {
            PartBlock block = partition.getBlocks().get(i);
            if (block.getJobId() == id) {
                index = i;
                isSearchSuccess = true;
                break;
            }
        }
        if (isSearchSuccess) {//      
            List blocks = partition.getBlocks();
            sortByAddress(blocks);//                   
            PartBlock block = partition.getBlocks().get(index);
            block.setState(Partition.NOT_ALLOCATE);
            block.setJobId(0);
            PartBlock afterBlock = null;
            PartBlock beforeBlock = null;
            int originalBlockSize=blocks.size()-1;//                 

            if (index != 0) {
                beforeBlock = blocks.get(index - 1);//      
            }
            if (index != blocks.size() - 1) {
                afterBlock = partition.getBlocks().get(index + 1);//      
            }
            //    
            if (index != 0) {
                sortByAddress(partition.getBlocks());
                if (beforeBlock.getState().equals(Partition.NOT_ALLOCATE)) {
                    block.setStartAddress(beforeBlock.getStartAddress());
                    block.setLength(beforeBlock.getLength() + block.getLength());
                    block.setEndAddress(block.getStartAddress() + block.getLength());
                    blocks.remove(beforeBlock);
                }
            }
            //    
            if (index != originalBlockSize) {
                if (afterBlock.getState().equals(Partition.NOT_ALLOCATE)) {
                    block.setLength(afterBlock.getLength() + block.getLength());
                    block.setEndAddress(block.getStartAddress() + block.getLength());
                    blocks.remove(afterBlock);
                }
            }
            lisenter.onAllocateSuccess(partition);//     
            isSearchSuccess=false;
        } else {
            lisenter.onSearchError(id);//     
        }
    }

    //  
    private void allocate() {
        Job job = lisenter.getJob();//      
        for (PartBlock block : partition.getBlocks()) {
            if (block.getLength() >= job.getLength() && block.getState().equals(Partition.NOT_ALLOCATE)) {//                        
                PartBlock newBlock = new PartBlock();
                newBlock.setJobId(job.getJobId());
                newBlock.setLength(job.getLength());
                newBlock.setStartAddress(block.getStartAddress());
                newBlock.setState(Partition.HAVE_ALLOCATE);
                newBlock.setEndAddress(newBlock.getStartAddress() + newBlock.getLength());
                block.setStartAddress(block.getStartAddress() + job.getLength());
                block.setLength(block.getLength() - job.getLength());
                partition.getBlocks().add(newBlock);
                isAllocateSuccess = true;
                break;
            }
        }

        if (!isAllocateSuccess) {
            lisenter.onOutOfMemory();//     
        } else {
            sortByAddress(partition.getBlocks());//        
            lisenter.onAllocateSuccess(partition);//     
            isAllocateSuccess = false;
        }
    }

    //      
    public void allocteByFirstFit() {
        while (true) {
            operate = lisenter.onGetOperate();
            switch (operate) {
            case ALLOCATE:
                sortByAddress(partition.getBlocks());
                allocate();
                break;
            case RETRIVE:
                retrieve();
                break;
            default:
                break;
            }
        }

    }

    //      
    public void allocteByBestFit() {
        while (true) {
            operate = lisenter.onGetOperate();
            switch (operate) {
            case ALLOCATE:
                sortByLengthDown(partition.getBlocks());
                allocate();
                break;
            case RETRIVE:
                retrieve();
                break;
            default:
                break;
            }
        }
    }

    //      
    public void allocteByBadestFit() {
        while (true) {
            operate = lisenter.onGetOperate();
            switch (operate) {
            case ALLOCATE:
                sortByLengthUp(partition.getBlocks());
                allocate();
                break;
            case RETRIVE:
                retrieve();
                break;
            default:
                break;
            }
        }
    }

    //         
    private void sortByAddress(List blocks) {
        Collections.sort(partition.getBlocks(), new Comparator() {
            @Override
            public int compare(PartBlock o1, PartBlock o2) {
                // TODO Auto-generated method stub
                if (o1.getStartAddress() > o2.getStartAddress()) {
                    return 1;
                } else if (o1.getStartAddress() < o2.getStartAddress()) {
                    return -1;
                }
                return 0;
            }
        });
    }

    //           
    private void sortByLengthDown(List blocks) {
        Collections.sort(partition.getBlocks(), new Comparator() {
            @Override
            public int compare(PartBlock o1, PartBlock o2) {
                // TODO Auto-generated method stub
                if (o1.getLength() > o2.getLength()) {
                    return 1;
                } else if (o1.getLength() < o2.getLength()) {
                    return -1;
                }
                return 0;
            }
        });
    }

    //           
    private void sortByLengthUp(List blocks) {
        Collections.sort(partition.getBlocks(), new Comparator() {
            @Override
            public int compare(PartBlock o1, PartBlock o2) {
                // TODO Auto-generated method stub
                if (o1.getLength() < o2.getLength()) {
                    return 1;
                } else if (o1.getLength() > o2.getLength()) {
                    return -1;
                }
                return 0;
            }
        });
    }

    //  ，    
    public void excute() {
        method=lisenter.onGetMethod();
        switch (method) {
        case FIRST_FIT:
            allocteByFirstFit();
            break;
        case BEST_FIT:
            allocteByBestFit();
            break;
        case BAD_FIT:
            allocteByBadestFit();
            break;
        default:
            break;
        }
    }
}

Job.java:

package com.chengshijian.operatesystem;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 *    ，        
 */
public class Job {
    private int jobId;//  id
    private int length;//    
    public int getJobId() {
        return jobId;
    }
    public void setJobId(int jobId) {
        this.jobId = jobId;
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

OnExcuteLisenter.java:

package com.chengshijian.operatesystem;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 *          
 * 
 */
public interface OnExecuteLisenter {
    Job getJob();//    
    int getJobId();//    id
    int onGetMethod();//    
    int onGetOperate();//    ，       
    void onSearchError(int id);//      ，            id     
    void onOutOfMemory();//     ，            ，          
    void onAllocateSuccess(Partition partition);//        
    void onRetrieveSuccess(Partition partition);//        
}

PartBlock.java:

package com.chengshijian.operatesystem;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 *     
 */
public class PartBlock {
    private int startAddress;//    
    private int endAddress;//    
    private int length;//     
    private String state;//     ，        
    private int jobId;//  id

    public int getEndAddress() {
        return this.endAddress;
    }

    public void setEndAddress(int endAddress) {
        this.endAddress = endAddress;
    }

    public PartBlock() {
        super();
        // TODO Auto-generated constructor stub
    }

    public PartBlock(int startAddress, int length, String state) {
        super();
        this.startAddress = startAddress;
        this.length = length;
        this.state = state;
        this.endAddress=this.startAddress+this.length;
    }

    public int getStartAddress() {
        return startAddress;
    }

    public void setStartAddress(int startAddress) {
        this.startAddress = startAddress;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public String getState() {
        return state;
    }

    public void setState(String state) {
        this.state = state;
    }

    public int getJobId() {
        return jobId;
    }

    public void setJobId(int jobId) {
        this.jobId = jobId;
    }

    @Override
    public String toString() {
        return "PartBlock [startAddress=" + startAddress + ", endAddress=" + endAddress + ", length=" + length
                + ", state=" + state + ", jobId=" + jobId + "]";
    }
}

Partition.java:

package com.chengshijian.operatesystem;

/**
 * Created by ChengShiJian on 2017/11/08.
 * 
 *    ，           
 */
import java.util.ArrayList;
import java.util.List;

public class Partition {
    public static final String HAVE_ALLOCATE="   ";
    public static final String NOT_ALLOCATE="   ";

    private List blocks=new ArrayList<>();
    public int length=1000;

    public List getBlocks() {
        return blocks;
    }

    public void setBlocks(List blocks) {
        this.blocks = blocks;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public Partition() {
        super();
        // TODO Auto-generated constructor stub
        blocks.add(new PartBlock(0,length,NOT_ALLOCATE));
    }

    public Partition(int length) {
        super();
        blocks.add(new PartBlock(0,length,NOT_ALLOCATE));
    }
}