Öncelikle, projenin gereksinimlerinden birisi linux platformunda çalışması olduğundan, ben şahsi olarak bu proje için hem Windows, hem de Linux alternatifi bulunan Code::Blocks adlı ufak IDE'yi kullandım. Code::Blocks ile ilgili detaylı bilgiyi ve indirme linklerine buradan erişebilirsiniz.
Konu ile aşinalık kazanmak açısından önce bir işlemci zamanlayıcısının ne iş yaptığından ve işlemlerin CPU zamanını nasıl paylaştığından bahsedelim.
İşlemci dediğimiz bilgisayar parçası, verileri sequential yani sıralı olarak işlediğinden dolayı, normalde bir işlemcinin aynı anda birden fazla işlem çalıştırma olanağı yoktur. Eskiden kullanılan sistemlerde, işletim sistemleri sadece 1 işlem çalıştırmaya olanak tanıyordu. Multitasking dediğimiz olgu, işletim sistemlerine işlemci zamanlayıcısı eklenmeye başlamasıyla beraber hayatımıza girdi.
CPU Scheduler, yani işlemci zamanlayıcısı, bir işletim sisteminin sahip olduğu temel bileşenlerden birisidir. Bu bileşenin görevi, işlemci zamanını sistemde o an için çalışmakta olan işlem ve iş parçacıkları arasında paylaştırmaktır. Bu zamanlama sistemi için, her işlemin çalışma durumunu belirten 5 durum vardır.
Figür 1.0 - İşlemlerin zamanlayıcı içerisindeki durumları
New, yani yeni durumu, program çalışmaya başladığı andaki durumdur. Yeni yaratılan her işlem, zamanlayıcı tarafından kabul edilir ve ready, yani hazır durumuna geçerler. Hazır durumunda bulunan işlemler, zamanlayıcının kendilerine işlemciyi kullanmak için sıra vermesini beklerler, sıraları geldiği an running yani çalışmakta durumuna geçerler. Eğer işlem, herhangi bir I/O operasyonu gerçekleştirirse (örneğin hard diskten veri okuma gibi) waiting yani bekleme durumuna geçer ve I/O operasyonu bitip interrupt gelene kadar zamanlayıcı o işlemi pas geçer. En son durum olan terminated yani sonlandırılma durumu ise biten bir işlemin zamanlayıcı kuyruğundan silinmesidir.
İşlemlerin zamanlayıcı içerisindeki durumlarını öğrendiğimize göre, zamanlayıcının işlemler arası nasıl geçiş yaptığına göz atalım.
Zamanlayıcı, daha önce de değindiğim üzere işlemcinin zamanını işlemler arasında paylaştırarak, kullanıcıda sanki bütün işlemler aynı anda çalışıyormuş hissi yaratır. Aslında olan şey eldeki işlem gücünün paylaştırılmasından ibarettir, fakat bu çok hızlı gerçekleştiğinden dolayı sanki işlemci gerçekten aynı anda bütün işlemleri işliyormuş gibi gelir.
Zamanlayıcının işlemler arası yaptığı geçişe context switch denir ve context switch sırasında kendine ayrılan süre biten işlem ready durumuna, sırası gelen işlem ise running durumuna geçer. Bu işlem sırasında ready durumuna geçirilen işlemin o anki durumunu içeren bütün bilgi(stack, registerlar, işlem içerisinde en son kalınan yer(program counter) vesaire) Process Context Block yani kısaca PCB içerisine kaydedilir, ve running durumuna getirilen işlemin daha önceden kaydedilen PCB'si geri yüklenir. Bu sayede işlemler arası geçiş yapılırken volatile olan verinin kaybı yaşanmaz.
Zamanlayıcı, işlemleri sıraya koyarken ve bir sonraki turda kimin çalışacağına karar verirken belirli başlı algoritmalar kullanır. Bunlardan bazıları şunlardır;
1-) First come, first served (FCFS) (İlk gelen hizmeti ilk alır)
2-) Shortest job first(SJF) (En kısa işi olan hizmeti ilk alır)
3-) Priority scheduling (PS) (Öncelik sırası en yüksek olan hizmeti ilk alır)
4-) Round - robin scheduling (RRS)
Şimdi bu algoritmaların çalışma prensiplerinden bahsedelim.
First come first served
Bu zamanlama algoritmasının mantığını bir banka kuyruğuna benzetebiliriz. İşlemler kuyruğa sokulur ve -işlemin işinin ne kadar uzun süreceği gibi değerlere bakılmaksızın- önce gelen hizmeti ilk alır.
Shortest job first
Bu methodda ise, zamanlayıcı kuyrukta hazırda bekleyen işlemler arasından her zaman işi en kısa olanı seçer. Bu methodun preemptive ve non-preemptive modelleri bulunmaktadır.
Preemptive modelinde, eğer bir işlem running durumundayken, yeni bir işlem kuyruğa eklenirse ve eklenen işlemin süresi, running durumundaki işlemin kalan süresinden daha kısaysa, yeni gelen işlem running durumuna geçirilir ve şuan çalışmakta olan işlem ise ready durumuna getirilir. Yani, zamanlayıcı bu modda her zaman en kısa süresi olana öncelik tanır.
Non-preemptive modelinde ise, yeni bir işlem geldiğinde şuan çalışan işlem hiçbir şekilde duraksatılmaz. Yeni gelen işlem kuyruğa eklenir ve şuan çalışmakta olan işlemin sırasının bitmesini bekler.
Priority Scheduling
Bu method ile çalışan bir zamanlayıcı, işlemlere öncelik değerine göre sıra verir. Her işlemin sahip olduğu bir priority değeri bulunmakla beraber, priority'si yüksek olan işlemler, düşük olan işlemlere karşı baskındır. Bu methodun dezavantajı starvation olmakla beraber eğer priority'si yüksek işlemler çoğunluktaysa, prioritysi düşük olan işlemler zamanlayıcı tarafından hiç dispatch edilmeyebilir.
Bu methodun da preemptive ve non-preemptive modu bulunmakla beraber SJF'deki mantıkla aynı çalışır.
Round robin scheduling
Son methodumuzda, her işlem zamanlayıcı tarafından eşit zaman aralıkları ile çalıştırılır. Bu zaman aralığına time quantum denir.
Terminoloji kısmını bitirdiğimize göre, artık kod kısmına geçebiliriz. Projenin dosya okuma vesaire gibi temel kısımlarını konuyu kısa tutmak açısından atlıyorum.
İşlemleri tutmak için kullandığım struct ve array tanımlamaları;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #define MAX_PROCESS_ENTRY 255 int m_iTimeQuantum = 2; int m_iProcessEntryCount = 0; struct processEntry { // Constant values int iBurstTime,iArrivalTime,iPriority; // Varies every calculation int iIndex,iTickTime, iWaitingTime; int iSwitchTime; bool isDone; void Reset() { iTickTime = 0; iWaitingTime = 0; iSwitchTime = 0; isDone = false; } } ; processEntry m_arProcessEntries[255]; |
Methodların tanımlamaları ;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 | double SimulatorEngine::doFCFS() { double avg = 0; for(int i = 0; i < m_uiProcessCount; i++) { /* If this process is arrived while another one is in his burst, incoming process *has to* wait until current process finishes its' burst. So we have to calculate waiting time according to that. */ if(tickedTime > processArray[i].iArrivalTime) waitingTime = (tickedTime - processArray[i].iArrivalTime); else waitingTime = tickedTime; // Increase total tick time tickedTime += processArray[i].iBurstTime; // Assign calculated waiting time to process entry processArray[i].iWaitingTime = waitingTime; // Increase total waiting time avg += waitingTime; } // Divide total waiting time to process count to calculate the *average* avg /= m_uiProcessCount; return avg; } double SimulatorEngine::doPS() { double avg = 0; int totalTick = getTotalBurst(); if(m_isPreemptive) { do { int currentProcessPriority = INT_MAX; if(currentProcess != -1) currentProcessPriority = processArray[currentProcess].iPriority; // Temporary variables int highestProcIndex = -1; int highestPriority = INT_MAX; // Determine new current process for(int i = 0; i < m_uiProcessCount; i++) { // We're not interested in already finished process(es). if(processArray[i].isDone) continue; // The process is not arrived yet, so we're skipping it. if(processArray[i].iArrivalTime > tickedTime) continue; // Check if process has higher priority than current highest one if(processArray[i].iPriority < highestPriority) { highestPriority = processArray[i].iPriority; highestProcIndex = i; } } // Context switch occurs if and only if shortest remaining job has a shorter remaining time. if(highestPriority < currentProcessPriority|| (currentProcess != -1 && processArray[currentProcess].isDone)) currentProcess = highestProcIndex; for(int i = 0; i < m_uiProcessCount; i++) { // We're not gonna tick waiting time for current process if(i == currentProcess) continue; // Not arrived yet, skip if(processArray[i].iArrivalTime > tickedTime) continue; // Process is finished, skip if(processArray[i].isDone) continue; // In this case, process is waiting and we should tick the waiting time processArray[i].iWaitingTime++; avg++; } // Increase the tick amount of current process and determine whether it's done or not. if(++processArray[currentProcess].iTickTime == processArray[currentProcess].iBurstTime) processArray[currentProcess].isDone = true; } while(++tickedTime < totalTick); } else { do { // Check whether current process is finished his job if(currentProcess == -1 || (currentProcess != -1 && processArray[currentProcess].isDone)) { // Temporary variables int highestProcIndex = -1; int highestPriority = INT_MAX; // Determine new current process for(int i = 0; i < m_uiProcessCount; i++) { // We're not interested in already finished process(es). if(processArray[i].isDone) continue; // The process is not arrived yet, so we're skipping it. if(processArray[i].iArrivalTime > tickedTime) continue; // Check if process has higher priority than current highest one if(processArray[i].iPriority < highestPriority) { highestPriority = processArray[i].iPriority; highestProcIndex = i; } } // We've picked next available highest priority process. currentProcess = highestProcIndex; } for(int i = 0; i < m_uiProcessCount; i++) { // We're not gonna tick waiting time for current process if(i == currentProcess) continue; // Not arrived yet, skip if(processArray[i].iArrivalTime > tickedTime) continue; // Process is finished, skip if(processArray[i].isDone) continue; // In this case, process is waiting and we should tick the waiting time processArray[i].iWaitingTime++; avg++; } // Increase the tick amount of current process and determine whether it's done or not. if(++processArray[currentProcess].iTickTime == processArray[currentProcess].iBurstTime) processArray[currentProcess].isDone = true; } while(++tickedTime < totalTick); } return avg / m_uiProcessCount; } double SimulatorEngine::doSTS() { double avg = 0; int totalTick= getTotalBurst(); if(m_isPreemptive) { do { int shortestRemainingTime = INT_MAX; int currProcRemTime = INT_MAX; int shortestRemainingIndex = -1; if(currentProcess != -1) currProcRemTime = processArray[currentProcess].iBurstTime - processArray[currentProcess].iTickTime; for(int i = 0; i < m_uiProcessCount; i++) { if(i == currentProcess) continue; // Not arrived yet if(processArray[i].iArrivalTime > tickedTime) continue; // Already finished if(processArray[i].isDone) continue; if((processArray[i].iBurstTime - processArray[i].iTickTime) < shortestRemainingTime) { shortestRemainingTime = (processArray[i].iBurstTime - processArray[i].iTickTime); shortestRemainingIndex = i; } } // Context switch occurs if and only if shortest remaining job has a shorter remaining time. if(shortestRemainingTime < currProcRemTime || (currentProcess != -1 && processArray[currentProcess].isDone)) currentProcess = shortestRemainingIndex; // Tick the waiting process(es) for(int i = 0; i < m_uiProcessCount; i++) { // We're not gonna tick waiting time for current process if(i == currentProcess) continue; // Not arrived yet, skip if(processArray[i].iArrivalTime > tickedTime) continue; // Process is finished, skip if(processArray[i].isDone) continue; // In this case, process is waiting and we should tick the waiting time processArray[i].iWaitingTime++; avg++; } // Increase the tick amount of current process and determine whether it's done or not. if(++processArray[currentProcess].iTickTime == processArray[currentProcess].iBurstTime) processArray[currentProcess].isDone = true; } while(++tickedTime < totalTick); } else { for(int i = 0; i < m_uiProcessCount; i++) { /* If this process is arrived while another one is in his burst, incoming process *has to* wait until current process finishes its' burst. So we have to calculate waiting time according to that. */ if(tickedTime > processArray[i].iArrivalTime) waitingTime = (tickedTime - processArray[i].iArrivalTime); else waitingTime = tickedTime; // Increase total tick time tickedTime += processArray[i].iBurstTime; // Assign calculated waiting time to process entry processArray[i].iWaitingTime = waitingTime; // Increase total waiting time avg += waitingTime; } } // Divide total waiting time to process count to calculate the *average* return avg /= m_uiProcessCount; } double SimulatorEngine::doRRS() { double avg = 0; int totalTick= getTotalBurst(); //cout << "Time Quantum : " << m_uiTimeQuantum << endl; // Initial waiting times for(int i = 0; i < m_uiProcessCount; i++) { processArray[i].iWaitingTime += processArray[i].iArrivalTime % m_uiTimeQuantum; avg += processArray[i].iArrivalTime % m_uiTimeQuantum; } do { int roundTime = 0; for(int i = 0; i < m_uiProcessCount; i++) { if(processArray[i].isDone || (processArray[i].iArrivalTime > tickedTime)) continue; int remainingTime = processArray[i].iBurstTime - processArray[i].iTickTime; // cout << "Remaining time of #" << i << " : " << remainingTime << endl; roundTime = remainingTime > m_uiTimeQuantum ? m_uiTimeQuantum:remainingTime; // cout << "Round time for #" << i << " : " << roundTime << endl; processArray[i].iTickTime += roundTime; for(int j = 0; j < m_uiProcessCount; j++) { if(i == j || processArray[j].isDone || (processArray[j].iArrivalTime > tickedTime)) continue; processArray[j].iWaitingTime += roundTime; avg += roundTime; } if (processArray[i].iBurstTime == processArray[i].iTickTime) { // cout << "Process #" << i << " done." << endl; processArray[i].isDone = true; } tickedTime += roundTime; } } while(tickedTime < totalTick); //cout << "Ticked time : " << tickedTime << "Total tick : " << totalTick << endl; return avg / m_uiProcessCount; } |
Evet, bir makalenin daha sonuna geldik. İlerleyen zamanlarda ara ara eski ödev ve projelere yer vermeye devam edeceğim. Sağlıcakla kalın!
No comments:
Post a Comment