Skip to main content

Example - Multiprocessor Scheduling with precedence

The feasible interval (release Time and Deadline) of each task in the precedence graph is given next to its name. The execution time for T1,T2....T7 is respectively 2, 2, 3, 1, 1, 1, 3.
The priority is in the following order, T1>T2>T3...>T7 ( T1 being the highest priority and T7 being the Lowest Priority)
a) What is the minimum number of processors required for feasibility?

Answer
Single Processor




At time 0, T2 and T6 are ready, Since T2 is an independant task it can scheduled.
At time 1, T2 is running and T3,T5 and T6 are ready (but all are dependant tasks)
At time 2, T2 completes, T1, T3,T5 and T6 are ready (T1 is starting because of high priority)
At time 3, T1 is running,
At time 4, T1 completes, T3, T4, T5 and T6 are ready.. Here T3 is ready to execute because of high priority and as well it satisfies the precedence constraint.
At time 6, T7 is also ready along with T4, T5 and T6.

Except T5 all the tasks meets their deadlines.
So, having one processor is not a feasible schedule..

Let us try for two processors

Two Processors


In the above schedule, all the tasks meets their deadline (so this is a feasible schedule)
Ans: The minimum number of processors required by the above task set is 2.

Comments

Popular posts from this blog

Installing ns3 in Ubuntu 22.04 | Complete Instructions

In this post, we are going to see how to install ns-3.36.1 in Ubuntu 22.04. You can follow the video for complete details Tools used in this simulation: NS3 version ns-3.36.1  OS Used: Ubuntu 22.04 LTS Installation of NS3 (ns-3.36.1) There are some changes in the ns3 installation procedure and the dependencies. So open a terminal and issue the following commands Step 1:  Prerequisites $ sudo apt update In the following packages, all the required dependencies are taken care and you can install all these packages for the complete use of ns3. $ sudo apt install g++ python3 python3-dev pkg-config sqlite3 cmake python3-setuptools git qtbase5-dev qtchooser qt5-qmake qtbase5-dev-tools gir1.2-goocanvas-2.0 python3-gi python3-gi-cairo python3-pygraphviz gir1.2-gtk-3.0 ipython3 openmpi-bin openmpi-common openmpi-doc libopenmpi-dev autoconf cvs bzr unrar gsl-bin libgsl-dev libgslcblas0 wireshark tcpdump sqlite sqlite3 libsqlite3-dev  libxml2 libxml2-dev libc6-dev libc6-dev-i386 libc...

Installation of NS2 (ns-2.35) in Ubuntu 20.04

Installation of NS2 (ns-2.35) in Ubuntu 20.04 LTS Step 1: Install the basic libraries like      $] sudo apt install build-essential autoconf automake libxmu-dev Step 2: install gcc-4.8 and g++-4.8 open the file using sudo mode $] sudo nano /etc/apt/sources.list Include the following line deb http://in.archive.ubuntu.com/ubuntu bionic main universe $] sudo apt update $] sudo apt install gcc-4.8 g++-4.8 Step 3:  Unzip the ns2 packages to home folder $] tar zxvf ns-allinone-2.35.tar.gz $] cd ns-allinone-2.35/ns-2.35 Modify the following make files. ~ns-2.35/Makefile.in Change @CC@ to gcc-4.8 change @CXX@ to g++-4.8 ~nam-1.15/Makefile.in ~xgraph-12.2/Makefile.in ~otcl-1.14/Makefile.in Change in all places  @CC@ to gcc-4.8 @CPP@ or @CXX@ to g++-4.8 open the file: ~ns-2.35/linkstate/ls.h Change at the Line no 137  void eraseAll() { erase(baseMap::begin(), baseMap::end()); } to This void eraseAll() { this->erase(baseMap::begin(), baseMap::end()); } All changes ...

Simulation of URDF, Gazebo and Rviz | ROS Noetic Tutorial 8

Design a User-defined robot of your choice (or you can use the URDF file) and enable the LIDAR Scanner so that any obstacle placed on the path of the light scan will cut the light rays. Visualize the robot in the Gazebo workspace, and also show the demonstration in RViz.   (NB: Gain knowledge on wiring URDF file and .launch file for enabling any user-defined robot to get launched in the gazebo platform.) SLAM : One of the most popular applications of ROS is SLAM(Simultaneous Localization and Mapping). The objective of the SLAM in mobile robotics is to construct and update the map of an unexplored environment with the help of the available sensors attached to the robot which will be used for exploring. URDF: Unified Robotics Description Format, URDF, is an XML specification used in academia and industry to model multibody systems such as robotic manipulator arms for manufacturing assembly lines and animatronic robots for amusement parks. URDF is especially popular with users of the ...