Wikipedia:Reference desk/Archives/Computing/2012 October 30

Computing desk
< October 29 << Sep | October | Nov >> October 31 >
Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


October 30

edit

python

edit

need small python script to do global find and replace with a plain text file. 70.114.254.43 (talk) 02:58, 30 October 2012 (UTC)[reply]

Consult the Python Manual, §6.2, Regular expression operations. The re.sub() function can find and replace strings. Nimur (talk) 04:19, 30 October 2012 (UTC)[reply]

thread execution in java

edit

i know that due to multithreading cpu idle time is reduced.
when cpu is free or waiting for input or output then it starts execution of another thread.
I am expressing my doubts based on below programme.

Source Code
class thread6
{
    public static void main(String args[])
    {
        Thread count1=new Thread(new CountDownEven());
        
        Thread t=Thread.currentThread();
        count1.start();
        for(int i=11;i<=20;i=i+2)
        {
            System.out.println(t.getName()+"----"+i);
        }
    }
}
class CountDownEven implements Runnable
{
    public void run()
    {
        Thread t=Thread.currentThread();
        for(int i=0;i<10;i=i+2)
        {
            System.out.println(t.getName()+"----"+i);
        }
    }
}

my doubts:

  1. why the above programme gives different outputs.?
  2. Execution starts from main thread. in main thread i have written for loop.Before that i wrote count1.start,which starts execution of another thread.but some times for loop in main thread gets executed before another thread.why ?how can i understand this ?
  3. when control moves from one thread to another thread?
  4. can you tell me execution of threads and behaviour of thread scheduler? or can you give some website details?
Output

outputs of above programme:
out put1


:

Thread-0----0

main----11

Thread-0----2

Thread-0----4
Thread-0----6
main----13
main----15
main----17
main----19
Thread-0----8

output2



Thread-0----0
Thread-0----2
Thread-0----4
main----11
main----13
main----15
Thread-0----6
Thread-0----8
main----17
main----19

output3:



main----11
Thread-0----0
Thread-0----2
main----13
main----15
main----17
main----19
Thread-0----4
Thread-0----6
Thread-0----8

— Preceding unsigned comment added by Phanihup (talkcontribs) 05:48, 30 October 2012 (UTC)[reply]

The scheduler of the OS (or of the Java VM, if that does not use the OS scheduler) decides which thread to run based on a number of factors, which potentially include I/O events, system load, and even the (virtual) toss of a coin. In your case, one simple explanation might be that your computer has multiple cores (most nowadays have), and that the systems schedules some threads immediately if there are idle cores, but lets the main threat running for a bit if they are otherwise occupied, e.g. with displaying sand clocks or morphing windows into the dock, or checking if the mouse hovers near a tool tip, or any other of the million things a modern OS does at any one time. --Stephan Schulz (talk) 07:52, 30 October 2012 (UTC)[reply]

spreadsheet link/synchronize sheets

edit

I want the several sheets in a spreadsheet to be multiple "views" into the same data. If I insert or delete a row in one sheet, I want it to be simultaneously inserted/deleted across all sheets. Is there any way to do that? Thanks. — Preceding unsigned comment added by 141.154.221.145 (talk) 09:30, 30 October 2012 (UTC)[reply]

Help with ASCII art in C

edit

I am completing this lab for a class. I have reached the point where I need to code the T out of asterisks.

My code is as follows:

#include <stdio.h>
#include <stdlib.h>
void starL(int width, int height)
{
  int i;

  // check if parameters are valid
  if ((width<2) || (height < 2) || (width%2==0))
    return;  // return without printing anything
  
  // print width stars, followed by a final \n
  for (i=0; i<width; i++)
    printf("*");

  // print height-1 rows of *\n
  for (i=0; i<height-1; i++)
    printf("*\n");
  
  printf("\n");
  
  return;   //  we are finished
}

The problem is, when I attempt to generate a 3x3 T, I get:

****
*

I somehow need to make the "width" line go above the "height" line, and then have the height line spaced (width/2) columns over. How would I do that? 169.231.8.73 (talk) 11:54, 30 October 2012 (UTC)[reply]

It looks like your width line is above the height line, you just need to output a "\n" after you are done drawing the width line. For moving things over, you'll need to add width/2 spaces in front of each piece of the height line. You can place for loops inside of each other, just give the inner one a new variable such as j. I don't want to just give you a solution, but play around with that idea and let us know if you have trouble. (Just edited after realizing I said height instead of width once)209.131.76.183 (talk) 12:17, 30 October 2012 (UTC)[reply]
I've formatted the question for easier reading. Nimur (talk) 15:03, 30 October 2012 (UTC)[reply]
I strongly suggest you manually step through the code, and print asterisks on a piece of paper (or in a text file), to see what your code is doing. StuRat (talk) 16:41, 30 October 2012 (UTC)[reply]

PCIe x1, x4 & x8 Cards' MD1 & MD2 Form Factors

edit

Are the specifications/dimensions of the MD1 and MD2 form factors for PCIe x1, x4 & x8 cards available anywhere online for free? My computer accepts regular cards, but I'm just curious to learn more about these exotic enterprisey form factors. — Preceding unsigned comment added by 49.245.15.32 (talk) 13:24, 30 October 2012 (UTC)[reply]

It looks like this is the spec update introducing the change: [1] 209.131.76.183 (talk) 13:33, 30 October 2012 (UTC)[reply]

Do I have to take care of cache coherence issues when I program with shared memory in Linux?

edit

Suppose I have a multiprocessor machine and I want to write multiprocess program in C/C++, which will run on separate processors on the machine and will allocate and access shared memory by Linux system calls, such as shmget(), shmat() and mmap() etc. Do I ever need to cope with cache coherence by explicitly invalidating/flushing CPU caches in the program? Or it's the Linux and/or the hardware will do this for me? I'm confused because as it's stated in Shared memory: "care must be taken to avoid issues if processes sharing memory are running on separate CPUs and the underlying architecture is not cache coherent". -- Justin545 (talk) 22:27, 30 October 2012 (UTC)[reply]

On a modern multicore or multiprocessor Intel architecture, the hardware cache controller will "dirty" cached copies of a cache line when that line is written by another core - see this Intel article (which will send you off to this tree of advice). So x86-32 and x86-64 are "cache coherent" in this sense; other architectures (I think MIPS) will require you to explicitly invoke memory barriers to ensure coherency. But this doesn't get you out of all the hard work, as you still have to be conscious of cache lines (if you had two cores beating on the same cache line you essentially defeat the cache's usefulness), and you still have the ordinary responsibilities for synchronised access you'd have with a single cpu, multithreaded system. -- Finlay McWalterTalk 23:16, 30 October 2012 (UTC)[reply]
I once worked on a shipping, commercial embedded system that used two MIPS 4K CPUs haphazardly attached to the main system memory, without cache coherency. This lack of cache coherency was a flaw, built in by a sloppy integrated-system designer; it was not a shortcoming of the MIPS architecture. The correct design should have used the MIPS cores, and connected them with e.g., a MIPS CPS or MIPS 74K CPS coherency manager block, which implements cache coherency for multiple MIPS cores, through cache snooping. Cache coherency isn't strictly a feature of an instruction set architecture; it's more properly an element of a complete system design; but because modern computers are so tightly integrated, few except the industry professional or the advanced computer engineering student ever needs to worry about it. To answer the original post: on Linux on an Intel multicore platform, you do not need to manage cache coherency. Intel's hardware handles this detail for you. What you should worry about is whether your program structure results in cache thrashing, which has a real and measurable impact to performance. Nimur (talk) 23:52, 30 October 2012 (UTC)[reply]
I had never been aware of cache coherency issue while learning multiple thread/process programming until recently I read more about shared memory. They (the teachers and the books) only talked about locking, function reentrancy or other thread/signal safety issues that I need to take care of, but never mentioned cache coherency. So I thought it shouldn't be a big deal otherwise they should at least have mentioned. (or I haven't got enough books or teachers?) But according to your two replies, it looks like I may not get out of the hard work if I'm not work with Intel CPUs. Other than Intel's CPU, AMD is often seen CPU for personal computers, ARM and MIPS are often seen CPUs for embeded system. Therefore, there is still a big chance I may need to consider cache cohereny issues in Linux when I encounter these non-Intel CPUs. Which makes it sound tough to use shared memory! Which makes it sound tough to use shared memory in userspace in Linux! --- Justin545 (talk) 00:55, 31 October 2012 (UTC) (excuse my English if there are errors)[reply]
Not that tough to use, really. All it means is that your program is exposed to the realities of system level programming, and that you don't get absolute platform independence just by coding in C to POSIX. That means your program will end up with an "arch" directory and a few places where chip specific stuff intrudes. And it does mean you'll end up reading the actual chip manuals for a bunch of different chips - none of which will have the stupid problem Nimur's had, but all of which will have their own stupid problems. Such is life. -- Finlay McWalterTalk 02:03, 31 October 2012 (UTC)[reply]
Thank you for your replies. I would probably check out APIs/libraries like OpenMP and Boost.Interprocess first to see if they can hide platform/architecture dependencies which POSIX Linux kernel and POSIX don't provide. Or, if that fails, I have to face the challenges that multiprocessor brings on... --- Justin545 (talk) 04:10, 31 October 2012 (UTC)[reply]
The kernel's responsibilities for mediating your access to memory pretty much ends with mmap et al (and giving you the pthreads synchronisation operations to allow you to coordinate safe access to the shared memory). Beyond that, you need to know the characteristics of the cache, particularly the cache line size (and alignment, but that always seems to be the same as size). On Linux that's in /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size; there's some other stuff in that same directory that's interesting too. -- Finlay McWalterTalk 05:32, 31 October 2012 (UTC)[reply]
Full cache coherence is very nice, but is just too much overhead for very large systems and even on smaller ones it imposes a performance and complexity overhead. In one commercial mainframe system from the past they could have the processors separated by several hundred feet using optical fibres but with shared memory and it all worked without performance problems because of the very good handling of this issue. With today's much faster processors even a single foot represents a big delay never mind the electronics required to detect and cope with cache problems when there really aren't any. So if your stuff will be used on other systems besides Intel or possibly on supercomputers using ix86 processors and you want to use multiple processors then you should worry about cache problems. Basically you need to think about acquiring and releasing shared memory use. Dmcq (talk) 11:18, 31 October 2012 (UTC)[reply]
Here's what POSIX says about it. In short, there are no guarantees unless you use OS-provided synchronization functions. If you do use them, and use them correctly (so that only one thread can access a given memory location at any time), then you're safe, and needn't worry about cache line boundaries and whatnot.
Note that the rules are the same for memory shared between processes as for threads within a single process. Also note that if you do have two threads racing on the same memory, there is no guarantee that the result will agree with any in-order interleaving of the threads' instructions, even on x86. See here for an example. So use OS synchronization. This applies on Windows also. -- BenRG (talk) 17:11, 31 October 2012 (UTC)[reply]
But incoherent cache invalidation means that a race conditions exists even if two threads aren't accessing the same memory. That's something that Intel systems guarantee will not occur. Specifically, false sharing on an Intel architecture does guarantee coherency - which is not the same as guaranteeing that you won't write code with an explicit race condition. So, on an i32 or x86 or x86_64 system, cache coherency is purely a performance consideration, not a functionality- or correctness- problem. On a system without coherency, false sharing means hidden race-conditions. Thread 1 accesses Variable A; and Thread 2 accesses Variable B; no contention seems present; but A and B share a cache-line; a race condition exists even though it should not. Thread 2 destroys the value of Variable A when it accesses Variable B. (That's not a race condition, it's an incoherent cache). This is covered in Chapter 5 of Computer Architecture, A Quantitative Approach; a limited online preview is available from Google Books. This book is a must-own if you're designing a CPU or working at the level of microarchitecture that cache details actually matter. Nimur (talk) 19:28, 31 October 2012 (UTC)[reply]