OSの講義の5.xの問題を解く
これが正解だぜ(どや)みたいなノリでは書いてないです、ただの平均的な技術力を持っているB2が解いているだけ
課題の取り組みをブログで書いてもいいという許可をもらった上で記事を書いてます
最新の課題内容であることや、答えが正しいかどうかは保証しません
このブログの情報で読者に何らかの不都合が生じても著者は責任は取らないです
5.1 Amdal 則を実測し可視化する
このページの問題を解く
golang と (Metal / Open CL / Cuda のうちの一つ) を使って以下の計算をして Amdahl則をグラフで可視化せよ。(他の例題でも良いが、面白いものであること) 3 ... n ( n は実験が現実的な整数 ) 間の素数を順次奇数で割っていくことで求める。 仕事がなくなったら、Worker が正しく停止する必要がある。すべての仕事が終わった後に正しく停止していることを説明せよ。 3 ... m,m+1 ... n のように分割し、Amdahl 則を実測したい。最初に m までを thread pool で実行し、それを終了を確認してから、残りを single thread で実行する。CPU 4 まで実測せよ。
アムダールの法則とは、「計算機の並列度をどれだけ上げても、計算時間が計算の並列化できない部分にかかる計算時間より短くなることはない」というもの。
golangの実装では、1からmまでの素数の判定の処理を「並列化できる部分」、m+1からnまでの素数の判定の処理を「並列化できない部分」というように表現してアムダールの法則を再現している。
package main
import (
"fmt"
"gonum.org/v1/plot"
"gonum.org/v1/plot/plotter"
"gonum.org/v1/plot/vg"
"math"
"sync"
"time"
)
func isPrime(number int) bool {
if number <= 1 {
return false
}
for i := 2; i <= int(math.Sqrt(float64(number))); i++ {
if number%i == 0 {
return false
}
}
return true
}
func worker(jobs <-chan int, results chan<- int, wg *sync.WaitGroup) {
defer wg.Done()
for number := range jobs {
if isPrime(number) {
results <- number
}
}
}
func calculatePrimesConcurrent(workerCount int, start int, end int) ([]int, time.Duration) {
jobs := make(chan int, end-start+1)
results := make(chan int, end-start+1)
var wg sync.WaitGroup
for w := 1; w <= workerCount; w++ {
wg.Add(1)
go worker(jobs, results, &wg)
}
startTime := time.Now()
for number := start; number <= end; number++ {
jobs <- number
}
close(jobs)
wg.Wait()
close(results)
primes := make([]int, 0)
for prime := range results {
primes = append(primes, prime)
}
return primes, time.Since(startTime)
}
func calculatePrimesSingleThread(start int, end int) ([]int, time.Duration) {
startTime := time.Now()
primes := make([]int, 0)
for number := start; number <= end; number++ {
if isPrime(number) {
primes = append(primes, number)
}
}
return primes, time.Since(startTime)
}
func main() {
m := 10000000
n := 20000000
workerCounts := []int{1, 2, 3, 4}
times := make([]time.Duration, len(workerCounts))
for i, workerCount := range workerCounts {
_, elapsedParallel := calculatePrimesConcurrent(workerCount, 3, m)
_, elapsedSingle := calculatePrimesSingleThread(m+1, n)
totalElapsed := elapsedParallel + elapsedSingle
times[i] = totalElapsed
fmt.Printf("Total time with %d worker(s): %s\n", workerCount, totalElapsed)
}
// Create a new plot for visualizing the results
p := plot.New()
p.Title.Text = "Performance comparison according to Amdahl's Law"
p.X.Label.Text = "Number of Workers"
p.Y.Label.Text = "Time (seconds)"
points := make(plotter.XYs, len(workerCounts))
for i, workerCount := range workerCounts {
points[i].X = float64(workerCount)
points[i].Y = times[i].Seconds()
}
line, pointsScatter, err := plotter.NewLinePoints(points)
if err != nil {
panic(err)
}
p.Add(line, pointsScatter)
p.Legend.Add("Worker times", line, pointsScatter)
// Save the plot to a SVG file.
if err := p.Save(6*vg.Inch, 8*vg.Inch, "amdahl.svg"); err != nil {
panic(err)
}
}
実行結果
$ go run prime_calculation.go Total time with 1 worker(s): 42.677063215s Total time with 2 worker(s): 38.473918247s Total time with 3 worker(s): 34.401609842s Total time with 4 worker(s): 30.953378576s
Workerの停止について
このコードでは、sync.WaitGroupとチャネルの終了が、全てのワーカーがタスクを完了した後に正しく停止することを保証する。wg.Wait()は全ワーカーがタスク終了を報告するまでメインゴルーチンの終了をブロックし、close(jobs)はワーカーにこれ以上待機するジョブが無いことを伝えるために使われる。これにより、全ワーカーは終了する。
5.2 PathFinderを使ったThreadの検証
このページの問題を解く
複数のJava の Thread が共有している文字列 String を調べて、Thread の実行の様子を調べよう。 interlave Server.stringWork() を実行する。 何回か実行して見て、動作が異なるかどうかを調べよう。
braunにsshする
$ ssh braun
singularityコンテナを立てる、sifファイルは先生が用意をしている
$ singularity shell --shell=/bin/zsh /mnt/ie-virsh/singularity/pathfinder/pathfinder.sif
gitlabからThreadTestを入れる
$ git clone https://gitlab.ie.u-ryukyu.ac.jp/os/ThreadTest $ cd ThreadTest
gradleでbuildする
$ gradle build
TestThreadを読む
package threadTest;
public class TestThread {
Server t1 = new Server();
Client t2 = new Client(t1);
Client t3 = new Client(t1);
public static void main(String arg[]) throws InterruptedException {
TestThread test = new TestThread();
test.test();
}
public void test() throws InterruptedException {
t2.start();
t3.start();
t2.join();
t3.join();
assert t1.count == 2 ;
System.err.println("testThread: count = "+t1.count);
}
}
どうやらマルチスレッドでのインクリメントをして結果があっているかどうかをテストするコードのようだ。
ソースコードを見るとわかるがスレッドセーフなコードではないため、最終的なインクリメントの結果が2ではなく1であることもある。
それをモデル検査で検出するのがこの課題の目的である。
$ /opt/jpf-core/bin/jpf +classpath=build/classes/java/main threadTest.TestThread
JavaPathfinder core system v8.0 (rev 1a704e1d6c3d92178504f8cdfe57b068b4e22d9c) - (C) 2005-2014 United States Government. All rights reserved.
====================================================== system under test
threadTest.TestThread.main()
====================================================== search started: 1/22/24, 4:39 AM
[WARNING] orphan NativePeer method: jdk.internal.misc.Unsafe.getUnsafe()Lsun/misc/Unsafe;
server-enter: count=0
server-leave: count=1
server-enter: count=1
server-leave: count=2
testThread: count = 2
server-enter: count=1
server-leave: count=2
server-enter: count=1
server-leave: count=2
server-enter: count=1
server-leave: count=2
server-leave: count=2
server-leave: count=2
server-leave: count=2
testThread: count = 2
server-leave: count=1
server-leave: count=1
server-enter: count=1
server-leave: count=1
server-leave: count=1
server-leave: count=2
server-leave: count=2
server-leave: count=2
server-enter: count=0
server-leave: count=1
server-leave: count=1
====================================================== error 1
gov.nasa.jpf.vm.NoUncaughtExceptionsProperty
java.lang.AssertionError
at threadTest.TestThread.test(TestThread.java:19)
at threadTest.TestThread.main(TestThread.java:10)
====================================================== snapshot #1
thread java.lang.Thread:{id:0,name:main,status:RUNNING,priority:5,isDaemon:false,lockCount:0,suspendCount:0}
call stack:
at threadTest.TestThread.test(TestThread.java:19)
at threadTest.TestThread.main(TestThread.java:10)
====================================================== results
error #1: gov.nasa.jpf.vm.NoUncaughtExceptionsProperty "java.lang.AssertionError at threadTest.TestThread..."
====================================================== statistics
elapsed time: 00:00:00
states: new=38,visited=15,backtracked=37,end=2
search: maxDepth=16,constraints=0
choice generators: thread=37 (signal=0,lock=1,sharedRef=20,threadApi=10,reschedule=6), data=0
heap: new=861,released=329,maxLive=527,gcCycles=48
instructions: 21676
max memory: 1024MB
loaded code: classes=92,methods=2349
====================================================== search finished: 1/22/24, 4:39 AM
このような感じでモデル検査が実行できる。
ちょっとやる気の問題で続きは君に任せようと思う。また今度。
