domingo, 30 de marzo de 2014

Examen parcial de Programación de Sistemas y Concurrencia. Curso 2012/2013.

Os dejo mi solución al ejercicio de C del primer parcial de la asignatura de segundo de Informática Programación de Sistemas y Concurrencia del curso pasado, 2012/2013. Repito que es mi solución y puede no ser correcta, así que se aceptan sugerencias de mejora como siempre ;). Os dejo un enlace para que podáis descargarlo pero, como siempre, os dejo mi código aquí también.
Primero el enunciado del ejercicio, aunque subo el pdf para descargar.



Se desea simular el almacenamiento en memoria de un planificador de tareas basado en prioridades. El planificador gestiona la lista de tareas del sistema que están en estado ejecutable, es decir, que pueden ejecutarse en cuanto les llegue el turno. Cada tarea se representa con un identificador (char *id) que es una cadena de caracteres, y un número (int pri) que representa la prioridad de la tarea. El planificador ordena las tareas en función de su prioridad teniendo en cuenta que cuanto más grande sea pri la tarea tiene más prioridad. Además, en el caso de haya tareas de igual prioridad, la ordenación depende del momento en que llegan a la estructura. Como se puede ver en la figura, la tarea t2 está después de la tarea t1 y esto se deberá a que t2 habrá pasado al estado de “lista para ejecutar” después que t1:



Implementar las siguientes operaciones:

void crear(T_Planificador *planif);
Inicializa el planificador creando un planificador vacío.

void insertar_tarea(T_Planificador *planif,int pri,char *id);
Inserta una nueva tarea id de prioridad pri en el planificador planif. La lista está ordenada por prioridad y en el caso de que exista una tarea con la misma prioridad se almacenará por orden de llegada. El identificador de tarea es único.

void mostrar (T_Planificador planificador);
Muestra el estado del planificador.

void eliminar_tarea(T_Planificador *planif,char *id,unsigned *ok);
Dado un planificador, elimina una tarea id que está preparada para ejecución. En el caso de que no exista dicha tarea, se devolverá 0 en el parámetro ok. OK valdrá 1 en el caso de que se haya realizado el borrado.

void planificar(T_Planificador *planif);
Extrae de la estructura la tarea que le corresponde ejecutarse.

void destruir(T_Planificador *planif);
Destruye toda la estructura eliminando y liberando la memoria de todos los nodos.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TNodo * T_Planificador;
struct TNodo {
 char *id;
 int pri;
 T_Planificador sig;
};

void crear(T_Planificador *planif){
 // Inicializa el planificador creando un planificador vacío.
 *planif = NULL;
}

void insertar_tarea(T_Planificador *planif,int pri,char *id){
 /*
  * Inserta una nueva tarea id de prioridad pri en el planificador planif. La lista está ordenada por
prioridad y en el caso de que exista una tarea con la misma prioridad se almacenará por orden de
llegada. El identificador de tarea es único.
  */
 T_Planificador ptr = *planif;
 T_Planificador ant = NULL;
 int insertado = 0;
 T_Planificador nuevo = malloc(sizeof(struct TNodo));
 nuevo ->id = id;
 nuevo->pri = pri;
 if(*planif == NULL){ // está vacío
  *planif = nuevo;
  nuevo->sig = NULL;
 }else{
 while(ptr != NULL && !insertado){
  if(ptr->pri > nuevo->pri){ //sigue por la lista, pues tiene menos prioridad
   ant = ptr;
   ptr = ptr -> sig;
  }else if (ptr->pri < nuevo->pri){
   if(ant != NULL){
    ant ->sig = nuevo;
    nuevo -> sig = ptr;
   }else{
    nuevo -> sig = ptr;
    *planif = nuevo;
   }
   insertado = 1;
  }else{
   nuevo -> sig = ptr -> sig;
   ptr -> sig = nuevo;
   insertado = 1;
  }
 }
 if(!insertado){ //por si es el último
   nuevo -> sig = NULL;
   ant -> sig = nuevo;
 }
 }

}

void mostrar (T_Planificador planificador){
 //Muestra el estado del planificador.
 printf("\nTareas del planificador por orden de ejecución (primera la que antes se ejecutará): \n");
 printf("Planificador ");
 while(planificador != NULL){
  printf("->  %d | %s  ",planificador->pri,  planificador -> id );
  planificador = planificador ->sig;
 }
}

void eliminar_tarea(T_Planificador *planif,char *id,unsigned *ok){
 /*
  * Dado un planificador, elimina una tarea id que está preparada para ejecución. En el caso de que
  no exista dicha tarea, se devolverá 0 en el parámetro ok. OK valdrá 1 en el caso de que se haya
 realizado el borrado.
  */
 T_Planificador ptr = *planif;
 T_Planificador ant = NULL;
 *ok = 0;
 while(!(*ok) && ptr != NULL){
  //int strcmp(const char *s1, const char *s2);
  if((strcmp(ptr ->id, id)) != 0   ){//sigo
   ant = ptr;
   ptr = ptr -> sig;
  }else{ //la hemos encontrado.
   if(ant != NULL){
    ant -> sig = ptr -> sig;

   }else{// es la primera
    *planif = ptr-> sig;
   }
   free(ptr);
   *ok = 1;

  }
 }


}
void planificar(T_Planificador *planif){
 //Extrae de la estructura la tarea que le corresponde ejecutarse.
 *planif = (*planif) -> sig;

}

void destruir(T_Planificador *planif){
 //Destruye toda la estructura eliminando y liberando la memoria de todos los nodos.

 T_Planificador ptr = *planif;
 while(ptr != NULL){
  *planif = ptr -> sig;
  free(ptr);
  ptr = *planif;
 }


}



int main(void) {
 //Podemos probar con los diferentes procedimientos para ver si funciona correctamente :)
 T_Planificador planificador;
 crear(&planificador);
 insertar_tarea(&planificador, 4, "t8");
 insertar_tarea(&planificador, 8, "t1");
 insertar_tarea(&planificador, 3, "t7");
 insertar_tarea(&planificador, 8, "t2");
 insertar_tarea(&planificador, 1, "t3");
 mostrar(planificador);
 planificar(&planificador);
 mostrar(planificador);
 planificar(&planificador);
 mostrar(planificador);
 destruir(&planificador);

 return EXIT_SUCCESS;
}

No hay comentarios:

Publicar un comentario