Ruby
†1 †3 †2 †4 Ruby YARV: Yet Another RubyVM Ruby Ruby Ruby C Ruby YARV OS C Ruby
An Implementation of Parallel Threads for YARV: Yet Another RubyVM
Koichi Sasada  ,†¹ Yukihiro Matsumoto  ,†² Atsushi Maeda  †³ and Mitaro Namiki  †4 In this paper, we describe an implementation of parallel threads for YARV: Yet Another RubyVM. The Ruby language is used worldwide because of its ease of use. Ruby also sup- ports multi-threaded programming. The current Ruby interpreter controls all threads only in user-level to achieve high portability. However, this user-level implementation can not sup- port blocking task and can not improve performance on parallel computers. To solve these problems, we implement parallel threads using native threads provided by systems software on YARV: Yet Another RubyVM what we are developing as another Ruby interpreter. To achieve parallel execution, correct synchronizations are needed. Especially, C extension li- braries for Ruby which are implemented without consideration about parallel execution need a particular scheme for running in parallel. And we also try to reduce a number of times of synchronization. In this paper, we show implementations of these schemes and results of performance improvement on parallel threads execution. Ruby 1. Ruby 13),15),16) Ruby 21) ↑1 ↑2（ ） ↑3
1 ↑4 1 Ruby Ruby 1 (B) (A) 2 m = Mutex.new th = Thread.new do # (A) m.synchronize do # (An) end end # (B) m.synchronize do (A) (Bm) Ruby Ruby # (Bm) end # ... th.join # th (An)
UNIX select Ruby Ruby 1 Ruby Fig. 1 Thread creation/joining/synchronization on Ruby Programming Ruby Ruby Ruby Ruby YARV 1 th Thread#join Ruby (Am) (Bm) Mutex YARV: Yet Another RubyVM 8),24) Ruby YARV Ruby Ruby YARV Ruby YARV YARV POSIX Ruby Ruby Ruby Ruby Pthread 5) Thread Ruby Ruby
Ruby
Ruby Ruby VM Ruby , GL GL GL OS C Ruby Ruby 2007 Ruby Vol. 48   No. SIG 0(PRO 34) Ruby YARV setjmp longjmp 2 Ruby Ruby 19),20)
Ruby Ruby 4 6 7
select Ruby 2. Ruby Ruby Ruby timeout 0 select Ruby 2.1 Ruby Ruby Ruby Ruby Ruby Ruby Ruby 2.1.1 Ruby Ruby OS Ruby Ruby 2.1.2 Ruby Ruby Ruby Ruby Ruby Ruby OS Ruby SIGVTALRM Ruby Ruby Ruby Ruby Ruby Ruby 3 4 Ruby (b) Ruby (1) ( 2 ) (3) Ruby Ruby (4) 2.2 Ruby 2.2.2 Ruby Ruby Ruby Ruby OS 2.2.1 Ruby Windows UNIX OS Pthread   Microsoft 2.1.2 N M Ruby Ruby M
M      N 1     1 Ruby 1 1 (a) (b) 2.1.2 (2)   (4) 1 1 Ruby 1 1 Scheduler Activations 2 ) M Ruby 14),22) (a) Ruby Ruby N Ruby Ruby 2007 Vol. 48   No. SIG 0(PRO 34) Ruby YARV 2.2.3
FL FL
GL
(c) GL Ruby 2 2 (b) GL (a) FL (d) Fig. 2   Synchronization Design 2 Ruby (e) (b)
2(b) GL RT1 (a) Ruby RT NM1 RT2 RT2 RT1  GL GL
RT1 RT1   RT2 Resource1 Resource2 FL1 FL2 RT1 RT2 5 NM2 MN2 (a) GL GL 6 (c) GL Ruby Ruby (d) Ruby Ruby (a) Ruby Ruby
(a) (b) GL (a) GL 2.2.4 Ruby Python7)
GL Fig. 3   Ruby Thread System Overview Ruby Ruby 1 1 GL Ruby 3. (d) Ruby Ruby 3.1 Ruby YARV Ruby 1 1 3 YARV Ruby 3 RT NT Ruby PE Processor Element PE Ruby 3.2 Ruby YARV Ruby Ruby C 4 thread_id Pthread pthread_t 2007 thread_id_t Ruby status Ruby (d) Vol. 48   No. SIG 0(PRO 34) Ruby YARV struct thread_data { thread_id_t thread_id; int status; struct thread_data *wait_next_id; lock_t lock; void (*unblock_func)(); cond_t sleep_cond; // VN // th = Thread.new do ... # (A) end # (A) th.raise SomeException Ruby 5 Fig.5 Raise an Exception to another Ruby Thread Ruby
(Mutex#synchronize)
Pthread pthread_mutex_lock / unlock   Windows Enter / LeaveCriticalSection
Ruby
Mutex VM
3.4 Ruby Ruby Ruby Ruby (Thread.new)   Ruby Ruby Pthread pthread_create  Windows _beginthreadex API Ruby Ruby (Thread#exit)   Ruby 3.5 Ruby Ruby Ruby Ruby Ruby (Thread#join) Pthread pthread_join Ruby VM 5
4 Fig. 4   Thread Management Data
7 }; 2007
6 Ruby Ruby Ruby Pthread Pthread select Ruby RT Pthread select pthread_kill Ruby Pthread
Ruby VM Ruby RT rt
8 Vol. 48   No. SIG 0(PRO 34) Ruby YARV g // UBF_sleep(thread_data *th){ pthread_cond_signal(th->sleep_cond, ...); } // ruby_sleep(thread_data *th, timeval *t){ set_unblock_function(th, UBF_sleep); if (t == 0) // pthread_cond_wait(th->sleep_cond, ...); else // pthread_cond_timedwait(th=>sleep_cond, ...); clear_unblock_function(th); CHECK_INTERRUPT_FLAG(th); } 7 Pthread Fig. 7   An program of sleep with Pthread Fig. 8   Memory Management on Current Ruby Interpreter TLS TLS Ruby TLS TLS Ruby Ruby pthread_getspecific C OS thread 3.7 Ruby Ruby YARV sleep Pthread pthread_cond_timedwait __thread 4.2 Ruby GC pthread_cond_wait sleep Ruby YARV 7 pthread_cond_signal Pthread C Ruby 4.2.1 Ruby Windows WaitForMultipleObjects Ruby Ruby SetEvent Ruby Thread#join 8 4. Ruby FreeList Ruby 4.1 Ruby
Ruby (a) FreeList Ruby FreeList Pthread 2007 rt#: Ruby Threads Number
wt#: Wating Threads Number 10 GC Fig. 10 Synchronization for Garbage Collection Ruby
10 GC 25) GC (b)
Ruby Ruby
GC RT1  GC rt# — wt# = 1 Ruby 4.2.2 Ruby Ruby FreeList Ruby FreeList TLFL
YARV 10 Fig. 9   Memory Management on Parallel Execution RT1 ( 1
rt# - RT2 RT4 wt#) FreeList Windows Ruby GC GC FreeList TLFL Ruby FreeList
1/N 4.2.3 YARV Ruby
YARV TLFL Pthread GC Vol. 48   No. SIG 0(PRO 34) Ruby YARV 11 /● (A) ・ cache_entry method_cache[CACHE_SIZE]; method_search_with_cache(class, id){ LOCK(method_cache_lock); // cache_entry *e = &method_cache[HASH(class, id)]; if (!(e->class == class && e->id == id)) { : •/ e->class = class; e->id = id; e->body = method_search(class, id); } UNLOCK(method_cache_lock); // return e->body; } /● (B) • cache_entry *method_cache[CACHE_SIZE]; method_search_with_cache(class, id){ cache_entry *e = method_cache[HASH(class, id)]; if (!(e->class == class && e->id == id)) { : •/ method_cache[HASH(class, id)] = e = new_entry( class, id, method_search(class, id)); } return e->body; } 11 Fig. 11   Method Cache Implementations 4.3.2 Ruby VM GL GL YARV GL

4.3.3
API
Safe rb_define_method_ts API GL YARV 4.4 GL Ruby Ruby GL longjmp 8)
4.4.1 YARV ID 11 (A) C Ruby ts:  Thread YARV GL (B) 11 GC 23)
2007 pthread_mutex_t giant_lock; int gl_locked; acquire_giantlock(){ for (int i=0; i<100; i++){ if (gl_locked == 0 && pthread_mutex_trylock(&giant_lock) == 0) { gl_locked = 1; return; } sched_yield(); } // pthread_mutex_lock(&giant_lock); gl_locked = 1; } 12 Pthread GC Fig. 12   A Program to Acquire Giant Lock with Pthread Ruby Ruby Ruby Ruby Ruby GL 3000 Ruby Ruby GL 4.4.3 Ruby GL GL Pthread Pthread pthread_mutex_trylock 4.4.5 100 sched_yield Ruby Ruby pthread_mutex_trylock GL GL 23) CPU 4.4.4 GL GL GL 1 CPU Ruby 2 GL 1 GL 1 GL GL Ruby 2.2.3 C GL Vol. 48   No. SIG 0(PRO 34) Ruby YARV 13 1 Table 1   Evaluation of Thread Management Primitives
Fig. 13 Overhead of Thread Context Switching 5. Ruby Ruby Thread.critical Ruby Intel Pentium D CPU 3.46GHz Dual Core Linux 2.6.17- 1.2174_FC5 SMP gcc version 4.1.1 20060525 (Red Hat 4.1.1-1) Ruby ruby 1.9.0 (2006-04-08) [x86_64-linux] Linux Thread.critical Pthread NPTL YARV 5.1.2 Ruby 10 Ruby 5.1 Ruby 5.1.1 Ruby 1 1 YARV (P=2) Ruby Ruby (Ruby) YARV (P=1) 2 Ruby pthread_create YARV Ruby YARV (P=2) YARV (P=1) YARV(P=2) 2 pthread_cond_wait Mutex Ruby YARV Ruby
CPU YARV
concat Ruby 4 Ruby YARV 13 C 8) 14 2 GL Table 2   Frequency of GL acquirement/competition
concat 4

CPU

CPU (Ruby)   2 CPU YARV (NoPara) Ruby YARV (P=2) YARV (NoPara) GL mandelbrot GL 4.4.5 fib tak concat GL GL
GL (NoPara) 1.2 hetero GL GL YARV (P=2) GL 2 GL
YARV (P=2) fib tak GL
gl GL YARV (NoPara) mandelbrot
6. 27) Java 10) Java
Java Java M N YARV Java 4) 6) No. SIG 0(PRO 34) Vol. 48 Ruby YARV Perl 12 ) Parrot 11 ) 15
2007 2    , 18) (2001). (2001).
 (PRO), Java Vol. 44, No. SIG 15 (PRO19), pp. 13–24 (2003). C 19) .. 20) ,        ,          : BSD UNIX , Vol. 36, No. 2, pp. 296–303 (1995). 21) pp. 515–521 (2003). 22) ACS, Vol. 44, No. SIG11(ACS3), pp. 215–225 (2003). 23) Ruby , Vol. 1, pp. 305–306 (2005). 67 24) ,  ’ YARV (PRO), Vol. 47, No. SIG 2(PRO28), pp. 57–73 (2006). 25)   (2002). ered harmful –, Linux Conference       , pp. 1–10 (2005). 27) : Vol. 16, No. 2, 3, pp. 1–19, 9–28 (1999). , 12 (     18 9 ) (     18 12  12 ( ) ACM 1997 2000 2004 ACM ( ) 2004 2006 ACM   IEEE