Faculty: Computer Science
Speciality: System programming
INTRODUCTION
Progress of modern branches of technics, technologies and biotechnologies, technologies of an environment, depends on a level of the theory and practical realization of methods of designing of the automated technical objects, technological installations and lines which are defined as difficult dynamic systems (DDS). In the list of factors of the unconditional decision of a problem of warranting of novelty and quality of design decisions the main place methods and occupy means modelling of dynamic systems which can be used at all stages of project DDS - from the formulation of technical and economic requirements, development and system designing, to tests and the beginning of pre-production operation [1]. However, complexity of such systems can be high (millions differential equations) and thereof modelling will demand significant hardware resources which will be used at the decision. However it is necessary to notice, that manufacturers of hardware do not stand on a place and every year the market of high-efficiency computing systems replenishes with new systems and architecture.
THEME’S ACTUALITY
Thus, the urgency of a theme given masters work can be considered works from the several sides. On the one hand - the author will develop the new distributed algorithm which will be tested on methods and enough known algorithms of modelling of difficult dynamic systems with the distributed parameters is offered. With another - indisputable innovation developed and researched system as in Ukraine in a kind of the objective reasons there is no opportunity to prosecute subjects of a similar sort.
PURPOSE, GOALS, OBJECT
The purpose of work is development mean of modelling by research of models of difficult dynamic systems is possible. The primary goals include:
Object of development is the algorithm of planning, and a subject means of modelling.
THE SCIENTIFIC NOVELTY
Scientific novelty consists in development of new means of modelling which basis is the developed algorithm of planning. The basic concepts of planning of processes.
REVIEW OF RESEARCH AND DELELOPMENT
Planning - maintenance of serial access of processes to one processor [3]. The scheduler - responsible is a part of operational system. Algorithm of planning - used algorithm for planning. The algorithm of planning without switchings (not priority) - does not demand interruption on the hardware timer, process stops only when is blocked or finishes work. The algorithm of planning with switchings (priority) - demands interruption on the hardware timer, process works only the allocated period of time, after that it stops on the timer to transmit management to the scheduler. Necessity of algorithm of planning depends on tasks for which the operational system will be used. The basic three systems: Systems of batch operation - can use not priority and priority algorithm (for example: for settlement programs); interactive systems - can use only priority algorithm, it is impossible to allow that one process has borrowed for a long time the processor (for example: a server of the common access or a personal computer); systems of real time - can use not priority and priority algorithm (for example: a control system of the car). In work systems of real time are considered just. Standard algorithms of planning [4]:
• " The First has come - by the first is served " (FIFO - First In Fist Out)
Processes are put in turn in process of receipt.
Advantages:
• Simplicity
• Validity (as in turn of buyers who last has come, that has appeared in the end of turn)
Lacks:
• The Process limited by opportunities of the processor can brake faster processes limited by devices of input/conclusion.
• " The Shortest task - the first " [5]
Advantages:
• Reduction of turnaround time
• Validity (as in turn of buyers who without delivery passes in before)
Lacks:
• Long process the borrowed processor, will not start up newer brief processes which send later.
• The Least remained time performance
The analogue previous but if new process comes, its full time of performance is compared to remained time of performance of current process.
• Three-level planning
The scheduler of access chooses tasks in the optimum image (for example: the processes limited by the processor and input/conclusion).
If in memory it is too much processes, the scheduler of memory unloads and loads some processes on a disk. The amount of processes being memory, refers to as a degree multitasking.
• Cyclic planning
The most simple algorithm of planning and often used.
The quantum of time of the processor is given to each process. When the quantum comes to an end process is translated by the scheduler in the end of turn. At blocking the processor drops out of turn.
Advantages:
• Simplicity
• Validity (as in turn of buyers, to everyone only on kg)
Lacks:
• If frequent switchings (quantum – 4 ms, and time of switching is equal 1 ms) there is a reduction of productivity.
• If rare switchings (quantum – 100 ms, and time of switching is equal 1 ms) there is an increase in time of the answer at inquiry.
• Priority planning[6,7]
To each process the priority is appropriated, and management is transferred process with the highest priority.
The priority can be dynamic and static.
The dynamic priority can be established so:
П=1/Т, where Т-a part of the quantum used last time
If 1/50 quantums, a priority 50 are used.
If all quantum, a priority 1 is used.
I.e. the processes limited by input/conclusion, will have a priority above processes limited by the processor.
Often processes unite on priorities in groups, and use priority planning among groups, but inside of group use cyclic planning.
• Groups with different quantum of time[8]
First process gets in group with the greatest priority and the least quantum of time if it uses all quantum gets in the second group, etc. the longest processes appear in group of the least priority and the greatest quantum of time. Process either finishes work, or passes in other group. This method reminds algorithm - " the Shortest task - the first ".
• Groups with different purpose of processes
Such mechanism allows to increase a priority of work with the client.
• The Guaranteed planning
In system with n-processes, to each process it will be given 1/n to time of the processor.
• Lottery planning
" Lottery tickets " for access to resources are distributed to processes. The scheduler can choose any ticket, casual image. The more tickets process, the has more at it than chances to grasp a resource.
• Fair planning
Processor time is distributed among users, instead of processes. It is fair if at one user some processes, and at another one.
• Planning in systems of real time[9]
Systems of real time share on:
• Rigid (rigid terms for each task) - management of movement
• Flexible (infringement of the time schedule are not desirable, but are admissible) - management of video and audio
External events to which the system should react, share:
• Periodic - stream video and audio
• Acyclic (unpredictable) - a signal about a fire
That the system of real time could be planned, it is necessary that the condition was satisfied in (1).
m - number of periodic events
i - number of event
P (i) - the period of receipt of event
T (i) - time which leaves on processing of event
I.e. the overloaded system of real time is not planned.
• Planning homogeneous processes
As homogeneous processes it is possible to consider video a server with several videos streams (some users look film).
Since all processes are important, it is possible to use cyclic planning.
But as the quantity of users and the sizes of the staff can vary, for real systems it does not approach.
• The General planning real time
The model when each process struggles for the processor with the task and the schedule of its performance is used.
The scheduler should know:
• Frequency from which each process should work
• Amount of works which to it should be executed
• The nearest term of performance of the next portion of the task
Let's consider an example from three processes. Process and is started every 30 ms, processing of the staff 10 ms. Process in frequency of 25 staff, i.e. everyone 40 ms, processing of the staff 15 ms. Process with frequency of 20 staff, i.e. everyone 50 ms, processing of the staff 5 ms (fig. 1).
We check, whether it is possible to plan these processes.
10/30+15/40+5/50=0.808 <1
The condition is carried out, to plan it is possible. Let's plan these processes static (the priority in advance is appointed to each process) and dynamic methods.
• Static algorithm of planning RMS (Rate Monotonic Scheduling)
Processes should satisfy to conditions:
• Process should be completed in time its period
• One process should not depend on another
• Identical processor time for each interval is required to Each process
• Acyclic processes do not have rigid terms
• Interruption of process occurs instantly
The priority in this algorithm is proportional to frequency. And it is equal to process 33 (frequency of the staff). In it is equal to process 25. With it is equal to process 20. Processes are carried out on a priority (fig. 2).
• Dynamic algorithm of planning EDF (Earliest Deadline First) [10]
The greatest priority is exposed to process which still had the least time of performance.
At big loadings system EDF has advantages.
Let's consider an example when And it is required to process for processing the staff – 15 ms.
We check, whether it is possible to plan these processes.
15/30+15/40+5/50=0.975 <1
Loading of system of 97.5 % (fig. 3).
CONCLUSION
As a result of research work were collected and studied materials on questions, to related to the theme of master's degree work. The applied methods and scheduling and development of leading firms algorithms, offered instrumental and programmatic facilities, principles of their construction were investigational. Instrumental programmatic models are developed for measuring of temporal parameters. Instrumental program models are developed for measuring of temporal parameters. Researches by programmatic models allowed to get the intervals of change of initial parameters for scheduling of time-tables algorithms. At writing of this abstract of thesis master's degree work is not yet completed.
REFERENCES
1. Святний В.А. Стан та перспективи розробок паралельних моделюючих середовищ для складних динамічних систем з розподіленими та зосередженими параметрами / В.А Святний, О.В. Молдованова, А.М. Чут // «Паралельне моделювання 2008».
2. Huang W. A parallel computing framework for dynamic power balancing in adaptive mesh refinement applications proceedings of Parallel Computational Fluid Dynamics / W. Huang, D.K. Tafti. – Wiiliamsburg.: VA, 1999. – 670 p.
3. Таненбаум Э. Современные операционные системы. 2-е изд / Э. Танненбаум. – СПб.: Питер, 2002. – 1040 с.: ил.
4. Олифер В.Г. Сетевые операционные системы / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2002. – 504 с.: ил.
5. Информационно аналитический центр о параллельных вычислениях и суперЭВМ [Электронный ресурс] http://parallel.ru
6. Таненбаум Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум, М. ван Стеен. – СПб.: Питер, 2003. – 887 с.: ил.
7. Бовет Д. Ядро Linux / Д. Бовет, М. Чезати. – СПб.: БХВ-Петербург, 2007. – 1104 с.: ил.
8. Martello S. Knapsack Problems / S. Martello, P. Toth – NY.: Wilies, 2006. – 275 p.
9. Pochet Y. Production Planning by Mixed Integer Programming / Y. Pochet, Laurence A. Wolsey – NY.: Springer, 2000. – 260 p.
10. Курс лекций о теории планирования [Электронный ресурс] http://www.intuit.ru/department/os/osintro/3/