3

我对 Go 很陌生,我的代码中有一件事我不明白。我写了一个简单的冒泡排序算法(我知道它不是很有效;))。现在我想启动 3 个 GoRoutines。每个线程都应该独立于其他线程对他的数组进行排序。完成后,函数。应该打印一个“完成”的消息。

这是我的代码:

package main 

import (
    "fmt"
    "time" //for time functions e.g. Now()
    "math/rand" //for pseudo random numbers
)


/* Simple bubblesort algorithm*/
func bubblesort(str string, a []int) []int {
    for n:=len(a); n>1; n-- {
        for i:=0; i<n-1; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i] //swap
            }
        }
    }
    fmt.Println(str+" done") //done message
    return a
}

/*fill slice with pseudo numbers*/
func random_fill(a []int) []int {
    for i:=0; i<len(a); i++ { 
        a[i] = rand.Int()
    }
    return a
}

func main() {
   rand.Seed( time.Now().UTC().UnixNano()) //set seed for rand.

   a1 := make([]int, 34589) //create slice
   a2 := make([]int, 42) //create slice
   a3 := make([]int, 9999) //create slice

   a1 = random_fill(a1) //fill slice
   a2 = random_fill(a2) //fill slice
   a3 = random_fill(a3) //fill slice
   fmt.Println("Slices filled ...")

   go bubblesort("Thread 1", a1) //1. Routine Start
   go bubblesort("Thread 2", a2) //2. Routine Start
   go bubblesort("Thread 3", a3) //3. Routine Start
   fmt.Println("Main working ...")

   time.Sleep(1*60*1e9) //Wait 1 minute for the "done" messages
}

这就是我得到的:

Slices filled ...
Main working ...
Thread 1 done
Thread 2 done
Thread 3 done

线程 2 不应该先完成,因为他的切片是最小的吗?似乎所有线程都在等待其他线程完成,因为“完成”消息同时出现,无论切片有多大..

我的脑虫在哪里?=)

提前致谢。

*编辑:将“time.Sleep(1)”放入bubblesort func的for循环中时。它似乎工作..但我想用这段代码记录不同机器上的持续时间(我知道,我必须改变随机的东西),所以睡眠会伪造结果。

4

3 回答 3

9

事实上,对于你的 goroutine 的执行顺序没有任何保证。

但是,如果您通过明确让 2 个处理器内核运行来强制执行真正的并行处理:

import (
    "fmt"
    "time" //for time functions e.g. Now()
    "math/rand" //for pseudo random numbers
    "runtime"
)
...

func main() {
   runtime.GOMAXPROCS(2)

   rand.Seed( time.Now().UTC().UnixNano()) //set seed for rand.
...

然后你会得到预期的结果:

Slices filled ...
Main working ...
Thread 2 done
Thread 3 done
Thread 1 done

最好的祝福

于 2013-01-18T13:01:27.823 回答
3

重要的是在整个潜在的长时间运行的工作负载完成之前将处理器“让给”给其他进程的能力。这在单核上下文或多核上下文中也适用(因为Concurrency 与 Parallelism 不同)。

这正是runtime.Gosched()函数所做的:

Gosched 产生处理器,允许其他 goroutine 运行。它不会暂停当前的 goroutine,因此会自动恢复执行。

请注意,“上下文切换”不是免费的:每次都会花费一些时间。

  • 在我的机器上没有让步,你的程序在 5.1 秒内运行。
  • 如果你在外循环(for n:=len(a); n>1; n--)中让步,它会在 5.2 秒内运行:开销很小。
  • 如果你在内部循环(for i:=0; i<n-1; i++)中让步,它会在 61.7 秒内运行:巨大的开销!

这是正确产生的修改后的程序,开销很小:

package main

import (
    "fmt"
    "math/rand"
    "runtime"
    "time"
)

/* Simple bubblesort algorithm*/
func bubblesort(str string, a []int, ch chan []int) {
    for n := len(a); n > 1; n-- {
        for i := 0; i < n-1; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i] //swap
            }
        }
        runtime.Gosched() // yield after part of the workload
    }
    fmt.Println(str + " done") //done message
    ch <- a
}

/*fill slice with pseudo numbers*/
func random_fill(a []int) []int {
    for i := 0; i < len(a); i++ {
        a[i] = rand.Int()
    }
    return a
}

func main() {
    rand.Seed(time.Now().UTC().UnixNano()) //set seed for rand.

    a1 := make([]int, 34589) //create slice
    a2 := make([]int, 42)    //create slice
    a3 := make([]int, 9999)  //create slice

    a1 = random_fill(a1) //fill slice
    a2 = random_fill(a2) //fill slice
    a3 = random_fill(a3) //fill slice
    fmt.Println("Slices filled ...")

    ch1 := make(chan []int) //create channel of result
    ch2 := make(chan []int) //create channel of result
    ch3 := make(chan []int) //create channel of result

    go bubblesort("Thread 1", a1, ch1) //1. Routine Start
    go bubblesort("Thread 2", a2, ch2) //2. Routine Start
    go bubblesort("Thread 3", a3, ch3) //3. Routine Start
    fmt.Println("Main working ...")

    <-ch1 // Wait for result 1
    <-ch2 // Wait for result 2
    <-ch3 // Wait for result 3
}

输出 :

Slices filled ...
Main working ...
Thread 2 done
Thread 3 done
Thread 1 done

正如我之前评论中所建议的,我还使用通道来实现集合点。

最好的祝福 :)

于 2013-01-21T11:05:32.353 回答
3

自 Go 1.2 发布以来,原程序无需修改即可正常运行。 您可以在Playground中尝试一下。

这在Go 1.2 发行说明中进行了解释:

在以前的版本中,一个永远循环的 goroutine 可能会饿死同一线程上的其他 goroutine,当 GOMAXPROCS 只提供一个用户线程时,这是一个严重的问题。在 Go 1.2 中,这部分得到了解决:调度程序在进入函数时偶尔被调用。

于 2013-12-30T09:04:48.950 回答