Appendix E

Cache Algorithm

The cache control facility uses AM and XMU cache areas. The facility divides the XMU cache area by staging unit (STU), and assigns the STU to a real disk device. The links are changed dynamically when reading or writing during daemon processes, etc.

Note the following points.

1. Cluster header freelist is related to config parameter CLSTH.

2. Threshold size is related to the VVL parameters thholdctrl and thholdsz.

3. XMCACHESZ means to use VVL parameter XMCACHESZ.

4. XM cache freelist is related to the ISL parameter "cachedev -C".

algorithm read                    /* when cache on */
     input: vbuf
     output: none
{
     /* selection of I/O path */
     if (cluster header freelist queueNote 1 is empty) {
          select path (following);
          /*
           * transfer the blocks directly from disk to user space or file system buffer cache;
           */
          goto io:
     }
     check threshold sizeNote 2;
     for (each STU (stagging unit) which contains reading blocks) {
          search the STU from hash queue;
          if (the STU is in XM cache) {
               if (all the reading blocks are in XM cache){
                    select path;
                    /*
                     * transfer the blocks from XM cache to user space or file system buffer cache;
                     * raise priority of the STU;
                     */
               } else {
                    if (there are some unflushed blocks in XM cache) {
                         select path;
                         /*
                          * get a new STU in AM cache temporarily;
                          * transfer the STU from disk to AM cache;
                          * transfer the unflushed blocks from XM cache to AM cache;
                          * transfer the STU from AM cache to XM cache;
                          * transfer the blocks from AM cache to user space or file system buffer cache;

                          * raise priority of the STU;
                          * free the temporary STU in AM cache;
                          */
                    } else {
                         select path;
                         /*
                          * get a new STU in AM cache temporarily;
                          * transfer the STU from disk to AM cache;
                          * transfer the STU from AM cache to XM cache;
                          * transfer the blocks from AM cache to user space or file system buffer cache;
                          * raise priority of the STU;
                          * free the temporary STU in AM cache;
                          */
                    }
               }
          } else {                    /* STU not in cache */
               if (smaller than threshold sizeNote2 &&
               enable to get a new STU in XM cache (getxmc algorithm)) {
               select path;               /* use new XM cache */
               /*
                * get a new STU in XM cache;
                * get a new STU in AM cache temporarily;
                * transfer the STU from disk to AM cache;
                * transfer the STU from AM cache to XM cache;
                * transfer the blocks from AM cache to user space or file system buffer cache;
                * free the temporary STU in AM cache;
                * set priority of the STU in XM cache;
                */
          } else {                    /* read without cache */
               select path;
               /*
                * transfer the blocks directly from disk to user space or file system buffer cache;
                */
          }
     }
 }
io:
     issue read request by cluster for each selected I/O path;
}



algorithm write               /* when cache on */
     input: vbuf
     output: none
{
     /* selection of I/O path */
     if (cluster header freelist queueNote 1 is empty) {
          select path (following);
          /*
           * transfer the blocks directly from disk to user space or file system buffer cache;
           */
          goto io:
     }

     check threshold sizeNote 2;
     for (each STU which contains writing blocks) {
          if (all or some writing blocks are in XM cache) {
               if (not root file system && smaller than threshold sizeNote 2) {
                    select path (following);
                    /*
                     * transfer the blocks from user space or file system buffer cache to XM cache;
                     * (no write to disk)
                     */
               } else {
                    select path;               /* write through */
                    /* transfer the blocks from user space or file system buffer cache to XM cache;
                     * transfer the blocks from user space or file system buffer cache to disk;
                     */
               }
          } else {               /* STU is not cache */
               if (smaller than threshold sizeNote2 &&
                    enable to get a new STU in XM cache (getxmc algorithm)) {
                    if (not root file system) {
                         select path;
                         /*
                          * get a new STU in XM cache;
                          * transfer the blocks from user space or file system buffer cache to XM cache;
                          * set priority of the STU;
                          * (no write to disk)
                          */
                    } else {
                         select path;               /* write through */
                         /*
                          * get a new STU in XM cache;
                          * transfer the blocks from user space or file system buffer cache to XM cache;
                          * transfer the blocks from user space or file system buffer cache to disk;
                          * set priority of the STU;
                          */
                    }
               } else {
                    select path;
                    /*
                     * get a new STU in AM cache temporarily;
                     * transfer the blocks asynchronously from AM cache to disk;
                     * (the temporary STU in AM cache is freed in interrupt routine)
                     */
               }
          }
     }
io:
     issue write request by cluster for each selected I/O path;

}

algorithm getxmc          /* get XM cache STU */
     input: device number of virtual volume
     output: a STU on XM cache
{
     if (exceeding XMCACHESZNote 3 || XM cache freelistNote 4 is empty) {
          if (not exceeding XMCACHESZ) {
               free the XM cache STU on other virtual volume;
               if (XM cache freelist become not empty)
                    goto get_freelist;
          }
          for (XM cache STU on same virtual volume from priority minimum to center) {
               if (not in I/O and not delayed write) {
                    remove this XM cache;
                    return XM cache (replace from the same virtual volume)
               }
          }
          if (XM cache freelist is empty) {
               wakeup (vcdaemon);
               free the XM cache STU on other virtual volume;
               if (XM cache freelist become not empty)
                    goto get_freelist;
               return fail to get XM cache;
          }
     }
get_freelist:
     remove XM cache STU from first freelist;
     return XM cache (get from freelist);
}