Keep process and victim pool items in dedicated storage during swapping (should gener...

diff --git a/Makefile b/Makefile
index 334dbb7..7e429af 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -3,19 +3,25 @@ CFLAGS=-g -Wall
 all: pool_test_gen pool_test_run process_test_gen process_test_run
 
 pool_test_gen: pool_test_gen.o
+       ${CC} ${CFLAGS} -o $@ $^
+
 pool_test_gen.o: pool_test_gen.c
 
 pool_test_run: pool_test_run.o pool.o
-pool_test_run.o: pool_test_run.c pool.h
+       ${CC} ${CFLAGS} -o $@ $^
 
+pool_test_run.o: pool_test_run.c pool.h
 pool.o: pool.c pool.h
 
 process_test_gen: process_test_gen.o
+       ${CC} ${CFLAGS} -o $@ $^
+
 process_test_gen.o: process_test_gen.c
 
 process_test_run: process_test_run.o process.o core.o swap.o pool.o
-process_test_run.o: process_test_run.c process.h core.h swap.h pool.h 
+       ${CC} ${CFLAGS} -o $@ $^
 
+process_test_run.o: process_test_run.c process.h core.h swap.h pool.h 
 process.o: process.c process.h core.h swap.h pool.h
 core.o: core.c core.h pool.h
 swap.o: swap.c swap.h core.h pool.h

diff --git a/pool.c b/pool.c
index 0ea8228..13825a7 100644 (file)
--- a/pool.c
+++ b/pool.c
@@ -489,3 +489,19 @@ resize:
  check_invariants(head);
   return true;
 }
+
+void pool_move_item(struct pool_item *from, struct pool_item *to) {
+  // from-item must be already allocated
+  assert(from->prev && from->next);
+
+  // to-item must not be already allocated
+  assert(to->prev == NULL && to->next == NULL);
+
+  *to = *from;
+#ifndef NDEBUG
+  from->prev = NULL;
+  from->next = NULL;
+#endif
+  to->prev->next = to;
+  to->next->prev = to;
+}

diff --git a/pool.h b/pool.h
index 8c0e228..58bc425 100644 (file)
--- a/pool.h
+++ b/pool.h
@@ -47,5 +47,6 @@ bool pool_realloc_moveable(
   struct pool_item *item,
   int size
 );
+void pool_move_item(struct pool_item *from, struct pool_item *to);
 
 #endif

diff --git a/process.c b/process.c
index f48b35d..a7bd73f 100644 (file)
--- a/process.c
+++ b/process.c
@@ -1,5 +1,6 @@
 #include <stdio.h> // temporary
 #include <stdlib.h>
+#include <string.h>
 #include "core.h"
 #include "process.h"
 #include "rassert.h"
@@ -13,6 +14,7 @@ int process_avail, process_spare;
 struct lru_item lru_head;
 
 struct process *victim;
+struct pool_item victim_core_item, victim_swap_item;
 
 #if 1
 static void check_invariants() {
@@ -24,6 +26,14 @@ static void check_invariants() {
     swap_head.item.limit -
     swap_head.spare -
     process_spare;
+  if (victim) {
+    assert(victim_core_item.prev);
+    assert(victim_swap_item.prev);
+  }
+  else {
+    assert(victim_core_item.prev == NULL);
+    assert(victim_swap_item.prev == NULL);
+  }
   for (int i = 0; i < n_processes; ++i)
     if (processes[i].size != -1) {
       if (processes[i].lru_item.prev) {
@@ -39,14 +49,14 @@ static void check_invariants() {
         );
       }
       else if (processes + i == victim) {
-        assert(processes[i].core_item.prev);
-        assert(processes[i].swap_item.prev);
+        assert(processes[i].core_item.prev == NULL);
+        assert(processes[i].swap_item.prev == NULL);
         assert(
           processes[i].size ==
-            processes[i].core_item.limit -
-            processes[i].core_item.base +
-            processes[i].swap_item.limit -
-            processes[i].swap_item.base
+            victim_core_item.limit -
+            victim_core_item.base +
+            victim_swap_item.limit -
+            victim_swap_item.base
         );
       }
       else {
@@ -80,6 +90,8 @@ void process_init(int n, int spare) {
   lru_head.next = &lru_head;
 
   victim = NULL;
+  memset(&victim_core_item, 0, sizeof(victim_core_item));
+  memset(&victim_swap_item, 0, sizeof(victim_swap_item));
  check_invariants();
 }
 
@@ -92,11 +104,15 @@ static void do_swap_out(int swap_out) {
     // getting rid of victims that are completely swapped
     if (victim == NULL)
       goto no_victim;
-    while ((size = victim->core_item.limit - victim->core_item.base) == 0) {
+    while ((size = victim_core_item.limit - victim_core_item.base) == 0) {
  printf("victimized %d\n", (int)(victim - processes));
-      // remove from core pool
-      pool_free(&core_head, &victim->core_item);
-      victim->core_item.prev = NULL;
+      // remove from core pool, using dedicated core item
+      pool_free(&core_head, &victim_core_item);
+      victim_core_item.prev = NULL;
+
+      // move dedicated to per-process swap item
+      pool_move_item(&victim_swap_item, &victim->swap_item);
+      victim_swap_item.prev = NULL; 
 
     no_victim:
       // take next least recently used process as victim
@@ -109,8 +125,14 @@ static void do_swap_out(int swap_out) {
       victim->lru_item.next->prev = victim->lru_item.prev;
       victim->lru_item.prev = NULL; // indicates not runnable
 
-      // put in swap pool
-      rassert(pool_alloc_moveable(&swap_head, &victim->swap_item, 0));
+      // move per-process to dedicated core item
+      pool_move_item(&victim->core_item, &victim_core_item);
+      victim->core_item.prev = NULL; 
+
+      // add to swap pool, using dedicated swap item
+      rassert(pool_alloc_moveable(&swap_head, &victim_swap_item, 0));
+ assert(victim_core_item.prev && victim_core_item.next);
+ assert(victim_swap_item.prev && victim_swap_item.next);
     }
 
     // calculate amount to swap
@@ -122,15 +144,15 @@ static void do_swap_out(int swap_out) {
     rassert(
       pool_realloc_moveable(
         &swap_head,
-        &victim->swap_item,
-        size + victim->swap_item.limit - victim->swap_item.base
+        &victim_swap_item,
+        size + victim_swap_item.limit - victim_swap_item.base
       )
     );
 
     // transfer data to swap
     swap_write(
-      ~victim->swap_item.limit,
-      victim->core_item.limit - size,
+      ~victim_swap_item.limit,
+      victim_core_item.limit - size,
       size
     );
 
@@ -138,10 +160,12 @@ static void do_swap_out(int swap_out) {
     rassert(
       pool_realloc_moveable(
         &core_head,
-        &victim->core_item,
-        victim->core_item.limit - victim->core_item.base - size
+        &victim_core_item,
+        victim_core_item.limit - victim_core_item.base - size
       )
     );
+ assert(victim_core_item.prev && victim_core_item.next);
+ assert(victim_swap_item.prev && victim_swap_item.next);
   }
 }
 
@@ -166,7 +190,7 @@ bool process_alloc(struct process *process, int size) {
   // not allowed to be in swap
   process->swap_item.prev = NULL;
 
-  // insert at head of in-core LRU list
+  // insert at head of LRU list
   process->lru_item.prev = &lru_head;
   process->lru_item.next = lru_head.next;
   process->lru_item.prev->next = &process->lru_item;
@@ -211,6 +235,7 @@ bool process_realloc(struct process *process, int size) {
 
 void process_run(struct process *process) {
   int swap_in, swap_out;
+  struct pool_item process_core_item, process_swap_item;
 
   // must be already allocated
   assert(process->size != -1);
@@ -224,19 +249,35 @@ void process_run(struct process *process) {
   }
   else {
     // no, need to swap some in
-    // if current victim, partly in core, otherwise add to core pool
-    if (process == victim)
+    memset(&process_core_item, 0, sizeof(process_core_item));
+    memset(&process_swap_item, 0, sizeof(process_swap_item));
+ 
+    // see whether victim or fully in swap
+    if (process == victim) {
+      // victim, take over the dedicated pool items
       victim = NULL;
-    else
-      rassert(pool_alloc_moveable(&core_head, &process->core_item, 0));
+
+      pool_move_item(&victim_core_item, &process_core_item);
+      victim_core_item.prev = NULL;
+
+      pool_move_item(&victim_swap_item, &process_swap_item);
+      victim_swap_item.prev = NULL;
+    }
+    else {
+      // fully in swap, take over only the per-process swap item
+      pool_move_item(&process->swap_item, &process_swap_item);
+      process->swap_item.prev = NULL;
+
+      rassert(pool_alloc_moveable(&core_head, &process_core_item, 0));
+    }
 
     // while not fully in core, make space and bring some in
     while (
       (
         swap_in =
           process->size +
-          process->core_item.base -
-          process->core_item.limit
+          process_core_item.base -
+          process_core_item.limit
       ) != 0
     ) {
       // free up as much core as we can, for this iteration
@@ -251,15 +292,15 @@ void process_run(struct process *process) {
       rassert(
         pool_realloc_moveable(
           &core_head,
-          &process->core_item,
-          swap_in + process->core_item.limit - process->core_item.base
+          &process_core_item,
+          swap_in + process_core_item.limit - process_core_item.base
         )
       );
 
       // transfer data to core
       swap_read(
-        ~process->swap_item.limit,
-        process->core_item.limit - swap_in,
+        ~process_swap_item.limit,
+        process_core_item.limit - swap_in,
         swap_in
       );
 
@@ -267,15 +308,19 @@ void process_run(struct process *process) {
       rassert(
         pool_realloc_moveable(
           &swap_head,
-          &process->swap_item,
-          process->swap_item.limit - process->swap_item.base - swap_in
+          &process_swap_item,
+          process_swap_item.limit - process_swap_item.base - swap_in
         )
       );
     }
 
-    // remove from swap pool
-    pool_free(&swap_head, &process->swap_item);
-    process->swap_item.prev = NULL;
+    // move dedicated to per-process core item
+    pool_move_item(&process_core_item, &process->core_item);
+    //process_core_item.prev = NULL; 
+
+    // remove from swap pool, using dedicated swap item
+    pool_free(&swap_head, &process_swap_item);
+    //process_swap_item.prev = NULL;
   }
 
   // insert at head of LRU list
@@ -290,9 +335,9 @@ void process_free(struct process *process) {
   // must be already allocated
   assert(process->size != -1);
 
-  // see whether in-core, victim or in-swap
+  // see whether fully in core, victim, or fully in swap
   if (process->lru_item.prev != NULL) {
-    // in core, remove from LRU list and core pool
+    // fully in core, remove from LRU list and core pool
     assert(process != victim);
 
     process->lru_item.prev->next = process->lru_item.next;
@@ -302,17 +347,17 @@ void process_free(struct process *process) {
     process->core_item.prev = NULL;
   }
   else if (process == victim) {
-    // victim, remove from core and swap pools
+    // victim, free the dedicated pool items
     victim = NULL;
 
-    pool_free(&core_head, &process->core_item);
-    process->core_item.prev = NULL;
+    pool_free(&core_head, &victim_core_item);
+    victim_core_item.prev = NULL;
 
-    pool_free(&swap_head, &process->swap_item);
-    process->swap_item.prev = NULL;
+    pool_free(&swap_head, &victim_swap_item);
+    victim_swap_item.prev = NULL;
   }
   else {
-    // in-swap, remove from swap pool
+    // fully in swap, remove from swap pool
     pool_free(&swap_head, &process->swap_item);
     process->swap_item.prev = NULL;
   }

diff --git a/process.h b/process.h
index c805128..3a74cda 100644 (file)
--- a/process.h
+++ b/process.h
@@ -21,6 +21,7 @@ extern int process_avail, process_spare;
 extern struct lru_item lru_head;
 
 extern struct process *victim;
+extern struct pool_item victim_core_item, victim_swap_item;
 
 void process_init(int n, int spare);
 bool process_alloc(struct process *process, int size);

diff --git a/process_test_run.c b/process_test_run.c
index 254e21c..5b342ab 100644 (file)
--- a/process_test_run.c
+++ b/process_test_run.c
@@ -26,29 +26,6 @@ int main(int argc, char **argv) {
     processes[i].size = -1;
 
   while (true) {
-#if 0
- for (int i = 0; i < n_processes; ++i) {
-  if (processes[i].size != -1) {
-   bool in_core = processes[i].core_item.prev != NULL;
-   int core_base = in_core ? processes[i].core_item.base : -1;
-   int core_size = in_core ? processes[i].core_item.limit - core_base : 0;
-   bool in_swap = processes[i].swap_item.prev != NULL;
-   int swap_limit = in_swap ? processes[i].swap_item.limit : 0;
-   int swap_size = in_swap ? swap_limit - processes[i].swap_item.base : 0;
-   rassert(core_size + swap_size == processes[i].size);
-   int swap_base = ~swap_limit;
-   for (int j = 0; j < processes[i].size; ++j) {
-    long long hash = i * 17 + j * 29;
-    hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
-    hash = (hash & 0xffffffffffffffffLL) + (hash >> 32);
-    if (j < core_size)
-     rassert(core_mem[core_base + j] == (int)hash);
-    else
-     rassert(swap_mem[swap_base + j - core_size] == (int)hash);
-   }
-  }
- }
-#endif
  //printf("avail %d %d %d\n", process_avail, core_head.avail, swap_head.avail);
     char buf[256];
     switch (scanf("%s", buf)) {
@@ -177,6 +154,7 @@ int main(int argc, char **argv) {
           old_size
         );
       else {
+        bool is_victim = processes + process == victim;
         bool in_core = processes[process].core_item.prev != NULL;
         bool in_swap = processes[process].swap_item.prev != NULL;
         int actual_old_size = processes[process].size;
@@ -189,10 +167,10 @@ int main(int argc, char **argv) {
           old_size,
           actual_old_size
         );
-        int core_base = in_core ? processes[process].core_item.base : -1;
-        int core_size = in_core ? processes[process].core_item.limit - core_base : 0;
-        int swap_limit = in_swap ? processes[process].swap_item.limit : 0;
-        int swap_size = in_swap ? swap_limit - processes[process].swap_item.base : 0;
+        int core_base = is_victim ? victim_core_item.base : in_core ? processes[process].core_item.base : -1;
+        int core_size = is_victim ? victim_core_item.limit - core_base : in_core ? processes[process].core_item.limit - core_base : 0;
+        int swap_limit = is_victim ? victim_swap_item.limit : in_swap ? processes[process].swap_item.limit : 0;
+        int swap_size = is_victim ? swap_limit - victim_swap_item.base : in_swap ? swap_limit - processes[process].swap_item.base : 0;
         rassert(core_size + swap_size == actual_old_size);
         int swap_base = ~swap_limit;
  printf("old core [%d,%d) swap [%d,%d)\n", core_base, core_base + core_size, swap_base, swap_base + swap_size);
@@ -221,12 +199,13 @@ done:
     if (processes[i].size == -1)
       printf("process %d: not allocated\n", i);
     else {
+      bool is_victim = processes + i == victim;
       bool in_core = processes[i].core_item.prev != NULL;
-      int core_base = in_core ? processes[i].core_item.base : -1;
-      int core_size = in_core ? processes[i].core_item.limit - core_base : 0;
+      int core_base = is_victim ? victim_core_item.base : in_core ? processes[i].core_item.base : -1;
+      int core_size = is_victim ? victim_core_item.limit - core_base : in_core ? processes[i].core_item.limit - core_base : 0;
       bool in_swap = processes[i].swap_item.prev != NULL;
-      int swap_limit = in_swap ? processes[i].swap_item.limit : 0;
-      int swap_size = in_swap ? swap_limit - processes[i].swap_item.base : 0;
+      int swap_limit = is_victim ? victim_swap_item.limit : in_swap ? processes[i].swap_item.limit : 0;
+      int swap_size = is_victim ? swap_limit - victim_swap_item.base : in_swap ? swap_limit - processes[i].swap_item.base : 0;
       int swap_base = ~swap_limit;
       printf("process %d: core [%d,%d) swap [%d,%d)\n", i, core_base, core_base + core_size, swap_base, swap_base + swap_size);
       for (int j = 0; j < processes[i].size; ++j) {