Sistemas  Operativos  

M.Sc. Luis Eduardo Sepúlveda Rodríguez

¡  Recordemos,  un  planificador  de  procesos  es  parte  de  un  SO  que  se  encarga  de  la  toma  de  decisiones  de  selección  sobre  los  procesos.  Existen  tres  tipos  de  planificadores  básicos:  

¡  Planificador  de  largo  plazo:  Llamado  “planificador  de  trabajos”.    

¡  Planificador  de  corto  plazo:  Llamado  “planificador  de  procesos”  .  

¡  Planificador  de  mediano  plazo:  Llamado  “planificador  de  swapping”.  

2  

¡  Utilización  de  CPU:  Tiempo  que  mantiene  la  CPU  ocupada.  Cuanto  más  grande  sea  este  tiempo  de  ocupación,  es  mejor.  

   ¡  Rendimiento  (Throughput):  Cantidad  de  procesos  que  

terminan  su  ejecución  por  unidad  de  tiempo.  Cuanto  más  grande  sea,  es  mejor.  

   ¡  Tiempo  de  ejecución  (Tejecución):  Es  la  cantidad  de  tiempo  que  

necesita  un  proceso  cualquiera  para  ejecutarse.      ¡  Tiempo  de  llegada  (Tllegada):  Momento  en  el  cual  un  proceso  es  

cargado  por  el  sistema  operativo  (lista  de  procesos  listos).  

3    

¡  Tiempo  de  salida  (Tsalida):  Momento  en  el  cual  un  proceso  termina  toda  su  ejecución  y  es  retirado  del  sistema.  

   ¡  Tiempo  de  servicio  (Tservicio):  Tiempo  que  tarda  un  proceso  en  

ejecutarse  y  salir  del  sistema  (                                                                                                      ).  Cuanto  más  pequeño  sea,  es  mejor.  

   ¡  Tiempo  de  espera  (Tespera):  Este  valor  expresa  todo  el  tiempo  que  el  

proceso  estuvo  inactivo  (                                                                                      ).  Cuanto  más  pequeño  sea,  es  mejor.  

   ¡  Índice  de  Servicio:  Valor  que  representa  el  porcentaje  de  tiempo  que  el  

proceso  se  está  ejecutando,  con  respecto  al  tiempo  que  permanece  en  el  sistema  (                                      ).  Este  valor  indica  si  el  proceso  fue  limitado  por  el  procesador  (valor  cercano  a  1)  o  por  los  dispositivos  de  entrada/salida  del  sistema  (valor  cercano  a  0).  

4    

TServicio = TiempoSalida −TiempoLlegada

TEspera = TiempoServicio −TiempoEjecución

IServicio =TEjecuciónTServicio

¡  Tiempo  de  servicio:    

¡  Tiempo  de  espera:          ¡  Índice  de  Servicio:  

5    

TServicio = TiempoSalida −TiempoLlegada

TEspera = TiempoServicio −TiempoEjecución

IServicio =TEjecuciónTServicio

 Los  valores  que  realmente  importan  son  los  promedios  de  estos  criterios  después  de  un  periodo  de  tiempo  y  de  haber  ejecutado  varios  procesos.  

6    

 Sólo  los  algoritmos  no  expulsivos  se  pueden  utilizar  en  los  planificadores  de  largo  y  mediano  plazo.  

       ¡  FCFS  (First    Come,  First    Served):        

§  Selecciona  un  proceso  según  el  orden  de  llegada,  esto  es,  el  proceso  que  primero  solicita  la  CPU  la  recibe  primero.  

   §  Utiliza  una  Política  no  expulsiva.  

   §  Fácil  implementación  pero  de  bajo  desempeño.  

   §  No  es  adecuado  para  sistemas  de  tiempo  compartido  (no  se  puede  permitir  

que  un  proceso  ocupe  la  CPU  durante  un  periodo  prolongado).  

§  Puede  hacer  esperar  a  los  procesos  cortos  hasta  que  terminen  los  más  largos.  

7  

¡  SJF  (Shortest  Job  First):        

§  Selecciona  el  proceso  cuyo  tiempo  de  ejecución  siguiente  (ráfaga  de  ejecución,  no  confundir  con  el  tiempo  de  ejecución  total)  sea  la  más  corta  (“primero  el  trabajo  más  corto”).  En  caso  de  encontrar  ambigüedad  en  la  selección,  entonces  se  procede  según  el  algoritmo  FCFS.    

   §  Utiliza  una  política  no  expulsiva.    

   §  Implementación  complicada,  ya  que  no  es  fácil  determinar  el  tamaño  de  los  

procesos  con  anterioridad.    

§  Este  algoritmo  no  es  muy  justo  con  los  procesos  cuya  duración  sea  grande  con  respecto  a  los  demás.  Causa  lo  que  se  conoce  como  el  bloque  indefinido  ó  inanición  (“starvation”),  esto  es  la  postergación  indefinida  de  los  procesos  cuyo  tiempo  de  ejecución,  siempre  es  muy  superior.  

8    

¡  SRTF  (Shortest  Remaining  Time  First):        

§  Selecciona  el  proceso  cuyo  tiempo  restante  de  ejecución  sea  menor,    es  realmente  la  versión  expulsiva  del  algoritmo  SJF.  

   §  Utiliza  una  política  expulsiva.    

§  Selecciona  el  proceso  cuyo  tiempo  restante  de  ejecución  (ráfaga)  sea  menor.  

9    

¡  Prioridad:        

§  A  cada  proceso  se  le  asigna  un  valor  entero  llamado  prioridad.  Se  debe  definir  de  antemano  la  valoración  de  la  prioridad.    

   §  Utiliza  política  expulsiva  y  no  expulsiva.    

   §  Si  se  está  trabajando  con  la  versión  expulsiva,  se  debe  verificar  que  la  prioridad  

de  todo  proceso  entrante  en  el  sistema,  para  saber  si  se  tiene  o  no  que  interrumpir  al  proceso  que  actualmente  se  ejecuta.  Puede  darse  de  dos  formas.  

▪  Prioridad  interna:  Definida  por  el  sistema  operativo.    ▪  Prioridad  externa:  Definida  por  criterios  ajenos  al  sistema.  

   §  Puede  presentar  el  problema  de  inanición,  pero  se  soluciona  aumentando  la  

prioridad  del  proceso  cada  vez  que  cumpla  un  determinado  tiempo  en  el  sistema  (técnica  de  envejecimiento).    

§  Si  dos  o  más  procesos  poseen  la  misma  prioridad,  entonces  se  hace  la  selección  usando  el  algoritmo  FCFS.   10  

¡  HRN  (High  Response  Next):        

§  Es  un  ejemplo  de  algoritmo  con  prioridad  interna  

§  Asigna  a  cada  proceso  una  prioridad,  seleccionando  aquel  que  tenga  el  valor  más  alto,  según  la  fórmula:    

▪  P:  Prioridad.  ▪  Te:  Tiempo  de  espera.  ▪  Tej:  Tiempo  de  ejecución.  

   §  Utiliza  la  política  expulsiva.    

 

§  Este  algoritmo  es  muy  justo  con  los  proceso,  aunque  produce  sobrecarga  en  el  sistema,  ya  que  hay  que  realizar  cálculos  por  cada  proceso.  

11  

Pr ioridad = (TEspera+TEjecución )TEjecución

¡  RR  (Round  Robin):      

§  Llamado   algoritmo   circular.   Va   colocando   los   procesos   en   una   lista   según   unas   reglas.   Se  seleccionará   el   proceso   que   esté   al   inicio   de   la   lista.   Una   vez   seleccionado   se   le   asigna   el  procesador  por  un  tiempo  determinado.  A  este  tiempo  se  le  conoce  por  el  nombre  de  Cuanto  o  Quantum.  

§  Utiliza  política  expulsiva.    §  Diseñado  especialmente  para  los  sistemas  de  tiempo  compartido.  §  Similar  al  FCFS  pero  con  expulsión  para  conmutar  entre  procesos.  §  El  Quantum  tiene  una  duración  entre  10  y  100  milisegundos.  §  El  cambio  de  contexto  debe  ser  menos  que  el  tiempo  del  Quantum.  §  El  tiempo  de  espera  promedio  suele  ser  muy  grande    

§  Reglas  del  RR:  ▪  Al  crear  un  proceso,  se  inserta  al  final  de  la  lista.  

▪  Cuando   un   proceso   termina   su   ejecución   totalmente,   es   retirado   de   la   lista   del   RR   y   se   procede   a  seleccionar  el  proceso  siguiente  en  la  lista.  

▪  Cuando  un  proceso  termina  su  Quantum,  se  pasa  al  final  de  la  lista  y  se  selecciona  el  siguiente.  ▪  Si  al  mismo  tiempo  un  proceso  llega  y  otro  termina  su  Quantum,  se  pondrá  al  final  de  la   lista  el  proceso  

entrante  y  posteriormente  el  que  terminó  su  Quantum.   12  

¡  FMQ  (Feedback  Multiple  Queues):        

§  Mantiene  a  los  procesos  en  varias  listas  interconectadas,  de  las  cuales  n–1  listas  operan  con  el  algoritmo  RR  regularmente,  y  las  n-­‐esima  lista  opera  con  el  algoritmo  FCFS.  

   §  Utiliza  política  expulsiva.    

   §  Cuando  un  proceso  ha  sido  atendido  un  número  k  de  veces,  este  proceso  se  mueve  

a  la  lista  siguiente  según  las  reglas  de  cada  algoritmo.      

§  Siempre  se  seleccionará  el  primer  proceso  que  esté  en  la  lista  de  nivel  más  bajo.  Esto  quiere  decir  que  sólo  se  atenderán  los  procesos  de  la  lista  FCFS,  cuando  no  existía  ningún  proceso  en  todas  las  listas  RR.  

   §  Cuando  un  proceso  termina,  simplemente  se  retira  de  la  lista  en  que  se  encuentra.  

   §  Los  procesos  se  crean  siempre  en  la  primera  lista.  

§  Este  algoritmo  soporta  muy  bien  la  sobrecarga  de  procesos,  esto  es  cuando  existen  demasiados  procesos  compitiendo  por  el  procesador  en  el  SO.   13  

RR  (Quantum  =  8)  

RR  (Quantum  =  16)  

FCFS  

FMQ  (Feedback  Multiple  Queues):