Σταθμισμένη δρομολόγηση για εξυπηρέτηση υπολογισμών μεταβλητού μεγέθους σε ετερογενείς αρχιτεκτονικές.

Abstract

Σε ένα ετερογενές σύστημα αρχιτεκτονικής συνδυάζονται διαφορετικές αρχιτεκτονικές επεξεργαστών, για παράδειγμα, κεντρικών μονάδων επεξεργασίας και επεξεργαστές γραφικών, οι οποίοι μπορεί να συνδέονται στον ίδιο δίαυλο, να μοιράζονται διεργασίες και να έχουν κοινόχρηστη μνήμη. Τα συστήματα αυτά δέχονται διαφορετικές διαδικασίες από διάφορες πηγές, με διαφορετικές προτεραιότητες και βάρη, οι οποίες για την εκτέλεση τους απαιτούν διαφορετικές αρχιτεκτονικές επεξεργαστών. Τα παραπάνω επιτυγχάνονται με την χρονοδρομολόγηση. Η χρονοδρομολόγηση είναι η διαδικασία με την οποία οι διεργασίες αποκτούν πρόσβαση στους πόρους του συστήματος (π.χ. επεξεργαστή, μνήμη κ.α). Η ανάγκη για έναν αλγόριθμο χρονοδρομολόγησης προκύπτει από την απαίτηση γρήγορων υπολογιστών συστημάτων για την επίτευξη πολυεπεξεργασίας (εκτέλεση περισσότερων από μία διεργασία κάθε φορά) και πολυπλεξίας (ταυτόχρονη μετάδοση πολλαπλών ροών). Η χρονοδρομολόγηση είναι μια θεμελιώδης λειτουργία του λειτουργικού συστήματος που καθορίζει ποια διαδικασία θα εκτελεστεί, όταν υπάρχουν πολλές εκτελέσιμες διαδικασίες. Ο τρόπος χρονοδρομολόγησης της CPU είναι ιδιαίτερα σημαντικός επειδή έχει αντίκτυπο στην αξιοποίηση των πόρων του συστήματος και στις παραμέτρους των επιδόσεων. Υπάρχει μια πληθώρα από αλγόριθμους χρονοδρομολόγησης όπως η ουρά προτεραιότητας, η συντομότερη εργασία πρώτη, η χρονοδρομολόγηση Round Robin, η χρονοδρομολόγηση με βάση την προτεραιότητα κλπ, αλλά εξαιτίας μιας σειράς από μειονεκτήματα αυτές οι τεχνικές σπάνια χρησιμοποιούνται στα λειτουργικά συστήματα πραγματικού χρόνου, εκτός της χρονοδρομολόγησης Round Robin. Ειδικά σε ένα ετερογενές σύστημα πολλαπλών πυρήνων, με την ύπαρξη πολλαπλών ουρών, με διαφορετική προτεραιότητα και βάρος η καθεμία, η διαδικασία χρονοδρομολόγησης/αποστολής διεργασιών από κάθε ουρά ξεχωριστά αλλά στο σύνολό τους, είναι ένα κρίσιμο ζήτημα. Ο σκοπός της παρούσας εργασίας ήταν να βρεθεί, μελετηθεί και υλοποιηθεί σε μια γλώσσα προγραμματισμού, όπως η C, ένας αλγόριθμος, βασισμένος στα βάρη των εργασιών, για να επιτευχθεί καλύτερη διαχείριση τέτοιων ουρών.

Heterogeneous System Architecture (HSA) is a type of computer processor architecture that integrates different processor architectures, for example central processing units and graphics processors, on the same bus with shared tasking and memory. These systems have different processes from different sources, with different priorities and weights, which are required to be performed by different processors architectures. The above is achieved by scheduling. Scheduling is the process by which processes are given access to system resources (e.g. processor cycles, communications bandwidth). The demand for fast computer systems, the execution of multiple processes simultaneously (multitasking) and requirement for transmitting multiple flows simultaneously (multiplexing) have as a result the need for an efficient scheduling algorithm. The basic function of the scheduler is to determine which process will be run when there are several runnable processes. Therefore the scheduler choices have an impact on the utilization of system resources and other performance parameters. There exists a number of CPU scheduling algorithms like First Come First Serve, Shortest Job First Scheduling, Round Robin scheduling, Priority Scheduling etc, but due to a number of disadvantages these are rarely used in real time operating systems except Round Robin scheduling. Especially in a heterogeneous multicore system with existence of multiple queues with different priority and weight each, the scheduling/ dispatching of each queue separately and on the whole, is a critical issue. The purpose is to find, study and implement in a program language such us C, an algorithm to achieve a better management in such queues.