Changes between Version 21 and Version 22 of GarbageCollectorNotes


Ignore:
Timestamp:
May 19, 2006 1:22:08 PM (8 years ago)
Author:
guest
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • GarbageCollectorNotes

    v21 v22  
    1212The tradeoff is in the fact that every Haskell binary has the RTS compiled into it, making Haskell binaries rather large. The RTS consists of facilities like the support of user threads (or Haskell threads), garbage collection etc. We are interested in focusing on Garbage Collection. However before we get into the GC, let us look at how that is connected to the rest of the system. 
    1313 
    14 == The Scheduler == 
    15 Most of the interesting things related to scheduling and multithreading in Haskell center around the function schedule() that is define in Schedule.c. This is the part of schedule that take a thread from the run and decides what to do with it.  
    16  
    17 {{{ 
    18 static Capability * schedule (Capability *initialCapability, Task *task) 
    19 }}} 
    20  
    21 In schedule() is a pretty classical scheduler loop. I have stripped away several parts of the code here to get down to the essentials. 
    22  
    23 {{{ 
    24 #!c 
    25     t = popRunQueue(cap); 
    26     prev_what_next = t->what_next; 
    27  
    28     switch (prev_what_next) { 
    29          
    30     case ThreadKilled: 
    31     case ThreadComplete: 
    32         /* Thread already finished, return to scheduler. */ 
    33         ret = ThreadFinished; 
    34         break; 
    35          
    36     case ThreadRunGHC: 
    37     { 
    38         StgRegTable *r; 
    39         r = StgRun((StgFunPtr) stg_returnToStackTop, &cap->r); 
    40         cap = regTableToCapability(r); 
    41         ret = r->rRet; 
    42         break; 
    43     } 
    44      
    45     case ThreadInterpret: 
    46         cap = interpretBCO(cap); 
    47         ret = cap->r.rRet; 
    48         break; 
    49          
    50     default: 
    51         barf("schedule: invalid what_next field"); 
    52     } 
    53 }}} 
    54  
    55 The scheduler picks up a thread off the run queand decides what to do with it. If it is runnable, then it calles the function StgRun() to run it. At the end of the code block, the variable “ret” is set to indicate why the the thread stopped.  
    56  
    57 Haskell threads are not time-sliced via a timer (potentially a time rinterrupt) the way OS threads are [cross check if there is some time sliced mechanism]. Instead they are interreupted by certain commonly occuring events. Due to the lazy nature of Haskell thunks need to be created and values need to be computed very often. Hence the execution of a thread entails lots of of memory allocation. One of the ways the execution of a thread is interrupted is when a thread has run out of space in its current block - it then returns control back to the scheduler.  
    58  
    59   I stand corrected about the above - ''We do have a time-slice mechanism: the timer interrupt (see Timer.c) sets the context_switch flag, which causes the running thread to return to the scheduler the next time a heap check fails (at the end of the current nursery block). When a heap check fails, the thread doesn't necessarily always return to the scheduler: as long as the context_switch flag isn't set, and there is another block in the nursery, it resets Hp and HpLim to point to the new block, and continues.'' 
    60  
    61 A GHC block is a 4k page that is page aligned for the OS VM system.   
    62  
    63 Here is what the scheduler does with the "ret" -  
    64  
    65 {{{ 
    66 #!c 
    67     switch (ret) { 
    68     case HeapOverflow: 
    69         ready_to_gc = scheduleHandleHeapOverflow(cap,t); 
    70         break; 
    71  
    72     case StackOverflow: 
    73         scheduleHandleStackOverflow(cap,task,t); 
    74         break; 
    75  
    76     case ThreadYielding: 
    77         if (scheduleHandleYield(cap, t, prev_what_next)) { 
    78             // shortcut for switching between compiler/interpreter: 
    79             goto run_thread;  
    80         } 
    81         break; 
    82  
    83     case ThreadBlocked: 
    84         scheduleHandleThreadBlocked(t); 
    85         break; 
    86  
    87     case ThreadFinished: 
    88         if (scheduleHandleThreadFinished(cap, task, t)) return cap; 
    89         ASSERT_FULL_CAPABILITY_INVARIANTS(cap,task); 
    90         break; 
    91  
    92     default: 
    93       barf("schedule: invalid thread return code %d", (int)ret); 
    94     } 
    95 }}} 
    96  
    97 The scheduleHandleHeapOverflow(cap,t) call decides to give the thread another block, (or a set of blocks if the thread was asking for allocation of a large object (a large object is one that is larger than a block). If the scheduleHandleHeapOverflow() function feels that there aren't enough free blocks left, it decides to Garbage Collect. This is the point at which everything else stops and the GC kicks in.  
    98  
     14== CapabilitiesAndScheduling ==  
    9915 
    10016== Stepping into the GC ==