First In – First Out

First In – First Out (Монгол: Эхэнд ирсэн нь эхэнд үйлчлүүлэх мөн Түрүүлж ирээд, Түрүүлж гарна) эсвэл "Ажил дуустал ажиллуулна"

Эртны системүүдэд "FCFS" гэдэг нь нэг програмыг дуустал нь ажилуулна гэж үздэг байсан.
Одоо, CPU хуулбарыг блоклолтонд ортол нь ажиллуулана.

* Эхэнд ирсэн нь Эхэнд үйлчлүүлнэ энэ нь Эхэнд ирсэн нь эхэнд гарна өгөгдөлын бүтэцтэй адил, дараалалд хамгийн түрүүлж ирсэн нь дарааллыг хамгийн түрүүнд орхино.
* Энэ нь Batch systems-д ашиглагддаг.
* Дарааллын сүүлээр дамжих шинэ процесс орж ирэхэд дарааллын толгойноос процессыг сонгох дарааллын дарааллын бүтцийг ашиглан програмчлалыг ойлгох, хэрэгжүүлэхэд хялбар байдаг.

Дундаж хугацааг тооцоолох

Хуваарилалтын алгоритм бүрийн хувьд дундаж хүлээгдэж буй хугацаа нь гүйцэтгэлийг үнэлэх чухал параметр юм. AWT буюу дундаж хүлээгдэж буй хугацаа нь хуваарилагчийг гүйцэтгэхийн тулд сонгох хүлээж буй хүлээгдэж буй хугацааны дундаж юм.

Хугацааны дундаж хугацааг багасгаад төлөвлөсөн алгоритмыг сайжруулна.

P1, P2, P3, P4 процессуудыг доорх хүснэгтэд үзүүлэв. Ирж буй цаг 0 ба тухайн тэсрэх хугацаатай ижилхэн дарааллыг гүйцэтгэхийн тулд FCFS хуваарийн алгоритмийг ашиглан дундаж хүлээгдэж буй хугацааг олоорой.

Дундаж хүлээх хугацаа бол = (0 + 21 +24 + 30)/4 = 18.75ms

Энэ нь дээрхи үйл явцуудын хувьд GANTT диаграмм юм.

Дундаж хүлээх хугацаа бол 18.75ms Дээрх өгөгдсөн процессуудын хувьд эхний P1 CPU-ийн эх үүсвэрүүдтэй байх болно,

* Тиймээс, P1 хүлээх хугацаа нь 0 байна
* P1 нь 21 ms-ийг шаарддаг тул P2-т хүлээгдэж буй хугацаа нь 21 ms байна
* Үүний нэгэн адилаар P3 процессийн хүлээх хугацаа P2 (21 + 3) ms = 24 ms байх P1 + гүйцэтгэх хугацаа болно.
* P4 процессын хувьд P1, P2, P3-ийн гүйцэтгэлийн хугацааны нийлбэр байх болно.

Дээрх GANTT диаграмм нь процесс бүрт хүлээх хугацааг төгс илэрхийлэх болно.

FCFS төлөвлөлтийн алгоритмын хүндрэлүүд

FCFS хуваарилах алгоритмтай хэд хэдэн дутагдал эсвэл хүндрэлүүд байна:

1. Энэ нь тасралтгүй алгоритм бөгөөд энэ нь процессын нэн тэргүүний асуудал биш юм. Хэрэв хамгийн бага ач холбогдол бүхий процесс ажиллаж байгаа бол өдөр тутмын нөөцлөлтийн процесс илүү их цагийг шаарддаг бөгөөд гэнэт зарим нэг давуу талтай процессууд, тухайлбал тасалдал гэх мэт системийн алдаа гаргахаас зайлсхийхийн тулд өндөр давуу эрхтэй процесс хүлээх хэрэгтэй болно Тиймээс, энэ тохиолдолд зохисгүй үйл явцын төлөвлөлтөөс болоод систем алдагдах болно.

2. Хамгийн оновчтой бус хүлээгдэж буй хугацаа.

3. Нөөцийн ашиглалт зэрэгцээ ашиглагдах боломжгүй бөгөөд энэ нь Convoy Effect-д хүргэдэг тул нөөцийг (CPU, I / O гэх мэт) ашигладаггүй.

Конвейерийн үр нөлөө гэж юу вэ?

Convoy Effect гэдэг нь нөөцийг богино хугацаанд ашиглахад шаардлагатай олон процессууд нь тухайн нөөцийг урт хугацаанд хадгалах нэг процессоор хаагддаг нөхцөл юм.

Энэ нь нөөц баялгийг зүй зохистой ашиглах, муу гүйцэтгэлд хүргэдэг.

FCFS төлөвлөлтийн алгоритмын программ

Энд бид энгийн C ++ програмыг процессийн хувьд arrival time 0-s авья.

Программд бид үйл явдлын жагсаалтын талаар өгөгдсөн массивын хугацааг тооцоолох дундаж дундаж хугацаа болон дундаж эргэлтийг тооцоолно.

/* Хэрэглээний энгийн C ++ програм
FCFS төлөвлөлт. */
#include<iostream>
using namespace std;
// бүх үйл явцын хүлээх хугацаа олох функ
void findWaitingTime(int processes[], int n, int bt[], int wt[])
{
    // Эхний процессын хүлээх хугацаа 0
    wt[0] = 0;
    // хүлээх хугацаах тооцоолж байна.
    for (int i = 1; i < n ; i++)
    {
        wt[i] =  bt[i-1] + wt[i-1];
    }
}
// цаг хугацааны эргэлтийг тооцоолох функц
void findTurnAroundTime( int processes[], int n, int bt[], int wt[], int tat[])
{
    // Нэмэлт өөрчлөлтийг тооцоолох.
    // bt[i] + wt[i]
    for (int i = 0; i < n ; i++)
    {
        tat[i] = bt[i] + wt[i];
    }
}
// Дундаж хугацаах тооцоолох функ
void findAverageTime( int processes[], int n, int bt[])
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;
    // бүх процессийн хүлээх хугацааг олох функц.
    findWaitingTime(processes, n, bt, wt);
    // бүх үйл явцын эргэх цагийг олох функц.
    findTurnAroundTime(processes, n, bt, wt, tat);
    // дэлгэцийн процессууд бүх нарийн ширийн зүйлсийг агуулсан болно
    cout << "Processes  "<< " Burst time  "<< " Waiting time  " << " Turn around time\n";
    // нийт хүлээгдэж буй хугацаа, нийт эргэлтийг тооцоолох.
    for (int i = 0; i < n; i++)
    {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << "   " << i+1 << "\t\t" << bt[i] <<"\t    "<< wt[i] <<"\t\t  " << tat[i] <<endl;
    }
 
    cout << "Average waiting time = "<< (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "<< (float)total_tat / (float)n;
}
// main function
int main()
{
    // process ids
    int processes[] = { 1, 2, 3, 4};
    int n = sizeof processes / sizeof processes[0];
    // Бүх процессын burst time
    int  burst_time[] = {21, 3, 6, 2};
    findAverageTime(processes, n,  burst_time);
    return 0;
}

ГАРАЛТ: Processes Burst time Waiting time Turn around time

         1 21 0 21

         2 3 21 24

         3 6 24 30

         4 2 30 32

Дундаж хүлээх хугацаа = 18.75

Дундаж эргэх хугацаа = 26.75

Энд бидэнд өгөгдсөн процессуудын өөр өөр үеийг тооцоолох энгийн томъёо байдаг:

Completion Time: Хугацаа дуусахаас эхлэн гүйцэтгэлийг гүйцэтгэх хугацаа.

Turn around time: Ирэхээсээ өмнө дуусгахад шаардагдах хугацаа. Энгийнээр хэлэхэд, энэ нь Completion time болон arrival time-н ялгаа юм.

Waiting time: Гүйцэтгэл эхлэхээс өмнө процесс хүлээх нийт хугацаа. Энэ нь Turn around time болон үйл явцын Burst time ялгаа юм. Дээрх programm-ын хувьд Arrival time нь бүх үйл явцын хувьд 0 гэж үздэг, үргэлжилсэн хувьсах хугацаатай programm-г хэрэгжүүлээд үзээрэй.