首页 > 编程语言 > 详细

使用Java模拟操作系统高优先级算法

时间：2014-12-29 21:21:51      阅读：394      评论：0      收藏：0      [点我收藏+]
最近做操作系统的课程设计，网上看到一些动态调度的算法都是基于C写的，下午闲来无事，用Java写了一个高优先级调度的算法玩玩，这个算法首先有这几条要注意
  • 优先级是否可以为负的，答案是肯定的，如果有一个线程阻塞了另外一个线程一直去运行就可能一直减去，让优先级变成负数了
  • 阻塞的时机：可以说阻塞的时机特别的重要，一旦到达时间需要线程进行阻塞的状态就要立刻将状态改变掉，让它产生调度
  • 恢复成就绪状态的问题：因为是有可能是线程进行I/O操作，让其阻塞了，所以说，一个时间片就需要让恢复阻塞的时间常数+1，当变为0的时候让他进入调度状态
  • 如果在系统中都是阻塞的线程怎么办？那没有办法，操作系统只能干等着让他们变为就绪状态的时候才能运行
先上一个PCB结构体函数块
  1. public class PCB {
  2. 	//进程的ID
  3. 	private long id;
  4. 	//优先级顺序
  5. 	private int priority;
  6. //	运行的cpu时间
  7. 	private long cputime;
  8. //  需要运行的时间
  9. 	private long alltime;
  10. //  即将阻塞的时间
  11. 	private long startblock;
  12. //	从阻塞中回复的时间
  13. 	private long blocktime;
  15. //	现在线程的状态
  16. 	private String state;
  17. 	
  18. 	
  19. 	public PCB(long id, int priority, long cputime, long alltime,
  20. 			long startblock, long blocktime, String state) {
  21. 		super();
  22. 		this.id = id;
  23. 		this.priority = priority;
  24. 		this.cputime = cputime;
  25. 		this.alltime = alltime;
  26. 		this.startblock = startblock;
  27. 		this.blocktime = blocktime;
  28. 		this.state = state;
  29. 	}
  31. 	public String getState() {
  32. 		return state;
  33. 	}
  35. 	public void setState(String state) {
  36. 		this.state = state;
  37. 	}
  39. 	public long getBlocktime() {
  40. 		return blocktime;
  41. 	}
  43. 	public void setBlocktime(long blocktime) {
  44. 		this.blocktime = blocktime;
  45. 	}

  46. //  运行的三个状态
  47. 	public final static String STATE_READY = "READY";
  48. 	public final static String STATE_RUN = "RUN";
  49. 	public final static String STATE_BLOCK = "BLOCK";

  51. 	
  52. 	
  53. 	public long getId() {
  54. 		return id;
  55. 	}
  57. 	public void setId(long id) {
  58. 		this.id = id;
  59. 	}
  61. 	public int getPriority() {
  62. 		return priority;
  63. 	}
  65. 	public void setPriority(int priority) {
  66. 		this.priority = priority;
  67. 	}
  69. 	public long getCputime() {
  70. 		return cputime;
  71. 	}
  73. 	public void setCputime(long cputime) {
  74. 		this.cputime = cputime;
  75. 	}
  77. 	public long getAlltime() {
  78. 		return alltime;
  79. 	}
  81. 	public void setAlltime(long alltime) {
  82. 		this.alltime = alltime;
  83. 	}
  85. 	public long getStartblock() {
  86. 		return startblock;
  87. 	}
  89. 	public void setStartblock(long startblock) {
  90. 		this.startblock = startblock;
  91. 	}
  93. }
好了，现在是主要的线程调度算法，注意优先级的调整：
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Comparator;
  4. import java.util.Iterator;
  5. import java.util.List;
  7. public class OrderImitate {
  8. 	
  9. //  按优先级次序排列的数组
  10. 	private ArrayList<PCB> priorityArrayList = null;
  11. 	
  12. 	
  13. /**
  14.  * 	优先级排序
  15.  */
  16. 	public void sortArray(){
  17. 		PCB[] pcbs = (PCB[])priorityArrayList.toArray(new PCB[priorityArrayList.size()]);
  18. 		Arrays.sort(pcbs, new MyComprator());
  19. 		List<PCB> list = Arrays.asList(pcbs);
  20. 		this.priorityArrayList = new ArrayList<PCB>(list);
  21. 	}
  22. 	
  23. /**
  24.  * 	初始化，按照书中的数据进行初始化操作
  25.  */
  26. 	private void init(){
  27. 		priorityArrayList = new ArrayList<PCB>();
  28. 		PCB zero = new PCB(0, 9, 0, 3, 2, 3, PCB.STATE_READY);
  29. 		priorityArrayList.add(zero);
  30. 		
  31. 		PCB one = new PCB(1, 38, 0, 3, -1, 0, PCB.STATE_READY);
  32. 		priorityArrayList.add(one);
  33. 		
  34. 		PCB two = new PCB(2, 30, 0, 6, -1, 0, PCB.STATE_READY);
  35. 		priorityArrayList.add(two);
  36. 		
  37. 		PCB three = new PCB(3, 29, 0, 3, -1, 0, PCB.STATE_READY);
  38. 		priorityArrayList.add(three);
  39. 		
  40. 		PCB four = new PCB(4, 0, 0, 4, -1, 0, PCB.STATE_READY);
  41. 		priorityArrayList.add(four);
  42. 		
  43. 		sortArray();
  44. 	}
  45. 	
  46. 	
  47. /**
  48.  * 优先级执行算法
  49.  * @return
  50.  */
  51. 	public boolean hightpPriority(){
  52. 		
  53. //		获得第一个元素
  54. 		PCB first = priorityArrayList.get(0);
  55. 		
  56. 		if(!first.getState().equals(PCB.STATE_BLOCK)){
  57. //			运行一次优先级顺序-3
  58. 			first.setPriority(first.getPriority()-3);
  59. 			first.setCputime(first.getCputime()+1);
  60. 			first.setAlltime(first.getAlltime()-1);
  61. //			是否进入阻塞状态
  62. 			if(first.getStartblock() > 0){
  63. 				first.setStartblock(first.getStartblock() - 1);
  64. 			}
  65. //			当是阻塞状态的时候，将状态变为阻塞
  66. 			if(first.getStartblock() == 0){
  67. 				first.setState(PCB.STATE_BLOCK);
  68. 			}
  69. 		}
  70. 		
  71. //		所需要的时间片完成，结束运行
  72. 		if(first.getAlltime() == 0){
  73. 			System.out.println("----------------------------------------------");
  74. 			System.out.println("ID " + first.getId() + " have done !");
  75. 			System.out.println("----------------------------------------------");
  76. 			priorityArrayList.remove(0);
  77. 		}
  78. 		
  79. //		后面的任务优先级+1
  80. 		Iterator<PCB> iterator = priorityArrayList.iterator();
  81. 		int count = 0;
  82. 		while(iterator.hasNext()){
  83. 			if(count == 0){
  84. 				count++;
  85. 				iterator.next();
  86. 				continue;
  87. 			}
  88. 			PCB pcb = iterator.next();
  89. 			pcb.setPriority(pcb.getPriority()+1);
  90. //			PCB的阻塞状态改变
  91. 			if(pcb.getBlocktime() != 0 && pcb.getState().equals(PCB.STATE_BLOCK)){
  92. 				pcb.setBlocktime(pcb.getBlocktime() -1);
  93. 				if(pcb.getBlocktime() == 0){
  94. 					pcb.setState(PCB.STATE_READY);
  95. 				}
  96. 			}
  97. 		}
  98. 		
  99. 		sortArray();
  100. 		
  101. 		return true;
  102. 	}
  103. 	
  104. 	/**
  105. 	 * 执行程序
  106. 	 */
  107. 	public void startRuning(){
  108. 		while(hightpPriority()){
  109. 			if(this.priorityArrayList.size() == 0){
  110. 				System.out.println("-----------------> ALL Works have done !");
  111. 				break;
  112. 			}
  113. //			输出数据
  114. 			Iterator<PCB> iterator = priorityArrayList.iterator();
  115. 			System.out.println("-----------------------------------------------------------------------------------------");
  116. 			System.out.println("ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE");
  117. 			while(iterator.hasNext()){
  118. 				PCB pcb = iterator.next();
  119. 				System.out
  120. 						.printf("%d %8d %12d %12d %13d %14d %18s\n", pcb.getId(),
  121. 								pcb.getPriority(), pcb.getCputime(),
  122. 								pcb.getAlltime(), pcb.getStartblock(),
  123. 								pcb.getBlocktime(), pcb.getState());
  124. 			}
  125. 			System.out.println("-----------------------------------------------------------------------------------------");
  126. 		}
  127. 	}
  128. 	
  129. 	public static void main(String[] args) {
  130. 		OrderImitate orderImitate = new OrderImitate();
  131. 		orderImitate.init();
  132. 		orderImitate.startRuning();
  133. 	}
  134. 	
  135. //	优先级次序调整，优先级高且没有阻塞的进程在前面
  136. 	class MyComprator implements Comparator<PCB> {
  137. 	    public int compare(PCB o1, PCB o2) {
  138. 	    	
  139. 			if((o1.getState().equals(PCB.STATE_READY) && o2.getState().equals(PCB.STATE_READY)) || (o1.getState().equals(PCB.STATE_BLOCK) && o2.getState().equals(PCB.STATE_BLOCK))){
  140. 				if(o1.getPriority() == o2.getPriority() ){
  141. 					return 0;
  142. 				}
  143. 				else if(o1.getPriority() > o2.getPriority()){
  144. 					return -1;
  145. 				}else {
  146. 					return 1;
  147. 				}
  148. 			}else if(o1.getState().equals(PCB.STATE_BLOCK) && o2.getState().equals(PCB.STATE_READY)){
  149. 				return 1;
  150. 			}else{
  151. 				return -1; 
  152. 			}
  153. 			
  154. 		}
  155. 	}
  156. 	
  157. }
一开始是想用优先队列的，但是碰上个问题，如果有多个线程同时进入阻塞状态，那么就可能第二个到后面那个都无法运行，这样没有完全排好序的优先队列就没有办法使用了，而且优先队列碰上一个大的问题，不知道什么，中途修改了队列中的值没有触发队列的排序，导致后面的一系列次序无法进行。


好的，现在看看最后的结果：
  1. -----------------------------------------------------------------------------------------
  2. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  3. 1       35            1            2            -1              0              READY
  4. 2       31            0            6            -1              0              READY
  5. 3       30            0            3            -1              0              READY
  6. 0       10            0            3             2              3              READY
  7. 4        1            0            4            -1              0              READY
  8. -----------------------------------------------------------------------------------------
  9. -----------------------------------------------------------------------------------------
  10. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  11. 1       32            2            1            -1              0              READY
  12. 2       32            0            6            -1              0              READY
  13. 3       31            0            3            -1              0              READY
  14. 0       11            0            3             2              3              READY
  15. 4        2            0            4            -1              0              READY
  16. -----------------------------------------------------------------------------------------
  17. ----------------------------------------------
  18. ID 1 have done !
  19. ----------------------------------------------
  20. -----------------------------------------------------------------------------------------
  21. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  22. 2       32            0            6            -1              0              READY
  23. 3       32            0            3            -1              0              READY
  24. 0       12            0            3             2              3              READY
  25. 4        3            0            4            -1              0              READY
  26. -----------------------------------------------------------------------------------------
  27. -----------------------------------------------------------------------------------------
  28. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  29. 3       33            0            3            -1              0              READY
  30. 2       29            1            5            -1              0              READY
  31. 0       13            0            3             2              3              READY
  32. 4        4            0            4            -1              0              READY
  33. -----------------------------------------------------------------------------------------
  34. -----------------------------------------------------------------------------------------
  35. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  36. 3       30            1            2            -1              0              READY
  37. 2       30            1            5            -1              0              READY
  38. 0       14            0            3             2              3              READY
  39. 4        5            0            4            -1              0              READY
  40. -----------------------------------------------------------------------------------------
  41. -----------------------------------------------------------------------------------------
  42. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  43. 2       31            1            5            -1              0              READY
  44. 3       27            2            1            -1              0              READY
  45. 0       15            0            3             2              3              READY
  46. 4        6            0            4            -1              0              READY
  47. -----------------------------------------------------------------------------------------
  48. -----------------------------------------------------------------------------------------
  49. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  50. 2       28            2            4            -1              0              READY
  51. 3       28            2            1            -1              0              READY
  52. 0       16            0            3             2              3              READY
  53. 4        7            0            4            -1              0              READY
  54. -----------------------------------------------------------------------------------------
  55. -----------------------------------------------------------------------------------------
  56. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  57. 3       29            2            1            -1              0              READY
  58. 2       25            3            3            -1              0              READY
  59. 0       17            0            3             2              3              READY
  60. 4        8            0            4            -1              0              READY
  61. -----------------------------------------------------------------------------------------
  62. ----------------------------------------------
  63. ID 3 have done !
  64. ----------------------------------------------
  65. -----------------------------------------------------------------------------------------
  66. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  67. 2       25            3            3            -1              0              READY
  68. 0       18            0            3             2              3              READY
  69. 4        9            0            4            -1              0              READY
  70. -----------------------------------------------------------------------------------------
  71. -----------------------------------------------------------------------------------------
  72. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  73. 2       22            4            2            -1              0              READY
  74. 0       19            0            3             2              3              READY
  75. 4       10            0            4            -1              0              READY
  76. -----------------------------------------------------------------------------------------
  77. -----------------------------------------------------------------------------------------
  78. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  79. 0       20            0            3             2              3              READY
  80. 2       19            5            1            -1              0              READY
  81. 4       11            0            4            -1              0              READY
  82. -----------------------------------------------------------------------------------------
  83. -----------------------------------------------------------------------------------------
  84. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  85. 2       20            5            1            -1              0              READY
  86. 0       17            1            2             1              3              READY
  87. 4       12            0            4            -1              0              READY
  88. -----------------------------------------------------------------------------------------
  89. ----------------------------------------------
  90. ID 2 have done !
  91. ----------------------------------------------
  92. -----------------------------------------------------------------------------------------
  93. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  94. 0       17            1            2             1              3              READY
  95. 4       13            0            4            -1              0              READY
  96. -----------------------------------------------------------------------------------------
  97. -----------------------------------------------------------------------------------------
  98. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  99. 4       14            0            4            -1              0              READY
  100. 0       14            2            1             0              3              BLOCK
  101. -----------------------------------------------------------------------------------------
  102. 可以看到这里因为线程阻塞产生了调度：
  103. -----------------------------------------------------------------------------------------
  104. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  105. 4       11            1            3            -1              0              READY
  106. 0       15            2            1             0              2              BLOCK
  107. -----------------------------------------------------------------------------------------
  108. -----------------------------------------------------------------------------------------
  109. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  110. 4        8            2            2            -1              0              READY
  111. 0       16            2            1             0              1              BLOCK
  112. -----------------------------------------------------------------------------------------
  113. -----------------------------------------------------------------------------------------
  114. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  115. 0       17            2            1             0              0              READY
  116. 4        5            3            1            -1              0              READY
  117. -----------------------------------------------------------------------------------------
  118. ----------------------------------------------
  119. ID 0 have done !
  120. ----------------------------------------------
  121. -----------------------------------------------------------------------------------------
  122. ID      PRIORITY      CPUTIME      ALLTIME      STARTBLOCK      BLOCKTIME      STATE
  123. 4        5            3            1            -1              0              READY
  124. -----------------------------------------------------------------------------------------
  125. ----------------------------------------------
  126. ID 4 have done !
  127. ----------------------------------------------
  128. -----------------> ALL Works have done !





使用Java模拟操作系统高优先级算法

原文：http://www.cnblogs.com/sober-reflection/p/4192315.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！