Εκτίμηση της απόδοσης παράλληλων και κατανεμημένων συστημάτων μέσω της ανάλυσης μοντέλων ουρών αναμονής

Abstract

Parallel and distributed systems play a signi?cant role in everyday computing applications. Perfomance analysis of such systems using analytical quueueing models is hard because of their complexity. Most of these systems are servicing a variety of jobs having totally di®erent requirements. In addition, the load to such systems is highly unpredictable and extremely variable. Even the most simple queueing model of a parallel or distributed system that may consist of only a few number of servers, queues or job classes is extremely di±cult to solve analytically. This is the reason why most researchers have used simulation models rather that mathematical analysis to tackle problems emerging to these systems. However, analytical models of such system are extremely useful in deeply understanding their behavior. This PhD thesis consists of two general parts. In the ?rst part which consists of two chapters (2 and 3) we focus on the mathematical analysis of a queueing model of a parallel system that is very common in real life parallel systems' applications. In the second part which consists of two chapters also (4 and 5), we study two optimal control problems that appeal also too often in real distributed systems. In the next four paragraphs we discuss in more detail the content of the four main chapters of the thesis. In chapter 2, we analyze a parallel system with two identical servers and pure space sharing among rigid jobs. The parallel system is modeled as an M=M=2 queue with two types of jobs. Jobs of one type are parallel ones and require two servers while jobs of the other type need one server to start execution. Analysis of the system leads to a quartic polynomial for which a real root inside the unit disk is located. This root is then used to derive closed-form expressions for the mean queue length, mean response time as well as mean utilization of the system. The maximal utilization of the servers is also found. In addition, we provide an approximation that simpli?es the previously found exact but complex expressions and gives insight into the impact of di®erent parameters on system performance. Numerical experiments are presented and our formulae are validated by simulation. In chapter 3, a parallel system with two job classes is analyzed. Type-1 jobs require one server for their execution and have exponentially distributed service times while type-2 jobs need two servers and have general service times. The model consists of a single queue served by two servers that may work either independently or in parallel. It is assumed that all jobs are rigid and share the servers according to pure space sharing. This particular model constitutes a generalization of the model introduced in chapter 2. We provide closed-form expressions, exact as well as approximate, for various performance measures of interest. The approximate formula is found to be extremely accurate for various distributions of the service times of type-2 jobs. Furthermore, the maximal occupancy of the servers as well as the maximal throughput are examined. Finally, numerical results to investigate the impact of each parameter on system performance are conducted