محاكاه خوارزميات جدوله المعالج -التطبيق العملي-

by evergreen Sat Mar 13, 2010 6:19 am

بسم الله الرحمن الرحيم ،

كنا
قد تكلمنا من قبل عن موضوع الجدوله وشرحنا عده أمور مهمه يجب أن تكون هي
الـ End Goal التي يجب أن نصل اليه من خلال أختيار أفضل خوارزميه من بين
عده خوارزميات . وفي ذلك الموضوع كنا قد وضعنا برنامج لمحاكاه خوازرميه
FCFS ، بالأضافه الى SJF والتي تبين فيما بعد أن هناك خلل بسيط بها ..

الموضوع الاصلي (مهم جدا لمن يريد فهم التطبيق) :
http://www.sudancs.com/viewtopic.php?f=13&t=50

موضوعنا
اليوم وهو محاوله محاكاه تلكم الخوارزميات وخاصه التي تصنف تحت
Non-Preemptive بشكل أكثر واقعيه ، أما بالنسبه لخوارزميات النوع
Preemptive فيصعب عملها باستخدام الأدوات التقليديه حيث يجب أن يكون هناك
Clock أو Timer يعمل بدأ من الساعه صفر وكل مره هذه الساعه تتغير بمقدار
واحد ، وبعدها نرى هل وصلت عمليه في هذا الزمن أم لأ ، وفي حال ذلك ندخل
العمليه .. وفي نفس اللحظه يجب أن يعمل برنامج فرعي (هل تشتم رائحه Thread
!) يقوم بالنظر الى أي عمليه قادمه وينظر في الأساس الى شيء معين على حسب
الخوازرميه ، فاذا كانت من النوع Priority فسوف ينظر الى الأولويه لتلك
العمليه ، وهنا في حال كانت أكبر من العمليه التي تعالج الأن ، سوف نقوم
بتوقيف Preempte العمليه الحاليه ونرجعها أخر الصف ، وندخل العمليه ذات
الأولويه الأكبر .. وهكذا سوف يعمل البرنامج ..

اذا علينا أن
نستخدم Timer بالأضافه الى Thread يقوم بعمليه الفحص هذه .. وبما أن لغه
سي++ لا تدعم هذه المفاهيم فيمكن أن نستخدم API النظام لحل تلك المشكله ،
أو نستخدم لغه سهله في هذه الأمور وبالطبع لا يوجد أسهل من الجميله جافا .

لذلك
سوف نركز في الموضوع اليوم على Non-Preemptive ، والمره القادمه سنبدأ في
كتابه المحاكي الدينامكي الذي كنت قد وعدت بكتابته في الموضوع السابق ..

حسنا ، بعد قرائتك للموضوع السابق ، سوف تكون لديك صوره مبسطه على طريقه عمل الخوارزميات هذه ، بالضبط كما توضحه الصوره التاليه :

في
الصوره أعلاه نلاحظ وجود ثلاثه أشياء رئيسيه ، وهي PCB وهي أختصار لـ
Process Control Block وهي كل ما تحتوي العمليه ، طبعا المحاكاه هنا بسيطه
لذلك سوف نتجاهل جميع الأمور ونأخذ في الأعتبار زمن الوصول والتنفيذ
والأنتظار والأولويه ، المكون الثاني وهو صف العمليات Ready Queue الذي
يختار المعالج منه العمليه المناسبه ، المكون الثالث وهو المعالج CPU وهي
الذي يأخذ من الصف ويرجع في أخر الصف ويقوم بالمعالجه ...

نبدأ بالمكون الأول وهو PCB ، وكما ذكرنا نريد فقط عده أشياء هي :

CODE:
int burstTime ; // time needed to execute process
int watingTime; // time that Process wating in readyQeue
int turnAroundTime; // time that Process take to finish ( burst + wating)
PriorityLevel pl ; // The Priority Of Process
int arraiveTime ; // Process Arrive Time

نقوم
بكتابه الملف الرأس Process.h ، لاحظ أنه فقط يحتوي على الأشياء الخاصه
بالعمليه ، بدون أحتوائه على أمور أخرى ككيفيه المعالجه فهذه من أختصاص
الـ CPU وليس الpcb .

لاحظ في الصوره التاليه الـ Interface
الخاصه بالملف ، وسوف نلاحظ الـ Encapsulate الجيد والـ Divition of
Responsibility أيضا في الكلاس فهو فقط يحتوي على بنيه pcb .

لاحظ دوال الـ Set & Get مهمه جدا فيما بعد ، وخاصه أنها Direct Access للمتغيرات الـ private .

الـدوال
الثلاثه الأخيره Operator Overloading ، طبعا هذه الدوال ضروريه جدا فيما
بعد ، وسوف نلاحظ أن هذه التقنيه من أفضل ما تميزت به لفه السي++ ، وخاصه
عندما نتعامل مع بني بيانات مثل LinkedList أو في حالتنا هذه Process .
طبعا الأولى للطباعه ، وسوف نطبع أشياء معينه في الكلاس والأخيرتين لاجراء
عمليات مقارنه بين عملتين ..

الكود المصدر للملف :

CODE:

/*
* Process
* class That Represnet The Process Control Block PCB
* and Hold Some Information about Process
* Tested in : G++ Compiler in MinGW Package
* Coded By : Wajdy Essam (romansy)
* FeedBack : SudanGeek@hotmail.com
*/

#include <iostream>
using namespace std ;

enum PriorityLevel { NO , Height , Low } ;

class Process
{
private :
// Process info
int burstTime ; // time needed to execute process
int watingTime; // time that Process wating in readyQeue
int turnAroundTime; // time that Process take to finish ( burst + wating)
PriorityLevel pl ; // The Priority Of Process
int arraiveTime ; // Process Arrive Time

public :
Process (int bt , int at = 0 , PriorityLevel p= NO ) : burstTime(bt),arraiveTime(at),pl(p)
{ setWatingTime(0); setTurnAroundTime(bt); }

void setBurstTime (int bt) { burstTime = bt ; }
void setWatingTime (int wt) { watingTime = wt ; }
void setTurnAroundTime (int at) { turnAroundTime = at; }
void setArraiveTime (int at) { arraiveTime = at ; }
void setPriorityLevel (PriorityLevel p) { pl = p ; }

int getBurstTime () { return burstTime ; }
int getWatingTime() { return watingTime; }
int getArraiveTime() { return arraiveTime ; }
int getTurnAroundTime() { return turnAroundTime; }
PriorityLevel getPriorityLevel () { return pl; }

friend ostream& operator << ( const ostream& out , const Process& p );
bool operator == (Process p );
bool operator > ( Process p );
};

bool Process :: operator > ( Process p )
{
if ( getArraiveTime() > p.getArraiveTime() )
return true ;
else
return false;
}

bool Process :: operator == ( Process p )
{
if ( getBurstTime() == p.getBurstTime() )
return true ;
else
return false;
}

ostream& operator << ( ostream& out , Process& p )
{
out << "[" << p.getBurstTime() << "," << p.getWatingTime() << "] " ;
return out ;
}

نأتي
الأن الى المكون الثاثي وهو الـ Ready Queue ، وهو عباره عن صف يحتوي على
العمليات ، حسنا هنا يمكن أن نطبق هذا الصف باستخدام المصفوفه العاديه
Array ولكننا سوف نخسر المساحه في حال عرفنا مصفوفه من 100 خانه ولم نحتاج
الى أكثر من 5 عمليات ! وفي الجهه الأخرى سوف يحصل OverFlow في حال عرفنا
مصفوفه من 5 خانات وأحتجنا الى أكثر من 10 عمليات .. لذلك الحل باستخدام
المصفوفات حل لا يجدي بتاتا ...

حل أخر ، وهو أستخدام مصفوفه قابله
للتوسع Vector ، طبعا حل ممتاز وقد يفي بالغرض ، ولكني بالعاده لا أحب
أستخدام الـ Utility classes الجاهزه وأحب أن أستخدم طرقي الخاصه وان كانت
أسوأ في الأداء . لذلك طبقت الصف باستخدام القوائم المتصله Double Linked List ...

حسنا
الأن قمنا بتكوين الصف وعرفنا كيف يمكن أن يكون الـ Implementation ، ولكن
مم تتكون العقد بداخل القائمه المتصله ؟ هل هي Int أو char .. بالطبع لا ،
نحن نتعامل مع صف من العمليات وليس صف من الأرقام أو الحروف .. لذلك
العقده يجب أن تكون من نوع Process . وهكذا يكون لدينا صف من العمليات.
طرق التعامل مع الـ Double Linked والـ Interface الذي يحتويه هذا الكلاس
مشروحه في قسم هياكل البيانات في موضوع "دوره في هياكل البيانات" للأخ
SudaNix وسوف تجد جميع المعلومات حول هذا الأمر ..

وبما أنه عاده
يجب أن تقوم بكتابه كلاس وخاصه في مثل هذه القوائم المتصله يعمل على
Primitive Data Type مثل int أو double وهذا أسهل من عمل قائمه لـ Process
من المره الأولى ، لذلك أبني العقده الواحده على النوع int ، وبعدها حول
هذا النوع الى Process وقم بتغيير ما يلزم ، أو الحل الأسهل وهو تحويل
الكلاس الى Template Based وكذا تكون رحيت دماغك من عمليه تحديد الـ Data
Type .
ننظر الى الـ Interface الخاص بالملف (بالطبع لن نحتاجها جميعا في عمليه المحاكاه ، ربما فقط 4 دوال منها ، ولكن زياده الخير خيرين ) .

لاحظ
التعامل مع الـ TYPE والذى لا نعرف الى ماذا يشير الى الأن ، قد يكون int
أو char (راجع درس الـ Template في قسم سي++ للأخ ابن تاشفين) ..

بالطبع لن نستغني أبدا عن الـ Operater Overloading وخاصه في مثل هذه الأوقات .

أخر
شيء والمفترض أني ما أتهاون في هذا الأمر ، وهو أنه جميع الـ Data في
الكلاس Node من نوع public وهذا غير والمفترض أن أقوم بجعلها private
وأقوم بتوفير Set&Get Function لكني تركتها كواجب تطبيقي للقارئ .

الكود المصدر للملف Double Linked List. :

CODE:

/*
* Double Linked List
* class that Make Double Linked List With Generic Data
* Tested in : G++ Compiler in MinGW Package
* Coded By : Wajdy Essam (romansy)
*FeedBack : SudanGeek@hotmail.com
*/

#include <iostream>
using namespace std ;

template <class TYPE>
class Node
{
public :
TYPE data ;
Node* next ;
Node* previous ;

Node (TYPE data ) : data(data) , next(NULL) , previous(NULL)
{ }
};

template <class TYPE>
class DoubleLinkedList
{
private :
Node<TYPE>* first ;
Node<TYPE>* last ;

public :
DoubleLinkedList () : first(NULL),last(NULL)
{ }

~DoubleLinkedList () ;
void forwardDisplay () ;
void backwardDisplay() ;
void insertAtFirst (TYPE d) ;
void insertAtLast (TYPE d) ;
void insertAtLoc (TYPE loc, TYPE d) ;
void removeAtFirst () ;
void removeAtLast () ;
void removeAtLoc (TYPE key) ;
int getCount () ;
void displayList () ;
void sort () ;
bool isEmpty () { return first == NULL ; }
Node<TYPE>* getAt (int index);
Node<TYPE>* operator[] (int index);
};

template <class TYPE >
DoubleLinkedList<TYPE> :: ~DoubleLinkedList()
{
// remove All Node
Node<TYPE>* current = first ;

while ( current != NULL )
{
Node<TYPE> *tmp = current ;
current = current->next ;
delete tmp ;
}
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: sort()
{
Node<TYPE>* current = first ;

while ( current != NULL )
{
Node<TYPE>* p = current ;

while ( p != NULL )
{
if ( current->data > p->data)
{
TYPE tmp = p->data ;
p->data = current->data ;
current->data = tmp ;
}
p = p->next ;
}
current = current->next ;
}
}

template <class TYPE >
int DoubleLinkedList<TYPE> :: getCount()
{
Node<TYPE>* tmp = first ;
int count = 0 ;

while ( tmp != NULL )
{
count++;
tmp = tmp->next;
}

return count ;
}

template <class TYPE >
Node<TYPE>* DoubleLinkedList<TYPE> :: getAt (int index)
{
Node<TYPE>* tmp = first ;

for (int i = 0 ; i<index ; i++)
tmp = tmp->next ;

return tmp ;
}

template <class TYPE >
Node<TYPE>* DoubleLinkedList<TYPE> :: operator[] (int index)
{
if ( index < 0 || index > getCount() )
return getAt(0) ;

Node<TYPE>* tmp = getAt(index) ;

return tmp ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: forwardDisplay ()
{
Node<TYPE>* current = first ;
cout << "\n\n" ;

while ( current != NULL )
{
cout << current->data ;

if ( current->next != NULL )
cout << " -> " ;

current = current->next ;
}

cout << "\n\n" ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: displayList ()
{
Node<TYPE>* current = first ;

while ( current != NULL )
{
cout << current->data.getBurstTime() << "\t\t\t"
<< current->data.getWatingTime() << "\t\t"
<< current->data.getTurnAroundTime() <<"\t\t" ;

if ( current->data.getPriorityLevel() == 0 )
cout << " NO " ;
else if ( current->data.getPriorityLevel() == 1 )
cout << " Hight " ;
else
cout << " LOW " ;

current= current->next ;

cout << "\n";
}
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: backwardDisplay ()
{
Node<TYPE>* current = last ;

while ( current != NULL )
{
cout << current->data << endl;
current = current->previous ;
}

cout << "\n\n" ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: insertAtFirst (TYPE d )
{
Node<TYPE>* myNode = new Node<TYPE>(d);

if ( first == NULL )
last = myNode ;

else
first->previous = myNode ;

myNode->next = first ;
first = myNode ;

}

template <class TYPE >
void DoubleLinkedList<TYPE> :: insertAtLast (TYPE d )
{
Node<TYPE>* myNode = new Node<TYPE>(d);

if ( first == NULL )
first = myNode ;

else
{
last->next = myNode ;
myNode->previous = last ;
}

last = myNode ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: insertAtLoc (TYPE loc , TYPE d)
{
Node<TYPE>* current = first ;
bool flag = false ;

while ( current != NULL )
{
if ( current->data == loc )
{
flag = true ;
break ;
}

current = current->next ;
}

if ( flag )
{
Node<TYPE>* myNode = new Node<TYPE>(d) ;

if ( current == last )
{
myNode->next = NULL ;
last = myNode;
}
else
{
myNode->next = current->next ;
current->next->previous = myNode ;
}

myNode->previous = current ;
current->next = myNode ;
}
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: removeAtFirst ()
{
Node<TYPE>* tmp = first ;

if ( first->next == NULL )
last = NULL ;

else
first->next->previous = NULL ;

first = first->next ;

delete tmp ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: removeAtLast ()
{
Node<TYPE>* tmp = last ;

if ( first->next == NULL )
first = NULL ;
else
last->previous->next = NULL ;

last = last->previous ;

delete tmp ;
}

template <class TYPE >
void DoubleLinkedList<TYPE> :: removeAtLoc (TYPE loc )
{
Node<TYPE>* current = first ;
bool flag = false ;

while ( current != NULL )
{
if ( current->data == loc )
{
flag = true ;
break ;
}

current = current->next ;
}

if ( flag )
{
if ( current == first )
first = current->next ;
else
current->previous->next = current->next ;

if ( current == last )
last = current->previous ;
else
current->next->previous = current->previous ;

delete current ;
}
}

نأتي
الأن لذكر المكون الرئيسي والذي يتحكم بكل العمليات وهو الـ CPU ، وصراحه
فكرت في طريقتين للتطبيق ، والأولى وهي عمل كلاس كامل يسمى CPU مهتمه فقط
معالجه العمليات وزياده أوقات الأنتظار للعمليات الأختيار .. وكما توضحه
الصوره التاليه :

وهنا
يجب بعدها أن أقوم بكتابه كل خوارزميه على حده ، لكن ما العلاقه التي
ستكون بين FCFS وبين CPU ؟ في الأصل FCFS هي طريقه للمعالجه يستخدمها الـ
CPU ... وبالطبع لا يمكن أن أجعل الكائن FCFS ضمن الكلاس CPU (تسمى
Composition) والسبب أنه هناك أكثر من خوازرميه نريد عملها ، يعني سنقوم
بعمل كائنات من كلاسات أخرى لا حاجه لنا بها ...

لو كنت أبرمج
بجافا ، كنت سأجعل FCFS يعمل implements للكلاس CPU (أظنها أفضل من عمليه
الـوراثه ) .. في سي++ يمكن أن أطبق مفهوم الـ Implemenst عن طريق الـ
Pure Virtual Function . وهنا سوف يكون الحال أفضل .. أي عمل كلاس CPU
يحتوي على الدوال أعلاه Pure ومن ثم أي كلاس FCFS وأي خوارزميه أخرى تعمل
وراثه للكلاس CPU وتعيد تعريف الدوال ..

الحل السابق ،ربما يكون
أفضل الحلول ، ولكن فضلت الحل الأسهل في رأيي وهو عمل كلاس FCFS ، وضمنه
يكون هناك معالج cpu يعمل على العمليات الموجوده في الصف ... صحيح أننا
سنضطر أن نعيد أجزاء كثيره من هذا الكلاس في الخوارزميه الأخرى مثلا RR ،
ولكن هذا أفضل وأسهل الحلول الأن ، اذا كنت تقترح حلول أخرى فبالتأكيد سوف
أرحب بها ...

نبدأ الأن في الخوارزميه الأولى وهي First Come First Server :

ننظر الى المتغيرات والدوال في الكلاس السابق ، حيث سنقوم باستخدامها بنفس الشكل والصوره في الخوارزميات الأخرى ،

أولا
ننظر الى طريقه تكوين الصف Queue حيث قمنا بعمل كائن من القائمه المترتبطه
تكون العقده فيها من نوع Process ، في حال أردنا أن نغير النوع الى مثلا
Membery فقط سنقوم بتغيير هذا السطر ، ولن نلمس الكلاس LinedList أبدا ،
هل عرفت فائده الTemplate الأن ؟

المتغير
numberOrPreocess و num هم عباره عن عداد لعدد العمليات في القائمه ،
المتغير waitTime هو عباره عن مجموع الـ waitTime لجميع العمليات في
القائمه ، المؤشر waitingTime هو يؤشر لمصوفه عددها هو عدد
numberOrPreocess الغرض منه حفظ زمن الأنتظار لكل عمليه في القائمه (طبعا
الكلاس Process يحتوي على متغير من نفس النوع ، لذلك قد تتسأئل ما الحاجه
هنا ؟) والسبب أننا أثناء المعالجه سوف نقوم بحذف العمليات من االصف
وبالتي سوف ينحذف هذا المتغير ، لذلك كل ما في الأمر استخدمنا المؤشر لكي
نحفظ به أزمان التأخير للعمليات لأننا كما ذكرنا سوف نقوم بحذفها لاحقا .
نفس الأمر مع المؤشر brustTime .

الدوال Menu لطباعه قائمه ، لا
دخل لها بالكلاس ويفضل أن تجعلها Non-Member Function ، الدوال setProces
هي لأخذ معلومات العمليه مثل زمن التنفيذ وعدد العمليات التي نريد
معالجتها و getProcess هي لطباعه معلومات العمليات الموجوده بالصف .. يمكن
أن نجعل هاتين الدوال أيضا Non-Member ولكن علينا أن نرسل لها الصف Queue
كمعامل ..

الداله المسؤوله عن كل شيء هي calculate (يمكن أن نشبها
بالمجدول Shecduler) حيث يقوم باختيار العمليه التاليه ، ويقوم بتمرريها
الى الداله cpu (المعالج) والذي بدوره يقوم بتنفيذ العمليه ، ومن ثم نقوم
بحذف العمليه بعد أنتائها ، وسوف نقوم أنثاء معالجه العمليه بزياده زمن
التأخير لكل العمليات الأخرى في الصف .. وسوف نكرر هذا الكلام الى أن
ينتهي الصف ويصبح Empty .

لاحظ في الكود المصدر التالي أن الداله calculate تقوم باختيار العمليه بناء على :

CODE:
Process p = Queue[i]->data;

حيث
i هو متغير لن نزيد قيمته وسوف تكون ثابته صفر (0) ، أي كل مره سنأخذ
العمليه الأولى في الصف ، بالطبع بعدما نعاجلها سوف نقوم بحذفها من الصف
والا سندور في حلقه لا نهائيه .

المخرج من تنفيذ البرنامج السابق :

حسنا
، أهم ما في المخرج أنك تتعرف متى يقوم المعالج بالتعامل مع العمليه
الجديده ، وهنا ستجد العباره New Process (بين قوسين زمن المعالجه وزمن
الانتظار الذي يكون في البدايه صفر) in CPU .

لاحظ أن صف العمليات
هنا بناء على FCFS أي المعالجه من هذا الأساس .. وستجد عندما تعالجت 24 ،
تم زياده زمن الأنتظار للعملتين ذات الرقم 3 ، وأصبح كل منهم زمن الأنتظار
له 24 ، والعمليه الأخيره زمن الأنتظار لها أصبح 27 بسبب أنتظارها للعمليه
الثانيه ..

الكود المصدر للملف FCFS :

CODE:

/*
* Operation System
* CPU Scheduling Algorithms
* First Came First Serve[FCFS]
* Strategy : None-Preemptive
* Coded By : Wajdy Essam
* Data Structure : Queue implemenation via Double Linked List That Hold Process
* Tested in : G++ Compiler in MinGW Package
* FeedBack : SudanGeek@hotmail.com
*/

#include <iostream>
#include "Process.h"
#include "DoubleLinkedList.h"
using namespace std ;

class FCFS
{
private :
DoubleLinkedList<Process> Queue ;
int numberOfProcess ;
int waitTime ;
int num ;

int *waitingTime ;
int *brustTime ;

public :
int menu () ;
void setProcessInfo () ;
void getProcessInfo () ;
void calculate () ;
void result () ;
int CPU (Process & p ) ;
void increaseOtherWaitingTime (int index , int waitTime);
};

void FCFS :: result ()
{
cout << "Burst Time \t Wating Time \t TurnAround Time \t \n" ;

cout << "\n" ;

for (int i=0 ; i<num ; i++)
{
cout << " " << brustTime[i] << "\t\t" ;
cout << " " << waitingTime[i] << "\t\t" ;
cout << " " << brustTime[i]+ waitingTime[i] << endl;
}

cout << "\n\nWating Time = " << waitTime << endl;
cout << "Average Time = " << (waitTime)/num << endl;
}

int FCFS :: CPU (Process& p )
{
cout << "Now Process : " << p << " In CPU \n" ;
int t = p.getBurstTime() ;
p.setBurstTime(0);
cout << "After Process : " << p << " In CPU \n" ;
return t ;
}

void FCFS :: increaseOtherWaitingTime (int index , int waitTime)
{
for (int i=0 ; i<numberOfProcess ; i++)
{
Queue[i]->data.setWatingTime( Queue[i]->data.getWatingTime() + waitTime);
}
}

void FCFS :: calculate ()
{
int i = 0 ;
int count = 0 ;
while ( ! Queue.isEmpty() )
{
Process p = Queue[i]->data;
Process tmp = p ;
int pTime = CPU(p);

getProcessInfo();

cout << "Process Leave : " << p << " From The Queue \n" ;
numberOfProcess-- ;
waitTime += p.getWatingTime();
waitingTime[count++] = p.getWatingTime();
Queue.removeAtLoc(tmp);

increaseOtherWaitingTime(i,pTime);
}
}

void FCFS :: getProcessInfo ()
{
Queue.forwardDisplay();
}

void FCFS :: setProcessInfo ()
{
cout << "\n\nEnter The Number of Process's : " ;
cin >> numberOfProcess ;

cout << "\n\n" ;

waitingTime = new int[numberOfProcess] ;
brustTime = new int[numberOfProcess] ;

for (int i=0 ; i<numberOfProcess ; i++)
{
cout << "Enter Burst Time For [" << (i+1) << "] Process : " ;
int bTime ;
cin >> bTime ;

brustTime[i] = bTime ;
Process p(bTime);
Queue.insertAtLast( p ) ;
}

waitTime = 0 ;
num = numberOfProcess ;
}

int FCFS:: menu ()
{
cout << "\n\n Enter Process Info (Number And QuantumTime) ............ [1] \n" ;
cout << " Exit From System ....................................... [2] \n" ;
cout << "\n \t\t >> " ;

int choice ;
cin >> choice ;

return choice ;
}

int main ()
{
bool state = true ;

while ( state )
{
FCFS fcfs ;

switch ( fcfs.menu() )
{
case 1 :
fcfs.setProcessInfo();
cout << "\n\nBefore Complete : \n" ;
fcfs.calculate() ;
cout << "\n\nAfter Complete : \n" ;
fcfs.result();
break ;

case 2 :
state = false ;
cout << "\n\nThank You For Using Out System ..... !\n\n";
break ;

default :
cout << "\n\nInvalid Choice , Try again ....!\n\n";
break ;
}
}

return 0 ;
}

نأتي
الأن للخوارزميه Round Robin وأختصارا RR ، وهذه الخوازرميه من نوع
Preemptive ولكن في هذه الخوازرميه لن نحتاج الى Timer لأن المعالج به
Timer يسمى QuantumTime يعالج به أي عمليه ، ففي حالت أنتهت العمليه من
المعالجه بعد أنتهاء فتره الـ Qunatum فسوف تخرج من الصف ،والا في هذه
الحاله سوف ترجع الى أخر الصف .. وهكذا تستمر العمليه الى أن ينتهي الصف ..

لو نظرنا الى الـ Interface الخاص به ، سنجده مشابه تماما للFCFS :

أيضا
يتشابه في أختيار العمليه ، حيث يقوم RR باختيار العمليه الأولى في الصف ،
لكن المعالجه تختلف ، حيث قبل أن نبدأ علميه المعالجه علينا أن نختبر قيمه
الـ Burst Time لهذه العمليه (زمن تنفيذها) فاذا كان أقل من الـ Quntum
Time (الزمن الثابت للمعالجه والذي سوف تقوم بادخاله عن طريق الداله
الجديده setQuntumTime ) سوف نقوم بتنفيذ هذ العمليه ونحذفها من الصف
وبالطبع نقوم بزياده زمن الأنتظار لكل العمليات الأخر في الصف (وهي القيمه
الراجعه من المعالج والتي سوف تكون دليل على الزمن التي استغرقته العمليه
في المعالجه ، كل ما في الأمر أننا سنأخذ هذه القيمه ونمررها الى داله
الزياده ).

أيضا في داله الأدخال setProcess سوف أقوم باستدعاء داله ادخال quntumTime ..

المخرج من تنفيذ البرنامج السابق :

لاحظ
أن العمليه اذا كان لها زمن تنتفيذ أكبر من قيمه الQuntime التي أدخلناها
في المخرج السابق 2 ، سوف تقوم بانقاص زمن المعالجه لها بمقدار الـ Quntum
وترجع الى أخر الصف ، وفي نفس الوقت نقوم بزياده زمن التأخير لجميع
العمليات في الصف بهذا المقدار .

نأتي الأن الى الخوارزميه
الثالثه وهي Shotest Jop First وهي اختصارا لـ SJF ، هنا في هذه
الخوارزميه كل ما يهمنا هو التعامل مع أقل عمليه وصلت مبكرا ... أي أقل
Brust وفي نفس الوقت تكون أقل زمن وصول Arrive Time (هنا سوف نستخدم
المتغير arrive الموجود في الملف process ) طبعا لن يكون هناك quntum ..

لاحظ
الـ Interface في الأعلى ، هو نفسه السابق بالضبط ، لكن مع زياده داله
getMin والتي ترجع العمليه الأصغر ذات الأقل زمن وصول Arrive Time وفي حال
تساوت عمليتين بنفس الزمن سوف ننظر الى زمن المعاجله ونأخذ الأقل Brust
Time .

المعالج هنا هو نفسه المعالج في FCFS لا يعطي أي اهتمام لأي
عمليه أخرى الا عندما ينتهي من التي بين يديه ، أهم نقطه قبل عمليه Calc
هي عمليه الترتيب sort ، حيث سنقوم بترتيب العمليات بشكل تصاعدي (من
الأصغر الى الأكبر ) هل تذكر المعامل < الذي قمنا باعاده تعريفه في
Process ، أنظر الى DoubleLinkedList في الداله sort وستجد فائدته هناك .

CODE:
if ( current->data > p->data)
{
TYPE tmp = p->data ;
p->data = current->data ;
current->data = tmp ;
}

لاحظ عمليه المقارنه هنا حيث data هو نوع غير معروف ، شكرا للخاصيه Template ووجود الـ Operator Overloading حيث بالأمكان عمل شفره واضحه للجميع باستخدام هذه المفاهيم الرائعه ..

أخر
أختلاف هنا وهي في الداله setProcess حيث سنقوم بادخال زمن الوصول لكل
عمليه ، المره القادمه في حال قمنا بعمل محاكي دينامكي لن نضطر الى ادخال
هذا الزمن لأنه المفترض يكون على حسب System Clock .

المخرج من خوارزميه SJF :

تبقت
الأن خوارزميتان هما Priority و Shotest Remaining Time First وأختصارا
SRTF .. هاتين الخوارزميتن من النوع Preemptive والذي "يجب" و"يجب" أن
يكون هناك Timer حتى نطبق مفهوم الـ Preemptive بالشكل ، طبعا نستطيع
تطبيق مفهوم الـ Timer بأبسط الطرق عن طريق متغير وكل دوره في الحلقه نقوم
بزياده واحد لهذا المتغير ، ولكن "يجب" أن يكون هناك مراقب لأي عمليه
جديده تدخل للنظام حتى نقوم بعمل اسقاط للعمليه الحاليه .. باختصار يجب أن
يكون الأمر More Dynamic !

باذن الله ، المره القادمه نحاول أن
نبدأ في كتابه محاكي للمعالج بشكل كامل وان شاء الله نستطيع بعمله
بمساعدتكم ، بعدها ربما يكون هذا المحاكي وسيله جيده للتدريس محاضره الـ
Process Scheduling بشكل ديناميكي يجعل الطالب أكثر أستيعابا للأمر ..

ملاحظه
أخيره ، البرامج أعلاه لن تعمل في Trbuo C++ 4 الا بعد تغييرات بسيطه (عده
أسطر) وقد تعمدت ذلك حتى يتعلم الطلاب هنا أن استخدام هذا المترجم سوف
يخفي الكثير من المفاهيم الضروريه ، لذلك عليك من الأن أخي الطالب عدم
التعامل بتاتا مع مثل هذا المترجم القديم واستخدام مترجمات سي++ قياسيه
جديده ، والا فلن تستطيع تنفيذ هذه البرامج ، أو أدفع $$ وسأكتبها لك بلغه
الأله أن أردت ذلك .

البرامج ملحقه في المرفقات ....

بالتوفيق للجميع ،

المرفقات:

Process Scheduling Algorithms.rar [324.26 KiB]

203 مرة