josephjang

C++ Standard Library Technical Report의 draft.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1711.pdf

(위 링크를 통해 다운받는 것이 현재 매우 느리므로, 본인에게 요청하면, 직접 보내줄 수 있다.)

n1540에서의 커다란 변경사항이라면 fixed size sequence인 array container가 추가되었다는 것이다. 기존부터 알려져있었지만, 특이할만한 사항은, array container 역시 aggregate라서 일반적인 array 처럼 initializer list를 사용한 초기화가 가능하다는 것이다. 즉, 다음과 같은 문법이 가능하다.

array a = { { 1, 2, 3, 4, 5 }}; // boost
array a = { 1, 2, 3, 4, 5 }; // tr1

기존 Standard Library 상의 container들의 불편한 점 중의 하나가 multi-dimension container를 초기화하기가 매우 불편했다는 것인데, 이것으로 해결이 어느 정도 가능했으면 한다.

몇몇 compiler 구현에서는 TR1의 몇몇 component들을 제공하고 있지만, 아직 boost쪽에서도 논의 중인 정도이므로, private/proprietary solution으로 TR1의 container들을 손수 구현해보는 것도 의미있고, 재미도 있는 일일 것 같다.

From http://article.gmane.org/gmane.comp.lib.boost.devel/112562/

곧 release될 boost 1.32의 변경사항들이다.

매우 유용할만한 Multi-index containers나 Program Options, 새로 제안된 iterator 개념을 구현한 Range Library,  C++에 없어서 불편했던 string utility – String algorithm, stream과 연동해서 여러 sink로의 serialization방법과 filtering 방법을 제공하는 Serialization framework가 새로 추가되었다.

http://www.meta-comm.com/engineering/boost/1_32_0_draft/

http://www.meta-comm.com/engineering/boost/boost_1_32_0.tar.bz2
http://www.meta-comm.com/engineering/boost/boost_1_32_0.tar.gz
http://www.meta-comm.com/engineering/boost/boost_1_32_0.zip

New Libraries

• Assignment Library: Filling containers with constant or generated data has never been easier, from Thorsten Ottosen.
• Minmax Library: Standard library extensions for simultaneous min/max and min/max element computations, from Hervé Brönnimann.
• Multi-index Containers Library: Containers with multiple STL-compatible access interfaces, from Joaquín M López Muñoz.
• Numeric Conversion Library: Optimized policy-based numeric conversions, from Fernando Cacciola.
• Program Options Library: Access to configuration data given on command line, in config files and other sources, from Vladimir Prus.
• Range Library: A new infrastructure for generic algorithms that builds on top of the new iterator concepts, from Thorsten Ottosen.
• Serialization Library: Serialization/de-serialization of arbitrary C++ data structures to various formats including text, binary, and xml, from Robert Ramey.
• String Algorithms Library: Collection of string related algorithms for case conversion, trimming, find/replace operations and more, from Pavol Droba.
• Tribool: 3-state boolean type library, from Doug Gregor.

Updated Libraries

• Compose: This deprecated library has been removed.
• Graph:
  • Added bundled properties to the adjacency_list and adjacency_matrix class templates, greatly simplifying the introduction of internal vertex and edge properties.
  • The LEDA graph adaptors have been ported to LEDA 4.5.
  • Added algorithms for betweenness centrality and betweenness centrality clustering.
  • Added circle layout and undirected spring layout algorithms.
• Signals Library: Introduced deterministic slot ordering, permitting slots to be connected at the beginning or end of slot groups or the slot list itself. Combiners may safely have state and are accessible from the signal.
• Utility: class template result_of added.
• Test Library:
  • namespace names gets shorten; old one still supported till next release
  • added proper encoding of XML PCDATA
  • support for wide string comparison implemented

  For complete list of changes see Test Library release notes.

Problem

Linux 시스템의 (swap을 포함한) 메모리가 모두 소진된 상태에서 중요한 프로세스(e.g. server app)가 OOM killer에게 죽는 현상이 발생할 수 있습니다. OOM killer가 무엇이고, 중요한 프로세스를 살아남게 하려면, 어떻게 해야할까요?

OOM killer is…

http://www.win.tue.nl/~aeb/linux/lk/lk-9.html#ss9.6

OOM(Out-Of-Memory) killer는

– a) 특정 (메모리가 부족한) 상황에서 동작해서,

– b) 특정 알고리즘에 의해 프로세스를 선택,

– 해당 프로세스를 kill 해서 메모리를 확보합니다.

OOM killer & Overcommit

위의 page에서는 OOM의 존재 자체가 일종의 버그라고 말합니다.

linux는 overcommit, 즉, 실제로 필요로 하는 메모리보다 더 많은 메모리를 (가상적으로) 할당하는 정책을 사용하기 때문에,

OOM killer가 필요한 상황이 발생하는 것입니다. 이러한 정책을 optimistic memory allocation이라고 부르구요. (반대로 pessimistic이 있겠죠)

Linux는 ‘프로세스는 자신이 요청한 메모리 양을 모두 쓰지 않는다’라는 낙관적인 가정을 하기 때문에 이렇게 부릅니다.

Linux는 최대한 할당은 늦게 하고, 한번 할당되면 계속 사용한다는 가정을 하고 VM 시스템을 만들었습니다.

brk() system call을 통해서 heap 크기를 늘리려고 시도할 때 (즉, virtual address space를 할당할 때)는 일단 허용하고,

실제로 memory frame이 할당되는 시점을 사용자 프로세스가 실제로 해당 메모리에 접근해서 fault가 일어날 때로 미루어서 이러한 정책을 구현합니다.

물론 OS는 사용자 프로세스들에 할당된 address space의 총합과 자신이 할당할 수 있는 memory frame의  전체 크기를 알기 때문에 overcommit을 방지할 수 있습니다.

Linux 2.6에서도 가능한 것 같습니다. /proc/sys/vm/overcommit_ratio를 조정해서, 둘 사이의 비율을 조정할 수 있습니다.

root@www src # uname -a
Linux www.lastmind.net 2.6.8-rc1 #1 Thu Jul 15 21:11:46 KST 2004 x86_64 4  GNU/Linux
root@www src # cat /proc/sys/vm/overcommit_ratio
50

이러한 정책은 어떻게 보면 매우 비합리적으로 보일 수도 있지만, 성능을 올리는데 효과가 있다고 합니다.

(예를 들어, 프로세스 fork시의 COW 정책도 일종의 overcommitting이라고 하는군요.)

OOM killer is …bad guy?

http://www.kerneltraffic.org/kernel-traffic/topics/OOM_Killer.html

kerneltraffic쪽의 page들을 보면, OOM killer가  a)와 b) 단계에서 사용하는 algorithm들에 문제(버그?)가 많았던 모양입니다.

특히 b)의 경우에는 heuristic일 뿐이라서, 중요한 프로세스와 아닌 프로세스를 구분하지 못하기 때문에,

데스크탑 환경이 아닌 서버 환경에서는 매우 치명적일 수 있습니다. 그 외에도 deadlock 같은 버그 문제도 보이는군요.

그래서 그런지 2.4.23에서 OOM Killer는 빠졌습니다만,

http://www.kerneltraffic.org/kernel-traffic/kt20031214_245.html#6

http://kerneltrap.org/node/view/1010

http://kerneltrap.org/node/view/1017

http://kerneltrap.org/comment/reply/1754

다시 그 필요성 때문에, 2.4.24-pre1에서 OOM killer를 kernel compile option(CONFIG_OOM_KILLER)의 형태로 추가했다고 합니다.

문제들은 계속 수정되는 것 같습니다만, b) algorithm이 heuristic라서 발생하는 문제는 여전한 것 같습니다. ^^;

debian의 kernel-image-2.4.26-1-686-smp의 image는

CONFIG_BINFMT_MISC=m
# CONFIG_OOM_KILLER is not set
CONFIG_PM=y

와 같이 OOM killer가 기본적으로 꺼져있군요.

OOM killer algorithm

mm/oom_kill.c를 보면 OOM killer의 코드가 나옵니다.

 *  The routines in this file are used to kill a process when
 *  we’re seriously out of memory. This gets called from kswapd()
 *  in linux/mm/vmscan.c when we really run out of memory.

kswapd는 kernel thread로 동작하면서, page cache를 유지하고 slab cache를 shrink하고 swapping out을 수행합니다.

http://www.csn.ul.ie/~mel/projects/vm/guide/html/understand/node68.html

a) zone마다 일정 수(pages_high)만큼의 page를 확보하기 위해 try_to_free_pages_zone()을 호출하는데,

shrink_caches()를 호출해서 128K 정도의 메모리를 확보하려고 합니다.

http://www.csn.ul.ie/~mel/projects/vm/guide/html/code/node38.html#SECTION001030200000000000000

이를 수행하지 못할 경우, oom_kill.c의 out_of_memory()를 통해, oom_kill()이 수행됩니다.

이는 physical memory를 swap할 공간도, cache를 shrink할 공간도 없다는 의미입니다.

b)

oom_kill()은 모든 task에 대해 badness()를 계산해서 가장 나쁜(badness()의 결과가 가장 큰) task를 kill합니다.

badness()의 주석을 보면,

/**
 * oom_badness – calculate a numeric value for how bad this task has been
 * @p: task struct of which task we should calculate
 * 
 * The formula used is relatively simple and documented inline in the
 * function. The main rationale is that we want to select a good task
 * to kill when we run out of memory.
 *
 * Good in this context means that:
 * 1) we lose the minimum amount of work done
 * 2) we recover a large amount of memory
 * 3) we don’t kill anything innocent of eating tons of memory
 * 4) we want to kill the minimum amount of processes (one)
 * 5) we try to kill the process the user expects us to kill, this
 *    algorithm has been meticulously tuned to meet the priniciple
 *    of least surprise … (be careful when you change it)
 */

주석을 좀 이상하게 적어놓은 것 같은데, 죽이기에 좋은(Good) task가 kill할 task가 됩니다.

이러한 알고리즘에 따르면,

기본적으로 적은 수의 프로세스를 죽여서 많은 양의 메모리를 확보할 수 있는 heuristic을 쓰는 것을 알 수 있습니다.

3번에서 메모리를 많이 사용하는 innocent는 죽이지 않는다고 했으나,

실제 코드를 보면, 여기서 innocent란, 단순하게 cpu를 많이 사용하는 프로세스를 의미하는 것 같습니다.

또한, super user process이거나 hardware를 access하는 경우 badness point를 1/4로 삭감해줍니다.

Solution

OOM killer가 heuristic에 기반하고 있기 때문에, 중요한 server process가 죽지않는 다는 보장을 하기가 힘듭니다.

(위의 badness() 값을 낮추는 방법들을 전부 쓰더라도)

하지만, OOM killer를 쓰지 않는다고 하더라도, 특정 프로세스가 종료할 때까지 기다리는 수 밖에 없고,

(malloc으로 할당 받은 메모리는 대체로 다시 반납하지 않습니다.)

page fault handler에서 page frame을 할당받지 못하면, init를 제외한 해당 task는 kill 되기 때문에,

OOM 상황에서는 어차피 치명적인 상황이 발생합니다.

따라서, OOM 상황이 발생하지 않도록 노력하는 것이 중요할 것 같네요.

server 어플리케이션의 경우에는 대체로 자신이 사용하고 있는 메모리 양을 알고 있으므로 이에 대한 제약을

어플리케이션 수준 또는 시스템 수준(ulimit)에서 가하는 것도 괜찮은 방법이라고 생각합니다.

그리고 메모리 바운드 어플리케이션이라면 대부분 swapping out 되는 것을 원하지 않을 것이므로,

page에 lock을 거는 방법을 생각해볼 수도 있겠네요. (physical page frame이 부족할 경우, 자동적으로 실패하겠죠)