pintos-os.org Git - pintos-anon/blob - solutions/p3.patch

   1 diff --git a/src/Makefile.build b/src/Makefile.build
   2 index e997d27..1057023 100644
   3 --- a/src/Makefile.build
   4 +++ b/src/Makefile.build
   5 @@ -62,7 +62,9 @@ userprog_SRC += userprog/gdt.c                # GDT initialization.
   6  userprog_SRC += userprog/tss.c         # TSS management.
   7
   8  # No virtual memory code yet.
   9 -#vm_SRC = vm/file.c                    # Some file.
  10 +vm_SRC = vm/page.c
  11 +vm_SRC += vm/frame.c
  12 +vm_SRC += vm/swap.c
  13
  14  # Filesystem code.
  15  filesys_SRC  = filesys/filesys.c       # Filesystem core.
  16 diff --git a/src/devices/timer.c b/src/devices/timer.c
  17 index 1aebae7..4b920e9 100644
  18 --- a/src/devices/timer.c
  19 +++ b/src/devices/timer.c
  20 @@ -206,7 +206,6 @@ timer_interrupt (struct intr_frame *args UNUSED)
  21        if (ticks < t->wakeup_time)
  22          break;
  23        sema_up (&t->timer_sema);
  24 -      thread_yield_to_higher_priority ();
  25        list_pop_front (&wait_list);
  26      }
  27  }
  28 diff --git a/src/threads/fixed-point.h b/src/threads/fixed-point.h
  29 deleted file mode 100644
  30 index ca88f97..0000000
  31 --- a/src/threads/fixed-point.h
  32 +++ /dev/null
  33 @@ -1,120 +0,0 @@
  34 -#ifndef THREADS_FIXED_POINT_H
  35 -#define THREADS_FIXED_POINT_H
  36 -
  37 -#include <debug.h>
  38 -
  39 -/* Parameters. */
  40 -#define FIX_BITS 32             /* Total bits per fixed-point number. */
  41 -#define FIX_P 16                /* Number of integer bits. */
  42 -#define FIX_Q 16                /* Number of fractional bits. */
  43 -#define FIX_F (1 << FIX_Q)      /* pow(2, FIX_Q). */
  44 -
  45 -#define FIX_MIN_INT (-FIX_MAX_INT)      /* Smallest representable integer. */
  46 -#define FIX_MAX_INT ((1 << FIX_P) - 1)  /* Largest representable integer. */
  47 -
  48 -/* A fixed-point number. */
  49 -typedef struct
  50 -  {
  51 -    int f;
  52 -  }
  53 -fixed_point_t;
  54 -
  55 -/* Returns a fixed-point number with F as its internal value. */
  56 -static inline fixed_point_t
  57 -__mk_fix (int f)
  58 -{
  59 -  fixed_point_t x;
  60 -  x.f = f;
  61 -  return x;
  62 -}
  63 -
  64 -/* Returns fixed-point number corresponding to integer N. */
  65 -static inline fixed_point_t
  66 -fix_int (int n)
  67 -{
  68 -  ASSERT (n >= FIX_MIN_INT && n <= FIX_MAX_INT);
  69 -  return __mk_fix (n * FIX_F);
  70 -}
  71 -
  72 -/* Returns fixed-point number corresponding to N divided by D. */
  73 -static inline fixed_point_t
  74 -fix_frac (int n, int d)
  75 -{
  76 -  ASSERT (d != 0);
  77 -  ASSERT (n / d >= FIX_MIN_INT && n / d <= FIX_MAX_INT);
  78 -  return __mk_fix ((long long) n * FIX_F / d);
  79 -}
  80 -
  81 -/* Returns X rounded to the nearest integer. */
  82 -static inline int
  83 -fix_round (fixed_point_t x)
  84 -{
  85 -  return (x.f + FIX_F / 2) / FIX_F;
  86 -}
  87 -
  88 -/* Returns X truncated down to the nearest integer. */
  89 -static inline int
  90 -fix_trunc (fixed_point_t x)
  91 -{
  92 -  return x.f / FIX_F;
  93 -}
  94 -
  95 -/* Returns X + Y. */
  96 -static inline fixed_point_t
  97 -fix_add (fixed_point_t x, fixed_point_t y)
  98 -{
  99 -  return __mk_fix (x.f + y.f);
 100 -}
 101 -
 102 -/* Returns X - Y. */
 103 -static inline fixed_point_t
 104 -fix_sub (fixed_point_t x, fixed_point_t y)
 105 -{
 106 -  return __mk_fix (x.f - y.f);
 107 -}
 108 -
 109 -/* Returns X * Y. */
 110 -static inline fixed_point_t
 111 -fix_mul (fixed_point_t x, fixed_point_t y)
 112 -{
 113 -  return __mk_fix ((long long) x.f * y.f / FIX_F);
 114 -}
 115 -
 116 -/* Returns X * N. */
 117 -static inline fixed_point_t
 118 -fix_scale (fixed_point_t x, int n)
 119 -{
 120 -  ASSERT (n >= 0);
 121 -  return __mk_fix (x.f * n);
 122 -}
 123 -
 124 -/* Returns X / Y. */
 125 -static inline fixed_point_t
 126 -fix_div (fixed_point_t x, fixed_point_t y)
 127 -{
 128 -  return __mk_fix ((long long) x.f * FIX_F / y.f);
 129 -}
 130 -
 131 -/* Returns X / N. */
 132 -static inline fixed_point_t
 133 -fix_unscale (fixed_point_t x, int n)
 134 -{
 135 -  ASSERT (n > 0);
 136 -  return __mk_fix (x.f / n);
 137 -}
 138 -
 139 -/* Returns 1 / X. */
 140 -static inline fixed_point_t
 141 -fix_inv (fixed_point_t x)
 142 -{
 143 -  return fix_div (fix_int (1), x);
 144 -}
 145 -
 146 -/* Returns -1 if X < Y, 0 if X == Y, 1 if X > Y. */
 147 -static inline int
 148 -fix_compare (fixed_point_t x, fixed_point_t y)
 149 -{
 150 -  return x.f < y.f ? -1 : x.f > y.f;
 151 -}
 152 -
 153 -#endif /* threads/fixed-point.h */
 154 diff --git a/src/threads/init.c b/src/threads/init.c
 155 index cebec2c..9729de7 100644
 156 --- a/src/threads/init.c
 157 +++ b/src/threads/init.c
 158 @@ -37,6 +37,8 @@
 159  #include "filesys/filesys.h"
 160  #include "filesys/fsutil.h"
 161  #endif
 162 +#include "vm/frame.h"
 163 +#include "vm/swap.h"
 164
 165  /* Page directory with kernel mappings only. */
 166  uint32_t *init_page_dir;
 167 @@ -127,6 +129,9 @@ main (void)
 168    filesys_init (format_filesys);
 169  #endif
 170
 171 +  frame_init ();
 172 +  swap_init ();
 173 +
 174    printf ("Boot complete.\n");
 175
 176    /* Run actions specified on kernel command line. */
 177 diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c
 178 index e3b90dc..f897882 100644
 179 --- a/src/threads/interrupt.c
 180 +++ b/src/threads/interrupt.c
 181 @@ -360,6 +360,8 @@ intr_handler (struct intr_frame *frame)
 182        in_external_intr = true;
 183        yield_on_return = false;
 184      }
 185 +  else
 186 +    thread_current ()->user_esp = frame->esp;
 187
 188    /* Invoke the interrupt's handler. */
 189    handler = intr_handlers[frame->vec_no];
 190 diff --git a/src/threads/synch.c b/src/threads/synch.c
 191 index 53197bb..317c68a 100644
 192 --- a/src/threads/synch.c
 193 +++ b/src/threads/synch.c
 194 @@ -113,28 +113,10 @@ sema_up (struct semaphore *sema)
 195    ASSERT (sema != NULL);
 196
 197    old_level = intr_disable ();
 198 -  sema->value++;
 199    if (!list_empty (&sema->waiters))
 200 -    {
 201 -      /* Find highest-priority waiting thread. */
 202 -      struct thread *max = list_entry (list_max (&sema->waiters,
 203 -                                                 thread_lower_priority, NULL),
 204 -                                       struct thread, elem);
 205 -
 206 -      /* Remove `max' from wait list and unblock. */
 207 -      list_remove (&max->elem);
 208 -      thread_unblock (max);
 209 -
 210 -      /* Yield to a higher-priority thread, if we're running in a
 211 -         context where it makes sense to do so.
 212 -
 213 -         Kind of a funny interaction with donation here.
 214 -         We only support donation for locks, and locks turn off
 215 -         interrupts before calling us, so we automatically don't
 216 -         do the yield here, delegating to lock_release(). */
 217 -      if (!intr_context () && old_level == INTR_ON)
 218 -        thread_yield_to_higher_priority ();
 219 -    }
 220 +    thread_unblock (list_entry (list_pop_front (&sema->waiters),
 221 +                                struct thread, elem));
 222 +  sema->value++;
 223    intr_set_level (old_level);
 224  }
 225
 226 @@ -210,33 +192,12 @@ lock_init (struct lock *lock)
 227  void
 228  lock_acquire (struct lock *lock)
 229  {
 230 -  enum intr_level old_level;
 231 -
 232    ASSERT (lock != NULL);
 233    ASSERT (!intr_context ());
 234    ASSERT (!lock_held_by_current_thread (lock));
 235
 236 -  old_level = intr_disable ();
 237 -
 238 -  if (lock->holder != NULL)
 239 -    {
 240 -      /* Donate our priority to the thread holding the lock.
 241 -         First, update the data structures. */
 242 -      struct thread *donor = thread_current ();
 243 -      donor->want_lock = lock;
 244 -      donor->donee = lock->holder;
 245 -      list_push_back (&lock->holder->donors, &donor->donor_elem);
 246 -
 247 -      /* Now implement the priority donation itself
 248 -         by recomputing the donee's priority
 249 -         and cascading the donation as far as necessary. */
 250 -      if (donor->donee != NULL)
 251 -        thread_recompute_priority (donor->donee);
 252 -    }
 253 -
 254    sema_down (&lock->semaphore);
 255    lock->holder = thread_current ();
 256 -  intr_set_level (old_level);
 257  }
 258
 259  /* Tries to acquires LOCK and returns true if successful or false
 260 @@ -267,39 +228,11 @@ lock_try_acquire (struct lock *lock)
 261  void
 262  lock_release (struct lock *lock)
 263  {
 264 -  enum intr_level old_level;
 265 -  struct thread *t = thread_current ();
 266 -  struct list_elem *e;
 267 -
 268    ASSERT (lock != NULL);
 269    ASSERT (lock_held_by_current_thread (lock));
 270
 271 -  old_level = intr_disable ();
 272 -
 273 -  /* Return donations to threads that want this lock. */
 274 -  for (e = list_begin (&t->donors); e != list_end (&t->donors); )
 275 -    {
 276 -      struct thread *donor = list_entry (e, struct thread, donor_elem);
 277 -      if (donor->want_lock == lock)
 278 -        {
 279 -          donor->donee = NULL;
 280 -          e = list_remove (e);
 281 -        }
 282 -      else
 283 -        e = list_next (e);
 284 -    }
 285 -
 286 -  /* Release lock. */
 287    lock->holder = NULL;
 288    sema_up (&lock->semaphore);
 289 -
 290 -  /* Recompute our priority based on our remaining donations,
 291 -     then yield to a higher-priority ready thread if one now
 292 -     exists. */
 293 -  thread_recompute_priority (t);
 294 -  thread_yield_to_higher_priority ();
 295 -
 296 -  intr_set_level (old_level);
 297  }
 298
 299  /* Returns true if the current thread holds LOCK, false
 300 @@ -318,7 +251,6 @@ struct semaphore_elem
 301    {
 302      struct list_elem elem;              /* List element. */
 303      struct semaphore semaphore;         /* This semaphore. */
 304 -    struct thread *thread;              /* Thread. */
 305    };
 306
 307  /* Initializes condition variable COND.  A condition variable
 308 @@ -363,26 +295,12 @@ cond_wait (struct condition *cond, struct lock *lock)
 309    ASSERT (lock_held_by_current_thread (lock));
 310
 311    sema_init (&waiter.semaphore, 0);
 312 -  waiter.thread = thread_current ();
 313    list_push_back (&cond->waiters, &waiter.elem);
 314    lock_release (lock);
 315    sema_down (&waiter.semaphore);
 316    lock_acquire (lock);
 317  }
 318
 319 -static bool
 320 -semaphore_elem_lower_priority (const struct list_elem *a_,
 321 -                               const struct list_elem *b_,
 322 -                               void *aux UNUSED)
 323 -{
 324 -  const struct semaphore_elem *a
 325 -    = list_entry (a_, struct semaphore_elem, elem);
 326 -  const struct semaphore_elem *b
 327 -    = list_entry (b_, struct semaphore_elem, elem);
 328 -
 329 -  return a->thread->priority < b->thread->priority;
 330 -}
 331 -
 332  /* If any threads are waiting on COND (protected by LOCK), then
 333     this function signals one of them to wake up from its wait.
 334     LOCK must be held before calling this function.
 335 @@ -399,12 +317,8 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
 336    ASSERT (lock_held_by_current_thread (lock));
 337
 338    if (!list_empty (&cond->waiters))
 339 -    {
 340 -      struct list_elem *max
 341 -        = list_max (&cond->waiters, semaphore_elem_lower_priority, NULL);
 342 -      list_remove (max);
 343 -      sema_up (&list_entry (max, struct semaphore_elem, elem)->semaphore);
 344 -    }
 345 +    sema_up (&list_entry (list_pop_front (&cond->waiters),
 346 +                          struct semaphore_elem, elem)->semaphore);
 347  }
 348
 349  /* Wakes up all threads, if any, waiting on COND (protected by
 350 diff --git a/src/threads/thread.c b/src/threads/thread.c
 351 index 9fa7f1c..f9f2310 100644
 352 --- a/src/threads/thread.c
 353 +++ b/src/threads/thread.c
 354 @@ -5,13 +5,11 @@
 355  #include <stdio.h>
 356  #include <string.h>
 357  #include "threads/flags.h"
 358 -#include "threads/init.h"
 359  #include "threads/interrupt.h"
 360  #include "threads/intr-stubs.h"
 361  #include "threads/palloc.h"
 362  #include "threads/switch.h"
 363  #include "threads/synch.h"
 364 -#include "devices/timer.h"
 365  #include "threads/vaddr.h"
 366  #ifdef USERPROG
 367  #include "userprog/process.h"
 368 @@ -56,7 +54,6 @@ static long long user_ticks;    /* # of timer ticks in user programs. */
 369  /* Scheduling. */
 370  #define TIME_SLICE 4            /* # of timer ticks to give each thread. */
 371  static unsigned thread_ticks;   /* # of timer ticks since last yield. */
 372 -static fixed_point_t load_avg;  /* Load average. */
 373
 374  /* If false (default), use round-robin scheduler.
 375     If true, use multi-level feedback queue scheduler.
 376 @@ -68,7 +65,8 @@ static void kernel_thread (thread_func *, void *aux);
 377  static void idle (void *aux UNUSED);
 378  static struct thread *running_thread (void);
 379  static struct thread *next_thread_to_run (void);
 380 -static void init_thread (struct thread *, const char *name, int priority);
 381 +static void init_thread (struct thread *, const char *name, int priority,
 382 +                         tid_t);
 383  static bool is_thread (struct thread *) UNUSED;
 384  static void *alloc_frame (struct thread *, size_t size);
 385  static void schedule (void);
 386 @@ -96,13 +94,11 @@ thread_init (void)
 387    lock_init (&tid_lock);
 388    list_init (&ready_list);
 389    list_init (&all_list);
 390 -  load_avg = fix_int (0);
 391
 392    /* Set up a thread structure for the running thread. */
 393    initial_thread = running_thread ();
 394 -  init_thread (initial_thread, "main", PRI_DEFAULT);
 395 +  init_thread (initial_thread, "main", PRI_DEFAULT, 0);
 396    initial_thread->status = THREAD_RUNNING;
 397 -  initial_thread->tid = allocate_tid ();
 398  }
 399
 400  /* Starts preemptive thread scheduling by enabling interrupts.
 401 @@ -122,18 +118,6 @@ thread_start (void)
 402    sema_down (&idle_started);
 403  }
 404
 405 -/* Adjust recent CPU of a thread based on load factor
 406 -   and recompute its priority. */
 407 -static void
 408 -adjust_recent_cpu (struct thread *t, void *aux)
 409 -{
 410 -  fixed_point_t load_factor = *(fixed_point_t *)aux;
 411 -
 412 -  t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
 413 -                           fix_int (t->nice));
 414 -  thread_recompute_priority (t);
 415 -}
 416 -
 417  /* Called by the timer interrupt handler at each timer tick.
 418     Thus, this function runs in an external interrupt context. */
 419  void
 420 @@ -151,41 +135,9 @@ thread_tick (void)
 421    else
 422      kernel_ticks++;
 423
 424 -  if (thread_mlfqs)
 425 -    {
 426 -      /* Update load average. */
 427 -      if (timer_ticks () % TIMER_FREQ == 0)
 428 -        {
 429 -          size_t ready_threads = list_size (&ready_list);
 430 -          if (t != idle_thread)
 431 -            ready_threads++;
 432 -
 433 -          load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg),
 434 -                              fix_mul (fix_frac (1, 60), fix_int (ready_threads)));
 435 -        }
 436 -
 437 -      /* Increment running process's recent_cpu. */
 438 -      if (t != idle_thread)
 439 -        t->recent_cpu = fix_add (t->recent_cpu, fix_int (1));
 440 -
 441 -      /* Update recent_cpu and thread priorities once per second. */
 442 -      if (timer_ticks () % TIMER_FREQ == 0)
 443 -        {
 444 -          fixed_point_t twice_load = fix_scale (load_avg, 2);
 445 -          fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1));
 446 -          fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1);
 447 -
 448 -          thread_foreach (adjust_recent_cpu, &load_factor);
 449 -        }
 450 -    }
 451 -
 452 -  /* Switch threads if time slice has expired. */
 453 -  if (++thread_ticks >= TIME_SLICE)
 454 -    {
 455 -      if (thread_mlfqs)
 456 -        thread_recompute_priority (thread_current ());
 457 -      intr_yield_on_return ();
 458 -    }
 459 +  /* Enforce preemption. */
 460 +  if (++thread_ticks >= TIME_SLICE)
 461 +    intr_yield_on_return ();
 462  }
 463
 464  /* Prints thread statistics. */
 465 @@ -215,7 +167,6 @@ tid_t
 466  thread_create (const char *name, int priority,
 467                 thread_func *function, void *aux)
 468  {
 469 -  struct thread *cur = thread_current ();
 470    struct thread *t;
 471    struct kernel_thread_frame *kf;
 472    struct switch_entry_frame *ef;
 473 @@ -230,10 +181,8 @@ thread_create (const char *name, int priority,
 474      return TID_ERROR;
 475
 476    /* Initialize thread. */
 477 -  init_thread (t, name, thread_mlfqs ? cur->priority : priority);
 478 -  tid = t->tid = allocate_tid ();
 479 -  t->nice = cur->nice;
 480 -  t->recent_cpu = cur->recent_cpu;
 481 +  init_thread (t, name, priority, allocate_tid ());
 482 +  tid = t->tid;
 483
 484    /* Stack frame for kernel_thread(). */
 485    kf = alloc_frame (t, sizeof *kf);
 486 @@ -252,8 +201,6 @@ thread_create (const char *name, int priority,
 487
 488    /* Add to run queue. */
 489    thread_unblock (t);
 490 -  if (priority > thread_get_priority ())
 491 -    thread_yield ();
 492
 493    return tid;
 494  }
 495 @@ -274,19 +221,6 @@ thread_block (void)
 496    schedule ();
 497  }
 498
 499 -/* Returns true if A has lower priority than B,
 500 -   within a list of threads. */
 501 -bool
 502 -thread_lower_priority (const struct list_elem *a_,
 503 -                        const struct list_elem *b_,
 504 -                        void *aux UNUSED)
 505 -{
 506 -  const struct thread *a = list_entry (a_, struct thread, elem);
 507 -  const struct thread *b = list_entry (b_, struct thread, elem);
 508 -
 509 -  return a->priority < b->priority;
 510 -}
 511 -
 512  /* Transitions a blocked thread T to the ready-to-run state.
 513     This is an error if T is not blocked.  (Use thread_yield() to
 514     make the running thread ready.)
 515 @@ -349,11 +283,11 @@ thread_exit (void)
 516  {
 517    ASSERT (!intr_context ());
 518
 519 +  syscall_exit ();
 520  #ifdef USERPROG
 521    process_exit ();
 522  #endif
 523 -  syscall_exit ();
 524 -
 525 +
 526    /* Remove thread from all threads list, set our status to dying,
 527       and schedule another process.  That process will destroy us
 528       when it calls thread_schedule_tail(). */
 529 @@ -399,26 +333,11 @@ thread_foreach (thread_action_func *func, void *aux)
 530      }
 531  }
 532
 533 -static void
 534 -recompute_priority_chain (void)
 535 -{
 536 -  enum intr_level old_level = intr_disable ();
 537 -  thread_recompute_priority (thread_current ());
 538 -  thread_yield_to_higher_priority ();
 539 -  intr_set_level (old_level);
 540 -}
 541 -
 542 -/* Sets the current thread's priority to PRIORITY. */
 543 +/* Sets the current thread's priority to NEW_PRIORITY. */
 544  void
 545 -thread_set_priority (int priority)
 546 +thread_set_priority (int new_priority)
 547  {
 548 -  if (!thread_mlfqs)
 549 -    {
 550 -      struct thread *t = thread_current ();
 551 -
 552 -      t->normal_priority = priority;
 553 -      recompute_priority_chain ();
 554 -    }
 555 +  thread_current ()->priority = new_priority;
 556  }
 557
 558  /* Returns the current thread's priority. */
 559 @@ -430,98 +349,33 @@ thread_get_priority (void)
 560
 561  /* Sets the current thread's nice value to NICE. */
 562  void
 563 -thread_set_nice (int nice)
 564 +thread_set_nice (int nice UNUSED)
 565  {
 566 -  thread_current ()->nice = nice;
 567 -  recompute_priority_chain ();
 568 +  /* Not yet implemented. */
 569  }
 570
 571  /* Returns the current thread's nice value. */
 572  int
 573  thread_get_nice (void)
 574  {
 575 -  return thread_current ()->nice;
 576 +  /* Not yet implemented. */
 577 +  return 0;
 578  }
 579
 580 +/* Returns 100 times the system load average. */
 581  int
 582  thread_get_load_avg (void)
 583  {
 584 -  int load_avg_int;
 585 -  enum intr_level level = intr_disable ();
 586 -  load_avg_int = fix_round (fix_scale (load_avg, 100));
 587 -  intr_set_level (level);
 588 -  return load_avg_int;
 589 +  /* Not yet implemented. */
 590 +  return 0;
 591  }
 592
 593 +/* Returns 100 times the current thread's recent_cpu value. */
 594  int
 595  thread_get_recent_cpu (void)
 596  {
 597 -  int recent_cpu_int;
 598 -  enum intr_level level = intr_disable ();
 599 -  recent_cpu_int = fix_round (fix_scale (thread_current ()->recent_cpu, 100));
 600 -  intr_set_level (level);
 601 -  return recent_cpu_int;
 602 -}
 603 -
 604 -/* Returns true if thread A has lower priority than thread B,
 605 -   within a list of donors. */
 606 -static bool
 607 -donated_lower_priority (const struct list_elem *a_,
 608 -                        const struct list_elem *b_,
 609 -                        void *aux UNUSED)
 610 -{
 611 -  const struct thread *a = list_entry (a_, struct thread, donor_elem);
 612 -  const struct thread *b = list_entry (b_, struct thread, donor_elem);
 613 -
 614 -  return a->priority < b->priority;
 615 -}
 616 -
 617 -/* Recomputes T's priority in terms of its normal priority and
 618 -   its donors' priorities, if any,
 619 -   and cascades the donation as necessary. */
 620 -void
 621 -thread_recompute_priority (struct thread *t)
 622 -{
 623 -  int old_priority = t->priority;
 624 -  int default_priority = t->normal_priority;
 625 -  int donation = PRI_MIN;
 626 -  if (thread_mlfqs)
 627 -    {
 628 -      default_priority = PRI_MAX - fix_round (t->recent_cpu) / 4 - t->nice * 2;
 629 -      if (default_priority < PRI_MIN)
 630 -        default_priority = PRI_MIN;
 631 -      else if (default_priority > PRI_MAX)
 632 -        default_priority = PRI_MAX;
 633 -    }
 634 -  if (!list_empty (&t->donors))
 635 -    donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
 636 -                           struct thread, donor_elem)->priority;
 637 -  t->priority = donation > default_priority ? donation : default_priority;
 638 -  if (t->priority > old_priority && t->donee != NULL)
 639 -    thread_recompute_priority (t->donee);
 640 -}
 641 -
 642 -/* If the ready list contains a thread with a higher priority,
 643 -   yields to it. */
 644 -void
 645 -thread_yield_to_higher_priority (void)
 646 -{
 647 -  enum intr_level old_level = intr_disable ();
 648 -  if (!list_empty (&ready_list))
 649 -    {
 650 -      struct thread *cur = thread_current ();
 651 -      struct thread *max = list_entry (list_max (&ready_list,
 652 -                                                 thread_lower_priority, NULL),
 653 -                                       struct thread, elem);
 654 -      if (max->priority > cur->priority)
 655 -        {
 656 -          if (intr_context ())
 657 -            intr_yield_on_return ();
 658 -          else
 659 -            thread_yield ();
 660 -        }
 661 -    }
 662 -  intr_set_level (old_level);
 663 +  /* Not yet implemented. */
 664 +  return 0;
 665  }
 666  \f
 667  /* Idle thread.  Executes when no other thread is ready to run.
 668 @@ -597,7 +451,7 @@ is_thread (struct thread *t)
 669  /* Does basic initialization of T as a blocked thread named
 670     NAME. */
 671  static void
 672 -init_thread (struct thread *t, const char *name, int priority)
 673 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
 674  {
 675    enum intr_level old_level;
 676
 677 @@ -606,17 +460,22 @@ init_thread (struct thread *t, const char *name, int priority)
 678    ASSERT (name != NULL);
 679
 680    memset (t, 0, sizeof *t);
 681 +  t->tid = tid;
 682    t->status = THREAD_BLOCKED;
 683    strlcpy (t->name, name, sizeof t->name);
 684    t->stack = (uint8_t *) t + PGSIZE;
 685 -  t->priority = t->normal_priority = priority;
 686 -  list_init (&t->children);
 687 +  t->priority = priority;
 688 +  t->exit_code = -1;
 689    t->wait_status = NULL;
 690 +  list_init (&t->children);
 691 +  sema_init (&t->timer_sema, 0);
 692 +  t->pagedir = NULL;
 693 +  t->pages = NULL;
 694 +  t->bin_file = NULL;
 695    list_init (&t->fds);
 696 +  list_init (&t->mappings);
 697    t->next_handle = 2;
 698    t->magic = THREAD_MAGIC;
 699 -  sema_init (&t->timer_sema, 0);
 700 -  list_init (&t->donors);
 701    old_level = intr_disable ();
 702    list_push_back (&all_list, &t->allelem);
 703    intr_set_level (old_level);
 704 @@ -645,14 +504,8 @@ next_thread_to_run (void)
 705  {
 706    if (list_empty (&ready_list))
 707      return idle_thread;
 708 -  else
 709 -    {
 710 -      struct thread *max
 711 -        = list_entry (list_max (&ready_list, thread_lower_priority, NULL),
 712 -                      struct thread, elem);
 713 -      list_remove (&max->elem);
 714 -      return max;
 715 -    }
 716 +  else
 717 +    return list_entry (list_pop_front (&ready_list), struct thread, elem);
 718  }
 719
 720  /* Completes a thread switch by activating the new thread's page
 721 diff --git a/src/threads/thread.h b/src/threads/thread.h
 722 index 2c85d88..b9e7b0c 100644
 723 --- a/src/threads/thread.h
 724 +++ b/src/threads/thread.h
 725 @@ -2,10 +2,10 @@
 726  #define THREADS_THREAD_H
 727
 728  #include <debug.h>
 729 +#include <hash.h>
 730  #include <list.h>
 731  #include <stdint.h>
 732  #include "threads/synch.h"
 733 -#include "threads/fixed-point.h"
 734
 735  /* States in a thread's life cycle. */
 736  enum thread_status
 737 @@ -89,19 +89,11 @@ struct thread
 738      enum thread_status status;          /* Thread state. */
 739      char name[16];                      /* Name (for debugging purposes). */
 740      uint8_t *stack;                     /* Saved stack pointer. */
 741 -
 742 -    /* Scheduler data. */
 743 -    int priority;                       /* Priority, including donations. */
 744 -    int normal_priority;                /* Priority, without donations. */
 745 -    struct list donors;                 /* Threads donating priority to us. */
 746 -    struct list_elem donor_elem;        /* Element in donors list. */
 747 -    struct thread *donee;               /* Thread we're donating to. */
 748 -    struct lock *want_lock;             /* Lock we're waiting to acquire. */
 749 -    int nice;                           /* Niceness. */
 750 -    fixed_point_t recent_cpu;           /* Recent amount of CPU time. */
 751 +    int priority;                       /* Priority. */
 752      struct list_elem allelem;           /* List element for all threads list. */
 753
 754      /* Owned by process.c. */
 755 +    int exit_code;                      /* Exit code. */
 756      struct wait_status *wait_status;    /* This process's completion status. */
 757      struct list children;               /* Completion status of children. */
 758
 759 @@ -110,18 +102,19 @@ struct thread
 760
 761      /* Alarm clock. */
 762      int64_t wakeup_time;                /* Time to wake this thread up. */
 763 -    struct list_elem timer_elem;        /* Element in wait_list. */
 764 +    struct list_elem timer_elem;        /* Element in timer_wait_list. */
 765      struct semaphore timer_sema;        /* Semaphore. */
 766 -
 767 -#ifdef USERPROG
 768 +
 769      /* Owned by userprog/process.c. */
 770      uint32_t *pagedir;                  /* Page directory. */
 771 -#endif
 772 -    struct file *bin_file;              /* Executable. */
 773 +    struct hash *pages;                 /* Page table. */
 774 +    struct file *bin_file;              /* The binary executable. */
 775
 776      /* Owned by syscall.c. */
 777      struct list fds;                    /* List of file descriptors. */
 778 +    struct list mappings;               /* Memory-mapped files. */
 779      int next_handle;                    /* Next handle value. */
 780 +    void *user_esp;                     /* User's stack pointer. */
 781
 782      /* Owned by thread.c. */
 783      unsigned magic;                     /* Detects stack overflow. */
 784 @@ -165,10 +158,6 @@ const char *thread_name (void);
 785
 786  void thread_exit (void) NO_RETURN;
 787  void thread_yield (void);
 788 -void thread_yield_to_higher_priority (void);
 789 -void thread_recompute_priority (struct thread *);
 790 -bool thread_lower_priority (const struct list_elem *, const struct list_elem *,
 791 -                            void *aux);
 792
 793  /* Performs some operation on thread t, given auxiliary data AUX. */
 794  typedef void thread_action_func (struct thread *t, void *aux);
 795 diff --git a/src/userprog/exception.c b/src/userprog/exception.c
 796 index 3682478..9cfcf93 100644
 797 --- a/src/userprog/exception.c
 798 +++ b/src/userprog/exception.c
 799 @@ -4,6 +4,7 @@
 800  #include "userprog/gdt.h"
 801  #include "threads/interrupt.h"
 802  #include "threads/thread.h"
 803 +#include "vm/page.h"
 804
 805  /* Number of page faults processed. */
 806  static long long page_fault_cnt;
 807 @@ -148,17 +149,14 @@ page_fault (struct intr_frame *f)
 808    write = (f->error_code & PF_W) != 0;
 809    user = (f->error_code & PF_U) != 0;
 810
 811 -  /* Handle bad dereferences from system call implementations. */
 812 -  if (!user)
 813 +  /* Allow the pager to try to handle it. */
 814 +  if (user && not_present)
 815      {
 816 -      f->eip = (void (*) (void)) f->eax;
 817 -      f->eax = 0;
 818 +      if (!page_in (fault_addr))
 819 +        thread_exit ();
 820        return;
 821      }
 822
 823 -  /* To implement virtual memory, delete the rest of the function
 824 -     body, and replace it with code that brings in the page to
 825 -     which fault_addr refers. */
 826    printf ("Page fault at %p: %s error %s page in %s context.\n",
 827            fault_addr,
 828            not_present ? "not present" : "rights violation",
 829 diff --git a/src/userprog/pagedir.c b/src/userprog/pagedir.c
 830 index a6a87b8..eed41b5 100644
 831 --- a/src/userprog/pagedir.c
 832 +++ b/src/userprog/pagedir.c
 833 @@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd)
 834    ASSERT (pd != init_page_dir);
 835    for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
 836      if (*pde & PTE_P)
 837 -      {
 838 -        uint32_t *pt = pde_get_pt (*pde);
 839 -        uint32_t *pte;
 840 -
 841 -        for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
 842 -          if (*pte & PTE_P)
 843 -            palloc_free_page (pte_get_page (*pte));
 844 -        palloc_free_page (pt);
 845 -      }
 846 +      palloc_free_page (pde_get_pt (*pde));
 847    palloc_free_page (pd);
 848  }
 849
 850 diff --git a/src/userprog/process.c b/src/userprog/process.c
 851 index 06ff27e..7a15814 100644
 852 --- a/src/userprog/process.c
 853 +++ b/src/userprog/process.c
 854 @@ -18,6 +18,8 @@
 855  #include "threads/palloc.h"
 856  #include "threads/thread.h"
 857  #include "threads/vaddr.h"
 858 +#include "vm/page.h"
 859 +#include "vm/frame.h"
 860
 861  static thread_func start_process NO_RETURN;
 862  static bool load (const char *cmd_line, void (**eip) (void), void **esp);
 863 @@ -58,7 +60,7 @@ process_execute (const char *file_name)
 864        sema_down (&exec.load_done);
 865        if (exec.success)
 866          list_push_back (&thread_current ()->children, &exec.wait_status->elem);
 867 -      else
 868 +      else
 869          tid = TID_ERROR;
 870      }
 871
 872 @@ -95,7 +97,6 @@ start_process (void *exec_)
 873        lock_init (&exec->wait_status->lock);
 874        exec->wait_status->ref_cnt = 2;
 875        exec->wait_status->tid = thread_current ()->tid;
 876 -      exec->wait_status->exit_code = -1;
 877        sema_init (&exec->wait_status->dead, 0);
 878      }
 879
 880 @@ -167,14 +168,13 @@ process_exit (void)
 881    struct list_elem *e, *next;
 882    uint32_t *pd;
 883
 884 -  /* Close executable (and allow writes). */
 885 -  file_close (cur->bin_file);
 886 +  printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
 887
 888    /* Notify parent that we're dead. */
 889    if (cur->wait_status != NULL)
 890      {
 891        struct wait_status *cs = cur->wait_status;
 892 -      printf ("%s: exit(%d)\n", cur->name, cs->exit_code);
 893 +      cs->exit_code = cur->exit_code;
 894        sema_up (&cs->dead);
 895        release_child (cs);
 896      }
 897 @@ -187,7 +187,13 @@ process_exit (void)
 898        next = list_remove (e);
 899        release_child (cs);
 900      }
 901 +
 902 +  /* Destroy the page hash table. */
 903 +  page_exit ();
 904
 905 +  /* Close executable (and allow writes). */
 906 +  file_close (cur->bin_file);
 907 +
 908    /* Destroy the current process's page directory and switch back
 909       to the kernel-only page directory. */
 910    pd = cur->pagedir;
 911 @@ -313,6 +319,12 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
 912      goto done;
 913    process_activate ();
 914
 915 +  /* Create page hash table. */
 916 +  t->pages = malloc (sizeof *t->pages);
 917 +  if (t->pages == NULL)
 918 +    goto done;
 919 +  hash_init (t->pages, page_hash, page_less, NULL);
 920 +
 921    /* Extract file_name from command line. */
 922    while (*cmd_line == ' ')
 923      cmd_line++;
 924 @@ -328,7 +340,7 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
 925        printf ("load: %s: open failed\n", file_name);
 926        goto done;
 927      }
 928 -  file_deny_write (file);
 929 +  file_deny_write (t->bin_file);
 930
 931    /* Read and verify executable header. */
 932    if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
 933 @@ -418,8 +430,6 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
 934  \f
 935  /* load() helpers. */
 936
 937 -static bool install_page (void *upage, void *kpage, bool writable);
 938 -
 939  /* Checks whether PHDR describes a valid, loadable segment in
 940     FILE and returns true if so, false otherwise. */
 941  static bool
 942 @@ -487,38 +497,22 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
 943    ASSERT (pg_ofs (upage) == 0);
 944    ASSERT (ofs % PGSIZE == 0);
 945
 946 -  file_seek (file, ofs);
 947    while (read_bytes > 0 || zero_bytes > 0)
 948      {
 949 -      /* Calculate how to fill this page.
 950 -         We will read PAGE_READ_BYTES bytes from FILE
 951 -         and zero the final PAGE_ZERO_BYTES bytes. */
 952        size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
 953        size_t page_zero_bytes = PGSIZE - page_read_bytes;
 954 -
 955 -      /* Get a page of memory. */
 956 -      uint8_t *kpage = palloc_get_page (PAL_USER);
 957 -      if (kpage == NULL)
 958 +      struct page *p = page_allocate (upage, !writable);
 959 +      if (p == NULL)
 960          return false;
 961 -
 962 -      /* Load this page. */
 963 -      if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
 964 -        {
 965 -          palloc_free_page (kpage);
 966 -          return false;
 967 -        }
 968 -      memset (kpage + page_read_bytes, 0, page_zero_bytes);
 969 -
 970 -      /* Add the page to the process's address space. */
 971 -      if (!install_page (upage, kpage, writable))
 972 +      if (page_read_bytes > 0)
 973          {
 974 -          palloc_free_page (kpage);
 975 -          return false;
 976 +          p->file = file;
 977 +          p->file_offset = ofs;
 978 +          p->file_bytes = page_read_bytes;
 979          }
 980 -
 981 -      /* Advance. */
 982        read_bytes -= page_read_bytes;
 983        zero_bytes -= page_zero_bytes;
 984 +      ofs += page_read_bytes;
 985        upage += PGSIZE;
 986      }
 987    return true;
 988 @@ -535,7 +529,7 @@ reverse (int argc, char **argv)
 989        argv[argc - 1] = tmp;
 990      }
 991  }
 992 -
 993 +
 994  /* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
 995     page-relative stack pointer is *OFS, and then adjusts *OFS
 996     appropriately.  The bytes pushed are rounded to a 32-bit
 997 @@ -611,37 +605,19 @@ init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
 998  static bool
 999  setup_stack (const char *cmd_line, void **esp)
1000  {
1001 -  uint8_t *kpage;
1002 -  bool success = false;
1003 -
1004 -  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
1005 -  if (kpage != NULL)
1006 +  struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
1007 +  if (page != NULL)
1008      {
1009 -      uint8_t *upage = ((uint8_t *) PHYS_BASE) - PGSIZE;
1010 -      if (install_page (upage, kpage, true))
1011 -        success = init_cmd_line (kpage, upage, cmd_line, esp);
1012 -      else
1013 -        palloc_free_page (kpage);
1014 +      page->frame = frame_alloc_and_lock (page);
1015 +      if (page->frame != NULL)
1016 +        {
1017 +          bool ok;
1018 +          page->read_only = false;
1019 +          page->private = false;
1020 +          ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
1021 +          frame_unlock (page->frame);
1022 +          return ok;
1023 +        }
1024      }
1025 -  return success;
1026 -}
1027 -
1028 -/* Adds a mapping from user virtual address UPAGE to kernel
1029 -   virtual address KPAGE to the page table.
1030 -   If WRITABLE is true, the user process may modify the page;
1031 -   otherwise, it is read-only.
1032 -   UPAGE must not already be mapped.
1033 -   KPAGE should probably be a page obtained from the user pool
1034 -   with palloc_get_page().
1035 -   Returns true on success, false if UPAGE is already mapped or
1036 -   if memory allocation fails. */
1037 -static bool
1038 -install_page (void *upage, void *kpage, bool writable)
1039 -{
1040 -  struct thread *t = thread_current ();
1041 -
1042 -  /* Verify that there's not already a page at that virtual
1043 -     address, then map our page there. */
1044 -  return (pagedir_get_page (t->pagedir, upage) == NULL
1045 -          && pagedir_set_page (t->pagedir, upage, kpage, writable));
1046 +  return false;
1047  }
1048 diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c
1049 index ef31316..e6be702 100644
1050 --- a/src/userprog/syscall.c
1051 +++ b/src/userprog/syscall.c
1052 @@ -6,6 +6,7 @@
1053  #include "userprog/pagedir.h"
1054  #include "devices/input.h"
1055  #include "devices/shutdown.h"
1056 +#include "filesys/directory.h"
1057  #include "filesys/filesys.h"
1058  #include "filesys/file.h"
1059  #include "threads/interrupt.h"
1060 @@ -13,6 +14,7 @@
1061  #include "threads/palloc.h"
1062  #include "threads/thread.h"
1063  #include "threads/vaddr.h"
1064 +#include "vm/page.h"
1065
1066
1067  static int sys_halt (void);
1068 @@ -28,11 +30,12 @@ static int sys_write (int handle, void *usrc_, unsigned size);
1069  static int sys_seek (int handle, unsigned position);
1070  static int sys_tell (int handle);
1071  static int sys_close (int handle);
1072 +static int sys_mmap (int handle, void *addr);
1073 +static int sys_munmap (int mapping);
1074
1075  static void syscall_handler (struct intr_frame *);
1076  static void copy_in (void *, const void *, size_t);
1077 -
1078 -/* Serializes file system operations. */
1079 +
1080  static struct lock fs_lock;
1081
1082  void
1083 @@ -71,6 +74,8 @@ syscall_handler (struct intr_frame *f)
1084        {2, (syscall_function *) sys_seek},
1085        {1, (syscall_function *) sys_tell},
1086        {1, (syscall_function *) sys_close},
1087 +      {2, (syscall_function *) sys_mmap},
1088 +      {1, (syscall_function *) sys_munmap},
1089      };
1090
1091    const struct syscall *sc;
1092 @@ -93,39 +98,6 @@ syscall_handler (struct intr_frame *f)
1093    f->eax = sc->func (args[0], args[1], args[2]);
1094  }
1095
1096 -/* Returns true if UADDR is a valid, mapped user address,
1097 -   false otherwise. */
1098 -static bool
1099 -verify_user (const void *uaddr)
1100 -{
1101 -  return (uaddr < PHYS_BASE
1102 -          && pagedir_get_page (thread_current ()->pagedir, uaddr) != NULL);
1103 -}
1104 -
1105 -/* Copies a byte from user address USRC to kernel address DST.
1106 -   USRC must be below PHYS_BASE.
1107 -   Returns true if successful, false if a segfault occurred. */
1108 -static inline bool
1109 -get_user (uint8_t *dst, const uint8_t *usrc)
1110 -{
1111 -  int eax;
1112 -  asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
1113 -       : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
1114 -  return eax != 0;
1115 -}
1116 -
1117 -/* Writes BYTE to user address UDST.
1118 -   UDST must be below PHYS_BASE.
1119 -   Returns true if successful, false if a segfault occurred. */
1120 -static inline bool
1121 -put_user (uint8_t *udst, uint8_t byte)
1122 -{
1123 -  int eax;
1124 -  asm ("movl $1f, %%eax; movb %b2, %0; 1:"
1125 -       : "=m" (*udst), "=&a" (eax) : "q" (byte));
1126 -  return eax != 0;
1127 -}
1128 -
1129  /* Copies SIZE bytes from user address USRC to kernel address
1130     DST.
1131     Call thread_exit() if any of the user accesses are invalid. */
1132 @@ -134,10 +106,22 @@ copy_in (void *dst_, const void *usrc_, size_t size)
1133  {
1134    uint8_t *dst = dst_;
1135    const uint8_t *usrc = usrc_;
1136 -
1137 -  for (; size > 0; size--, dst++, usrc++)
1138 -    if (usrc >= (uint8_t *) PHYS_BASE || !get_user (dst, usrc))
1139 -      thread_exit ();
1140 +
1141 +  while (size > 0)
1142 +    {
1143 +      size_t chunk_size = PGSIZE - pg_ofs (usrc);
1144 +      if (chunk_size > size)
1145 +        chunk_size = size;
1146 +
1147 +      if (!page_lock (usrc, false))
1148 +        thread_exit ();
1149 +      memcpy (dst, usrc, chunk_size);
1150 +      page_unlock (usrc);
1151 +
1152 +      dst += chunk_size;
1153 +      usrc += chunk_size;
1154 +      size -= chunk_size;
1155 +    }
1156  }
1157
1158  /* Creates a copy of user string US in kernel memory
1159 @@ -149,25 +133,40 @@ static char *
1160  copy_in_string (const char *us)
1161  {
1162    char *ks;
1163 +  char *upage;
1164    size_t length;
1165
1166    ks = palloc_get_page (0);
1167    if (ks == NULL)
1168      thread_exit ();
1169 -
1170 -  for (length = 0; length < PGSIZE; length++)
1171 +
1172 +  length = 0;
1173 +  for (;;)
1174      {
1175 -      if (us >= (char *) PHYS_BASE || !get_user (ks + length, us++))
1176 +      upage = pg_round_down (us);
1177 +      if (!page_lock (upage, false))
1178 +        goto lock_error;
1179 +
1180 +      for (; us < upage + PGSIZE; us++)
1181          {
1182 -          palloc_free_page (ks);
1183 -          thread_exit ();
1184 +          ks[length++] = *us;
1185 +          if (*us == '\0')
1186 +            {
1187 +              page_unlock (upage);
1188 +              return ks;
1189 +            }
1190 +          else if (length >= PGSIZE)
1191 +            goto too_long_error;
1192          }
1193 -
1194 -      if (ks[length] == '\0')
1195 -        return ks;
1196 +
1197 +      page_unlock (upage);
1198      }
1199 -  ks[PGSIZE - 1] = '\0';
1200 -  return ks;
1201 +
1202 + too_long_error:
1203 +  page_unlock (upage);
1204 + lock_error:
1205 +  palloc_free_page (ks);
1206 +  thread_exit ();
1207  }
1208
1209  /* Halt system call. */
1210 @@ -181,7 +180,7 @@ sys_halt (void)
1211  static int
1212  sys_exit (int exit_code)
1213  {
1214 -  thread_current ()->wait_status->exit_code = exit_code;
1215 +  thread_current ()->exit_code = exit_code;
1216    thread_exit ();
1217    NOT_REACHED ();
1218  }
1219 @@ -192,7 +191,7 @@ sys_exec (const char *ufile)
1220  {
1221    tid_t tid;
1222    char *kfile = copy_in_string (ufile);
1223 -
1224 +
1225    lock_acquire (&fs_lock);
1226    tid = process_execute (kfile);
1227    lock_release (&fs_lock);
1228 @@ -215,11 +214,11 @@ sys_create (const char *ufile, unsigned initial_size)
1229  {
1230    char *kfile = copy_in_string (ufile);
1231    bool ok;
1232 -
1233 +
1234    lock_acquire (&fs_lock);
1235    ok = filesys_create (kfile, initial_size);
1236    lock_release (&fs_lock);
1237 -
1238 +
1239    palloc_free_page (kfile);
1240
1241    return ok;
1242 @@ -231,16 +230,16 @@ sys_remove (const char *ufile)
1243  {
1244    char *kfile = copy_in_string (ufile);
1245    bool ok;
1246 -
1247 +
1248    lock_acquire (&fs_lock);
1249    ok = filesys_remove (kfile);
1250    lock_release (&fs_lock);
1251 -
1252 +
1253    palloc_free_page (kfile);
1254
1255    return ok;
1256  }
1257 -
1258 +\f
1259  /* A file descriptor, for binding a file handle to a file. */
1260  struct file_descriptor
1261    {
1262 @@ -320,18 +319,7 @@ sys_read (int handle, void *udst_, unsigned size)
1263    struct file_descriptor *fd;
1264    int bytes_read = 0;
1265
1266 -  /* Handle keyboard reads. */
1267 -  if (handle == STDIN_FILENO)
1268 -    {
1269 -      for (bytes_read = 0; (size_t) bytes_read < size; bytes_read++)
1270 -        if (udst >= (uint8_t *) PHYS_BASE || !put_user (udst++, input_getc ()))
1271 -          thread_exit ();
1272 -      return bytes_read;
1273 -    }
1274 -
1275 -  /* Handle all other reads. */
1276    fd = lookup_fd (handle);
1277 -  lock_acquire (&fs_lock);
1278    while (size > 0)
1279      {
1280        /* How much to read into this page? */
1281 @@ -339,32 +327,49 @@ sys_read (int handle, void *udst_, unsigned size)
1282        size_t read_amt = size < page_left ? size : page_left;
1283        off_t retval;
1284
1285 -      /* Check that touching this page is okay. */
1286 -      if (!verify_user (udst))
1287 +      /* Read from file into page. */
1288 +      if (handle != STDIN_FILENO)
1289          {
1290 +          if (!page_lock (udst, true))
1291 +            thread_exit ();
1292 +          lock_acquire (&fs_lock);
1293 +          retval = file_read (fd->file, udst, read_amt);
1294            lock_release (&fs_lock);
1295 -          thread_exit ();
1296 +          page_unlock (udst);
1297          }
1298 -
1299 -      /* Read from file into page. */
1300 -      retval = file_read (fd->file, udst, read_amt);
1301 +      else
1302 +        {
1303 +          size_t i;
1304 +
1305 +          for (i = 0; i < read_amt; i++)
1306 +            {
1307 +              char c = input_getc ();
1308 +              if (!page_lock (udst, true))
1309 +                thread_exit ();
1310 +              udst[i] = c;
1311 +              page_unlock (udst);
1312 +            }
1313 +          bytes_read = read_amt;
1314 +        }
1315 +
1316 +      /* Check success. */
1317        if (retval < 0)
1318          {
1319            if (bytes_read == 0)
1320              bytes_read = -1;
1321            break;
1322          }
1323 -      bytes_read += retval;
1324 -
1325 -      /* If it was a short read we're done. */
1326 -      if (retval != (off_t) read_amt)
1327 -        break;
1328 +      bytes_read += retval;
1329 +      if (retval != (off_t) read_amt)
1330 +        {
1331 +          /* Short read, so we're done. */
1332 +          break;
1333 +        }
1334
1335        /* Advance. */
1336        udst += retval;
1337        size -= retval;
1338      }
1339 -  lock_release (&fs_lock);
1340
1341    return bytes_read;
1342  }
1343 @@ -381,7 +386,6 @@ sys_write (int handle, void *usrc_, unsigned size)
1344    if (handle != STDOUT_FILENO)
1345      fd = lookup_fd (handle);
1346
1347 -  lock_acquire (&fs_lock);
1348    while (size > 0)
1349      {
1350        /* How much bytes to write to this page? */
1351 @@ -389,21 +393,21 @@ sys_write (int handle, void *usrc_, unsigned size)
1352        size_t write_amt = size < page_left ? size : page_left;
1353        off_t retval;
1354
1355 -      /* Check that we can touch this user page. */
1356 -      if (!verify_user (usrc))
1357 -        {
1358 -          lock_release (&fs_lock);
1359 -          thread_exit ();
1360 -        }
1361 -
1362 -      /* Do the write. */
1363 +      /* Write from page into file. */
1364 +      if (!page_lock (usrc, false))
1365 +        thread_exit ();
1366 +      lock_acquire (&fs_lock);
1367        if (handle == STDOUT_FILENO)
1368          {
1369 -          putbuf (usrc, write_amt);
1370 +          putbuf ((char *) usrc, write_amt);
1371            retval = write_amt;
1372          }
1373        else
1374          retval = file_write (fd->file, usrc, write_amt);
1375 +      lock_release (&fs_lock);
1376 +      page_unlock (usrc);
1377 +
1378 +      /* Handle return value. */
1379        if (retval < 0)
1380          {
1381            if (bytes_written == 0)
1382 @@ -420,7 +424,6 @@ sys_write (int handle, void *usrc_, unsigned size)
1383        usrc += retval;
1384        size -= retval;
1385      }
1386 -  lock_release (&fs_lock);
1387
1388    return bytes_written;
1389  }
1390 @@ -435,7 +438,7 @@ sys_seek (int handle, unsigned position)
1391    if ((off_t) position >= 0)
1392      file_seek (fd->file, position);
1393    lock_release (&fs_lock);
1394 -
1395 +
1396    return 0;
1397  }
1398
1399 @@ -449,7 +452,7 @@ sys_tell (int handle)
1400    lock_acquire (&fs_lock);
1401    position = file_tell (fd->file);
1402    lock_release (&fs_lock);
1403 -
1404 +
1405    return position;
1406  }
1407
1408 @@ -465,8 +468,110 @@ sys_close (int handle)
1409    free (fd);
1410    return 0;
1411  }
1412 +\f
1413 +/* Binds a mapping id to a region of memory and a file. */
1414 +struct mapping
1415 +  {
1416 +    struct list_elem elem;      /* List element. */
1417 +    int handle;                 /* Mapping id. */
1418 +    struct file *file;          /* File. */
1419 +    uint8_t *base;              /* Start of memory mapping. */
1420 +    size_t page_cnt;            /* Number of pages mapped. */
1421 +  };
1422 +
1423 +/* Returns the file descriptor associated with the given handle.
1424 +   Terminates the process if HANDLE is not associated with a
1425 +   memory mapping. */
1426 +static struct mapping *
1427 +lookup_mapping (int handle)
1428 +{
1429 +  struct thread *cur = thread_current ();
1430 +  struct list_elem *e;
1431 +
1432 +  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1433 +       e = list_next (e))
1434 +    {
1435 +      struct mapping *m = list_entry (e, struct mapping, elem);
1436 +      if (m->handle == handle)
1437 +        return m;
1438 +    }
1439 +
1440 +  thread_exit ();
1441 +}
1442 +
1443 +/* Remove mapping M from the virtual address space,
1444 +   writing back any pages that have changed. */
1445 +static void
1446 +unmap (struct mapping *m)
1447 +{
1448 +  list_remove (&m->elem);
1449 +  while (m->page_cnt-- > 0)
1450 +    {
1451 +      page_deallocate (m->base);
1452 +      m->base += PGSIZE;
1453 +    }
1454 +  file_close (m->file);
1455 +  free (m);
1456 +}
1457
1458 -/* On thread exit, close all open files. */
1459 +/* Mmap system call. */
1460 +static int
1461 +sys_mmap (int handle, void *addr)
1462 +{
1463 +  struct file_descriptor *fd = lookup_fd (handle);
1464 +  struct mapping *m = malloc (sizeof *m);
1465 +  size_t offset;
1466 +  off_t length;
1467 +
1468 +  if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
1469 +    return -1;
1470 +
1471 +  m->handle = thread_current ()->next_handle++;
1472 +  lock_acquire (&fs_lock);
1473 +  m->file = file_reopen (fd->file);
1474 +  lock_release (&fs_lock);
1475 +  if (m->file == NULL)
1476 +    {
1477 +      free (m);
1478 +      return -1;
1479 +    }
1480 +  m->base = addr;
1481 +  m->page_cnt = 0;
1482 +  list_push_front (&thread_current ()->mappings, &m->elem);
1483 +
1484 +  offset = 0;
1485 +  lock_acquire (&fs_lock);
1486 +  length = file_length (m->file);
1487 +  lock_release (&fs_lock);
1488 +  while (length > 0)
1489 +    {
1490 +      struct page *p = page_allocate ((uint8_t *) addr + offset, false);
1491 +      if (p == NULL)
1492 +        {
1493 +          unmap (m);
1494 +          return -1;
1495 +        }
1496 +      p->private = false;
1497 +      p->file = m->file;
1498 +      p->file_offset = offset;
1499 +      p->file_bytes = length >= PGSIZE ? PGSIZE : length;
1500 +      offset += p->file_bytes;
1501 +      length -= p->file_bytes;
1502 +      m->page_cnt++;
1503 +    }
1504 +
1505 +  return m->handle;
1506 +}
1507 +
1508 +/* Munmap system call. */
1509 +static int
1510 +sys_munmap (int mapping)
1511 +{
1512 +  unmap (lookup_mapping (mapping));
1513 +  return 0;
1514 +}
1515 +\f
1516 +/* On thread exit, close all open files and unmap all mappings. */
1517  void
1518  syscall_exit (void)
1519  {
1520 @@ -475,12 +580,19 @@ syscall_exit (void)
1521
1522    for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
1523      {
1524 -      struct file_descriptor *fd;
1525 -      fd = list_entry (e, struct file_descriptor, elem);
1526 +      struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
1527        next = list_next (e);
1528        lock_acquire (&fs_lock);
1529        file_close (fd->file);
1530        lock_release (&fs_lock);
1531        free (fd);
1532      }
1533 +
1534 +  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
1535 +       e = next)
1536 +    {
1537 +      struct mapping *m = list_entry (e, struct mapping, elem);
1538 +      next = list_next (e);
1539 +      unmap (m);
1540 +    }
1541  }
1542 diff --git a/src/vm/frame.c b/src/vm/frame.c
1543 new file mode 100644
1544 index 0000000..ef55376
1545 --- /dev/null
1546 +++ b/src/vm/frame.c
1547 @@ -0,0 +1,162 @@
1548 +#include "vm/frame.h"
1549 +#include <stdio.h>
1550 +#include "vm/page.h"
1551 +#include "devices/timer.h"
1552 +#include "threads/init.h"
1553 +#include "threads/malloc.h"
1554 +#include "threads/palloc.h"
1555 +#include "threads/synch.h"
1556 +#include "threads/vaddr.h"
1557 +
1558 +static struct frame *frames;
1559 +static size_t frame_cnt;
1560 +
1561 +static struct lock scan_lock;
1562 +static size_t hand;
1563 +
1564 +/* Initialize the frame manager. */
1565 +void
1566 +frame_init (void)
1567 +{
1568 +  void *base;
1569 +
1570 +  lock_init (&scan_lock);
1571 +
1572 +  frames = malloc (sizeof *frames * init_ram_pages);
1573 +  if (frames == NULL)
1574 +    PANIC ("out of memory allocating page frames");
1575 +
1576 +  while ((base = palloc_get_page (PAL_USER)) != NULL)
1577 +    {
1578 +      struct frame *f = &frames[frame_cnt++];
1579 +      lock_init (&f->lock);
1580 +      f->base = base;
1581 +      f->page = NULL;
1582 +    }
1583 +}
1584 +
1585 +/* Tries to allocate and lock a frame for PAGE.
1586 +   Returns the frame if successful, false on failure. */
1587 +static struct frame *
1588 +try_frame_alloc_and_lock (struct page *page)
1589 +{
1590 +  size_t i;
1591 +
1592 +  lock_acquire (&scan_lock);
1593 +
1594 +  /* Find a free frame. */
1595 +  for (i = 0; i < frame_cnt; i++)
1596 +    {
1597 +      struct frame *f = &frames[i];
1598 +      if (!lock_try_acquire (&f->lock))
1599 +        continue;
1600 +      if (f->page == NULL)
1601 +        {
1602 +          f->page = page;
1603 +          lock_release (&scan_lock);
1604 +          return f;
1605 +        }
1606 +      lock_release (&f->lock);
1607 +    }
1608 +
1609 +  /* No free frame.  Find a frame to evict. */
1610 +  for (i = 0; i < frame_cnt * 2; i++)
1611 +    {
1612 +      /* Get a frame. */
1613 +      struct frame *f = &frames[hand];
1614 +      if (++hand >= frame_cnt)
1615 +        hand = 0;
1616 +
1617 +      if (!lock_try_acquire (&f->lock))
1618 +        continue;
1619 +
1620 +      if (f->page == NULL)
1621 +        {
1622 +          f->page = page;
1623 +          lock_release (&scan_lock);
1624 +          return f;
1625 +        }
1626 +
1627 +      if (page_accessed_recently (f->page))
1628 +        {
1629 +          lock_release (&f->lock);
1630 +          continue;
1631 +        }
1632 +
1633 +      lock_release (&scan_lock);
1634 +
1635 +      /* Evict this frame. */
1636 +      if (!page_out (f->page))
1637 +        {
1638 +          lock_release (&f->lock);
1639 +          return NULL;
1640 +        }
1641 +
1642 +      f->page = page;
1643 +      return f;
1644 +    }
1645 +
1646 +  lock_release (&scan_lock);
1647 +  return NULL;
1648 +}
1649 +
1650 +
1651 +/* Tries really hard to allocate and lock a frame for PAGE.
1652 +   Returns the frame if successful, false on failure. */
1653 +struct frame *
1654 +frame_alloc_and_lock (struct page *page)
1655 +{
1656 +  size_t try;
1657 +
1658 +  for (try = 0; try < 3; try++)
1659 +    {
1660 +      struct frame *f = try_frame_alloc_and_lock (page);
1661 +      if (f != NULL)
1662 +        {
1663 +          ASSERT (lock_held_by_current_thread (&f->lock));
1664 +          return f;
1665 +        }
1666 +      timer_msleep (1000);
1667 +    }
1668 +
1669 +  return NULL;
1670 +}
1671 +
1672 +/* Locks P's frame into memory, if it has one.
1673 +   Upon return, p->frame will not change until P is unlocked. */
1674 +void
1675 +frame_lock (struct page *p)
1676 +{
1677 +  /* A frame can be asynchronously removed, but never inserted. */
1678 +  struct frame *f = p->frame;
1679 +  if (f != NULL)
1680 +    {
1681 +      lock_acquire (&f->lock);
1682 +      if (f != p->frame)
1683 +        {
1684 +          lock_release (&f->lock);
1685 +          ASSERT (p->frame == NULL);
1686 +        }
1687 +    }
1688 +}
1689 +
1690 +/* Releases frame F for use by another page.
1691 +   F must be locked for use by the current process.
1692 +   Any data in F is lost. */
1693 +void
1694 +frame_free (struct frame *f)
1695 +{
1696 +  ASSERT (lock_held_by_current_thread (&f->lock));
1697 +
1698 +  f->page = NULL;
1699 +  lock_release (&f->lock);
1700 +}
1701 +
1702 +/* Unlocks frame F, allowing it to be evicted.
1703 +   F must be locked for use by the current process. */
1704 +void
1705 +frame_unlock (struct frame *f)
1706 +{
1707 +  ASSERT (lock_held_by_current_thread (&f->lock));
1708 +  lock_release (&f->lock);
1709 +}
1710 diff --git a/src/vm/frame.h b/src/vm/frame.h
1711 new file mode 100644
1712 index 0000000..496f623
1713 --- /dev/null
1714 +++ b/src/vm/frame.h
1715 @@ -0,0 +1,23 @@
1716 +#ifndef VM_FRAME_H
1717 +#define VM_FRAME_H
1718 +
1719 +#include <stdbool.h>
1720 +#include "threads/synch.h"
1721 +
1722 +/* A physical frame. */
1723 +struct frame
1724 +  {
1725 +    struct lock lock;           /* Prevent simultaneous access. */
1726 +    void *base;                 /* Kernel virtual base address. */
1727 +    struct page *page;          /* Mapped process page, if any. */
1728 +  };
1729 +
1730 +void frame_init (void);
1731 +
1732 +struct frame *frame_alloc_and_lock (struct page *);
1733 +void frame_lock (struct page *);
1734 +
1735 +void frame_free (struct frame *);
1736 +void frame_unlock (struct frame *);
1737 +
1738 +#endif /* vm/frame.h */
1739 diff --git a/src/vm/page.c b/src/vm/page.c
1740 new file mode 100644
1741 index 0000000..f08bcf8
1742 --- /dev/null
1743 +++ b/src/vm/page.c
1744 @@ -0,0 +1,293 @@
1745 +#include "vm/page.h"
1746 +#include <stdio.h>
1747 +#include <string.h>
1748 +#include "vm/frame.h"
1749 +#include "vm/swap.h"
1750 +#include "filesys/file.h"
1751 +#include "threads/malloc.h"
1752 +#include "threads/thread.h"
1753 +#include "userprog/pagedir.h"
1754 +#include "threads/vaddr.h"
1755 +
1756 +/* Maximum size of process stack, in bytes. */
1757 +#define STACK_MAX (1024 * 1024)
1758 +
1759 +/* Destroys a page, which must be in the current process's
1760 +   page table.  Used as a callback for hash_destroy(). */
1761 +static void
1762 +destroy_page (struct hash_elem *p_, void *aux UNUSED)
1763 +{
1764 +  struct page *p = hash_entry (p_, struct page, hash_elem);
1765 +  frame_lock (p);
1766 +  if (p->frame)
1767 +    frame_free (p->frame);
1768 +  free (p);
1769 +}
1770 +
1771 +/* Destroys the current process's page table. */
1772 +void
1773 +page_exit (void)
1774 +{
1775 +  struct hash *h = thread_current ()->pages;
1776 +  if (h != NULL)
1777 +    hash_destroy (h, destroy_page);
1778 +}
1779 +
1780 +/* Returns the page containing the given virtual ADDRESS,
1781 +   or a null pointer if no such page exists.
1782 +   Allocates stack pages as necessary. */
1783 +static struct page *
1784 +page_for_addr (const void *address)
1785 +{
1786 +  if (address < PHYS_BASE)
1787 +    {
1788 +      struct page p;
1789 +      struct hash_elem *e;
1790 +
1791 +      /* Find existing page. */
1792 +      p.addr = (void *) pg_round_down (address);
1793 +      e = hash_find (thread_current ()->pages, &p.hash_elem);
1794 +      if (e != NULL)
1795 +        return hash_entry (e, struct page, hash_elem);
1796 +
1797 +      /* No page.  Expand stack? */
1798 +      if (address >= PHYS_BASE - STACK_MAX
1799 +          && address >= thread_current ()->user_esp - 32)
1800 +        return page_allocate ((void *) address, false);
1801 +    }
1802 +  return NULL;
1803 +}
1804 +
1805 +/* Locks a frame for page P and pages it in.
1806 +   Returns true if successful, false on failure. */
1807 +static bool
1808 +do_page_in (struct page *p)
1809 +{
1810 +  /* Get a frame for the page. */
1811 +  p->frame = frame_alloc_and_lock (p);
1812 +  if (p->frame == NULL)
1813 +    return false;
1814 +
1815 +  /* Copy data into the frame. */
1816 +  if (p->sector != (block_sector_t) -1)
1817 +    {
1818 +      /* Get data from swap. */
1819 +      swap_in (p);
1820 +    }
1821 +  else if (p->file != NULL)
1822 +    {
1823 +      /* Get data from file. */
1824 +      off_t read_bytes = file_read_at (p->file, p->frame->base,
1825 +                                        p->file_bytes, p->file_offset);
1826 +      off_t zero_bytes = PGSIZE - read_bytes;
1827 +      memset (p->frame->base + read_bytes, 0, zero_bytes);
1828 +      if (read_bytes != p->file_bytes)
1829 +        printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
1830 +                read_bytes, p->file_bytes);
1831 +    }
1832 +  else
1833 +    {
1834 +      /* Provide all-zero page. */
1835 +      memset (p->frame->base, 0, PGSIZE);
1836 +    }
1837 +
1838 +  return true;
1839 +}
1840 +
1841 +/* Faults in the page containing FAULT_ADDR.
1842 +   Returns true if successful, false on failure. */
1843 +bool
1844 +page_in (void *fault_addr)
1845 +{
1846 +  struct page *p;
1847 +  bool success;
1848 +
1849 +  /* Can't handle page faults without a hash table. */
1850 +  if (thread_current ()->pages == NULL)
1851 +    return false;
1852 +
1853 +  p = page_for_addr (fault_addr);
1854 +  if (p == NULL)
1855 +    return false;
1856 +
1857 +  frame_lock (p);
1858 +  if (p->frame == NULL)
1859 +    {
1860 +      if (!do_page_in (p))
1861 +        return false;
1862 +    }
1863 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
1864 +
1865 +  /* Install frame into page table. */
1866 +  success = pagedir_set_page (thread_current ()->pagedir, p->addr,
1867 +                              p->frame->base, !p->read_only);
1868 +
1869 +  /* Release frame. */
1870 +  frame_unlock (p->frame);
1871 +
1872 +  return success;
1873 +}
1874 +
1875 +/* Evicts page P.
1876 +   P must have a locked frame.
1877 +   Return true if successful, false on failure. */
1878 +bool
1879 +page_out (struct page *p)
1880 +{
1881 +  bool dirty;
1882 +  bool ok;
1883 +
1884 +  ASSERT (p->frame != NULL);
1885 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
1886 +
1887 +  /* Mark page not present in page table, forcing accesses by the
1888 +     process to fault.  This must happen before checking the
1889 +     dirty bit, to prevent a race with the process dirtying the
1890 +     page. */
1891 +  pagedir_clear_page (p->thread->pagedir, p->addr);
1892 +
1893 +  /* Has the frame been modified? */
1894 +  dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
1895 +
1896 +  /* Write frame contents to disk if necessary. */
1897 +  if (p->file != NULL)
1898 +    {
1899 +      if (dirty)
1900 +        {
1901 +          if (p->private)
1902 +            ok = swap_out (p);
1903 +          else
1904 +            ok = file_write_at (p->file, p->frame->base, p->file_bytes,
1905 +                                p->file_offset) == p->file_bytes;
1906 +        }
1907 +      else
1908 +        ok = true;
1909 +    }
1910 +  else
1911 +    ok = swap_out (p);
1912 +  if (ok)
1913 +    {
1914 +      //memset (p->frame->base, 0xcc, PGSIZE);
1915 +      p->frame = NULL;
1916 +    }
1917 +  return ok;
1918 +}
1919 +
1920 +/* Returns true if page P's data has been accessed recently,
1921 +   false otherwise.
1922 +   P must have a frame locked into memory. */
1923 +bool
1924 +page_accessed_recently (struct page *p)
1925 +{
1926 +  bool was_accessed;
1927 +
1928 +  ASSERT (p->frame != NULL);
1929 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
1930 +
1931 +  was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
1932 +  if (was_accessed)
1933 +    pagedir_set_accessed (p->thread->pagedir, p->addr, false);
1934 +  return was_accessed;
1935 +}
1936 +
1937 +/* Adds a mapping for user virtual address VADDR to the page hash
1938 +   table.  Fails if VADDR is already mapped or if memory
1939 +   allocation fails. */
1940 +struct page *
1941 +page_allocate (void *vaddr, bool read_only)
1942 +{
1943 +  struct thread *t = thread_current ();
1944 +  struct page *p = malloc (sizeof *p);
1945 +  if (p != NULL)
1946 +    {
1947 +      p->addr = pg_round_down (vaddr);
1948 +
1949 +      p->read_only = read_only;
1950 +      p->private = !read_only;
1951 +
1952 +      p->frame = NULL;
1953 +
1954 +      p->sector = (block_sector_t) -1;
1955 +
1956 +      p->file = NULL;
1957 +      p->file_offset = 0;
1958 +      p->file_bytes = 0;
1959 +
1960 +      p->thread = thread_current ();
1961 +
1962 +      if (hash_insert (t->pages, &p->hash_elem) != NULL)
1963 +        {
1964 +          /* Already mapped. */
1965 +          free (p);
1966 +          p = NULL;
1967 +        }
1968 +    }
1969 +  return p;
1970 +}
1971 +
1972 +/* Evicts the page containing address VADDR
1973 +   and removes it from the page table. */
1974 +void
1975 +page_deallocate (void *vaddr)
1976 +{
1977 +  struct page *p = page_for_addr (vaddr);
1978 +  ASSERT (p != NULL);
1979 +  frame_lock (p);
1980 +  if (p->frame)
1981 +    {
1982 +      struct frame *f = p->frame;
1983 +      if (p->file && !p->private)
1984 +        page_out (p);
1985 +      frame_free (f);
1986 +    }
1987 +  hash_delete (thread_current ()->pages, &p->hash_elem);
1988 +  free (p);
1989 +}
1990 +
1991 +/* Returns a hash value for the page that E refers to. */
1992 +unsigned
1993 +page_hash (const struct hash_elem *e, void *aux UNUSED)
1994 +{
1995 +  const struct page *p = hash_entry (e, struct page, hash_elem);
1996 +  return ((uintptr_t) p->addr) >> PGBITS;
1997 +}
1998 +
1999 +/* Returns true if page A precedes page B. */
2000 +bool
2001 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
2002 +           void *aux UNUSED)
2003 +{
2004 +  const struct page *a = hash_entry (a_, struct page, hash_elem);
2005 +  const struct page *b = hash_entry (b_, struct page, hash_elem);
2006 +
2007 +  return a->addr < b->addr;
2008 +}
2009 +
2010 +/* Tries to lock the page containing ADDR into physical memory.
2011 +   If WILL_WRITE is true, the page must be writeable;
2012 +   otherwise it may be read-only.
2013 +   Returns true if successful, false on failure. */
2014 +bool
2015 +page_lock (const void *addr, bool will_write)
2016 +{
2017 +  struct page *p = page_for_addr (addr);
2018 +  if (p == NULL || (p->read_only && will_write))
2019 +    return false;
2020 +
2021 +  frame_lock (p);
2022 +  if (p->frame == NULL)
2023 +    return (do_page_in (p)
2024 +            && pagedir_set_page (thread_current ()->pagedir, p->addr,
2025 +                                 p->frame->base, !p->read_only));
2026 +  else
2027 +    return true;
2028 +}
2029 +
2030 +/* Unlocks a page locked with page_lock(). */
2031 +void
2032 +page_unlock (const void *addr)
2033 +{
2034 +  struct page *p = page_for_addr (addr);
2035 +  ASSERT (p != NULL);
2036 +  frame_unlock (p->frame);
2037 +}
2038 diff --git a/src/vm/page.h b/src/vm/page.h
2039 new file mode 100644
2040 index 0000000..b71b9da
2041 --- /dev/null
2042 +++ b/src/vm/page.h
2043 @@ -0,0 +1,50 @@
2044 +#ifndef VM_PAGE_H
2045 +#define VM_PAGE_H
2046 +
2047 +#include <hash.h>
2048 +#include "devices/block.h"
2049 +#include "filesys/off_t.h"
2050 +#include "threads/synch.h"
2051 +
2052 +/* Virtual page. */
2053 +struct page
2054 +  {
2055 +    /* Immutable members. */
2056 +    void *addr;                 /* User virtual address. */
2057 +    bool read_only;             /* Read-only page? */
2058 +    struct thread *thread;      /* Owning thread. */
2059 +
2060 +    /* Accessed only in owning process context. */
2061 +    struct hash_elem hash_elem; /* struct thread `pages' hash element. */
2062 +
2063 +    /* Set only in owning process context with frame->frame_lock held.
2064 +       Cleared only with scan_lock and frame->frame_lock held. */
2065 +    struct frame *frame;        /* Page frame. */
2066 +
2067 +    /* Swap information, protected by frame->frame_lock. */
2068 +    block_sector_t sector;       /* Starting sector of swap area, or -1. */
2069 +
2070 +    /* Memory-mapped file information, protected by frame->frame_lock. */
2071 +    bool private;               /* False to write back to file,
2072 +                                   true to write back to swap. */
2073 +    struct file *file;          /* File. */
2074 +    off_t file_offset;          /* Offset in file. */
2075 +    off_t file_bytes;           /* Bytes to read/write, 1...PGSIZE. */
2076 +  };
2077 +
2078 +void page_exit (void);
2079 +
2080 +struct page *page_allocate (void *, bool read_only);
2081 +void page_deallocate (void *vaddr);
2082 +
2083 +bool page_in (void *fault_addr);
2084 +bool page_out (struct page *);
2085 +bool page_accessed_recently (struct page *);
2086 +
2087 +bool page_lock (const void *, bool will_write);
2088 +void page_unlock (const void *);
2089 +
2090 +hash_hash_func page_hash;
2091 +hash_less_func page_less;
2092 +
2093 +#endif /* vm/page.h */
2094 diff --git a/src/vm/swap.c b/src/vm/swap.c
2095 new file mode 100644
2096 index 0000000..76fcf71
2097 --- /dev/null
2098 +++ b/src/vm/swap.c
2099 @@ -0,0 +1,85 @@
2100 +#include "vm/swap.h"
2101 +#include <bitmap.h>
2102 +#include <debug.h>
2103 +#include <stdio.h>
2104 +#include "vm/frame.h"
2105 +#include "vm/page.h"
2106 +#include "threads/synch.h"
2107 +#include "threads/vaddr.h"
2108 +
2109 +/* The swap device. */
2110 +static struct block *swap_device;
2111 +
2112 +/* Used swap pages. */
2113 +static struct bitmap *swap_bitmap;
2114 +
2115 +/* Protects swap_bitmap. */
2116 +static struct lock swap_lock;
2117 +
2118 +/* Number of sectors per page. */
2119 +#define PAGE_SECTORS (PGSIZE / BLOCK_SECTOR_SIZE)
2120 +
2121 +/* Sets up swap. */
2122 +void
2123 +swap_init (void)
2124 +{
2125 +  swap_device = block_get_role (BLOCK_SWAP);
2126 +  if (swap_device == NULL)
2127 +    {
2128 +      printf ("no swap device--swap disabled\n");
2129 +      swap_bitmap = bitmap_create (0);
2130 +    }
2131 +  else
2132 +    swap_bitmap = bitmap_create (block_size (swap_device)
2133 +                                 / PAGE_SECTORS);
2134 +  if (swap_bitmap == NULL)
2135 +    PANIC ("couldn't create swap bitmap");
2136 +  lock_init (&swap_lock);
2137 +}
2138 +
2139 +/* Swaps in page P, which must have a locked frame
2140 +   (and be swapped out). */
2141 +void
2142 +swap_in (struct page *p)
2143 +{
2144 +  size_t i;
2145 +
2146 +  ASSERT (p->frame != NULL);
2147 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
2148 +  ASSERT (p->sector != (block_sector_t) -1);
2149 +
2150 +  for (i = 0; i < PAGE_SECTORS; i++)
2151 +    block_read (swap_device, p->sector + i,
2152 +                p->frame->base + i * BLOCK_SECTOR_SIZE);
2153 +  bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
2154 +  p->sector = (block_sector_t) -1;
2155 +}
2156 +
2157 +/* Swaps out page P, which must have a locked frame. */
2158 +bool
2159 +swap_out (struct page *p)
2160 +{
2161 +  size_t slot;
2162 +  size_t i;
2163 +
2164 +  ASSERT (p->frame != NULL);
2165 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
2166 +
2167 +  lock_acquire (&swap_lock);
2168 +  slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
2169 +  lock_release (&swap_lock);
2170 +  if (slot == BITMAP_ERROR)
2171 +    return false;
2172 +
2173 +  p->sector = slot * PAGE_SECTORS;
2174 +  for (i = 0; i < PAGE_SECTORS; i++)
2175 +    block_write (swap_device, p->sector + i,
2176 +                 p->frame->base + i * BLOCK_SECTOR_SIZE);
2177 +
2178 +  p->private = false;
2179 +  p->file = NULL;
2180 +  p->file_offset = 0;
2181 +  p->file_bytes = 0;
2182 +
2183 +  return true;
2184 +}
2185 diff --git a/src/vm/swap.h b/src/vm/swap.h
2186 new file mode 100644
2187 index 0000000..34d5d51
2188 --- /dev/null
2189 +++ b/src/vm/swap.h
2190 @@ -0,0 +1,11 @@
2191 +#ifndef VM_SWAP_H
2192 +#define VM_SWAP_H 1
2193 +
2194 +#include <stdbool.h>
2195 +
2196 +struct page;
2197 +void swap_init (void);
2198 +void swap_in (struct page *);
2199 +bool swap_out (struct page *);
2200 +
2201 +#endif /* vm/swap.h */