Alarm Clock

Vista previa

En esta primera tarea, usted debe prestar atención a los siguientes archivos:

  • pintos/src/devices/

    • timer.h

    • timer.c

  • pintos/src/threads/

    • thread.h

    • thread.c

Ahora que ya sabemos en que directorio se encuentra cada archivo, por comodidad, nos limitaremos a llamar cada archivo solo por su nombre, usted ya sabe en que directorio se encuentra cada uno de estos.

La funcionalidad de timing, puede encontrarse en timer.h y timer.c. Veamos algunas funciones importantes que se encuentran en estos archivos:

  • int64_t timer_interrupt (struct intr_frame*args UNUSED); Es el reloj de Pintos. Cuando esta función sea llamada, la variable global ticks se incrementará en uno.

  • int64_t timer_elapsed (int64_t); Devuelve el numero de ticks que han transcurrido desde que Pintos inició su ejecución.

  • void timer_sleep(int64_t ticks); Suspende la ejecución del thread actual hasta que hayan transcurrido al menos el número de ticks recibidos como argumento.

La primera tarea es reimplementar timer_sleep. Veamos la implementación que se tiene inicialmente de timer_sleep:

thread.c
void
timer_sleep (int64_t ticks) 
{
  int64_t start = timer_ticks ();

  ASSERT (intr_get_level () == INTR_ON);
  while (timer_elapsed (start) < ticks) 
    thread_yield ();
}

Esto es conocido como "busy waiting". Lo que sucede en esta versión es que, existe un loop que revisa de forma iterativa el tiempo transcurrido y llama a thread_yield() hasta que hayan transcurrido el número de ticks recibidos como argumento.

De forma más detallada, esta implementación inicial, revisa si un thread debe estar durmiendo, si sí se supone que lo está, este cede su lugar a otro thread (yield) y se calendariza un nuevo thread al procesador. Pero thread_yield coloca al thread actual en ejecución, en un ready state de forma que no se garantiza que threads que estén dormidos sean calendarizados de nuevo al procesador antes que sea su hora de despertar, por lo que se desperdicia tiempo del procesador en tenerlo switcheando threads dormidos fuera y dentro de él.

Manos a la obra... en una sola maniobra

Siga los siguientes consejos, y logrará implementar la funcionalidad de Alarm Clock correctamente, logrando así sus primeros 24 puntos aproximadamente en esta primera fase.

La idea general que seguiremos para deshacernos del "busy waiting" es bloquear a los threads, de forma que ya no se encuentren en un ready state y cuando sea su hora de despertar los desbloqueamos.

Para ello, haga lo siguiente:

  • Defina en thread.h un nuevo atributo en la estructura thread, que sea un entero que represente el tiempo que un thread debe permanecer dormido.

thread.h
struct thread
  {
    /* Owned by thread.c. */
    tid_t tid;                          /* Thread identifier. */
    enum thread_status status;          /* Thread state. */
    char name[16];                      /* Name (for debugging purposes). */
    uint8_t *stack;                     /* Saved stack pointer. */
    int priority;                       /* Priority. */
    struct list_elem allelem;           /* List element for all threads list. */

    /* Shared between thread.c and synch.c. */
    struct list_elem elem;              /* List element. */
    //--------------------------------------
    //PUEDE DECLARARLO AQUI COMO UN uint64_t
    //--------------------------------------

#ifdef USERPROG
    /* Owned by userprog/process.c. */

  • Defina en thread.c una estructura que sea una lista de los threads que están en espera de que se cumpla su tiempo de estar durmiendo.

thread.c
/* Random value for struct thread's `magic' member.
   Used to detect stack overflow.  See the big comment at the top
   of thread.h for details. */
#define THREAD_MAGIC 0xcd6abf4b

//---------------------------------------------------------
// PUEDE DEFINIRLA AQUI IGUAL QUE COMO SE DEFINE ready_list
//---------------------------------------------------------

/* List of processes in THREAD_READY state, that is, processes
   that are ready to run but not actually running. */
static struct list ready_list;

/* List of all processes.  Processes are added to this list
   when they are first scheduled and removed when they exit. */

  • Inicialice la lista anterior en thread_init, supongamos que en el paso anterior le llamó a esta "lista_espera" .

thread.c
void
thread_init (void) 
{
  ASSERT (intr_get_level () == INTR_OFF);

  lock_init (&tid_lock);
  list_init (&ready_list);
  list_init (&all_list);

  //--------------------------
  list_init ( &lista_espera );
  //--------------------------

  /* Set up a thread structure for the running thread. */
  initial_thread = running_thread ();

  • Deshágase del problema inicial removiendo el ciclo y llamando a una función que usted definirá en thread.c, llamémosle insertar_en_lista_espera, que tome al thread actual, lo bloquee y lo inserte en la lista de espera que definimos en el paso anterior.

timer.c
void
timer_sleep (int64_t ticks) 
{
  //int64_t start = timer_ticks ();

  ASSERT (intr_get_level () == INTR_ON);
  /*while (timer_elapsed (start) < ticks) 
    thread_yield ();*/
    
  //-----------------------------
  insertar_en_lista_espera(ticks);
  //-----------------------------
}

Quizás quiera agregar la definición de esta nueva función en thread.h antes de implementarla en thread.c.

  • Implemente insertar_en_lista_espera, esta se vería de la siguiente forma:

thread.c
void insertar_en_lista_espera(int64_t ticks){

	//Deshabilitamos interrupciones
	enum intr_level old_level;
	old_level = intr_disable ();

	/* Remover el thread actual de "ready_list" e insertarlo en "lista_espera"
	Cambiar su estatus a THREAD_BLOCKED, y definir su tiempo de expiracion */
	
	struct thread *thread_actual = thread_current ();
  thread_actual->TIEMPO_DORMIDO = timer_ticks() + ticks;
  
  /*Donde TIEMPO_DORMIDO es el atributo de la estructura thread que usted
	  definió como paso inicial*/
	
  list_push_back(&lista_espera, &thread_actual->elem);
  thread_block();

  //Habilitar interrupciones
	intr_set_level (old_level);
}

  • Ahora que aseguramos que los threads estan bloqueados en esa lista, y que conocemos cuantos ticks deben permanecer en ella, debemos desbloquearlos cuando se haya cumplido su tiempo de expiración, para ello regresamos a timer.c y en timer_interrupt podemos llamar a otra función que usted definirá nuevamente en thread.c la cual llamaremos ahora, remover_thread_durmiente.

timer.c
/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED)
{
  ticks++;
  thread_tick ();

  //------------------------------
  remover_thread_durmiente(ticks);
  //------------------------------

}

Quizás quiera agregar la definición de esta nueva función en thread.h antes de implementarla en thread.c.

  • Y remover_thread_durmiente se vería de la siguiente forma.

thread.c
void remover_thread_durmiente(int64_t ticks){

	/*Cuando ocurra un timer_interrupt, si el tiempo del thread ha expirado
	Se mueve de regreso a ready_list, con la funcion thread_unblock*/
	
	//Iterar sobre "lista_espera"
	struct list_elem *iter = list_begin(&lista_espera);
	while(iter != list_end(&lista_espera) ){
		struct thread *thread_lista_espera= list_entry(iter, struct thread, elem);
		
		/*Si el tiempo global es mayor al tiempo que el thread permanecía dormido
		  entonces su tiempo de dormir ha expirado*/
		
		if(ticks >= thread_lista_espera->TIEMPO_DORMIDO){
			//Lo removemos de "lista_espera" y lo regresamos a ready_list
			iter = list_remove(iter);
			thread_unblock(thread_lista_espera);
		}else{
			//Sino, seguir iterando
			iter = list_next(iter);
		}
	}
  
}

  • Si usted siguió todos los pasos anteriores de forma correcta, puede ejecutar el comando make grade en la ubicación pintos/src/threads debería pasar algunos tests, equivalentes aproximadamente a 24/100 puntos de esta fase.

  • Por lo que ha realizado con éxito la primera tarea de la primera fase de Pintos.

  • Es probable que en las siguientes tareas, usted tenga que modificar o agregar cosas en las funciones que modificamos o agregamos en esta primera tarea, por lo que tome en cuenta que estarán sujetas a cambios.

Nota importante

Esta tarea prácticamente es un empujón, que le sirve a usted para adentrarse en este proyecto y aprobar los primeros tests. Su propósito era que trabajara y entendiera unas cuantas estructuras como lo son los threads y listas, y alguna de las cosas que logró hacer fueron las siguientes:

  • Manipulación de threads.

    • Añadir atributos a esta estructura.

    • Utilizar las funciones definidas en thread.c (thread_block, thread_unblock, thread_current).

  • Manipulación de listas.

    • Crear e inicializar una lista.

    • Insertar elementos.

    • Remover elementos.

    • Recorrer la lista.

    • Tomar un elemento de la lista, instanciarlo y manipularlo.

  • Habilitar y deshabilitar interrupciones.

Esto le será de utilidad ya que son acciones que realizará de manera muy frecuente a lo largo de todo el proyecto, o se topará con cosas a implementar que serán muy parecidas y sigan esta misma lógica.

Además considero que esta tarea guiada le servirá para perderle el miedo a modificar archivos, tratar de implementar cosas, y desarrollar ideas que usted pueda tener. Se le invita a intentar hacer lo realizado de otra forma, quién sabe, ¿No crear nuevas funciones en thread.c?, ¿Utilizar otra estructura distinta a una lista?, ¿Hacerlo todo en timer.c?, etc... esas son solo ideas, no significa que funcione... esto queda a su imaginación...

NOTA: Tome en cuenta que, en las siguientes tareas de las distintas fases del proyecto, ya no será todo tan detallado ni específico, se proporcionarán hints, mas sin embargo no será la solución exacta como se presentó en esta tarea de esta fase.

PreviousPintos: Guía Fase 1NextPriority Scheduling

Last updated