Round-robin scheduling

A Round Robin preemptive scheduling example with quantum=3

Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing.[1][2] As the term is generally used, time slices (also known as time quanta)[3] 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.

Process scheduling

To schedule processes fairly, a round-robin scheduler generally employs time-sharing, giving each job a time slot or quantum[4] (its allowance of CPU time), and interrupting the job if it is not completed by then. The job is resumed next time a time slot is assigned to that process. If the process terminates or changes its state to waiting during its attributed time quantum, the scheduler selects the first process in the ready queue to execute. In the absence of time-sharing, or if the quanta were large relative to the sizes of the jobs, a process that produced large jobs would be favored over other processes.

Round-robin algorithm is a pre-emptive algorithm as the scheduler forces the process out of the CPU once the time quota expires.

For example, if the time slot is 100 milliseconds, and job1 takes a total time of 250 ms to complete, the round-robin scheduler will suspend the job after 100 ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100 ms each), job1 will get another allocation of CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.

  • Job1 = Total time to complete 250 ms (quantum 100 ms).
  1. First allocation = 100 ms.
  2. Second allocation = 100 ms.
  3. Third allocation = 100 ms but job1 self-terminates after 50 ms.
  4. Total CPU time of job1 = 250 ms

Consider the following table with the arrival time and execute time of the process with the quantum time of 100 ms to understand the round-robin scheduling:

Process name Arrival time Execute time
P0 0 250
P1 50 170
P2 130 75
P3 190 100
P4 210 130
P5 350 50
Round Robin Scheduling
Round Robin Scheduling

Another approach is to divide all processes into an equal number of timing quanta such that the quantum size is proportional to the size of the process. Hence, all processes end at the same time.

Network packet scheduling

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.

See also

References

  1. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
  2. ^ Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
  3. ^ Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. p. 409. ISBN 978-0-13-380591-8.
  4. ^ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2010). "Process Scheduling". Operating System Concepts (8th ed.). John Wiley & Sons (Asia). p. 194. ISBN 978-0-470-23399-3. 5.3.4 Round Robin Scheduling

Read other articles:

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Henry Wilson – berita · surat kabar · buku · cendekiawan · JSTOR Henry Wilson Untuk kegunaan lain, lihat Henry Wilson. Henry Wilson (16 Februari 1812 – 22 November 1875) adalah Wakil Pres...

 

 

Komisi X Dewan Perwakilan Rakyat Republik IndonesiaJenisJenisKomisi DPR RI dengan lingkup tugas di bidang Pendidikan, Olahraga, dan Sejarah PimpinanKetuaSyaiful Huda (PKB) Wakil KetuaAgustina Wilujeng Pramestuti (PDI-P) Wakil KetuaHetifah Sjaifudian (Golkar) Wakil KetuaDede Yusuf (Demokrat) Wakil KetuaAbdul Fikri Faqih (PKS) KomposisiPartai & kursi   PDI-P (12)   Golkar (8)   Gerindra (7)   NasDem (6)   PKB (6)   Demokrat (5)   PKS (5...

 

 

Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Buddhahood di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan. (Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemahan ...

1986 novel by Iain Banks The Bridge First editionAuthorIain BanksCover artistPhilip Mann ACECountryScotlandLanguageEnglishPublisherMacmillan PublishersPublication date1986Media typePrint (Hardback & Paperback)Pages256 ppISBN0-06-105358-9OCLC36103885Dewey Decimal823/.914 21LC ClassPR6052.A485 B75 1997 The Bridge is a novel by Scottish author Iain Banks. It was published in 1986. The book switches between three protagonists, John Orr, Alex, and the Barbarian. It is an unconve...

 

 

Yang MuliaAlbertus SoegijapranataS.J.Uskup Agung SemarangFoto resmi SoegijapranataKeuskupan agungSemarangPenunjukan1 Agustus 1940Masa jabatan berakhir22 Juli 1963PendahuluTidak ada, jabatan baruPenerusJustinus DarmojuwonoImamatTahbisan imam15 Agustus 1931oleh Laurentius SchrijnenTahbisan uskup6 Oktober 1940oleh Petrus Johannes WillekensInformasi pribadiNama lahirSoegijaLahir(1896-11-25)25 November 1896Surakarta, Hindia BelandaWafat22 Juli 1963(1963-07-22) (umur 66)St...

 

 

Archbishop of Canterbury from 1991 to 2002 For other people named George Carey, see George Carey (disambiguation). The Right Reverend and Right HonourableThe Lord Carey of CliftonPCArchbishop of CanterburyChurchChurch of EnglandProvinceCanterburyDioceseCanterburyIn office1991–2002PredecessorRobert RuncieSuccessorRowan WilliamsOther post(s)Honorary assistant bishop in Swansea & Brecon (2004–?), in Southwark and in Bristol; in Oxford (?–2017)Life peer (2002);Primate of All EnglandOrde...

Basilika Maria Mahakudus dari Amal KasihBasilika Minor Kolegiat Imperial Kuno dan Terkemuka Bunda Maria Mahakudus dari Amal Kasihbahasa Italia: Antichissima Regia ed Insigne Basilica Collegiata di Maria Santissima dell'ElemosinaBasilika Maria Mahakudus dari Amal Kasih37°30′15.2″N 15°5′11.5″E / 37.504222°N 15.086528°E / 37.504222; 15.086528Koordinat: 37°30′15.2″N 15°5′11.5″E / 37.504222°N 15.086528°E / 37.504222; 15.08...

 

 

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند  الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

 

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Fuentepinilla – news · newspapers · books · scholar · JSTOR (May 2024) (Learn how and when to remove this message) Municipality in Castile and León, SpainFuentepinillaMunicipalityPalace of Fuente PinillaFuentepinillaLocation in Spain.Show map of Castile and Le...

Long-duration mission to the International Space Station This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Expedition 6 – news · newspapers · books · scholar · JSTOR (September 2007) (Learn how and when to remove this message) ISS Expedition 6Promotional posterMission typeISS ExpeditionMission duration159 ...

 

 

1796 conspiracy to overthrow the Directory by Babeuf This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Conspiracy of the Equals – news · newspapers · books · scholar · JSTOR (February 2017) (Learn how and when to remove this message) Conspiracy of the EqualsA 1796 engraving, denigrating the conspiracy (1796)Na...

 

 

PT Bank DBS IndonesiaJenisJasa keuangan/publikDidirikanJakarta, Indonesia (1989)KantorpusatDBS Bank Tower, Jakarta, IndonesiaTokohkunciTeo Tzai Win Melvin (Presiden Direktur)Situs webwww.dbs.id Didirikan pada 1989, dan menjadi bagian dari kelompok usaha DBS Group di Singapura, PT Bank DBS Indonesia merupakan salah satu bank yang telah berdiri lama di Asia. Dengan 44 cabang dan 1.600 karyawan aktif di 11 kota besar di Indonesia, Bank DBS Indonesia menyediakan layanan perbankan menyeluruh untuk...

Decreasing HIV prevalence nationwide, Haiti was a first example other countries could take from to deal with the global Aids Epidemic at the time. [1] [2] With an estimated 150,000 people living with HIV/AIDS in 2016 (or an approximately 2.1 percent prevalence rate among adults aged 15–49), Haiti has the most overall cases of HIV/AIDS in the Caribbean and its HIV prevalence rates among the highest percentage-wise in the region.[3] There are many risk-factor groups f...

 

 

Cet article est une ébauche concernant le Kazakhstan. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. District d'Auliekol Sceau Noms Nom kazakh Әулиекөл ауданы Nom russe Administration Pays Kazakhstan Oblys Kostanaï Centre administratif Auliekol Démographie Population 46 071 hab. (2013[1]) Géographie Coordonnées 52° 21′ 00″ nord, 64° 07′ 48″ es...

 

 

Part of a series onEthnicity in Houston African Americans Czechs Hispanics and Latinos Mexicans Central Americans Asians Chinese Japanese Koreans Pakistanis Vietnamese Germans Jews Poles Roma vte The current Congregation Beth Israel The Jewish community of Houston, Texas has grown and thrived since the 1800s. As of 2008, Jews lived in many Houston neighborhoods and Meyerland is the center of the Jewish community in the area. History Previous Temple Beth Israel, now Heinen Theatre of the Hous...

1803 and 1804 treaties between the U.S. and Native Americans This article is about the 19th century US treaties. For the 14th century Franco-Scots treaty, see Treaty of Vincennes-Edinburgh. Treaty of VincennesTypeRecognition of American land claimsSignedJune 6th 1803LocationVincennes, Indiana TerritoryConditionTransfer of money and goods to nativesSignatories William Henry Harrison Little Turtle Chekommia Black Hoof Parties United States of America Miami Wea (Piankeshaw, Kickapoo) Shawnee Lan...

 

 

Niniek L. KarimNiniek di Festival Film Indonesia 2015LahirSri Rochani Soesetio Karim[1]14 Januari 1949 (umur 75)Mataram, Nusa Tenggara Barat, IndonesiaNama lainNiniek L. KarimAlmamaterFakultas Psikologi Universitas IndonesiaPekerjaanAktrisdosenTahun aktif1986—sekarang Dra. Sri Rochani Soesetio Karim (lahir 14 Januari 1949), yang lebih dikenal dengan Niniek L. Karim, adalah seorang pemeran dan dosen Indonesia. Selain berkarier di dunia seni peran, Niniek juga mengajar...

 

 

В Википедии есть статьи о других людях с такой фамилией, см. Карадемир. Тугба Карадемиртур. Tuğba Karademir Персональные данные Гражданство Турция Дата рождения 17 марта 1985(1985-03-17) (39 лет) Место рождения Анкара Рост 165 см Бывшиетренеры Роберт Тебби Место проживания Берри (Онтарио, �...

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أغسطس 2015) منطقة دون موينغ (بالتايلندية: เขตดอนเมือง)‏     خريطة الموقع الشع�...

 

 

American romantic comedy streaming series FoursomeGenreTeen dramaComedyCreated by Marissa Read Selyna Warre Directed byAmy York RubinStarring Jenn McAllister Meghan Falcone Brooke Markham Rickey Thompson Logan Paul Cameron Moulène Rahart Adams Madeline Whitby Sarah Yarkin Monica Sherer John Milhiser Jared Wernick Tucker Albrizzi Country of originUnited StatesOriginal languageEnglishNo. of seasons4No. of episodes36 (list of episodes)ProductionExecutive producers Marissa Read Selyna Warren Sha...