操作系统课程设计报告资料

1、东北大学秦皇岛分校计算机与通信工程学院操作系统课程设计设计题目OPT的模拟实现进程管理器专业名称计算机科学与技术班级学号2123509学生姓名徐泽建指导教师管莹设计时间2015.01 . 042015.01.15课程设计任务书专业：计算机科学与技术 学号：2123509 学生姓名（签名）： 实验一：必做题设计题目：一、设计实验条件808实验室二、设计任务及要求1. 基于空闲分区表的最佳适应算法地模拟实现；2. 建立一张类似课本122页的分区使用表；3. 参考课本125页分配流程，采用最佳适应算法，为其在分区使用表中分配内存；4. 程序要能够在图形界面下形象显示作业，及表中信息；5. 最后，对最

2、佳适应算法和其它算法做出比较分析。三、设计报告的内容1. 设计题目与设计任务（设计任务书）(1)、设计可用的内存空闲空间，并能动态输入用户作业所需的内存大小。(2)、编程模拟各种分配算法的实施过程， 按照老师要求，我采用“最佳适应算法发”来分配内存，而在发生内存空间不足时，采用最近最远使用算法（LRU）回收内存。(3)、实现界面功能，能与用户进行交互，在用户界面建立两张表，一张表示空闲分区表，一张表示内存分配表，在软件界面，用户可以手动添加作业和删除作业。2. 前言（绪论）(设计的目的、意义等)最佳适应算法是一种理论上的算法，它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法

3、能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。通过该课题进一步加深对可变分区存储机制的理解。加深对存储器动态分区分配算法的认识。掌握 “最佳适应算法发”的内存分配过程。掌握内存的回收策略。3. 设计主体（各部分设计内容、分析、结论等）（1）最佳适应算法（best fit）所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次

4、找到的能满足要求的空闲区，必然是最佳的。这样，在存储器中会留下许多难以利用的小空闲区。（2）数据结构部分1、内存类(Mem类)：相当于一个内存块，里面有成员变量：（一）、private int size=0;代表内存块的大小（二）、private int addr=0;代表内存块的起始地址（三）、private String name="null"内存块的标志名（每个内存块仅有一个）（四）、private int times=0;内存块未被访问的次数，times越大代表越久没被访问，根据LRU，当内存不够时，将内存中times最大的给置换出来。里面还有关于各个成员变量的ge

5、t和set函数2、空闲链表类（freeList类）：存储关于空闲内存块的一条链，始终将最小的内存放在表头，利用了java库里的LinkedList<Mem>类，规定内存大小为512，设初始为一个空白内存，大小为512.随着内存的不断分配，LinkedList<Mem>也会随之增多，产生碎片等。freeList类有成员变量及方法：（一）、private LinkedList<Mem> freeList;并配有get和set方法。（二）、addFreeMem(Mem work)：用于当内存不足，释放内存时，接受从内存作业链表释放出来的内存块，并将它们按照从小到大

6、的顺序排列。（三）、simpleAdd(Mem)：这是一个内部使用方法，由于其中代码使用频繁，因此将它封装成一个方法。（四）、Mem useFreeMem(Mem work)：用于在用户申请一个作业时，将空闲列表中符合条件并且在最上面的一个内存块分给他。3、内存分配表（public class MemTable ）：用于存储已分配的内存块，也是一条链LinkedList<Mem>类，起始表为空，只有用户申请作业后，表内才会增加内容，并且在内存不够分配新作业时，自动选择最久没用的内存块分配给他。MemTable的成员变量及方法：（一）、private LinkedList<Me

7、m> usedList;并配有get和set方法。（二）、addUsedList (Mem work)：用于在用户申请一个作业时，内存会自动将空闲分区表的一块内存分给作业,因此内存分配表增加了一项，使用此方法给内存分配表增加一项。（三）、Mem freeUsedMem()：内存不够时，将内存分配表中最久没使用的释放出去。（四）、Mem freeWork(String name)：用于在用户申请释放一个作业时，将内存分配表的内存释放出去。（五）、int needFreeMem(Mem work)：当用户打算分配内存给一作业时，先判断用户输入的作业名是不是有和原本作业名一样，当有一样时，再判

8、断该内存大小是否和原来一样，若是一样，置内存表中的作业的times为0，其余times比它原来小的加一。当内存不一样时则出错，不做任何处理。当没有名字一样时，做出分配内存的动作。4、界面类（Interface extends JFrame implements ActionListener, KeyListener）实现界面上各种按钮、表、输入框以及事件的触发等（一）、界面上各种组件：private JTable freeTable,usedTable;private JPanel topPanel,midPanel,endPanel,endPanel1,endPanel2;private O

9、bject freeContent,usedContent;private Object freeTitle="Address","Size",usedTitle="Name","Address","Size","Times"private JButton create,delete;private JTextField createName,createSize,deleteName;private int freeRows=1,usedRows=0;private Fre

10、eList freeMems;private MemTable usedMems;private LinkedList<Mem> freeList,usedList;private GridLayout layout,endPanelLayout;private JScrollPane freeScroll,usedScroll;private Mem work;private JScrollBar JSB;（二）、void actionPerformed(ActionEvent e)：用于两个按钮的触发事件。（三）、void init()：界面初始化。（四）、void keyTy

11、ped(KeyEvent e)：用于触发键盘事件，不让输入大小的框输入除数字以外的东西。（五）、void setTableContentByList(LinkedList<Mem> freeList1,LinkedList<Mem> usedList1):用于将List的内容传到两个表上。（六）、void updateTableContent()：用于更新表内的值。5、主类（Main1类）：实现主函数功能，调用界面类。（3）代码部分：1、freeList类：package bizuo;import java.util.*;public class FreeList pr

12、ivate LinkedList<Mem> freeList;public FreeList()freeList = new LinkedList<Mem>();Mem freeMem = new Mem();freeMem.setAddr(0);freeMem.setSize(512);freeList.add(freeMem);public FreeList(LinkedList<Mem> freeList)this.freeList=freeList;public LinkedList<Mem> getFreeList() return f

13、reeList;public void setFreeList(LinkedList<Mem> freeList) this.freeList = freeList;public Mem useFreeMem(Mem work)if(freeList.size()>0)for(int i=0;i<freeList.size();i+)if(freeList.get(i).getSize()>work.getSize()work.setAddr(freeList.get(i).getAddr();Mem freeMem=freeList.get(i);freeMem

14、.setAddr(freeList.get(i).getAddr()+work.getSize();freeMem.setSize(freeList.get(i).getSize()-work.getSize();freeList.remove(i);simpleAdd(freeMem);return work;else if(freeList.get(i).getSize()=work.getSize()work.setAddr(freeList.get(i).getAddr();freeList.remove(i);return work;return null;public void a

15、ddFreeMem(Mem work)/释放某个作业时，获得空闲区。Mem freeMem = new Mem();boolean hasNext=false;boolean hasPrivor=false;boolean isAlone=true;if(freeList.size()>0)for(int i=0;i<freeList.size();i+)if(freeList.get(i).getAddr()+freeList.get(i).getSize()=work.getAddr()hasPrivor=true;isAlone=false;for(int j=0;j<

16、freeList.size();j+)if(work.getAddr()+work.getSize()=freeList.get(j).getAddr()hasNext=true;freeMem.setAddr(freeList.get(i).getAddr();freeMem.setSize(freeList.get(i).getSize()+work.getSize()+freeList.get(j).getSize();if(i>j)freeList.remove(i);freeList.remove(j);elsefreeList.remove(j);freeList.remov

17、e(i);simpleAdd(freeMem);break;if(hasNext=false)freeMem.setAddr(freeList.get(i).getAddr();freeMem.setSize(freeList.get(i).getSize()+work.getSize();freeList.remove(i);simpleAdd(freeMem);break;if(hasPrivor=false)for(int i=0;i<freeList.size();i+)if(work.getAddr()+work.getSize()=freeList.get(i).getAdd

18、r()isAlone=false;freeMem.setAddr(work.getAddr();freeMem.setSize(freeList.get(i).getSize()+work.getSize();freeList.remove(i);simpleAdd(freeMem);break;if(isAlone=true)freeMem.setAddr(work.getAddr();freeMem.setSize(work.getSize();simpleAdd(freeMem);elsefreeMem.setAddr(work.getAddr();freeMem.setSize(wor

19、k.getSize();freeList.add(freeMem);public void simpleAdd(Mem freeMem)/将空闲存储块送到空嫌链表if(freeList.size()>0)for(int k=0;k<freeList.size();k+)if(freeList.get(k).getSize()>freeMem.getSize()freeList.add(k, freeMem);break;else if(k=freeList.size()-1)freeList.add(freeMem);break;elsefreeList.add(freeMe

20、m);public void printList()System.out.println("地址"+" "+"大小");if(freeList.size()>0)for(int i=0;i<freeList.size();i+)System.out.println(freeList.get(i).getAddr()+" "+freeList.get(i).getSize();elseSystem.out.print("null null");2、MemTable类：package b

21、izuo;import java.util.LinkedList;public class MemTable private LinkedList<Mem> usedList;public MemTable()usedList = new LinkedList<Mem>();public MemTable(LinkedList<Mem> usedList)this.usedList=usedList;public LinkedList<Mem> getUsedList() return usedList;public void setUsedLi

22、st(LinkedList<Mem> usedList) this.usedList = usedList;public void addUsedList(Mem work)if(usedList.size()>0)for(int i=0;i<usedList.size();i+)if(work.getAddr()<usedList.get(i).getAddr()usedList.add(i,work);for(int j=0;j<usedList.size();j+)if(j!=i)usedList.get(j).timesPlus();break;el

23、se if(i=usedList.size()-1)usedList.add(work);for(int j=0;j<usedList.size()-1;j+)usedList.get(j).timesPlus();break;elseusedList.add(work);public void printList()System.out.println("名字"+" "+"地址"+" "+"大小"+" "+"次数");if(usedList.siz

24、e()>0)for(int i=0;i<usedList.size();i+)System.out.println(usedList.get(i).getName()+" "+usedList.get(i).getAddr()+" "+usedList.get(i).getSize()+" "+usedList.get(i).getTimes();elseSystem.out.print("null null null");public int needFreeMem(Mem work)if(usedL

25、ist.size()>0)for(int i=0;i<usedList.size();i+)if(usedList.get(i).getName().equals(work.getName()if(usedList.get(i).getSize()=work.getSize()for(int j=0;j<usedList.size();j+)if(j!=i)&&(usedList.get(j).getTimes()<usedList.get(i).getTimes()usedList.get(j).timesPlus();usedList.get(i).

26、setTimes(0);return 0; /返回0时说明作业大小一致，并且名字一致return 1;/返回1是说明作业名字一致，但大小不一致，应该提示错误return 2;/返回2是说明没有作业名字一致的，需要空闲存储空间public Mem freeUsedMem()Mem work=new Mem();int num=0;int times=0;for(int i=0;i<usedList.size();i+)if(usedList.get(i).getTimes()>times)times=usedList.get(i).getTimes();num=i;work=used

27、List.get(num);usedList.remove(num);return work;public Mem freeWork(String name)Mem work=new Mem();System.out.print(name);for(int i=0;i<usedList.size();i+)if(usedList.get(i).getName().equals(name)work=usedList.get(i);usedList.remove(i);return work;return null;3、Mem类：package bizuo;public class Mem

28、private int size=0;private int addr=0;private String name="null"private int times=0;public int getTimes() return times;public void setTimes(int times) this.times = times;public int getSize() return size;public void setSize(int size) this.size = size;public int getAddr() return addr;public

29、void setAddr(int addr) this.addr = addr;public String getName() return name;public void setName(String name) = name;public void timesPlus()times+;4、Interface类package bizuo;import javax.swing.*;import java.awt.*;import java.awt.event.*;import java.util.*;import static javax.swing.JFrame.*;p

30、ublic class Interface extends JFrame implements ActionListener, KeyListenerprivate JTable freeTable,usedTable;private JPanel topPanel,midPanel,endPanel,endPanel1,endPanel2;private Object freeContent,usedContent;private Object freeTitle="Address","Size",usedTitle="Name",

31、"Address","Size","Times"private JButton create,delete;private JTextField createName,createSize,deleteName;private int freeRows=1,usedRows=0;private FreeList freeMems;private MemTable usedMems;private LinkedList<Mem> freeList,usedList;private GridLayout layout,endP

32、anelLayout;private JScrollPane freeScroll,usedScroll;private Mem work;private JScrollBar JSB;public Interface()init();setVisible(true);setSize(470,420);public void init()layout=new GridLayout(3,1);endPanelLayout=new GridLayout(2,1);setLayout(layout);freeMems=new FreeList();usedMems=new MemTable();se

33、tTableContentByList(freeMems.getFreeList(),usedMems.getUsedList();System.out.print(freeList.size()+" "+usedList.size();freeTable=new JTable(freeContent,freeTitle);usedTable=new JTable(usedContent,usedTitle);freeTable.setEnabled(false);usedTable.setEnabled(false);freeScroll=new JScrollPane(

34、freeTable);usedScroll=new JScrollPane(usedTable);freeScroll.setPreferredSize(new Dimension(450,100);usedScroll.setPreferredSize(new Dimension(450,100);topPanel=new JPanel();midPanel=new JPanel();endPanel=new JPanel();endPanel1=new JPanel();endPanel2=new JPanel();topPanel.setPreferredSize(new Dimensi

35、on(470, 140);midPanel.setPreferredSize(new Dimension(470, 140);topPanel.add(new JLabel("未分配内存表");topPanel.add(freeScroll);/freeScrollmidPanel.add(new JLabel("已分配内存表");midPanel.add(usedScroll);/usedScrollcreateName=new JTextField(10);createSize=new JTextField(10);deleteName=new JT

36、extField(10);create=new JButton("创建作业");delete=new JButton("删除作业");create.addActionListener(this);delete.addActionListener(this);createSize.addKeyListener(this);endPanel.setLayout(endPanelLayout);endPanel1.add(new JLabel("名字");endPanel1.add(createName);endPanel1.add(new

37、 JLabel("大小");endPanel1.add(createSize);endPanel1.add(create);endPanel2.add(new JLabel("名字");endPanel2.add(deleteName);endPanel2.add(delete);endPanel.add(endPanel1);endPanel.add(endPanel2);add(topPanel);add(midPanel);add(endPanel);public void actionPerformed(ActionEvent e) if(e.g

38、etSource()=create)Mem mem=new Mem();work=new Mem();if(createName.getText().equals("")work.setName("null");elsework.setName(createName.getText();if(!createSize.getText().equals("")&&(Integer.parseInt(createSize.getText()<=512)System.out.print("aaaaaaaaaaa

39、a");work.setSize(Integer.parseInt(createSize.getText();int i=usedMems.needFreeMem(work);if(i=2)mem=freeMems.useFreeMem(work);while(mem=null)Mem mem1=usedMems.freeUsedMem();freeMems.addFreeMem(mem1);mem=freeMems.useFreeMem(work);usedMems.addUsedList(mem);setTableContentByList(freeMems.getFreeLis

40、t(),usedMems.getUsedList();updateTableContent();else if(i=0)setTableContentByList(freeMems.getFreeList(),usedMems.getUsedList();updateTableContent();else if(i=1)System.out.println("Sorry,the name :"+work.getName()+" is used;");createName.setText("");createSize.setText(&

41、quot;");else if(e.getSource()=delete)work=new Mem();if(usedList.size()>0)if(!deleteName.getText().equals("")work=usedMems.freeWork(deleteName.getText();if(work!=null)freeMems.addFreeMem(work);setTableContentByList(freeMems.getFreeList(),usedMems.getUsedList();updateTableContent();e

42、lseSystem.out.println("Sorry,have no work used this name");elseSystem.out.println("Sorry,here is no work!");deleteName.setText("");/*public class VoteElectKeyListener implements KeyListener Overridepublic void keyTyped(KeyEvent e) / TODO Auto-generated method stubint ke

43、yChar=e.getKeyChar();if (keyChar>=KeyEvent.VK_0 && keyChar<=KeyEvent.VK_9) else e.consume(); Overridepublic void keyPressed(KeyEvent e) / TODO Auto-generated method stubOverridepublic void keyReleased(KeyEvent e) / TODO Auto-generated method stubpublic void keyPressed(KeyEvent e)if(e.g

44、etKeycode()>=0 && e.getKeyCode()<=9) /这里该怎么写？ */public void setTableContentByList(LinkedList<Mem> freeList1,LinkedList<Mem> usedList1)freeList=freeList1;/freeMems.getFreeList();usedList=usedList1;/usedMems.getUsedList();freeRows=freeList.size();usedRows=usedList.size();free

45、Content=new ObjectfreeRows2;usedContent=new ObjectusedRows4;if(freeList.size()>0)for(int i=0;i<freeList.size();i+)freeContenti0=freeList.get(i).getAddr();freeContenti1=freeList.get(i).getSize();System.out.println(freeContenti0+" "+freeContenti1);if(usedList.size()>0)for(int i=0;i&

46、lt;usedList.size();i+)usedContenti0=usedList.get(i).getName();usedContenti1=usedList.get(i).getAddr();usedContenti2=usedList.get(i).getSize();usedContenti3=usedList.get(i).getTimes();System.out.println(usedContenti0+" "+usedContenti1);public void updateTableContent()topPanel.removeAll();mi

47、dPanel.removeAll();freeTable=new JTable(freeContent,freeTitle);usedTable=new JTable(usedContent,usedTitle);freeTable.setEnabled(false);usedTable.setEnabled(false);freeScroll=new JScrollPane(freeTable);usedScroll=new JScrollPane(usedTable);freeScroll.setPreferredSize(new Dimension(450,100);usedScroll

48、.setPreferredSize(new Dimension(450,100);topPanel.add(new JLabel("未分配内存表");topPanel.add(freeScroll);midPanel.add(new JLabel("已分配内存表");midPanel.add(usedScroll);topPanel.validate();midPanel.validate();Overridepublic void keyTyped(KeyEvent e) / TODO Auto-generated method stubint key

49、Char=e.getKeyChar();if (keyChar>=KeyEvent.VK_0 && keyChar<=KeyEvent.VK_9) else e.consume();Overridepublic void keyPressed(KeyEvent e) / TODO Auto-generated method stubOverridepublic void keyReleased(KeyEvent e) / TODO Auto-generated method stub5、Main1类package bizuo;import java.lang.Mat

50、h;public class Main1 public static void main(String args)Interface window=new Interface();（4）、结果展示部分：图1.初始状态 图2.给一个名字1 大小30 的作业分配内存后图3.再创建一个内存大小为490的作业，由于内存不够，自动将作业1释放图4.内存分配完后空闲表消失图5. 内存表太大时出现内存表的滚动条图6.手动删除了一个首地址为30的作业四、常见内存分配算法对比：（1）首次适应算法。使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，

51、从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。（2）循环首次适应算法。该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至找到一个能满足要求的空闲分区，并从中划出一块来分给作业。该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的

52、空闲分区。（3）最佳适应算法。该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。（4）最差适应算法。最差适应算法中，该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。（选做题目）设计题目：一、设计实验条件808实验室二、设计任务及要求对Linux操作系统的处理机管理、存储器管理、文件管理、设备管理中一个或几个功能进行较全面系统分析，分析内容包括设计实现原