第 十三 章 存储系统

本章节描述存储管理系统的各方面,以及控制其操作的各种过程。

第 13.1 节 垃圾回收

Scheme的对象(如序对,字符串,过程)都不会通过scheme程序明确释放。相反,一旦确定对象无法访问,存储管理系统会自动回收与该对象关联的存储空间。为了回收此存储空间,ChezScheme会在程序运行时,定期运行垃圾回收器。 从已知的入口开始,即机器寄存器,回收器找到所有可访问的对象,复制它们(在大多数情况下),以消除它们之间的碎片,并回收无法访问的对象占用的存储空间。

收集行为是由默认的collect-request处理器触发的,该处理器通过一个collect-request中断完成调用,该中断在分配了大约n个字节的存储空间之后产生,其中n是参数collect-trip-bytes的值。默认的collect-request处理器,通过调用名为collect的无参数过程,发起一个收集行为。回收处理器可通过改变参数collect-request-handler的值来重新定义。一个程序还可以直接通过调用collect,来使collect-request中断之间发起一次回收行为。

ChezScheme的收集器是基于世代的收集器。它根据对象的世代(初略地说,是收集次数)对其进行隔离,并且收集老代对象的频率比新代对象频率低,由于新代对象往往很容易就无法访问了,所以大多数收集工作只花很少的时间。仅当堆被压缩(查看4.8章节的Scompact_heap)或collecttarget-generation 参数被设置为static,对象才会被放入静态世代。

非静态世代从0开始递增,直到达到collect-maximum-generation的当前值。存储管理系统把最新分配的对象放入第0代。在第0代的回收期间,默认情况下会把留存的第0代对象移动到第一代。同样地,回收第一代期间,会把留存的第0代和第1代对象移至第2代,如此重复。在回收最大非静态代期间,所有留存的非静态对象都将移至最大非静态代。通过这种机制,一个对象有可能跳过一个或多个世代,但这在许多对象上不太可能发生,并且如果这些对象变得不可访问,则最终将回收它们的存储。

gc-trip是一个内置的计数器,用来控制何时回收每一代。每次调用不带参数的collect,gc-trip自增1。设回收世代的基数为r,已回收的世代是最高代g,则gc-trip是rg的倍数。如果collect-generation-radix设置为4,系统每次都回收第0代,每4次回收一次第1代,每16次回收第2代,以此类推。

每次调用单个参数g的collect,第g代会回收,并且gc-trip前进到下一个rg的边界,但不超过下一个rg+1边界,其中r还是collect-generation-radix的值。

当用第二个参数tg调用collect时,tg确定目标代。当g是最大非静态代,tg必须是g,或者是static符号。其他情况,tg必须是g或者g+1。当目标代是static符号,所有在非静态代的数据都将移至静态代。位于静态代的对象不会被回收。当程序的常驻代码或数据结构加载并初始化后,减少后续的回收开销方面很好用。

通过设置本节中描述的参数,可以对垃圾回收期器的行为进行实质性的调整。通过重新定义collect-request handler来调用带有显式g和tg参数的collect,甚至有可能完全覆盖收集器的默认策略,以确定何时回收每个世代。例如,程序员可以通过重新定义handler,显式的g,tg参数调用collect,以在长时间内将最大非静态代视为静态生成代,并且在那段时间里绝不会等于最大静态代。

有关ChezScheme收集器的更多信息,请参见报告"Don't stop the BiBOP: Flexible and efficient storage management for dynamically typed languages"。[13

过程: (collect)

过程: (collect g)

过程: (collect g tg)

返回: 未定义

: (chezscheme)

g 必须是一个非负fixnum,不能大于最大非静态代,即collect-maximum-generation返回值。

如果g是最大非静态代,tg必须是一个等于g的fixnum,或者是符号static。其他情况,tg必须是一个等于或大于g的fixnum。

该过程会促使存储管理器发起一次垃圾回收。回收动作是定期调用collect-request处理器,但也可以显式调用它以在特定时间(例如在计时计算之前)强制回收。在ChezScheme的线程版本中,调用collect的线程必须是唯一的活动线程。

如本节的引言中所述,系统会根据g和tg(如果提供)确定要回收的世代。

过程: (collect-rendezvous)

返回: 未定义

: (chezscheme)

请求一次垃圾回收(与系统指定的进行回收时的方式相同)。所有运行中的线程都会配合,以便其中一个线程顺利调用collect-request处理器。在此期间,其他的线程都暂停直到该处理器返回。

请注意,如果collect-request处理器(查看collect-request-handler)没有调用collect,那么collect-rendezvous不会实际地执行一次垃圾回收。

全局参数: collect-notify

: (chezscheme)

如果collect-notify设置为#t,每当运行一次回收时,回收器会打印一条信息。collect-notify默认值是 #f。

全局参数: collect-trip-bytes

: (chezscheme)

此参数确定允许在垃圾回收之间分配的大概存储量。该值必须是正fixnum。

ChezScheme在内部以大块分配内存,并通过内联操作将这些块细分以提高效率。存储管理器确定是否为每个分配的大块仅请求一次回收。此外,从存储管理器请求回收到兑现回收之间可能需要一段时间,特别是如果通过with-interrupts-disableddisable-interrupts暂时禁用了中断。因此,collect-trip-bytes仅是一种近似度量。

全局参数: collect-generation-radix

: (chezscheme)

此参数确定默认情况下,collect-request处理器调用不带参数的collect时收集每一代的频率。该值必须是正fixnum。 每回收rg</sup次,就会回收一次世代,其中r是collect-generation-radix的值,g是世代编号。

collect-generation-radix设置为1,将强制每次回收都回收所有世代。将collect-generation-radix设置为非常大的数会无限期地延迟延迟收集较老的一代。

全局参数: collect-maximum-generation

: (chezscheme)

此参数确定当前使用的最大非静态代,也是当前使用的所有世代的总数。其值是1到254之间的整数。当设置成1时,只有两个非静态世代可以使用。当设置成2时,有三个世代可以使用,以此类推。设置为254时,将使用255个非静态代,再加上单个静态代,总共256个代。提高世代数能有效地减少了收集旧对象的频率,减少收集开销,但也可能会增加系统中保留的不可访问对象的数量,从而增加所需的内存总量。

全局参数: collect-request-handler

: (chezscheme)

该值必须是一个过程。每当系统确定要开始回收时(即自上次回收以来,已分配了由参数collect-trip-bytes确定的存储量之后),将调用该不带参数的过程。

默认情况下,collect-request-handler仅调用不带参数的collect。

可以将collect-request-handler设置为空,以禁止自动回收工作。如下:

(collect-request-handler void)

想要暂时禁止回收,还可以通过critical-section防止任何中断发生来做到。

全局参数: release-minimum-generation

: (chezscheme)

该参数的值必须是0到collect-maximum-generation之间,包括默认的collect-maximum-generation值。

在分配新数据并进行回收时,存储管理系统会自动从操作系统请求其他虚拟内存地址空间。相应地,在堆明显缩小时,系统会尝试将先前获得的某些虚拟内存返回给操作系统。默认情况下,系统仅在针对最大非静态代进行回收之后才尝试这样做。 也可要求系统在针对年轻代的回收时这样做,方法是将release-minimum-generation更改为小于collect-maximum-generation。 当设置了参数的一代,或任何较旧的一代是回收的目标一代时,存储管理系统将在回收之后,尝试将不需要的虚拟内存返回给操作系统。

collect-maximum-generation设置为新值g时,如果(a)两个参数在更改前具有相同的值,或(b)release-minimum-generation有一个大于g的值,则release-minimum-generation也隐式设置为g。

全局参数: heap-reserve-ratio

: (chezscheme)

该参数确定与当前占用的内存量(不包括已设为静态的内存区域)成比例的近似保留内存量(未按释放最小生成条目中所述返回到O/S)。它必须是不精确的非负flonum值。如果设置为精确的实际值,则精确的值将转换为不精确的值。默认值1.0为每个当前占用的非静态页面保留一页内存。 将其设置为较小的值,可能的结果是较小的平均虚拟内存占用量。而将其设置为较大的值,可能的结果是较少的操作系统调用,以请求和释放内存空间。

弱对, 星历对, 和守护者

弱对允许程序维护指向对象的弱指针。指向对象的弱指针不会阻止存储管理系统回收该对象,但是只要该对象在系统中是可访问的,它仍然有效。

星历对类似于弱对,但是星历对组合了两个指针,其中仅在保留第一个指针的情况下才保留第二个指针。

守护者允许程序保护对象防止垃圾回收器的重分配,并确定应何时重新分配对象。

弱对,星历对,守护者允许程序在单独的数据结构(例如hash tables)中保留关于对象的信息,而不需要关心保留的信息会一直留在系统中。

星历对对允许这种数据结构保留键-值组合,其中一个值可以引用其键,但是如果不需要另外保存,则可以回收该组合。

此外,守护者允许被无限期释放的对象得以保存,以便可以重新使用它们,或者可以使用存储在对象中的数据执行清理或其他操作。

[12]中描述了ChezScheme使用的守护者和弱对的实例。 在[23]中描述了星历对,但是ChezScheme中的实现避免了二次时间最坏情况行为。

过程: (weak-cons obj1 obj2)

返回: 一个弱对

: (chezscheme)

新序对中,obj1为car,obj2为cdr。除了两种以外,弱对与普通序对是无法区分的:

弱对可以使用谓词weak-pair?区别于普通序对。

弱对在其car里保留一个指向对象的弱指针。

弱对中的car里的弱指针就像普通指针一样,只要它指向的对象可以通过系统中某个地方的普通(非弱)指针访问即可。 然而,如果垃圾回收器检测到没有非弱指针指向对象时,它会将每个指向对象的弱指针替换为broken weak-pointer对象,#!bwp,并丢弃该对象。

弱对的cdr字段不是弱指针,因此可以使用弱对来形成弱保持对象的列表。 可以使用普通的列表处理操作(例如length,map和assv)来操纵这些列表。 可使用set-car!set-cdr!修改弱对;set-car!后,car字段将包含指向新对象的弱指针,替代旧对象。 构建列表和哈希表的关联对时,弱对特别好用。

弱对没有阅读器语法,其的打印跟其他普通对相同。所以弱对被写入后读取时,会变成普通对。

(define x (cons 'a 'b))
(define p (weak-cons x '()))
(car p) => (a . b)

(define x (cons 'a 'b))
(define p (weak-cons x '()))
(set! x '*)
(collect)
(car p) => #!bwp

如果垃圾回收提升序对到第一代先于(set! x '*),以上的后一个示例可能会返回(a . b)。 可能有必要强制一个老代回收行为来回收该对象。 存储管理系统仅保证一旦删除了该对象的所有非弱指针,该对象最终将被回收,但不保证何时回收。

过程: (weak-pair? obj)

返回: 如果obj是弱对,返回#t,否则返回#f。

: (chezscheme)

(weak-pair? (weak-cons 'a 'b)) => #t
(weak-pair? (cons 'a 'b)) => #f
(weak-pair? "oops") => #f

过程: (ephemeron-cons obj1 obj2)

返回: 一个新的星历对

: (chezscheme)

obj1是新对的car,obj2是新对的cdr。星历对与普通对没有区别,除了以下两个方面:

  1. 星历对可以使用谓词ephemeron-pair?以区分普通对。
  2. 星历对的car包含一个指向对象的弱指针,并且只有保留了星历对的car的情况下才保留星历对的cdr。

一个星历对的行为类似弱对,但cdr还经过特殊处理:将星历对的cdr设置为#!bwp的同时,会将car设置为#!bwp。那么通过cdr对象去引用car对象时,不一定需要保留car(这跟弱对不同)。相反,出于某种原因,car必须独立于cdr对象保存。

像弱对和其他对一样,星历对可以使用set-car!set-cdr!对其进行修改。并且,由于没有针对星历对的阅读器语法,星历对打印方式跟普通对一样。

(define x (cons 'a 'b))
(define p (ephemeron-cons x x))
(car p) => (a . b)
(cdr p) => (a . b)

(define x (cons 'a 'b))
(define p (ephemeron-cons x x))
(set! x '*)
(collect)
(car p) => #!bwp
(cdr p) => #!bwp

(define x (cons 'a 'b))
(define p (weak-cons x x)) ; 这不是一个星历对
(set! x '*)
(collect)
(car p) => (a . b)
(cdr p) => (a . b)

与弱对一样,如果垃圾回收提升该pair至老代的工作发生在给x赋值*之前,则上面中间示例的最后两个表达式实际上可能会返回(a.b)。 但是,在上面的最后一个示例中,最后两个表达式的结果将始终为(a.b),因为弱对的cdr拥有非弱引用,并且该非弱引用阻止了car成为#!bwp。

过程: (ephemeron-pair? obj)

返回: 如果obj是星历对,返回#t,否则返回#f。

: (chezscheme)

(ephemeron-pair? (ephemeron-cons 'a 'b)) => #t
(ephemeron-pair? (cons 'a 'b)) => #f
(ephemeron-pair? (weak-cons 'a 'b)) => #f
(ephemeron-pair? "oops") => #f

过程: (bwp-object? obj)

返回: 如果obj是损坏的弱对对象,返回#t,否则返回#f。

: (chezscheme)

(bwp-object? #!bwp) => #t
(bwp-object? 'bwp) => #f

(define x (cons 'a 'b))
(define p (weak-cons x '()))
(set! x '*)
(collect (collect-maximum-generation))
(car p) => #!bwp
(bwp-object? (car p)) => #t

过程: (make-guardian)

返回: 一个新的守护者

: (chezscheme)

守护者用程序来表示,封装注册的对象组,以保护它们。当守护者创建后,注册对象组为空。通过将对象作为参数传递给守护者,可以向守护者注册对象:

(define G (make-guardian))
(define x (cons 'aaa 'bbb))
x => (aaa . bbb)
(G x)

注册对象时,也可以指定"representative"对象,继续上面的示例:

(define y (cons 'ccc 'ddd))
y => (ccc . ddd)
(G y 'rep)

与守护者关联的注册对象组在逻辑上分为两个不相交的子组:一个子组引用“可访问”对象,另一组引用“不可访问”对象。 不可访问对象是经过验证无法访问的对象(通过保护机制本身或通过弱对或星历对的car除外)。而可访问对象是未经证明的对象。“经过验证”一词在这里很重要:有可能在可访问组中某些对象确实不可访问,但这尚未得到证明。在某些情况下,直到对象实际上变得不可访问很久之后(在当前实现中,直到发生包含对象的世代的垃圾收集),才可能做出这种证明。

向守护者注册的对象最初被放置在可访问组中,并在它们变得不可访问后的某个时刻移入不可访问组。 不可访问组中的对象可通过调用不带参数的守护者来检索。如果不可访问组中没有对象,则守护者返回#f。继续上面的示例:

(G) => #f
(set! x #f)
(set! y #f)
(collect)
(G) => (aaa . bbb)   ; this might come out second
(G) => rep           ; and this first
(G) => #f

对G的初始调用返回#f,因为绑定到x和y的对是向G注册的唯一对象,并且仍然可以通过这些绑定访问这些对。调用collect时,对象将移入不可访问的组。 因此,对G的两次调用将返回先前绑定到x的对和先前绑定到y的对的代表,尽管可能与所示顺序相反。(如上所述,对于弱对,如果对象已迁移到较早的一代,则调用collect实际上可能不足以证明该对象不可访问。)

即使一个未使用"representative"对象注册的,从守护者返回的对象被证明了无法访问(除了可能通过弱对或星历对的car字段),如果还未被存储管理系统回收,那么在删除了守护者系统内部或外部的最后一个非弱指针之前,不会回收它。 实际上,从守护者那里获取的对象在这方面或任何其他方面都没有特殊的地位。此功能避免了共享或循环结构可能会出现的问题。 由不可访问对象组成的共享或循环结构将被完整地保留,并且每个向守护者进行注册保存的片段都将放置在不可访问组里。 程序员可以完全控制结构体的处理顺序。

一个对象可以在守护者里多次注册,在这种情况下,可以多次检索该对象:

(define G (make-guardian))
(define x (cons 'aaa 'bbb))
(G x)
(G x)
(set! x #f)
(collect)
(G) => (aaa . bbb)
(G) => (aaa . bbb)

它也可以向多个守护者注册,并且守护者本身也可以向其他守护者注册。

如果一个对象没有使用"representative"对象向守护者注册,并且已经放入弱对或星历对的car字段,它将一直保留在car字段里,直到它从守护者返回并被其他程序丢弃,或者被守护者自身丢弃。

(define G (make-guardian))
(define x (cons 'aaa 'bbb))
(define p (weak-cons x '()))
(G x)
(set! x #f)
(collect)
(set! y (G))
y => (aaa . bbb)
(car p) => (aaa . bbb)
(set! y #f)
(collect 1)
(car p) => #!bwp

(上面的第一个回收器将提升该对象到至少第一代,所以要求第二次回收器调用为第一代的回收,也可以通过多次调用collect来强制这样做。)

另一方面,如果指定"representative"对象(对象本身除外),被守护对象会从弱对或星历对的car字段被抛弃,与此同时,"representative"对象可以从守护者获得。

(define G (make-guardian))
(define x (cons 'aaa 'bbb))
(define p (weak-cons x '()))
(G x 'rep)
(set! x #f)
(collect)
(G) => rep
(car p) => #!bwp

下面的示例说明了在释放守护者本身时,已释放对象会将弱对的car字段设置为#!bwp:

(define G (make-guardian))
(define x (cons 'aaa 'bbb))
(define p (weak-cons x '()))
(G x)
(set! x #f)
(set! G #f)
(collect)
(car p) => #!bwp

下面的示例演示如何使用监护人来释放外部存储,例如由C库“ malloc”和“ free”操作管理的存储。

(define malloc
  (let ([malloc-guardian (make-guardian)])
    (lambda (size)
      ; first free any storage that has been dropped.  to avoid long
      ; delays, it might be better to deallocate no more than, say,
      ; ten objects for each one allocated
      (let f ()
        (let ([x (malloc-guardian)])
          (when x
            (do-free x)
            (f))))
      ; then allocate and register the new storage
      (let ([x (do-malloc size)])
        (malloc-guardian x)
        x))))

do-malloc必须返回一个Scheme对象“header”,其中包含指向外部存储的指针(可能是一个无符号整数),并且所有对外部存储的访问都必须通过header进行。 特别是必须注意,删除相应的header之后,将没有指针指向Scheme以外的外部存储。do-free必须使用该封装的指针释放外部存储。 这两个原语都可使用foreign-allocforeign-free,或者使用C库里的"malloc"和"free"运算符(作为外部过程导入)来定义。(请参阅第4章。)

如果不希望等到调用malloc释放以前由malloc分配的已删除存储时,则可以使用collect-request处理程序来检查并释放已删除存储,如下所示。

(define malloc)
(let ([malloc-guardian (make-guardian)])
  (set! malloc
    (lambda (size)
      ; allocate and register the new storage
      (let ([x (do-malloc size)])
        (malloc-guardian x)
        x)))
  (collect-request-handler
    (lambda ()
      ; first, invoke the collector
      (collect)
      ; then free any storage that has been dropped
      (let f ()
        (let ([x (malloc-guardian)])
          (when x
            (do-free x)
            (f)))))))

只需进行一点重构,就可以将封装的外部地址注册为每个header的代表,在这种情况下,do-free将仅将外部地址作为参数。

第 13.3 节 锁定对象

从C变量或数据结构指向Scheme对象的所有指针,通常应在输入(或重新输入)Scheme之前丢弃。 如果无法遵循该准则,则可以通过锁对象或等效的C库过程Slock_object(第4.8节)锁定对象。

过程: (lock-object obj)

返回: unspecified

: (chezscheme)

锁定对象可防止存储管理器收回或重定位该对象。 应谨慎使用锁定,因为它会引入内存碎片并增加存储管理开销。

如果未解锁对象,锁定也会导致意外保留存储空间。 可以通过解锁对象或等效的C库过程Sunlock_object来解锁对象。

锁定立即值(例如,fixnum,布尔值和字符)或已设为静态的对象是不必要但无害的。

过程: (unlock-object obj)

返回: unspecified

: (chezscheme)

连续调用lock-objectSlock_object或同时调用这两个过程,可以多次锁定对象,在这种情况下,必须先通过相等次数的unlock-objectSunlock_object的调用来将其解锁。

一个包含在锁定对象里的对象,比如已锁定的序对中的car对象,是无需锁定的,除非存在一个单独的指向该对象的指针。 也就是说,如果仅通过外部对象来间接访问内部对象,则应将其解锁,以便收集器在收集期间可以自由地重新放置它。

解锁立即值(例如,fixnum,布尔值和字符)或已设为静态的对象是不必要的,无效的但无害的。

过程: (locked-object? obj)

返回: 如果obj已经锁定,或者是立即值,或者是静态的,则返回#t

: (chezscheme)

如果收集器无法重新定位或回收obj,则该谓词将返回true,包括立即值,例如fixnums,布尔值和字符,以及已被设置为静态的对象。

results matching ""

    No results matching ""