Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Процесс пен желілік жоспарлаушылар қолданатын алгоритмдер Есептеуде жоспарлау
Algorithm employed by process and network schedulers in computing
scheduling in computing
Round robin (RR) – есептеуде процесс пен желілік жоспарлаушылар қолданатын алгоритмдердің бірі. Әдетте қолданылатындай, уақыт тілімдері (уақыт кванты деп те аталады) әр процеске тең үлестерде және айналма ретімен беріледі, барлық процестерді басымдықсыз (циклдік орындаушы деп те аталады) басқарады. Round robin жоспарлауы қарапайым, орындалуы оңай және процестердің тоқтауына жол бермейді. Round robin жоспарлау басқа жоспарлау мәселелеріне де қолданылуы мүмкін, мысалы компьютерлік желілердегі дерек пакеттерін жоспарлауға. Бұл операциялық жүйе тұжырымы. Алгоритмнің атауы басқа салалардан белгілі, әр адам өз кезегімен бірдей үлес алатын дөңгелек робин принципінен алынған.
Round robin (RR) is one of the algorithms employed by process and network schedulers in computing. As the term is generally used, time slices (also known as time quanta) are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as cyclic executive). Round robin scheduling is simple, easy to implement, and starvation free. Round robin scheduling can be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an operating system concept. The name of the algorithm comes from the round robin principle known from other fields, where each person takes an equal share of something in turn.
Желілік пакеттерді жоспарлау
Ең жақсы күш-жігермен пакеттік коммутацияда және басқа статистикалық мультиплекстеуде, дөңгелек робинді жоспарлау бірінші келгеніне бірінші кезекте тұрудың орнына қолданылуы мүмкін. Мультиплексор, коммутатор немесе маршрутизатор әрбір дерек ағыны үшін жеке кезекшеге ие болады, мұнда дерек ағыны оның бастапқы және түменгі мекенжайы бойынша анықталады. Алгоритм кезекте дерек пакеттері бар әрбір белсенді дерек ағынына ортақ арнада пакеттерді кезең-кезеңмен, қайталама тәртіппен жіберуге мүмкіндік береді. Жоспарлау жұмысқа қабілетті, яғни егер бір ағын пакеттерінен таусылса, келесі дерек ағыны оның орнын басады. Осылайша, жоспарлау байланыс ресурстарының босқа кетіп қалуын болдырмауға тырысады. Дерек пакеттерінің мөлшері бірдей болған жағдайда, дөңгелек робинді жоспарлау ең-аз әділділікке қол жеткізеді, себебі ең ұзақ күткен дерек ағынына жоспарлау басымдығы беріледі. Егер дерек пакеттерінің мөлшері бір жұмыстан екіншісіне күрт өзгеше болса, бұл қанағаттандырмауы мүмкін. Үлкен пакеттерді өндіретін пайдаланушы басқа пайдаланушылардан артықшылық алады. Мұндай жағдайда әділ кезекке тұру тиімдірек болар еді. Егер қызмет сапасының кепілді немесе дифференциалды деңгейде ұсынылса, тек ең жақсы күш-жігермен байланыс емес, дефицитті дөңгелек робинді (DRR) жоспарлау, салмақты дөңгелек робинді (WRR) жоспарлау немесе салмақты әділ кезекке тұру (WFQ) қарастырылуы мүмкін. Бірнеше терминалдар ортақ физикалық ортаға қосылған көп қолжетімді желілерде дөңгелек робинді жоспарлауды токендік кіру арналарының схемалары, мысалы, Token Ring, немесе орталық басқару стансасынан дауыс беру немесе ресурстарды резервтеу арқылы қамтамасыз етуге болады. Орталықтандырылған сымсыз пакеттік радио желісінде, көптеген станциялар бір жиілік арнасын бөліседі, орталық базалық станцияның жоспарлау алгоритмі мобильді станциялар үшін дөңгелек робиндік режимде уақыт тілімдерін резервтеу арқылы әділдікті қамтамасыз ете алады. Дегенмен, егер байланыс жағдайын бейімдеу қолданылса, "құнды" пайдаланушыларға басқаларға қарағанда белгілі бір көлемдегі деректерді жіберу үшін көбірек уақыт қажет болады, себебі арна жағдайлары әртүрлі. Таратуды арна жағдайлары жақсарғанша күту немесе кем дегенде жоспарлауды арзан пайдаланушыларға басымдық беру тиімдірек болар еді. Дөңгелек робинді жоспарлау мұны пайдаланбайды. Жоғары өтімділікке және жүйелік спектр тиімділігіне арнаға тәуелді жоспарлау арқылы қол жеткізуге болады, мысалы, пропорционалды әділ алгоритм немесе максималды өтімділік жоспарлау. Соңғысы жоспарлаудың тоқтауымен сипатталады. Бұл жоспарлау түрі компьютерлердегі операциялық жүйелердің негізгі алгоритмдерінің бірі болып табылады және оны дөңгелек кезек дерек құрылымы арқылы жүзеге асыруға болады.
In best effort packet switching and other statistical multiplexing, round robin scheduling can be used as an alternative to first come first served queuing. A multiplexer, switch, or router that provides round robin scheduling has a separate queue for every data flow, where a data flow may be identified by its source and destination address. The algorithm allows every active data flow that has data packets in the queue to take turns in transferring packets on a shared channel in a periodically repeated order. The scheduling is work conserving, meaning that if one flow is out of packets, the next data flow will take its place. Hence, the scheduling tries to prevent link resources from going unused. Round robin scheduling results in max min fairness if the data packets are equally sized, since the data flow that has waited the longest time is given scheduling priority. It may not be desirable if the size of the data packets varies widely from one job to another. A user that produces large packets would be favored over other users. In that case fair queuing would be preferable. If guaranteed or differentiated quality of service is offered, and not only best effort communication, deficit round robin (DRR) scheduling, weighted round robin (WRR) scheduling, or weighted fair queuing (WFQ) may be considered. In multiple access networks, where several terminals are connected to a shared physical medium, round robin scheduling may be provided by token passing channel access schemes such as Token Ring, or by polling or resource reservation from a central control station. In a centralized wireless packet radio network, where many stations share one frequency channel, a scheduling algorithm in a central base station may reserve time slots for the mobile stations in a round robin fashion and provide fairness. However, if link adaptation is used, it will take a much longer time to transmit a certain amount of data to "expensive" users than to others since the channel conditions differ. It would be more efficient to wait with the transmission until the channel conditions are improved, or at least to give scheduling priority to less expensive users. Round robin scheduling does not utilize this. Higher throughput and system spectrum efficiency may be achieved by channel dependent scheduling, for example a proportionally fair algorithm, or maximum throughput scheduling. Note that the latter is characterized by undesirable scheduling starvation. This type of scheduling is one of the very basic algorithms for Operating Systems in computers which can be implemented through a circular queue data structure.