Java 中的 FCFS 程序（带到达时间）

2024年9月10日 | 阅读 6 分钟

什么是 FCFS 调度算法？

先到先服务 (FCFS) 是一种非抢占式的 CPU 调度算法。它按照进程进入就绪队列的顺序进行调度。进程逐个执行直到完成。

什么是到达时间？

到达时间是指进程进入就绪队列的时间。

非抢占式：当一个进程终止或从运行状态转换为等待状态时，采用非抢占式调度。

先进先出 (FIFO)，也称为先到先服务 (FCFS)，是最简单的调度算法。FIFO 只是按照进程进入就绪队列的顺序将它们排队。

在这种调度方式中，先到的进程先执行，下一个进程只有在前一个进程完全执行完毕后才开始执行。

在此，我们假设所有进程的到达时间均为 0。

完成时间：进程完成其执行的时间。
周转时间：完成时间和到达时间之间的时间差。周转时间 = 完成时间 - 到达时间
等待时间 (W.T)：周转时间和执行时间之间的时间差。
等待时间 = 周转时间 - 执行时间。

FCFS 实现

FCFS 算法

输入进程及其执行时间 (bt)。
计算所有进程的等待时间 (wt)。
由于第一个进程不需要等待，所以第一个进程的等待时间为 0，即 wt[0] = 0。
计算所有其他进程的等待时间，即对于进程 i -> wt[i] = bt[i-1] + wt[i-1]
计算所有进程的周转时间 = 等待时间 + 执行时间。
计算平均等待时间 = 总等待时间 / 进程数。
类似地，计算平均周转时间 = 总周转时间 / 进程数。

给定 n 个进程及其执行时间，任务是使用 FCFS 调度算法计算平均等待时间和平均周转时间。

FCFS.java

import java.util.*;
public class FCFS {	
	// Process class to represent a process
	static class Process {
		private int at; // arrival time
		private int bt; // burst time
		private int ct; // completion time
		private int tat; // turnaround time
		private int wt; // waiting time
		private int pid; // process ID
		// Getter method to get a variable value of the process
		public int getVar(String var) {
			if (var.equals("at"))
				return at;
			if (var.equals("bt"))
				return bt;
			if (var.equals("ct"))
				return ct;
			if (var.equals("tat"))
				return tat;
			if (var.equals("wt"))
				return wt;
			return pid;
		}
		// Setter method to set a variable value of the process
		public void setVar(String var, int value) {
			if (var.equals("at"))
				at = value;
			else if (var.equals("bt"))
				bt = value;
			else if (var.equals("ct"))
				ct = value;
			else if (var.equals("tat"))
				tat = value;
			else if (var.equals("wt"))
				wt = value;
			else
				pid = value;
		}
		// Update the turnaround time and waiting time after completion
		public void updateAfterCt() {
			tat = ct - at;
			wt = tat - bt;
		}
		// Display the process details
		public void display() {
			System.out.printf("%d\t%d\t%d\t%d\t%d\t%d\n", pid, at, bt, ct, tat, wt);
		}
	}
	// Calculate the average of a variable value for all processes
	public static float average(ArrayList<Process> P, String var) {
		int total = 0;
		for (Process temp : P) {
			total += temp.getVar(var);
		}
		return (float) total / P.size();
	}
	public static void main(String[] args) {
		/*
		Input description.
		First line contains an integer n
		the next n lines contain 2 space separated integers
		containing values for arrival time and burst time for
		example:
		2
		0 3
		1 2
		*/
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int counter = 0;
		ArrayList<Process> P = new ArrayList<Process>(n);
		// Create a process object for each input and add to the process list
		for (int i = 0; i < n; i++) {
			Process temp = new Process();
			temp.setVar("pid", counter++);
			temp.setVar("at", sc.nextInt());
			temp.setVar("bt", sc.nextInt());
			P.add(temp);
		}
		// Sort the process list by arrival time
		Collections.sort(P, new Comparator<Process>() {
			public int compare(Process first, Process second) {
				return first.getVar("at") - second.getVar("at");
			}
		});
		System.out.println("pid\tat\tbt\tct\ttat\twt");
		// Calculate completion time and display the details of the first process
		P.get(0).setVar("ct", P.get(0).getVar("at") + P.get(0).getVar("bt"));
		P.get(0).updateAfterCt();
		P.get(0).display();
		// Calculate completion time and display the details of the remaining processes
	for (int i = 1; i < P.size(); i++) {
		// Loop through the remaining processes
		if (P.get(i).getVar("at") < P.get(i - 1).getVar("ct")) {
			// If the process arrives before the previous process completes
			P.get(i).setVar("ct", P.get(i - 1).getVar("ct") + P.get(i).getVar("bt"));
			// Calculate completion time as the completion time of previous process plus its burst time
		} else {
			// If the process arrives after the previous process completes
			System.out.printf("curr['at'] : %d, prev['ct'] : %d\n\n", P.get(i).getVar("at"),
					P.get(i - 1).getVar("ct"));
			P.get(i).setVar("ct", P.get(i).getVar("at") + P.get(i).getVar("bt"));
			// Calculate completion time as the arrival time plus its burst time
		}
		P.get(i).updateAfterCt(); // Update the turnaround time and waiting time for the current process
		P.get(i).display(); // Display the details of the current process
	}
	System.out.printf("Average waiting time : %f\n", average(P, "wt"));
	sc.close(); // Close the scanner
}
}

输出

PID     AT      BT      CT      TAT     WT
0       0       10      10      10      0
1       10      5       15      5       0
2       15      8       23      8       0
Avg_turnaround:7.666666666666667
Avg_Waitingtime:0.0

服务时间：也称为执行时间，是指进程在 CPU 上完成其执行所需的时间量。它代表 CPU 花费在执行该特定进程指令上的时间。

等待时间：是指进程在获得 CPU 执行机会之前在就绪队列中等待的总时间。

FCFS 实现

输入进程及其执行时间 (bt) 和到达时间 (at)
计算所有其他进程的等待时间，即对于给定进程 i：wt[i] = (bt[0] + bt[1] +...... bt[i-1]) - at[i]
现在计算所有进程的周转时间 = 等待时间 + 执行时间
平均等待时间 = 总等待时间 / 进程数
平均周转时间 = 总周转时间 / 进程数

让我们根据以下数据计算平均等待时间和周转时间。

进程	执行时间	到达时间	等待时间	周转时间	完成时间
1	5	0	0	5	5
2	9	3	2	11	14
3	6	6	8	14	20

FCFS.java

public class FCFS{ 
// Java program for implementation of FCFS 
// scheduling with different arrival time 
// Function to find the waiting time for all 
// processes 
static void findWaitingTime(int processes[], int n, int bt[], int wt[], int at[]) 
{ 
	int service_time[] = new int[n]; 
	service_time[0] = at[0]; 
	wt[0] = 0; 
	// calculating waiting time 
	for (int i = 1; i < n ; i++) 
	{ 
		//representing wasted time in queue 
		int wasted=0; 
		// Add burst time of previous processes 
		service_time[i] = service_time[i-1] + bt[i-1]; 
		// Find waiting time for current process = 
		// sum - at[i] 
		wt[i] = service_time[i] - at[i]; 
		// If waiting time for a process is in negative 
		// that means it is already in the ready queue 
		// before CPU becomes idle so its waiting time is 0 
		// wasted time is basically time for process to wait after a process is over 
		if (wt[i] < 0) { 
			wasted = Math.abs(wt[i]); 
			wt[i] = 0; 
		} 
		//Add wasted time 
		service_time[i] = service_time[i] + wasted; 
	} 
} 
// Function to calculate turn around time 
static void findTurnAroundTime(int processes[], int n, int bt[], 
									int wt[], int tat[]) 
{ 
	// Calculating turnaround time by adding bt[i] + wt[i] 
	for (int i = 0; i < n ; i++) 
		tat[i] = bt[i] + wt[i]; 
} 
// Function to calculate average waiting and turn-around 
// times. 
static void findavgTime(int processes[], int n, int bt[], int at[]) 
{ 
	int wt[] = new int[n], tat[] = new int[n]; 
	// Function to find waiting time of all processes 
	findWaitingTime(processes, n, bt, wt, at); 
	// Function to find turnaround time for all processes 
	findTurnAroundTime(processes, n, bt, wt, tat); 
	// Display processes along with all details 
	System.out.print("Processes " + " Burst Time " + " Arrival Time "
		+ " Waiting Time " + " Turn-Around Time "
		+ " Completion Time \n"); 
	int total_wt = 0, total_tat = 0; 
	for (int i = 0 ; i < n ; i++) 
	{ 
		total_wt = total_wt + wt[i]; 
		total_tat = total_tat + tat[i]; 
		int compl_time = tat[i] + at[i]; 
		System.out.println(i+1 + "\t\t" + bt[i] + "\t\t"
			+ at[i] + "\t\t" + wt[i] + "\t\t "
			+ tat[i] + "\t\t " + compl_time); 
	} 
	System.out.print("Average waiting time = "
		+ (float)total_wt / (float)n); 
	System.out.print("\nAverage turnaround time = "
		+ (float)total_tat / (float)n); 
} 
// Driver code 
	public static void main(String args[]) { 
		// Process id's 
	int processes[] = {1, 2, 3}; 
	int n = processes.length; 
	// Burst time of all processes 
	int burst_time[] = {5, 9, 6}; 
	// Arrival time of all processes 
	int arrival_time[] = {0, 3, 6}; 
	findavgTime(processes, n, burst_time, arrival_time); 
	} 
} 

输出

Average waiting time = 3.33333
Average turnaround time = 10.0

下一主题Java 中的不可变 Map

Java 中的 FCFS 程序（带到达时间）

什么是 FCFS 调度算法？

什么是到达时间？

FCFS 实现

FCFS 算法

FCFS 实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的 FCFS 程序（带到达时间）

什么是 FCFS 调度算法？

什么是到达时间？

FCFS 实现

FCFS 算法

FCFS 实现

相关帖子

Java 中以毫秒为单位获取昨天的日期

Java 中的计数器如何与日期配合使用

Java 中是否需要前向声明

Java 中的不同包

Java AWS Polly

Remove Special Characters from String

Java 中的汉诺塔程序

Java 中二叉树的左视图

Count Inversions Problem in Java

Java 中 GSON 的 fromJson() 和 toJson() 方法的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器