*** 作系统作业调度问题，请具体详细解答一下每一个作业的开始，完成，

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

例：设n=3，考虑以下实例：

这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。

限界函数

批处理作扮厅业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。

在作业调度问相应的排列空间树中，每一个节点E都对应于一个已安排的作业集。以该节点为根的子树中所含叶节点的完成时间和可表示为：

设|M|=r，且L是以节点E为根的子树中的叶节点，相应的作业调度为{pk,k=1,2,……n}，其中pk是第k个安排的作业。如果从节点E到叶节点L的路上，每一个作业pk在机器1上完成处理后都能立即在机器2上简渗开始处理，即从pr+1开始，机器1没有空闲时间，则对于该叶节点L有：

注：(n-k+1)t1pk,因为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上t1pk。

如果不能做到上面这一点，则s1只会增加，从而有：。

类似地，如果从节点E开始到节点L的路上，从作业pr+1开始，机器2没有空闲时间，则：

同理拦缺脊可知，s2是的下界。由此得到在节点E处相应子树中叶节点完成时间和的下界是：

注意到如果选择Pk，使t1pk在k>=r+1时依非减序排列，S1则取得极小值。同理如果选择Pk使t2pk依非减序排列，则S2取得极小值。

这可以作为优先队列式分支限界

大数据的时代， 到处张嘴闭嘴唤握都是Hadoop, MapReduce, 不跟上时代怎么行？ 可是对一个hadoop的新手， 写一个属于自己的MapReduce程序还是小有点难度的， 需要建立一个maven项目， 还要搞清楚和芦庆各种库的依赖， 再加上编译运行， 基本上头大两圈了吧。 这也使得很多只是想简单了解一下MapReduce的人望而却步。

本文会教你如何用最快最简单的方法编写和运行一个属于自己的MapReduce程序， let's go!

首先有两个前提：

1. 有一个已经可以运行的hadoop 集群（也可以是伪分布系统)， 上面的hdfs和mapreduce工作正常 （这个真的哗轮是最基本的了， 不再累述， 不会的请参考 http://hadoop.apache.org/docs/current/)

2. 集群上安装了JDK (编译运行时会用到）

正式开始

1. 首先登入hadoop 集群里面的一个节点， 创建一个java源文件， 偷懒起见， 基本盗用官方的word count (因为本文的目的是教会你如何快编写和运行一个MapReduce程序， 而不是如何写好一个功能齐全的MapReduce程序）

内容如下：

import java.io.IOException

import java.util.StringTokenizer

import org.apache.hadoop.conf.Configuration

import org.apache.hadoop.fs.Path

import org.apache.hadoop.io.IntWritable

import org.apache.hadoop.io.Text

import org.apache.hadoop.mapreduce.Job

import org.apache.hadoop.mapreduce.Mapper

import org.apache.hadoop.mapreduce.Reducer

import org.apache.hadoop.mapreduce.lib.input.FileInputFormat

import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat

import org.apache.hadoop.util.GenericOptionsParser

public class myword {

public static class TokenizerMapper

extends Mapper<Object, Text, Text, IntWritable>{

private final static IntWritable one = new IntWritable(1)

private Text word = new Text()

public void map(Object key, Text value, Context context

) throws IOException, InterruptedException {

StringTokenizer itr = new StringTokenizer(value.toString())

while (itr.hasMoreTokens()) {

word.set(itr.nextToken())

context.write(word, one)

}

}

}

public static class IntSumReducer

extends Reducer<Text,IntWritable,Text,IntWritable>{

private IntWritable result = new IntWritable()

public void reduce(Text key, Iterable<IntWritable>values,

Context context

) throws IOException, InterruptedException {

int sum = 0

for (IntWritable val : values) {

sum += val.get()

}

result.set(sum)

context.write(key, result)

}

}

public static void main(String[] args) throws Exception {

Configuration conf = new Configuration()

String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs()

if (otherArgs.length != 2) {

System.err.println('Usage: wordcount <in><out>')

System.exit(2)

}

Job job = new Job(conf, 'word count')

job.setJarByClass(myword.class)

job.setMapperClass(TokenizerMapper.class)

job.setCombinerClass(IntSumReducer.class)

job.setReducerClass(IntSumReducer.class)

job.setOutputKeyClass(Text.class)

job.setOutputValueClass(IntWritable.class)

FileInputFormat.addInputPath(job, new Path(otherArgs[0]))

FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]))

System.exit(job.waitForCompletion(true) ? 0 : 1)

}

}

与官方版本相比， 主要做了两处修改

1） 为了简单起见，去掉了开头的 package org.apache.hadoop.examples

2） 将类名从 WordCount 改为 myword, 以体现是我们自己的工作成果 :)

2. 拿到hadoop 运行的class path, 主要为编译所用

运行命令

hadoop classpath

保存打出的结果，本文用的hadoop 版本是Pivotal 公司的Pivotal hadoop, 例子：

/etc/gphd/hadoop/conf:/usr/lib/gphd/hadoop/lib/*:/usr/lib/gphd/hadoop/.//*:/usr/lib/gphd/hadoop-hdfs/./:/usr/lib/gphd/hadoop-hdfs/lib/*:/usr/lib/gphd/hadoop-hdfs/.//*:/usr/lib/gphd/hadoop-yarn/lib/*:/usr/lib/gphd/hadoop-yarn/.//*:/usr/lib/gphd/hadoop-mapreduce/lib/*:/usr/lib/gphd/hadoop-mapreduce/.//*::/etc/gphd/pxf/conf::/usr/lib/gphd/pxf/pxf-core.jar:/usr/lib/gphd/pxf/pxf-api.jar:/usr/lib/gphd/publicstage:/usr/lib/gphd/gfxd/lib/gemfirexd.jar::/usr/lib/gphd/zookeeper/zookeeper.jar:/usr/lib/gphd/hbase/lib/hbase-common.jar:/usr/lib/gphd/hbase/lib/hbase-protocol.jar:/usr/lib/gphd/hbase/lib/hbase-client.jar:/usr/lib/gphd/hbase/lib/hbase-thrift.jar:/usr/lib/gphd/hbase/lib/htrace-core-2.01.jar:/etc/gphd/hbase/conf::/usr/lib/gphd/hive/lib/hive-service.jar:/usr/lib/gphd/hive/lib/libthrift-0.9.0.jar:/usr/lib/gphd/hive/lib/hive-metastore.jar:/usr/lib/gphd/hive/lib/libfb303-0.9.0.jar:/usr/lib/gphd/hive/lib/hive-common.jar:/usr/lib/gphd/hive/lib/hive-exec.jar:/usr/lib/gphd/hive/lib/postgresql-jdbc.jar:/etc/gphd/hive/conf::/usr/lib/gphd/sm-plugins/*:

3. 编译

运行命令

javac -classpath xxx ./myword.java

xxx部分就是上一步里面取到的class path

运行完此命令后， 当前目录下会生成一些.class 文件， 例如：

myword.class myword$IntSumReducer.class myword$TokenizerMapper.class

4. 将class文件打包成.jar文件

运行命令

jar -cvf myword.jar ./*.class

至此, 目标jar 文件成功生成

5. 准备一些文本文件， 上传到hdfs, 以做word count的input

例子：

随意创建一些文本文件， 保存到mapred_test 文件夹

运行命令

hadoop fs -put ./mapred_test/

确保此文件夹成功上传到hdfs 当前用户根目录下

6. 运行我们的程序

运行命令

hadoop jar ./myword.jar myword mapred_test output

顺利的话， 此命令会正常进行， 一个MapReduce job 会开始工作， 输出的结果会保存在 hdfs 当前用户根目录下的output 文件夹里面。

至此大功告成！

如果还需要更多的功能， 我们可以修改前面的源文件以达到一个真正有用的MapReduce job。

但是原理大同小异， 练手的话， 基本够了。

一个抛砖引玉的简单例子， 欢迎板砖。

转载

---