Haskell MVar：如何首先执行最短作业？ [英] Haskell MVar : How to execute shortest job first?

问题描述

当有多个线程正在等待写入MVar时，它们将以先进先出方式执行。我想根据最短的作业调度执行线程。

我已经累了使用MVar编码。这里的工作是计算斐波纳契数并写入MVar。第一个线程计算Fibonacci 30和第二个线程计算Fibonacci 10.由于计算Fibonacci 10的时间小于30，因此第二个线程应该首先执行。我没有从以下代码块获得所需的结果。

如何在Haskell中实现最短作业第一次调度（或可能使用Haskell STM）？

代码

 模块Main 
其中
 import Control.Parallel 
 import Control.Concurrent 
 
 import System.IO 
 
 
 nfib :: Int  - > Int 
 nfib n | n = 2 = 1 
 |否则= par n1（pseq n2（n1 + n2））
其中n1 = nfib（n-1）
 n2 = nfib（n-2）
 
 
类型MInt = MVar Int 
 
 updateMVar :: MInt  - > Int  - > IO（）
 updateMVar nv = do x1 < -  readMVar n 
 let y = nfib v 
 x2 < -  readMVar n 
如果x1 == x2 
 do t<  -  takeMVar n 
 putMVar ny 
 else return（）
 
 main :: IO（）
 main = do 
n < -  newEmptyMVar 
 putMVar n 0 
 
 forkIO（updateMVar n 30）
t < -  readMVar n 
 putStrLn（n is：++（show t））
 
 forkIO（updateMVar n 10）
t<  -  readMVar n 
 putStrLn（n is：++（show t））
  
 
 
 
 输出 
  n is：832040 
n is：55 
  
 
 
解决方案
要实现调度，您需要使用MVars和线程在一起。从空MVar开始。分叉您希望在后台运行的作业。主线程然后可以依次阻塞每个结果。最快的会来的。像这样：
  { - ＃LANGUAGE BangPatterns＃ - } 
 
 import Control.Parallel 
 import Control.Concurrent 
 
 import System.IO 
 
 nfib :: Int  - > Int 
 nfib n | n = 2 = 1 
 |否则= par n1（pseq n2（n1 + n2））
其中n1 = nfib（n-1）
 n2 = nfib（n-2）
 
 main :: （）
 main = do 
 result<  -  newEmptyMVar 
 
 forkIO $ do 
 let！x = nfib 40 
 putMVar result x 
 forkIO $ do 
 let！x = nfib 30 
 putMVar result x 
 
t<  -  takeMVar result 
 print $最快的结果是：++ show t 
t<  -  takeMVar results 
 print $最慢的结果是：++显示t 
  
请注意，使用bang模式来评估MVar外部的fibonacci调用是很重要的（不要简单地将未评估的thunk返回主线程）。 
 
 
 
使用线程运行时编译：
  $ ghc -o A --make A.hs -threaded -fforce-recomp -rtsopts 
 [1 of 1]编译Main（A.hs，Ao）
链接A.exe ... 
  
可在两个核心上运行：
  $ ./A.exe + RTS -N2 
最快的结果是：832040
最慢的结果是：102334155
  
生产力也很好（使用+ RTS -s查看运行时性能统计信息）。
 生产力89.3％的总用户，已经过去的总时间的178.1％
  
完成将其结果打印第一。主线程将阻塞，直到第二个线程完成。
 
 
 
主要的是利用MVar空/全语义来阻塞每个主线程子线程。
 
When more than one thread is waiting to write an MVar, they are executed in first-in first-out scheme. I want to execute thread as per shortest job scheduling. 

I have tired to code this using MVar. Here job is to calculate a Fibonacci number and write a MVar. 1st thread calculates Fibonacci 30 and 2nd thread calculates Fibonacci 10. As time taken for calculating Fibonacci 10 is less than 30, thus 2nd thread should execute first. I a not getting the desired result from the following block of code. 

How to implement shortest job first scheduling in Haskell (or may be using Haskell STM)?

Code
module Main
where
import Control.Parallel
import Control.Concurrent

import System.IO


nfib :: Int -> Int
nfib n | n <= 2 = 1
       | otherwise = par n1 (pseq n2 (n1 + n2 ))
                 where n1 = nfib (n-1)
                       n2 = nfib (n-2)


type MInt = MVar Int

updateMVar :: MInt -> Int -> IO ()
updateMVar n v = do x1 <- readMVar n
        let y = nfib v
        x2 <- readMVar n            
        if x1 == x2 
        then do t <- takeMVar n 
            putMVar n y
        else return()

main :: IO ()
main = do
 n <- newEmptyMVar
 putMVar n 0

 forkIO(updateMVar n 30)
 t <- readMVar n
 putStrLn("n is : " ++  (show t))   

 forkIO(updateMVar n 10)
 t <- readMVar n
 putStrLn("n is : " ++  (show t))
Output
n is : 832040
n is : 55

解决方案
To implement scheduling you need to use MVars and threads together. Start with an empty MVar. Fork the jobs you wish to run in the background. The main thread can then block on each result in turn. The fastest will come first. Like so:
{-# LANGUAGE BangPatterns #-}

import Control.Parallel
import Control.Concurrent

import System.IO

nfib :: Int -> Int
nfib n | n <= 2     = 1
       | otherwise  = par n1 (pseq n2 (n1 + n2 ))
                 where n1 = nfib (n-1)
                       n2 = nfib (n-2)

main :: IO ()
main = do
    result <- newEmptyMVar

    forkIO $ do
        let !x = nfib 40
        putMVar result x
    forkIO $ do
        let !x = nfib 30
        putMVar result x

    t      <- takeMVar result
    print $ "Fastest result was: " ++ show t
    t      <- takeMVar result
    print $ "Slowest result was: " ++ show t
Note that it is important to use bang patterns to evaluate the fibonacci calls outside of the MVar (don't want to simply return an unevaluated thunk to the main thread). 

Compile with the threaded runtime:
$ ghc -o A --make A.hs -threaded  -fforce-recomp -rtsopts
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A.exe ...
And run on two cores:
$ ./A.exe  +RTS -N2
"Fastest result was: 832040"
"Slowest result was: 102334155"
Productivity is pretty good as well (use +RTS -s to see runtime performance statistics).
Productivity  89.3% of total user, 178.1% of total elapsed
The first thread to finish will have its result printed first. The main thread will then block until the second thread is done.

The main thing is to take advantage of MVar empty/full semantics to block the main thread on each of the children threads.

                        
这篇关于Haskell MVar：如何首先执行最短作业？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！