LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 12-02-2022, 12:47 PM   #1
gzorp
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Rep: Reputation: 0
Synchronization - How to synchronize reading of segmented file by multiple children processes


Cheers. I am given a text file e.g. of 10 lines, which is segmented. For example, we have 5 segments each containing 2 lines inside them (e.g. segment 1 loads lines 1 and 2, segment 2 loads lines 3 and 4, and so on...) .

I want to be able to spawn children processes which randomly select a segment and retrieve it SYNCHRONIZED. To be able to make that connection between the parent and child processes I must use shared memory. So I fork() for the children, which select a segment which is then requested to the parent processes which acts like a server, getting requests and placing the requested segment into shared memory to be then read by the children. My goal is to synchronize the following problem.

Quote:
However, when a segment has been loaded into the shared memory then it can serve any incoming requests asking for that segment without mutual exclusion. When there is no longer need for that segment and a request has been made for another, then we switch the segment in the shared memory. Requests that cannot be executed since the requested segment is NOT currently in the shared memory, are blocked until the segment desired is placed into memory. They are then recalled using FIFO strategy.
For the purposes of the exercise I am asked to use semaphores to achieve the FIFO line of recall. So when a process is blocked, it is saved in a QUEUE inside the semaphore, and when the semaphore is then "signaled", it unblocks the first blocked process.

I am aware that I am looking at a variation of the one writer / multiple readers problem. However, I find it very difficult to continue and can't find how to place semaphores in a way such as to achieve the desired result. I also know that I must use a array of semaphores, one for each segment. I have wrote some C code, but I am missing the main synchronization scheme implementation to achieve the above.

Here is some C-style pseudocode of what I have so far.

PHP Code:


struct shared 
{
    
sem_tarray_of_semaphores;
    
sem_t place_request;
    
sem_t wait_response;
    
sem_t mutex;
    
char** data;
    
int readCounter 0;
    
int currentSegment = -1;
};

struct childRequest {
    
int segment;
    
int childID;
};

void childProcess(int childIdint requestsPerChildvoidsharedvoidrequestBuffer ) {
   
    for(
int i 0requestsPerChildi++) {
        
        
int segment select_random_segment();
        
        
// Somewhere here I THINK
        // a sem_wait() must be placed for all requests that
        // want a segment that is not in memory
        // ????
        // if (currentSegment != segment)
        //    sem_wait(shared->array_of_semaphores[segment])
        // ????, and this semaphore must be "posted" when counter = 0
        
        
        // Place request
        
requestBuffer->segment segment;
        
requestBuffer->childID childId;
        
        
sem_post(place_request);
        
sem_wait(wait_response);
        
        
// If reached here, the requested segment is in memory
        // We can READ this now...
    
    
}
    
}

int main() {
    
FILE *fp fopen("derised_text_file.txt""r");
    
int segments 5;
    
int lines_per_segment total_number_of_lines(fp) / segments;
    
    
// Assume we have attached and gotten the shared memory
    
shm_ptr get_shared_memorysizeof(shared));
    
request_buffer get_shared_memory(sizeof(childRequest));
    
    
sem_init(shm_ptr->place_request0);
    
sem_init(shm_ptr->wait_response0);
    
sem_init(shm_ptr->mutex1);
    
    for (
int i 0segmentsi++)
        
sem_init(shm_ptr->array_of_semaphores[i], ??);
    
    
int childrenProcesses 15;
    
int requestsPerChild 5;
    
    for (
int i 0childrenProcessesi++ ) {
        if (
fork() == 0)
            
childProcess(0requestsPerChildshm_ptrrequest_buffer);
    }
    
    
// Serve the requested segment into memory
    
for (0childrenProcesses requestsPerChildi++ ) {
        
// Wait for a request to be placed
        
wait(place_request);
        
        
// TO PLACE LINES INTO char** data;
        
        
signal(wait_response);
        
        
    }

I don't know I am going to be able to keep the information as of which segment is the next one to be unblocked. E.g. if I am serving segment 1 and a request for 3,4,4 come in, how when I am done with 1, I will switch to 3 (as it came first), and when I am done with it, I am going to unblock both requests needing 4. Also since we know which segment is first and last, I think these should be responsible for the communication with the parent/server.

Any help/hint would be greatly appreciated, as I feel like I have stuck a wall.

Last edited by gzorp; 12-04-2022 at 07:00 AM.
 
Old 12-03-2022, 08:19 AM   #2
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,428
Blog Entries: 1

Rep: Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679
And I feel you have forgotten your previous question.
 
1 members found this post helpful.
Old 12-03-2022, 08:42 AM   #3
gzorp
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by NevemTeve View Post
And I feel you have forgotten your previous question.
Hi! Well no, because now I am informed I have to do the FIFO management of the processes via semaphores, so I will not be explicitly using a FIFO queue created by me, but a one created indirectly via semaphores.
 
Old 12-03-2022, 09:58 AM   #4
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,428
Blog Entries: 1

Rep: Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679
You could quote the actual text of your homework instead of your interpretation.
 
Old 12-03-2022, 10:37 AM   #5
gzorp
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by NevemTeve View Post
You could quote the actual text of your homework instead of your interpretation.
Hi again. This is what I have done. I have translated and quoted the actual text as I was given it, in the 3rd paragraph. I have just not placed in quotes.
 
Old 12-03-2022, 11:37 AM   #6
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,428
Blog Entries: 1

Rep: Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679
You can still edit your post and add the quotation marks.
 
Old 12-03-2022, 01:54 PM   #7
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=15, FreeBSD_12{.0|.1}
Posts: 6,005
Blog Entries: 23

Rep: Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967Reputation: 3967
Quote:
Originally Posted by NevemTeve View Post
And I feel you have forgotten your previous question.
@gzorp: I think the point being made is that you never responded to those who provided helpful replies in your other thread but simply abandoned it, and them. Please be respectful of the time that others put into reading your questions and sharing their knowledge - sharing is an interactive process!

And, per the LQ Rules, please do not post homework assignments verbatim. We're happy to assist if you have specific questions or have hit a stumbling point, however. Let us know what you've already tried and what references you have used (including class notes, books, and Google searches) and we'll do our best to help. Also, keep in mind that your instructor might also be an LQ member.
 
1 members found this post helpful.
Old 12-03-2022, 02:51 PM   #8
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,683

Rep: Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008
Quote:
Originally Posted by gzorp View Post
Hi! Well no, because now I am informed I have to do the FIFO management of the processes via semaphores, so I will not be explicitly using a FIFO queue created by me, but a one created indirectly via semaphores.
Why do you think this? Is this from part of the assignment that you haven't posted here?
 
Old 12-04-2022, 04:52 AM   #9
gzorp
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by ntubski View Post
Why do you think this? Is this from part of the assignment that you haven't posted here?
It's been quoted on the 4th paragraph of my question. It's an instruction given by my professor.
 
Old 12-04-2022, 05:20 AM   #10
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,428
Blog Entries: 1

Rep: Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679Reputation: 1679
Both third and fourth paragraphs in OP look like your own ideas, not the authentic source.
 
Old 12-04-2022, 07:00 AM   #11
gzorp
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by astrogeek View Post
@gzorp: I think the point being made is that you never responded to those who provided helpful replies in your other thread but simply abandoned it, and them. Please be respectful of the time that others put into reading your questions and sharing their knowledge - sharing is an interactive process!

And, per the LQ Rules, please do not post homework assignments verbatim. We're happy to assist if you have specific questions or have hit a stumbling point, however. Let us know what you've already tried and what references you have used (including class notes, books, and Google searches) and we'll do our best to help. Also, keep in mind that your instructor might also be an LQ member.
Thanks for your answer. I did not abandon the thread. I had a question for which some useful ideas were provided, but it does not apply to what I now want to achieve now, that's why it is a separate question. Since my approach changed, I cannot report anything new to the old answer since I will no longer work on it. Also, what constitutes "homework"? I had a question about a given task, which I did my due diligence for, I know my theory, but I have hit a stumbling point as you say. One thing I have learned to do as a junior computer scientist is ask questions about things when I can't overcome a problem. I never asked for an answer given on a silver platter. I just wanted a hint or an idea/some pseudocode on how to approach it, and get unstuck. So I think even if my professor is also a LQ member, I haven't made any mistake I should be condemned for. I will keep your suggestions in mind.
 
Old 12-04-2022, 09:34 AM   #12
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,683

Rep: Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008Reputation: 2008
Quote:
Originally Posted by gzorp View Post
It's been quoted on the 4th paragraph of my question. It's an instruction given by my professor.
Okay, the reason I asked about it is if you read e.g., https://manned.org/sem_post.3p you'll see that semaphores don't always guarantee FIFO ordering. So I wonder if you could have misunderstood your professor's instructions.

Are the fields in struct shared also given in the instructions? It seems like you could just use the counter of the semaphore itself (sem_getvalue()), so most of the fields except for array_of_semaphores and data wouldn't be needed.

I would suggest adding an exit() at the end of childProcess(), otherwise you will get a lot of unexpected grandchild processes. Also, I don't think it makes any sense to have requestBuffer be in shared memory (because that would prevent you from handling more than one request at a time).
 
Old 12-04-2022, 01:56 PM   #13
dugan
LQ Guru
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 10,773

Rep: Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097Reputation: 5097
Quote:
Originally Posted by ntubski View Post
Okay, the reason I asked about it is if you read e.g., https://manned.org/sem_post.3p you'll see that semaphores don't always guarantee FIFO ordering. So I wonder if you could have misunderstood your professor's instructions.
Yeah I think this is a key point. You need to actually implement a FIFO queue. And then, and only then, you use the semaphores to prevent race conditions.
 
Old 12-05-2022, 12:43 PM   #14
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,102
Blog Entries: 4

Rep: Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662Reputation: 3662
... and if you can use C++, these things have already been built and perfected for(!) you. You can grab a "FIFO queue" right off the shelf. Most other things, too. The implementations are just as efficient but the human-labor is considerably less. "Do not do a thing already done."

Also always bear in mind the underlying hardware, which is getting and servicing all of the requests coming from everywhere. If the device is "SSD" then this is much less of a problem because "it's really memory," but if the device is rotating there are now mechanical considerations. (Also, [virtual] memory considerations.) If you exceed the physical ability of the hardware, you will probably create a "sophisticated" process that is actually much slower(!) than a simpler one: "dozens of threads, all stuck in traffic on a two-lane road behind a drawbridge."

"Asynchronous message-passing" often turns out to be more efficient (and, more scalable) than "shared memory." Only one process receives requests for information, and sends the information back in a reply. It uses a (non-shared) memory segment as a buffer, or simply relies upon the filesystem to do so. It issues asynchronous requests for data to be retrieved from backing storage, and is notified when each of these requests complete. Only this one process knows – or, needs to know – the full picture.

And, guess what: there are already libraries out there which do all of this, in various languages. Check places like "github" and "sourceforge" and search them very carefully before you set out to write anything "new." (Because, it undoubtedly isn't.)

Last edited by sundialsvcs; 12-05-2022 at 12:51 PM.
 
Old 12-05-2022, 03:36 PM   #15
EdGr
Member
 
Registered: Dec 2010
Location: California, USA
Distribution: I run my own OS
Posts: 912

Rep: Reputation: 436Reputation: 436Reputation: 436Reputation: 436Reputation: 436
I think your professor is not doing you any favors by having you take the wrong approach.

The problem is easily solved by writing a multithreaded program. With threads, memory is shared by default. Synchronization becomes easy.

Of course, if you did that, you will likely receive an "F" for not following instructions even if the solution was technically superior.
Ed
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
cobbler multi-segmented chrobry Linux - Server 0 08-10-2010 05:23 PM
[SOLVED] Combining two segmented DVDs into one. vikas027 Solaris / OpenSolaris 3 07-08-2010 11:54 PM
Gnome/gdm startup apps: Why are some children of gdm and others children of init? sixerjman Linux - Software 1 07-04-2009 11:48 AM
Session-to-Session Segmented Downloads Raymond C. Glassford Mandriva 2 08-29-2008 10:44 AM
email synchronization (not file synchronization) Moebius Linux - Software 6 10-05-2004 06:31 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 11:12 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration