Home » SQL & PL/SQL » SQL & PL/SQL » Round Robin implementaion through sql script (Oracle 10g)
Round Robin implementaion through sql script [message #472236] |
Thu, 19 August 2010 06:11  |
virmahi
Messages: 266 Registered: April 2008 Location: India
|
Senior Member |
|
|
Hi,
I have to implement round robin algorothim in sql script for allocation of some items to another entity. Not really sure how to do that and if there would be locks while selecting the one which is already being updated and so...!
Please give me some hint as how to go about it when the number of users involved would be very high to whom the items would be allocated in round robin function.
Regards,
Mahi
|
|
|
|
|
|
Re: Round Robin implementaion through sql script [message #472312 is a reply to message #472236] |
Thu, 19 August 2010 16:49   |
Solomon Yakobson
Messages: 3305 Registered: January 2010 Location: Connecticut, USA
|
Senior Member |
|
|
virmahi wrote on Thu, 19 August 2010 07:11Hi,
I have to implement round robin algorothim in sql script for allocation of some items to another entity.
Are you talking about distributing some quantity as even as possible? If so:
variable amount_to_distribute number
exec :amount_to_distribute := 10;
select deptno,
trunc(:amount_to_distribute / count(deptno) over()) +
case
when mod(:amount_to_distribute,count(deptno) over()) >= row_number() over(order by deptno) then 1
else 0
end amount
from dept
order by deptno
/
DEPTNO AMOUNT
------------------------- -------------------------
10 3
20 3
30 2
40 2
SQL> exec :amount_to_distribute := 19;
PL/SQL procedure successfully completed.
SQL> /
DEPTNO AMOUNT
------------------------- -------------------------
10 5
20 5
30 5
40 4
SQL>
SY.
|
|
|
Re: Round Robin implementaion through sql script [message #472604 is a reply to message #472312] |
Mon, 23 August 2010 00:07   |
virmahi
Messages: 266 Registered: April 2008 Location: India
|
Senior Member |
|
|
I am sorry, I couldn't explain it. Please see the table scripts
Create table lead(Lead_id number, allocated_fsc varchar2(12),is_free char);
Create table fsc(fsc_id varchar2(12), allocated_lead number, active char default 1);
insert into lead values(1,'',1);
insert into lead values(2,'',1);
insert into lead values(3,'',1);
insert into lead values(4,'',1);
insert into lead values(5,'',1);
insert into lead values(6,'',1);
insert into lead values(7,'',1);
insert into lead values(8,'',1);
insert into lead values(9,'',1);
insert into lead values(10,'',1);
insert into fsc values('FSC1',null,1);
insert into fsc values('FSC2',null,1);
insert into fsc values('FSC3',null,1);
insert into fsc values('FSC4',null,1);
LEAD_ID FSC
---------- --------
1 FSC1
2 FSC2
3 FSC3
4 FSC4
5
6
7
8
9
10
The logic is that there should be equal distribution of Lead_ID among the FSCs using round robin algorithm.
There can be simultaneous LEADs coming in the system (web application with multiple sessions) to be allocated to FSCs.
When there is only one request ..for eg one LEAD comes in with LEAD_ID 1, then it would be assigned to the FSC1 and the 'FSC1' would be updated with the LEAD_ID value.
There would be an update statement for assignment of LEAD to FSC and when the next LEAD LEAD_ID 2 comes it would be assigned to the FSC2 in round robin function.
But when multiple LEADS come in system though various sessions and in that case assignment of FSCs to LEAD_IDs in round robin is a challenge.
For eg, when Lead_ID 1,2,3,4 comes together in one go, then FSC1 would be assigned to them all, but only one of them would get updated.
And once updated it would be commited too. And then the FSC2 should be updated with the one in queue.
Not sure how to handle the assignment of FSC when there is simultaneous requests for FSC by multiple LEAD_ID at the same time. There may be case when LEAD_ID 1,2,3,4 all request and FSC1 is set for the assignment in different sessions logged in by LEAD_IDs.
How to handle the circumstance so that the FSCs are allocated in fair order to LEAD_IDs with no blocking.
When there is an update done for one LEAD by one FSC and before the commit is done, the other session might be doing the same thing.
Please suggest as how to handle such situation.
[Updated on: Mon, 23 August 2010 02:26] Report message to a moderator
|
|
|
|
Re: Round Robin implementaion through sql script [message #472735 is a reply to message #472660] |
Mon, 23 August 2010 09:26   |
 |
Alessandro Rossi
Messages: 166 Registered: September 2008 Location: Rome
|
Senior Member |
|
|
You've been quite parsimonious with that description!
And by the different definitions of Round Robin around the net, your request doesn't match with any of them. Not even the Round Robing Scheduling (that I mentioned before) could be next to it because it is based on suspension and resumption of a process witch shouldn't be compatible with your environment probably.
I suppose you're probably facing with a resource contention problem where you have a limited pool of resources to be allocated to the incoming requests, but it's just a supposition I had after interpreting the steps you described to solve your problem(in a probably wrong way!).
If so I advice you to leave the idea to implement a solution using SQL or a Database Server (it's not built for that).
And, also if I supposed a wrong case, describe better what you should effectively do because it's not very clear.
Don't pretend that others, also if better skilled than you, could be able to solve your problem without knowing it!
[Updated on: Mon, 23 August 2010 09:27] Report message to a moderator
|
|
|
Re: Round Robin implementaion through sql script [message #472750 is a reply to message #472660] |
Mon, 23 August 2010 12:41   |
 |
LKBrwn_DBA
Messages: 487 Registered: July 2003 Location: WPB, FL
|
Senior Member |
|
|
virmahi wrote on Mon, 23 August 2010 04:14Please look into the given scenario and suggest me something. I am stuck as how to handle the multiple session updations using round robin.
The scenario you are describing looks more like a "queuing" issue than "round robin" resource allocation.
1) Leads arrive ....
2) You assign to "next available" fsc
3) In no fsc is available, the lead remains in the queue.
4) When fsc "commits" lead, it becomes available.
[Updated on: Mon, 23 August 2010 12:52] by Moderator Report message to a moderator
|
|
|
Re: Round Robin implementaion through sql script [message #472796 is a reply to message #472750] |
Mon, 23 August 2010 23:47   |
virmahi
Messages: 266 Registered: April 2008 Location: India
|
Senior Member |
|
|
The scenario you are describing looks more like a "queuing" issue than "round robin" resource allocation.
May be I am not clear...but the main perpose of the logic is to maintain a fair distribution of LEADS among FSCs.
LEADs are opportunities generated by telesales or when some one visits a branch of insurance company. So the generated leads are sent to the system via webservices. They can be many in number at a time.
The FSCs are officers who process the LEADS. If there are 4 FSCs then they all should get LEADs in a fair way equally so Round Robin algorithm is required.
Had the number of LEADs coming been only 1 then it would have been assigned to FSC1 and if after sometime another LEAD comes t would get assigned to FSC2. But there will be simultaneous LEADs coming in system to request a FSC and to get updated/mapped to a FSC. So a case can be that LEAD1, LEAD2, LEAD3 will try to update with FSC1 at the same time.
One Lead would be assigned to FSC1, next LEAD to FSC2, FSC3, FSC4, and then to FSC1, FSC2....! while all LEADS who came in system at one point of time would be trying to mapp with the FSC1.
[Updated on: Mon, 23 August 2010 23:49] Report message to a moderator
|
|
|
|
|
|
Re: Round Robin implementaion through sql script [message #472971 is a reply to message #472953] |
Wed, 25 August 2010 02:42   |
 |
Alessandro Rossi
Messages: 166 Registered: September 2008 Location: Rome
|
Senior Member |
|
|
monasingh wrote on Wed, 25 August 2010 06:17To:Alessandro Rossi
The Leads needs to be mapped with the FSCs whose turn comes up as per Round Robin.
To do so the mutex on the Requests Queue of the solution I described before should be handled with a supplementary queue. In this way the FCS as soon as it finishes its job en-queues its self in that supplementary queue to pull its request whet it will be its turn.
monasingh wrote on Wed, 25 August 2010
Are you sure Round Robin is not possible in oracle database using any script?
The solution of this problem doesn't need a SQL database, but it needs a service with Queuing features.
Oracle database has the Streams and AQ feature anyway, witch is a component common to other Oracle products too. It's not a SQL feature, but a component of the Oracle products with PL/SQL, Java and other interfaces, to implement a queueing service.
Anyway the reasons why I said that a database is not built for this purpose are that:
- There is no need to store volatile structures into physical memory and a database can just use it, there are some memory structures too on Oracle, but they're very limited.
- There are no structures that could optimally implement a queue in a database.
Bye Alessandro
|
|
|
|
Re: Round Robin implementaion through sql script [message #473034 is a reply to message #472988] |
Wed, 25 August 2010 09:18   |
 |
Alessandro Rossi
Messages: 166 Registered: September 2008 Location: Rome
|
Senior Member |
|
|
If you don't say anything about the exact environment you're trying to configure (Application Server in use, kind of web services and everything about it), it would be really hard to try helping you.
If I would have to develop something for it I opt to for a java solution like this
import java.util.*;
import java.util.concurrent.*;
public class TestRR {
private static LinkedBlockingQueue<LEADRequest> requests;
private static LinkedBlockingQueue<FSCSServer> processes;
public static int FSCSs = 4;
public static synchronized void print(String m) {
System.out.println(Calendar.getInstance().getTime()+":"+m);
}
public static class LEADRequest {
int elapsedTime;
private static int lastid = 0;
public int id=lastid++;
public LEADRequest(int time) {
print("generating LEAD"+id);
elapsedTime = time;
}
public void setElapsedTime(int t) {
elapsedTime = t;
}
public int getElapsedTime() {
return elapsedTime;
}
public int getId() {
return id;
}
}
public static class FSCSServer extends Thread{
public void print(String s) {
TestRR.print(String.format("FSCS_%d :%s",id,s));
}
private static int lastid = 0;
public int id=lastid++;
LEADRequest currRequest;
public void elaborate() throws InterruptedException {
print(String.format("to process LEAD_%d",currRequest.getId()));
if (currRequest.getElapsedTime() > 0 ) {
sleep(currRequest.getElapsedTime());
}
else {
processing = false;
}
print(String.format("processed LEAD_%d",currRequest.getId()));
}
private boolean processing = true;
public void run() {
print("Started");
synchronized (this) {
try {
while (processing) {
wait();
currRequest = requests.take();
elaborate();
processes.put(this);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
print("Halted");
}
}
public static void main(String[] args) throws InterruptedException {
processes = new LinkedBlockingQueue<FSCSServer>();
requests = new LinkedBlockingQueue<LEADRequest>();
int reqTimes[] = {
10,5,2,4,9,20,3,7,8,1,6,8,2,0,0,0,0,0,0,0
};
int pauses[] = {
0,1,0,0,0,9,0,0,0,0,0,20
};
for (int i = 0; i < 4; i++) {
FSCSServer s = new FSCSServer();
s.start();
processes.put(s);
}
print("Start");
for (int i = 0; i < reqTimes.length; i++) {
requests.put(new LEADRequest(reqTimes[i]*100));
FSCSServer s = processes.take();
synchronized (s) {
s.notify();
}
if (i < pauses.length) {
Thread.sleep(pauses[i]*100);
}
}
print("Stop");
}
}
In this sample I'm en-queuing a succession of requests (like your LEADS) that should have an elapsed time of the corresponding value on the array reqTimes ( in tenth of seconds ) and that should have a pause between the generation of a request and the following one of the corresponding value in the array pauses ( in tenth of seconds ).
The duration of the requests here is
10,5,2,4,9,20,3,7,8,1,6,8,2,0,0,0,0,0,0,0
where 0 indicates a request that kills the process that elaborates it.
And time between one request generation and the following is
0,1,0,0,0,9,0,0,0,0,0,20
where 0 indicates that the following request will be generated at the same time of it.
This is the spool of that execution:
Wed Aug 25 16:01:24 CEST 2010:Start
Wed Aug 25 16:01:24 CEST 2010:FSCS_0 :Started
Wed Aug 25 16:01:24 CEST 2010:FSCS_1 :Started
Wed Aug 25 16:01:24 CEST 2010:FSCS_3 :Started
Wed Aug 25 16:01:24 CEST 2010:FSCS_2 :Started
Wed Aug 25 16:01:24 CEST 2010:generating LEAD0
Wed Aug 25 16:01:24 CEST 2010:generating LEAD1
Wed Aug 25 16:01:24 CEST 2010:FSCS_0 :to process LEAD_0
Wed Aug 25 16:01:24 CEST 2010:FSCS_1 :to process LEAD_1
Wed Aug 25 16:01:24 CEST 2010:generating LEAD2
Wed Aug 25 16:01:24 CEST 2010:FSCS_2 :to process LEAD_2
Wed Aug 25 16:01:24 CEST 2010:generating LEAD3
Wed Aug 25 16:01:24 CEST 2010:FSCS_3 :to process LEAD_3
Wed Aug 25 16:01:24 CEST 2010:generating LEAD4
Wed Aug 25 16:01:24 CEST 2010:FSCS_2 :processed LEAD_2
Wed Aug 25 16:01:24 CEST 2010:generating LEAD5
Wed Aug 25 16:01:24 CEST 2010:FSCS_2 :to process LEAD_4
Wed Aug 25 16:01:25 CEST 2010:FSCS_1 :processed LEAD_1
Wed Aug 25 16:01:25 CEST 2010:FSCS_1 :to process LEAD_5
Wed Aug 25 16:01:25 CEST 2010:FSCS_3 :processed LEAD_3
Wed Aug 25 16:01:25 CEST 2010:FSCS_0 :processed LEAD_0
Wed Aug 25 16:01:25 CEST 2010:FSCS_2 :processed LEAD_4
Wed Aug 25 16:01:25 CEST 2010:generating LEAD6
Wed Aug 25 16:01:25 CEST 2010:generating LEAD7
Wed Aug 25 16:01:25 CEST 2010:FSCS_3 :to process LEAD_6
Wed Aug 25 16:01:25 CEST 2010:generating LEAD8
Wed Aug 25 16:01:25 CEST 2010:FSCS_0 :to process LEAD_7
Wed Aug 25 16:01:25 CEST 2010:generating LEAD9
Wed Aug 25 16:01:25 CEST 2010:FSCS_2 :to process LEAD_8
Wed Aug 25 16:01:26 CEST 2010:FSCS_3 :processed LEAD_6
Wed Aug 25 16:01:26 CEST 2010:generating LEAD10
Wed Aug 25 16:01:26 CEST 2010:FSCS_3 :to process LEAD_9
Wed Aug 25 16:01:26 CEST 2010:FSCS_3 :processed LEAD_9
Wed Aug 25 16:01:26 CEST 2010:generating LEAD11
Wed Aug 25 16:01:26 CEST 2010:FSCS_3 :to process LEAD_10
Wed Aug 25 16:01:26 CEST 2010:FSCS_0 :processed LEAD_7
Wed Aug 25 16:01:26 CEST 2010:FSCS_0 :to process LEAD_11
Wed Aug 25 16:01:26 CEST 2010:FSCS_2 :processed LEAD_8
Wed Aug 25 16:01:26 CEST 2010:FSCS_3 :processed LEAD_10
Wed Aug 25 16:01:27 CEST 2010:FSCS_1 :processed LEAD_5
Wed Aug 25 16:01:27 CEST 2010:FSCS_0 :processed LEAD_11
Wed Aug 25 16:01:28 CEST 2010:generating LEAD12
Wed Aug 25 16:01:28 CEST 2010:generating LEAD13
Wed Aug 25 16:01:28 CEST 2010:generating LEAD14
Wed Aug 25 16:01:28 CEST 2010:generating LEAD15
Wed Aug 25 16:01:28 CEST 2010:FSCS_2 :to process LEAD_12
Wed Aug 25 16:01:28 CEST 2010:generating LEAD16
Wed Aug 25 16:01:28 CEST 2010:FSCS_0 :to process LEAD_13
Wed Aug 25 16:01:28 CEST 2010:FSCS_1 :to process LEAD_14
Wed Aug 25 16:01:28 CEST 2010:FSCS_0 :processed LEAD_13
Wed Aug 25 16:01:28 CEST 2010:FSCS_1 :processed LEAD_14
Wed Aug 25 16:01:28 CEST 2010:FSCS_0 :Halted
Wed Aug 25 16:01:28 CEST 2010:FSCS_3 :to process LEAD_15
Wed Aug 25 16:01:28 CEST 2010:generating LEAD17
Wed Aug 25 16:01:28 CEST 2010:generating LEAD18
Wed Aug 25 16:01:28 CEST 2010:FSCS_3 :processed LEAD_15
Wed Aug 25 16:01:28 CEST 2010:FSCS_1 :Halted
Wed Aug 25 16:01:28 CEST 2010:FSCS_3 :Halted
Wed Aug 25 16:01:28 CEST 2010:generating LEAD19
Wed Aug 25 16:01:28 CEST 2010:FSCS_2 :processed LEAD_12
Wed Aug 25 16:01:28 CEST 2010:Stop
Wed Aug 25 16:01:28 CEST 2010:FSCS_2 :to process LEAD_16
Wed Aug 25 16:01:28 CEST 2010:FSCS_2 :processed LEAD_16
Wed Aug 25 16:01:28 CEST 2010:FSCS_2 :Halted
Bye Alessandro
|
|
|
|
|
|
|
|
|
|
Goto Forum:
Current Time: Sun Apr 27 18:42:51 CDT 2025
|