Round Robin
Round Robin je algoritam za raspoređivanje procesa u operativnim sistemima. Svakom procesu se dodeljuje vremenski kvant (time slice) tokom kojeg može da koristi procesor. Kada procesu istekne svoj vremenski kvant, on se vraća na kraj reda čekanja, a procesuru se dodeljuje sledećem procesu u redu. Ovaj proces se ponavlja dok svi procesi ne budu završeni.
Za dati vremenski kvant i listu procesa sa njihovim vremenima izvršavanja, implementirati funkciju koja primenjuje Round Robin algoritam i izračunava koliko je sliceova potrebno da se svi procesi završe.
int round_robin(cvor *sentinel, int time_slice)Ulaz
Sa standardnog ulaza se učitava lista procesa oblika:
[p1, p2, p3, ..., pn]
gde je
Izlaz
Na standardni izlaz se ispisuje broj sliceova potrebnih da se svi procesi završe.
Primer
Ulaz
[10, 20, 30]
5
Izlaz
12
Primer
Ulaz
[4, 2, 8]
3
Izlaz
6
Primer
Ulaz
[]
5
Izlaz
0
Primer
Ulaz
[5, 4, 3, 2, 1]
1
Izlaz
15
Rešenje
liste.h
#ifndef LISTE_H
#define LISTE_H
#include <stddef.h> /* za size_t */
/* Čvor jednostruko povezane liste. */
typedef struct cvor {
int podatak;
struct cvor *sledeci;
} cvor;
/* Statusni kodovi za operacije nad listom. */
typedef enum {
OK,
NEDOVOLJNO_MEMORIJE,
NEMA_ELEMENATA
} status;
/*
* Kreiranje i uništavanje liste
*/
/* Kreira praznu listu sa sentinel-čvorom. Vraća pokazivač na sentinel ili NULL. */
cvor *inicijalizuj_listu(void);
/* Oslobađa sve "prave" elemente liste; sentinel ostaje. */
void obrisi_listu(cvor *sentinel);
/* Kao gore, ali održava i pokazivač na kraj liste. */
void obrisi_listu_sa_krajem(cvor *sentinel, cvor **pokazivac_na_kraj);
/* Oslobađa sve elemente i sentinel; poništava pokazivač na listu. */
void unisti_listu(cvor **psentinel);
/*
* Osnovne operacije ubacivanja
*/
/* Dodaje novi element na početak liste (iza sentinela). */
status dodaj_na_pocetak(cvor *sentinel, int podatak);
/* Dodaje novi element na kraj liste, složenosti O(n). */
status dodaj_na_kraj(cvor *sentinel, int podatak);
/* Dodaje novi element na kraj liste, uz održavanje pokazivača na kraj (O(1)). */
status dodaj_na_kraj_sa_krajem(cvor *sentinel,
cvor **pokazivac_na_kraj,
int podatak);
/* Umeće već alocirani čvor odmah iza zadatog elementa (bez provera). */
void ubaci_iza_elementa(cvor *element, cvor *novi);
/* Umeće već alocirani čvor "ispred" zadatog tako što se podaci zamene. */
void ubaci_ispred_elementa(cvor *element, cvor *novi);
/*
* Brisanje
*/
/* Briše prvi pravi element liste (iza sentinela) i vraća njegovu vrednost. */
status obrisi_sa_pocetka(cvor *sentinel, int *podatak);
/* Kao gore, ali održava i pokazivač na kraj liste. */
status obrisi_sa_pocetka_sa_krajem(cvor *sentinel,
cvor **pokazivac_na_kraj,
int *podatak);
/* Briše prvi element sa datom vrednošću; ako ne postoji, vraća NEMA_ELEMENATA. */
status obrisi_prvi_sa_vrednoscu(cvor *sentinel, int vrednost);
/*
* Pretraga
*/
/* Vraća pokazivač na prvi čvor sa datom vrednošću ili NULL ako takav ne postoji. */
cvor *nadji_prvi(cvor *sentinel, int vrednost);
/* Vraća prethodni čvor u odnosu na prvi čvor sa datom vrednošću, ili NULL. */
cvor *nadji_prethodni(cvor *sentinel, int vrednost);
/*
* Sortirano ubacivanje i učešljavanje (merge)
*/
/* Umeće novi element tako da lista ostane sortirana (neopadajuće). */
status ubaci_sortirano(cvor *sentinel, int podatak);
/* Objedinjava dve sortirane liste s1 i s2 u s1; s2 postaje prazna. */
void objedini(cvor *s1, cvor *s2);
/*
* Učitavanje
*/
/* Učita listu u formatu [1, 2, 3] sa stdin u zadatu povezanu listu. */
status ucitaj_listu(cvor *sentinel);
/*
* Ispis
*/
/* Ispisuje sve elemente liste (bez sentinela) u jednom redu. */
void ispisi_elemente_liste(cvor *sentinel);
#endif /* LISTE_H */main.c
#include <stdio.h>
#include <stdlib.h>
#include "liste.h"
int round_robin_simulacija(cvor *sentinel, int time_slice)
{
if (sentinel->sledeci == NULL) {
return 0; // prazna lista
}
/* Napravi kružnu listu */
cvor *tekuci = sentinel->sledeci;
while (tekuci->sledeci != NULL) {
tekuci = tekuci->sledeci;
}
tekuci->sledeci = sentinel->sledeci;
/* Simulacija round robin algoritma */
int count = 0;
cvor *prethodni = tekuci;
tekuci = tekuci->sledeci;
while (1) {
tekuci->podatak -= time_slice;
count++;
if (tekuci->podatak <= 0) {
if (tekuci == tekuci->sledeci) {
// Poslednji cvor
free(tekuci);
break;
}
prethodni->sledeci = tekuci->sledeci;
free(tekuci);
tekuci = prethodni->sledeci;
} else {
prethodni = tekuci;
tekuci = tekuci->sledeci;
}
}
return count;
}
int main(void)
{
cvor *lista = inicijalizuj_listu();
if (lista == NULL) {
fprintf(stderr, "Greska pri inicijalizaciji liste.\n");
return 1;
}
if (ucitaj_listu(lista) != OK) {
fprintf(stderr, "Greska pri ucitavanju liste.\n");
obrisi_listu(lista);
return 1;
}
int time_slice;
scanf("%d", &time_slice);
printf("%d\n", round_robin_simulacija(lista, time_slice));
free(lista);
return 0;
}liste.c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "liste.h"
/* Pročita jedan ceo broj iz niske, koristeći strtol. */
static int procitaj_int(const char **s, int *vrednost)
{
char *kraj;
long val = strtol(*s, &kraj, 10);
if (kraj == *s) {
return 0; /* nije bilo broja */
}
*vrednost = (int)val;
*s = kraj;
return 1;
}
/* Pomoćna funkcija: kreira novi čvor sa datom vrednošću. */
static cvor *novi_cvor(int podatak)
{
cvor *novi = malloc(sizeof(cvor));
if (novi == NULL)
return NULL;
novi->podatak = podatak;
novi->sledeci = NULL;
return novi;
}
/* Kreira praznu listu sa sentinel-čvorom. */
cvor *inicijalizuj_listu(void)
{
cvor *s = malloc(sizeof(cvor));
if (s == NULL)
return NULL;
s->podatak = 0; /* vrednost se ne koristi */
s->sledeci = NULL; /* prazna lista */
return s;
}
/* Oslobađa sve prave elemente liste; sentinel ostaje. */
void obrisi_listu(cvor *sentinel)
{
cvor *tekuci = sentinel->sledeci;
while (tekuci != NULL) {
cvor *p = tekuci;
tekuci = tekuci->sledeci;
free(p);
}
sentinel->sledeci = NULL;
}
/* Oslobađa sve prave elemente i resetuje pokazivač na kraj. */
void obrisi_listu_sa_krajem(cvor *sentinel, cvor **pokazivac_na_kraj)
{
cvor *tekuci = sentinel->sledeci;
while (tekuci != NULL) {
cvor *p = tekuci;
tekuci = tekuci->sledeci;
free(p);
}
sentinel->sledeci = NULL;
*pokazivac_na_kraj = sentinel;
}
/* Uništava čitavu listu, uključujući sentinel-čvor. */
void unisti_listu(cvor **psentinel)
{
if (*psentinel == NULL)
return;
obrisi_listu(*psentinel);
free(*psentinel);
*psentinel = NULL;
}
/* Dodaje novi element na početak liste (iza sentinela). */
status dodaj_na_pocetak(cvor *sentinel, int podatak)
{
cvor *novi = novi_cvor(podatak);
if (novi == NULL)
return NEDOVOLJNO_MEMORIJE;
novi->sledeci = sentinel->sledeci;
sentinel->sledeci = novi;
return OK;
}
/* Dodaje novi element na kraj liste, složenosti O(n). */
status dodaj_na_kraj(cvor *sentinel, int podatak)
{
cvor *novi = novi_cvor(podatak);
if (novi == NULL)
return NEDOVOLJNO_MEMORIJE;
novi->sledeci = NULL;
cvor *p = sentinel;
while (p->sledeci != NULL)
p = p->sledeci;
p->sledeci = novi;
return OK;
}
/* Dodaje novi element na kraj liste, uz održavanje pokazivača na kraj. */
status dodaj_na_kraj_sa_krajem(cvor *sentinel,
cvor **pokazivac_na_kraj,
int podatak)
{
(void)sentinel; /* sentinel je implicitno jednak *pokazivac_na_kraj na početku */
cvor *novi = novi_cvor(podatak);
if (novi == NULL)
return NEDOVOLJNO_MEMORIJE;
novi->sledeci = NULL;
(*pokazivac_na_kraj)->sledeci = novi;
*pokazivac_na_kraj = novi;
return OK;
}
/* Umeće već alocirani čvor odmah iza zadatog elementa. */
void ubaci_iza_elementa(cvor *element, cvor *novi)
{
if (element == NULL || novi == NULL)
return;
novi->sledeci = element->sledeci;
element->sledeci = novi;
}
/* Umeće novi čvor "ispred" datog elementa zamjenom podataka. */
void ubaci_ispred_elementa(cvor *element, cvor *novi)
{
if (element == NULL || novi == NULL)
return;
/* Umećemo novi iza elementa, pa menjamo podatke. */
novi->sledeci = element->sledeci;
element->sledeci = novi;
int tmp = element->podatak;
element->podatak = novi->podatak;
novi->podatak = tmp;
}
/* Briše prvi pravi element liste i vraća njegovu vrednost. */
status obrisi_sa_pocetka(cvor *sentinel, int *podatak)
{
if (sentinel->sledeci == NULL)
return NEMA_ELEMENATA;
cvor *p = sentinel->sledeci;
*podatak = p->podatak;
sentinel->sledeci = p->sledeci;
free(p);
return OK;
}
/* Briše prvi element i održava pokazivač na kraj. */
status obrisi_sa_pocetka_sa_krajem(cvor *sentinel,
cvor **pokazivac_na_kraj,
int *podatak)
{
if (sentinel->sledeci == NULL)
return NEMA_ELEMENATA;
cvor *p = sentinel->sledeci;
*podatak = p->podatak;
sentinel->sledeci = p->sledeci;
free(p);
if (sentinel->sledeci == NULL)
*pokazivac_na_kraj = sentinel;
return OK;
}
/* Pronalaženje prvog elementa sa datom vrednošću. */
cvor *nadji_prvi(cvor *sentinel, int vrednost)
{
for (cvor *p = sentinel->sledeci; p != NULL; p = p->sledeci)
if (p->podatak == vrednost)
return p;
return NULL;
}
/* Pronalaženje prethodnog elementa u odnosu na prvi sa datom vrednošću. */
cvor *nadji_prethodni(cvor *sentinel, int vrednost)
{
cvor *prev = sentinel;
cvor *curr = sentinel->sledeci;
while (curr != NULL) {
if (curr->podatak == vrednost)
return prev;
prev = curr;
curr = curr->sledeci;
}
return NULL;
}
/* Briše prvi element sa zadatom vrednošću. */
status obrisi_prvi_sa_vrednoscu(cvor *sentinel, int vrednost)
{
cvor *prev = nadji_prethodni(sentinel, vrednost);
if (prev == NULL)
return NEMA_ELEMENATA;
cvor *za_brisanje = prev->sledeci;
prev->sledeci = za_brisanje->sledeci;
free(za_brisanje);
return OK;
}
/* Umeće element u sortiranu listu (neopadajući poredak). */
status ubaci_sortirano(cvor *sentinel, int podatak)
{
cvor *novi = novi_cvor(podatak);
if (novi == NULL)
return NEDOVOLJNO_MEMORIJE;
cvor *prev = sentinel;
cvor *curr = sentinel->sledeci;
while (curr != NULL && curr->podatak < podatak) {
prev = curr;
curr = curr->sledeci;
}
novi->sledeci = curr;
prev->sledeci = novi;
return OK;
}
/* Učešljava dve sortirane liste u prvu (s1); s2 postaje prazna. */
void objedini(cvor *s1, cvor *s2)
{
cvor *p = s1;
cvor *a = s1->sledeci;
cvor *b = s2->sledeci;
while (a != NULL && b != NULL) {
if (a->podatak <= b->podatak) {
p->sledeci = a;
a = a->sledeci;
} else {
p->sledeci = b;
b = b->sledeci;
}
p = p->sledeci;
}
p->sledeci = (a != NULL) ? a : b;
s2->sledeci = NULL; /* druga lista je sada prazna */
}
/* Učita listu u formatu [1, 2, 3] sa stdin u zadatu povezanu listu. */
status ucitaj_listu(cvor *sentinel)
{
char linija[1024];
if (fgets(linija, sizeof(linija), stdin) == NULL)
return NEMA_ELEMENATA; /* ili tretirati kao OK-prazno */
const char *p = linija;
/* lokalni pokazivač na kraj liste – na početku je to sentinel */
cvor *kraj = sentinel;
/* Preskoči beline i očekuj '[' */
while (isspace((unsigned char)*p)) p++;
if (*p != '[') {
return NEMA_ELEMENATA;
}
p++; /* preko '[' */
/* Prazna lista '[]'? */
while (isspace((unsigned char)*p)) p++;
if (*p == ']') {
return OK;
}
/* Inače čitamo brojeve odvojene zarezima. */
for (;;) {
int x;
while (isspace((unsigned char)*p)) p++;
if (!procitaj_int(&p, &x)) {
return NEMA_ELEMENATA;
}
if (dodaj_na_kraj_sa_krajem(sentinel, &kraj, x) != OK) {
return NEDOVOLJNO_MEMORIJE;
}
while (isspace((unsigned char)*p)) p++;
if (*p == ',') {
p++; /* preko zareza, ide sledeći broj */
continue;
} else if (*p == ']') {
break; /* kraj liste */
} else {
return NEMA_ELEMENATA;
}
}
return OK;
}
/* Ispis svih elemenata liste (bez sentinela). */
void ispisi_elemente_liste(cvor *sentinel)
{
printf("[");
for (cvor *p = sentinel->sledeci; p != NULL; p = p->sledeci) {
printf("%d", p->podatak);
if (p->sledeci != NULL)
printf(", ");
}
printf("]\n");
}