ФГБОУ ВО «КГТА имени В. А. ДЕГТЯРЕВА»
Кафедра ПМ и САПР

ЛАБОРАТОРНАЯ РАБОТА №6

Вариант 5

Тема работы: Алгоритмы вытесняющего планирования

Цель работы: Изучение алогоритмы вытесняющего лпанирования FCFS, SJF.

Исполнитель: ст. гр. И-121 Володькин М. Д.

Руководитель: Котов В. В.


Работу выполнил:
Работу защитил:
Теоретическое введение

Процесс планирования осуществляется частью операционной системы, называемой планировщиком. В случае вытесняющего планирования он может принимать решения о выборе для исполнения нового процесса из числа находящихся в состоянии готовность в следующих случаях:

1. Когда процесс переводится из состояния исполнение в состояние закончил исполнение.

2. Когда процесс переводится из состояния исполнение в состояние ожидание.

3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера).

4. Когда процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие).

При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом.

Вытесняющее планирование обычно используется в системах разделения времени: Windows 2000 и выше, UNIX/Linux, MAC OS и др. В этом режиме планирования процесс может быть приостановлен в любой момент исполнения. Операционная система устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого интервала времени – кванта. После прерывания процессор передается в распоряжение следующего процесса. Временные прерывания помогают гарантировать приемлемое время отклика процессов для пользователей, работающих в диалоговом режиме, и предотвращают «зависание» компьютерной системы из-за зацикливания какой-либо программы.

Алгоритм, получивший название Round Robin (сокращенно RR), является модификацией алгоритма FCFS. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см. рис. 6.1). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

Реализуется такой алгоритм так же, как и FCFS, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта.

• Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst), меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново.

• Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.

Практическая часть

Задание 1.

    Реализовать программу, выполняющую планирование процессов по

алгоритмам RR и SJF.

RR

#include

#include "algorithm"

#include "deque"

#include "chrono"

#include "thread"
using namespace std;

class Process;

enum class STATUS {

READINESS,

EXECUTION,

COMPLETED
};
class Process

{

public:

Process(unsigned int id =0 , unsigned int cpuBurst= 0, unsigned int priority=0, STATUS status = STATUS::READINESS) : id(id), cpu_burst(cpuBurst),

priority(priority),

status(status) {
}
virtual Process() {

---

}
unsigned int getId() const {

return this->id;

}
void setId(unsigned int id) {

this->id = id;

}
unsigned int getCpuBurst() const {

return this->cpu_burst;

}
void setCpuBurst(unsigned int cpuBurst) {

this->cpu_burst = cpuBurst;

}
unsigned int getPriority() const {

return this->priority;

}
void setPriority(unsigned int priority) {

this->priority = priority;

}
STATUS getStatus() const {

return this->status;

}
void setStatus(STATUS status) {

this->status = status;

}
unsigned int getTimeWait() const;
void setTimeWait(unsigned int timeWait);
unsigned int getTimeExecution() const;
void setTimeExecution(unsigned int timeExecution);
friend ostream &operator<<(ostream &os, const Process &process);
private:

unsigned int id = 0;

unsigned int cpu_burst = 0;

unsigned int priority = 0;

unsigned int time_wait = 0;

unsigned int time_execution = 0;

STATUS status = STATUS::READINESS;

};
ostream &operator<<(ostream &os, const Process &process) {

os << process.id <<"\t"<


return os;

}
unsigned int Process::getTimeWait() const {

return time_wait;

}
void Process::setTimeWait(unsigned int timeWait) {

time_wait = timeWait;

}
unsigned int Process::getTimeExecution() const {

return time_execution;

}
void Process::setTimeExecution(unsigned int timeExecution) {

time_execution = timeExecution;

}
void RoundRobin(deque
& deque,unsigned int QUANTUM_TIME,unsigned int TIME_SWITCH,unsigned int& avg_waiting_time,unsigned int& avg_full_time_execution,unsigned int num)

{

Process cur_process;
while(!deque.empty())

{
if(deque.size() > 1)

{

for(int i =0;i
{

cout<<"**************************************SWITCH*************************************"<
}

}
unsigned int cur_quantum_time = QUANTUM_TIME;

cur_process = deque.front();
cur_process.setStatus(STATUS::EXECUTION);

avg_waiting_time += cur_process.getTimeWait();

avg_full_time_execution+= cur_process.getTimeWait();
while(cur_quantum_time != 0)

{

if(cur_process.getCpuBurst() >0)

{

cur_process.setCpuBurst(cur_process.getCpuBurst() -1);

cout<
avg_full_time_execution++;

if(cur_process.getCpuBurst() <= 0)

{

deque.pop_front();

RoundRobin(deque,QUANTUM_TIME,TIME_SWITCH,avg_waiting_time,avg_full_time_execution,num);

if(deque.empty()) return;

}

}

else

{

deque.pop_front();

RoundRobin(deque,QUANTUM_TIME,TIME_SWITCH,avg_waiting_time,avg_full_time_execution,num);

}

cur_quantum_time--;

for (auto &element: deque) {

element.setTimeWait(element.getTimeWait() + 1);

}

}

if(!deque.empty())

{

deque.push_back(cur_process);

deque.pop_front();
avg_waiting_time+=TIME_SWITCH;

}
//this_thread::sleep_for(chrono::milliseconds(TIME_SWITCH*1000));

}
}
int main() {

const unsigned int QUANTUM_TIME = 4;

const unsigned int TIME_SWITCH = 0;

unsigned int avg_waiting_time = 0;

unsigned int avg_full_time_execution = 0;
unsigned int num = 0;

unsigned int cpu_burst = 0;

unsigned int id_process = 0;

unsigned int priority = 0;

deque
deque1;

cout<<"Input a count process: "<
cin>> num;

cout<<"ID\tCPU burst\tPriority"<
for(int i =0;i
{

cin>>id_process>>cpu_burst>>priority;

Process process(id_process,cpu_burst,priority,STATUS::READINESS);

deque1.push_back(process);

}

//cout<<"ID\tCPU burst\tPriority"<
RoundRobin(deque1,QUANTUM_TIME,TIME_SWITCH,avg_waiting_time,avg_full_time_execution,num);

avg_waiting_time = avg_waiting_time/num;

avg_full_time_execution = avg_full_time_execution/num;

cout<<"Average wait time: "<return 0;

}

SJF

import java.util.*;

import java.util.concurrent.TimeUnit;

import java.util.stream.Collectors;

import java.util.ArrayDeque;
public class Process {

private int id = 0;

private int cpu_burst = 0;

private int time_wait = 0;

int time_execution = 0;

Status current = Status.READINESS;
Process(){}
public Process(int id, int cpu_burst) {

this.id = id;

this.cpu_burst = cpu_burst;

}
public int getId() {

return id;

}
public void setId(int id) {

this.id = id;

}
public int getCpu_burst() {

return cpu_burst;

}
public void setCpu_burst(int cpu_burst) {

this.cpu_burst = cpu_burst;

}
public Status getCurrent() {

return current;

}
public void setCurrent(Status current) {

this.current = current;

}
public int getTime_wait() {

return time_wait;

}
public void setTime_wait(int time_wait) {

this.time_wait = time_wait;

}
public int getTime_execution() {

return time_execution;

}
public void setTime_execution(int time_execution) {

this.time_execution = time_execution;

}

}

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int id= 0;

int cpu_burst = 0;

int avg_waiting_time = 0;

int priority = 0;

int avg_full_time_execution = 0;
System.out.println("Input a count process: ");

int num = in.nextInt();
ArrayDeque
pool = new ArrayDeque
();

System.out.println("ID\tCPU burst\tPriority");

for(int i =0;i
{

id = in.nextInt();

cpu_burst = in.nextInt();

priority = in.nextInt();

Process process = new Process(id,cpu_burst);

pool.add(process);

}

sjf(pool,avg_waiting_time,avg_full_time_execution,num);

}
public static void fcfs(ArrayDeque
pool, int avg_waiting_time, int avg_full_time_execution, int num)

{

Process cur_process = new Process();

Scanner in = new Scanner(System.in);

while (!pool.isEmpty())

{

System.out.println("Add a new process?");

String str = in.nextLine();

if(str.equals("+"))

{

System.out.println("ID\tCPU burst\tPriority");

int id = in.nextInt();

int cpu_burst = in.nextInt();

int priority = in.nextInt();

ArrayList
processes = processes = new ArrayList<>(pool);

Process process = new Process(id,cpu_burst);

pool.add(process);

Comparator
comparator = new Comparator
() {

@Override

public int compare(Process o1, Process o2) {

return o1.getCpu_burst() - o2.getCpu_burst();

}

} ;

processes = new ArrayList<>(pool);

processes.sort(comparator);

str = "";

num =+1;

fcfs(new ArrayDeque<>(processes),avg_waiting_time,avg_full_time_execution,num);
}

cur_process = pool.getFirst();

cur_process.setCurrent(Status.EXECUTION);

avg_waiting_time += cur_process.getTime_wait();

avg_full_time_execution+= cur_process.getTime_wait();

pool.removeFirst();

while (cur_process.getCpu_burst() != 0)

{
avg_full_time_execution++;

pool.forEach(process -> {

process.setTime_wait(process.getTime_wait()+ 1);

});

System.out.format("ID: %s CPU_BURST: %s Status: %s\n",cur_process.getId(),cur_process.getCpu_burst(),cur_process.getCurrent());

cur_process.setCpu_burst(cur_process.getCpu_burst() -1);
try {

TimeUnit.SECONDS.sleep(0);

} catch (InterruptedException ie) {

Thread.currentThread().interrupt();

}

}

cur_process.setCurrent(Status.COMPLETED);

System.out.format("ID: %s CPU_BURST: %s Status: %s\n",cur_process.getId(),cur_process.getCpu_burst(),cur_process.getCurrent());

System.out.println("***************************************************************************");

}

avg_waiting_time = avg_waiting_time/num;

avg_full_time_execution = avg_full_time_execution/num;

System.out.format("Average wait time: %s\tAverage full time execution: %s",avg_waiting_time,avg_full_time_execution);

}
public static void sjf(ArrayDeque
pool,int avg_waiting_time, int avg_full_time_execution, int num)

{

Comparator
comparator = new Comparator
() {

@Override

public int compare(Process o1, Process o2) {

return o1.getCpu_burst() - o2.getCpu_burst();

}

} ;

ArrayList
processes = new ArrayList<>(pool);

processes.sort(comparator);

fcfs(new ArrayDeque<>(processes),avg_waiting_time,avg_full_time_execution,num);

}

}

Тесты

SJF



RR

Ковров 2023

---

Смотрите также файлы

• Философские аспекты. Применение антиагрегантов.docx

• Занятие Тема Знакомство. I. Организационный момент Придумано кемто Просто и мудро, При встрече здороваться.doc

• Кошикова Умитжан Мауленовна 2022 2023 оу жылы пояснительная записка. Данное занятие.docx

• Форма проведения итоговой аттестации для обучающихся 9 класса.pptx

• Отчет о прохождении производственной практики практики по получению профессиональных умений и опыта.docx