在一个只支持4道程序同时运行的多道程序系统中,若在一段时间内先后到达6个作业,其提交时刻和估计运行时间由下表给出。
时间: 2023-05-26 13:06:47 浏览: 223
提交时间 | 运行时间
---|---
1 | 5
2 | 2
3 | 1
4 | 6
5 | 3
6 | 4
先来一个比较直观的思路,假设每次都选最短作业优先(SJF,Shortest Job First)算法。
在 t=1 时,有 3 个作业可选,分别是 1、2、3,选择运行时间最短的 3 号作业,同时加入等待队列中的作业是 1 号作业。
在 t=4 时,有 4 个作业可选,分别是 1、2、4、5,选择运行时间最短的 5 号作业,同时加入等待队列中的作业是 2 号作业。
在 t=7 时,有 4 个作业可选,分别是 1、2、4、6,选择运行时间最短的 1 号作业,同时加入等待队列中的作业是 4 号作业。
在 t=12 时仍然有 3 个作业可选,分别是 1、2、6,选择运行时间最短的 2 号作业,同时加入等待队列中的作业是 6 号作业。
最终的结果是:
作业 | 提交时间 | 运行时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间
---|---|---|---|---|---|---
1 | 1 | 5 | 1 | 6 | 5 | 1.000
2 | 2 | 2 | 4 | 6 | 4 | 2.000
3 | 3 | 1 | 2 | 3 | 1 | 1.000
4 | 4 | 6 | 7 | 13 | 9 | 1.500
5 | 5 | 3 | 12 | 15 | 10 | 3.333
6 | 6 | 4 | 17 | 21 | 15 | 3.750
其中,开始时间、完成时间、周转时间和带权周转时间的计算方法可以参考之前的解答。
相关问题
编写并调度一个多道程序系统的作业调度模拟承租
这是一个比较复杂的问题,需要考虑多个方面,包括进程调度策略、资源分配、进程状态转换等等。下面是一个比较简单的多道程序系统的作业调度模拟承租的实现思路:
1. 进程调度策略
多道程序系统中,有多个进程同时运行,因此需要考虑如何调度这些进程。通常有以下几种调度策略:
- 先来先服务(FCFS,First-Come, First-Served):按照进程的到达时间顺序进行调度,先到先服务。
- 最短作业优先(SJF,Shortest Job First):按照进程的执行时间进行调度,执行时间短的进程先执行。
- 优先级调度(Priority Scheduling):为每个进程分配一个优先级,按照优先级进行调度,优先级高的进程先执行。
- 时间片轮转(Round Robin):为每个进程分配一个时间片,按照时间片轮流调度各个进程。
2. 资源分配
多道程序系统中,有多个进程同时运行,需要考虑如何分配资源。通常需要分配的资源包括 CPU 时间、内存空间、I/O 设备等等。为了避免资源争用和死锁等问题,需要采用合适的资源分配算法。其中比较常见的算法包括:
- 银行家算法(Banker's Algorithm):一种避免死锁的资源分配算法,通过预测进程未来可能需要的资源来进行资源分配。
- 最佳适应算法(Best Fit Algorithm):一种内存分配算法,选择最小的满足进程需要的内存块进行分配。
- 最近未使用算法(LRU,Least Recently Used):一种页面置换算法,选择最近最久未使用的页面进行置换。
3. 进程状态转换
多道程序系统中,进程的状态转换比较复杂,通常有以下几个状态:
- 就绪状态(Ready):进程已经准备好运行,正在等待 CPU 时间。
- 运行状态(Running):进程正在运行,占用 CPU 时间。
- 阻塞状态(Blocked):进程因为等待某些资源(如 I/O 设备)而无法运行。
- 终止状态(Terminated):进程已经完成任务,结束运行。
进程状态转换的流程如下:
- 就绪状态 -> 运行状态:当进程获得 CPU 时间时,从就绪状态转换为运行状态。
- 运行状态 -> 阻塞状态:当进程需要等待某些资源时,从运行状态转换为阻塞状态。
- 阻塞状态 -> 就绪状态:当进程获得等待的资源时,从阻塞状态转换为就绪状态。
- 运行状态 -> 终止状态:当进程完成任务时,从运行状态转换为终止状态。
4. 实现思路
基于以上的进程调度策略、资源分配算法和进程状态转换,可以实现一个简单的多道程序系统的作业调度模拟承租。具体实现步骤如下:
- 定义进程控制块(PCB)结构体,包含进程状态、优先级、需要的资源等信息。
- 定义进程队列,包括就绪队列、阻塞队列等。
- 实现进程调度算法,根据不同的调度策略进行进程调度。
- 实现资源分配算法,根据不同的资源分配策略进行资源分配。
- 实现进程状态转换函数,根据进程当前状态和需要转换的状态进行状态转换。
- 编写主函数,模拟多个进程同时运行的情况,循环调用进程调度函数和状态转换函数,直到所有进程完成任务。
需要注意的是,实际的多道程序系统比这个简单的模拟系统要复杂得多,需要考虑更多的因素,如进程间通信、死锁避免、内存管理等等。因此,这里只是提供了一个简单的实现思路,具体实现还需要更加深入的研究和实践。
编写并调度一个多道程序系统的作业调度模拟程序
这里提供一个基于Python的多道程序系统作业调度模拟程序的实现。
首先,我们需要定义作业的数据结构:
```python
class Job:
def __init__(self, pid, arrival_time, burst_time):
self.pid = pid
self.arrival_time = arrival_time
self.burst_time = burst_time
self.remaining_time = burst_time
```
每个作业有三个属性:进程ID、到达时间和执行时间。`remaining_time`属性表示作业还需要执行的时间。
接下来定义一个作业队列:
```python
class JobQueue:
def __init__(self):
self.jobs = []
self.current_job = None
def add_job(self, job):
self.jobs.append(job)
def get_next_job(self):
if len(self.jobs) == 0:
return None
self.current_job = self.jobs.pop(0)
return self.current_job
def is_empty(self):
return len(self.jobs) == 0
```
作业队列是一个FIFO队列,用于存储还未执行的作业。`current_job`属性表示当前正在执行的作业,如果没有作业正在执行,则为`None`。
接下来定义一个调度器:
```python
class Scheduler:
def __init__(self, time_slice):
self.time_slice = time_slice
self.job_queue = JobQueue()
def add_job(self, job):
self.job_queue.add_job(job)
def execute_job(self):
if self.job_queue.is_empty():
return None
job = self.job_queue.get_next_job()
if job.remaining_time > self.time_slice:
job.remaining_time -= self.time_slice
self.job_queue.add_job(job)
else:
job.remaining_time = 0
return job
```
调度器执行作业的方式是轮转调度算法,每次执行一个时间片。如果作业执行完毕,则将其从队列中删除,否则将其重新加入队列。
最后,我们编写一个模拟程序:
```python
import random
NUM_JOBS = 10
MAX_ARRIVAL_TIME = 10
MAX_BURST_TIME = 5
TIME_SLICE = 2
scheduler = Scheduler(TIME_SLICE)
for i in range(NUM_JOBS):
arrival_time = random.randint(0, MAX_ARRIVAL_TIME)
burst_time = random.randint(1, MAX_BURST_TIME)
job = Job(i, arrival_time, burst_time)
scheduler.add_job(job)
current_time = 0
while not scheduler.job_queue.is_empty():
job = scheduler.execute_job()
if job is not None:
print("Time {}: Job {} executed, {} ms remaining".format(current_time, job.pid, job.remaining_time))
else:
print("Time {}: No jobs to execute".format(current_time))
current_time += TIME_SLICE
```
该程序首先生成一些随机作业,然后执行调度器,直到所有作业都执行完毕。在每个时间片中,程序输出正在执行的作业的信息,或者提示没有作业在执行。
这是一个简单的多道程序系统作业调度模拟程序的实现。可以根据需要对其进行扩展,例如添加更复杂的调度算法或实现阻塞和唤醒机制。